00001 /*===========================================================================*/ 00002 /* */ 00003 /* This file is part of a demonstration application for use with the */ 00004 /* SYMPHONY Branch, Cut, and Price Library. This application is a solver for */ 00005 /* the Vehicle Routing Problem and the Traveling Salesman Problem. */ 00006 /* */ 00007 /* (c) Copyright 2000-2008 Ted Ralphs. All Rights Reserved. */ 00008 /* */ 00009 /* This application was developed by Ted Ralphs (tkralphs@lehigh.edu) */ 00010 /* */ 00011 /* This software is licensed under the Common Public License. Please see */ 00012 /* accompanying file for terms. */ 00013 /* */ 00014 /*===========================================================================*/ 00015 00016 #ifndef _VRP_TYPES2_H 00017 #define _VRP_TYPES2_H 00018 00019 /* SYMPHONY include files */ 00020 #include "sym_proto.h" 00021 00022 /* VRP include files */ 00023 #include "vrp_common_types.h" 00024 #include "vrp_cg_params.h" 00025 #include "vrp_lp_params.h" 00026 #ifdef COMPILE_HEURS 00027 #include "heur_params.h" 00028 #include "lb_params.h" 00029 00030 /*---------------------------------------------------------------------------*\ 00031 * Here we keep track of the computation time for the lower and upper 00032 * bounding procedures 00033 \*---------------------------------------------------------------------------*/ 00034 00035 typedef struct BD_TIMES{ 00036 double ub_overhead; /*overhead time used doing the upper bounding*/ 00037 double ub_heurtime; /*actual comp time spent doing the upper bounding*/ 00038 double lb_overhead; /*overhead time spent doing the lower bounding*/ 00039 double lb_heurtime; /*actual comp time spent doing the lower bounding*/ 00040 }bd_times; 00041 00042 /*---------------------------------------------------------------------------*\ 00043 * The heurs structure is used to keep track of the various heuristic processes 00044 * which are currently running. The jobs field contains the number of processes 00045 * currently running. The tids field is an array containing the tid's of these 00046 * processes. 00047 \*---------------------------------------------------------------------------*/ 00048 00049 typedef struct HEURS{ 00050 int jobs; 00051 int *tids; 00052 char *finished; 00053 int *starter; 00054 }heurs; 00055 00056 /*---------------------------------------------------------------------------*\ 00057 * Contains the tree correspoding to the best lower bound found using 00058 * lagrangian relaxation 00059 \*---------------------------------------------------------------------------*/ 00060 00061 typedef struct LOW_BD{ 00062 int *tree; 00063 edge_data *best_edges; 00064 double lower_bound; 00065 }low_bd; 00066 00067 /*---------------------------------------------------------------------------*\ 00068 * This structure contains the values of the time out parameters for 00069 * upper and lower bounding routines. 00070 \*---------------------------------------------------------------------------*/ 00071 00072 typedef struct TIME_OUT_PAR{ 00073 int ub; 00074 int lb; 00075 }time_out_par; 00076 #endif 00077 00078 00079 /*---------------------------------------------------------------------------*\ 00080 * The "small_graph" data structure is used to store the subset of the 00081 * edges that will be used initially in actually solving the problem. 00082 * These edges usually consist of any edges found among the ones used in 00083 * the heuristics solutions and the set of shortest edges adjacent to 00084 * each node in the graph 00085 \*---------------------------------------------------------------------------*/ 00086 00087 typedef struct SMALL_GRAPH{ /* this gets passed eg. to lin-kerninghan */ 00088 int vertnum; /* vertnum in the restricted (small) graph */ 00089 int edgenum; /* edgenum in the restricted (small) graph */ 00090 int allocated_edgenum; 00091 int del_edgenum; 00092 edge_data *edges; /* The data for these edges */ 00093 }small_graph; 00094 00095 #ifndef COMPILE_HEURS 00096 typedef struct CLOSENODE{ /*close node to a particular one */ 00097 int node; 00098 int cost; 00099 }closenode; 00100 #endif 00101 00102 typedef struct VRP_PARAMS{ 00103 char infile[MAX_FILE_NAME_LENGTH + 1]; 00104 int verbosity; 00105 char tsp_prob; 00106 int k_closest; 00107 int min_closest; 00108 int max_closest; 00109 int add_all_edges; 00110 int add_depot_edges; 00111 int base_variable_selection; 00112 int use_small_graph; 00113 char small_graph_file[MAX_FILE_NAME_LENGTH]; 00114 int colgen_strat[2]; 00115 #ifdef COMPILE_HEURS 00116 int *rand_seed; 00117 int tours_to_keep; 00118 time_out_par time_out; 00119 int do_heuristics; 00120 #endif 00121 00122 int test; 00123 char test_dir[MAX_FILE_NAME_LENGTH +1]; /* Test files directory */ 00124 }vrp_params; 00125 00126 /*---------------------------------------------------------------------------*\ 00127 * The problem data structure contains the data for a problem instance, as 00128 * well as some of the tours that have been generated. 00129 \*---------------------------------------------------------------------------*/ 00130 00131 typedef struct VRP_PROBLEM{ 00132 char name[100]; /* the name of the problem instance */ 00133 vrp_params par; 00134 vrp_cg_params cg_par; 00135 vrp_lp_params lp_par; 00136 #ifdef COMPILE_HEURS 00137 heur_params heur_par; 00138 lb_params lb_par; 00139 #endif 00140 int dg_id; /* drawgraph process id */ 00141 int vertnum; /* the number of nodes in the problem, including 00142 the depot */ 00143 int edgenum; /* number of edges in the problem */ 00144 int *edges; 00145 int numroutes; /* contains the number of routes that the problem 00146 is to be solved with. can be prespecified. */ 00147 int depot; /* the index of the depot, usually 1 */ 00148 int capacity; /* the capacity of a truck */ 00149 int *demand; /* an array containing the demands for each node. 00150 node i's demand is p->demand[i-1] */ 00151 int *posx; /* x coordinate for display purposes */ 00152 int *posy; /* y coordinate for display purposes */ 00153 00154 distances dist; /* the data about the distances in the problem */ 00155 00156 best_tours *cur_tour; /* temporary tour storage */ 00157 #ifdef COMPILE_HEURS 00158 best_tours *tours; /* an array of the best tours found */ 00159 int *tourorder; /* a binary tree containing the ordering of the 00160 tours in best_tours */ 00161 int tournum; /* the number of tours stored in best_tours-1 */ 00162 low_bd *lb; /* contains the information on the best lower 00163 bound */ 00164 #endif 00165 small_graph *g; /* contains the edge data for the reduced graph*/ 00166 #if defined(CHECK_CUT_VALIDITY) || defined(TRACE_PATH) 00167 int feas_sol_size; 00168 int *feas_sol; 00169 #endif 00170 #ifdef COMPILE_HEURS 00171 bd_times bd_time; 00172 #endif 00173 int *zero_vars; 00174 int zero_varnum; 00175 }vrp_problem; 00176 00177 #endif