00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00012
00013 #ifndef _VRP_H
00014 #define _VRP_H
00015
00016
00017 class VRP
00018 {
00019
00020 friend class OnePointMove;
00021 friend class TwoPointMove;
00022 friend class ThreePointMove;
00023 friend class TwoOpt;
00024 friend class ThreeOpt;
00025 friend class OrOpt;
00026 friend class CrossExchange;
00027
00028 friend class Postsert;
00029 friend class Presert;
00030 friend class MoveString;
00031 friend class Swap;
00032 friend class SwapEnds;
00033 friend class Concatenate;
00034 friend class Flip;
00035
00036 friend class ClarkeWright;
00037 friend class Sweep;
00038
00039 public:
00040 VRP(int n);
00041
00042 VRP(int n, int ndays);
00043
00044
00045
00046 ~VRP();
00047
00048
00049 void read_TSPLIB_file(const char *infile);
00050
00051 void write_TSPLIB_file(const char *outfile);
00052
00053
00054 void show_next_array();
00055 void show_pred_array();
00056 bool verify_routes(const char *message);
00057 bool check_fixed_edges(const char *message);
00058 void create_pred_array();
00059 void print_stats();
00060
00061
00062 void write_solution_file(const char *filename);
00063 void write_solutions(int num_sols, const char *filename);
00064 void write_tex_file(const char *filename);
00065 void read_solution_file(const char *filename);
00066 int read_fixed_edges(const char *filename);
00067
00068
00069 void export_solution_buff(int *sol_buff);
00070 void import_solution_buff(int *sol_buff);
00071 void export_canonical_solution_buff(int *sol_buff);
00072
00073
00074 void show_routes();
00075 void show_route(int k);
00076 void summary();
00077
00078
00079 void reset();
00080
00081
00082 bool plot(const char *filename, int options, int orientation);
00083 bool plot(const char *filename);
00084 bool plot_route(int r, const char *filename);
00085
00086
00087 bool clone(VRP *W);
00088
00089
00090 double RTR_solve(int heuristics, int intensity, int max_stuck, int num_perturbs,
00091 double dev, int nlist_size, int perturb_type, int accept_type, bool verbose);
00092
00093 double SA_solve(int heuristics, double start_temp, double cool_ratio,
00094 int iters_per_loop, int num_loops, int nlist_size, bool verbose);
00095
00096
00097 char name[VRPH_STRING_SIZE];
00098
00099
00100 void set_daily_demands(int day);
00101 void set_daily_service_times(int day);
00102
00103
00104 bool create_default_routes();
00105 bool create_default_routes(int day);
00106
00107
00108 bool eject_node(int k);
00109 int inject_set(int num, int *nodelist, int rules, int attempts);
00110 void eject_neighborhood(int j, int num, int *nodelist);
00111
00112
00113 void refresh_routes();
00114 void normalize_route_numbers();
00115 void update_route(int j, VRPRoute *R);
00116 void clean_route(int r, int heuristics);
00117 double split(double p);
00118 int split_routes(double p, int **ejected_routes, double *t);
00119 void add_route(int *route_buff);
00120 void append_route(int *sol_buff, int *route_buff);
00121 int intersect_solutions(int *new_sol, int **routes, int *sol1, int *sol2, int min_routes);
00122 int find_common_routes(int *sol1, int *sol2, int *route_nums);
00123
00124
00125 void list_fixed_edges(int *fixed_list);
00126 void unfix_all();
00127 void fix_edge(int start, int end);
00128 void unfix_edge(int start, int end);
00129 void fix_string(int *node_string, int k);
00130
00131
00132 int get_num_nodes();
00133 double get_total_route_length();
00134 double get_total_service_time();
00135 double get_best_sol_buff(int *sol_buff);
00136 double get_best_total_route_length();
00137 int get_total_number_of_routes();
00138 int get_num_original_nodes();
00139 int get_num_days();
00140 double get_best_known();
00141 void set_best_total_route_length(double val);
00142 int get_max_veh_capacity();
00143 double get_max_route_length();
00144
00145
00146 VRPSolutionWarehouse *solution_wh;
00147 VRPRouteWarehouse *route_wh;
00148
00149
00150 void create_distance_matrix(int type);
00151
00152 void create_neighbor_lists(int nsize);
00153
00154
00155 bool perturb();
00156 bool eject_route(int r, int *route_buff);
00157 bool inject_node(int j);
00158
00159
00160 void reverse_route(int i);
00161
00162
00163 int num_evaluations[NUM_HEURISTICS];
00164 int num_moves[NUM_HEURISTICS];
00165
00166 private:
00167
00168
00169 int num_nodes;
00170 double total_route_length;
00171 double total_service_time;
00172 int *best_sol_buff;
00173 double best_total_route_length;
00174 int total_number_of_routes;
00175 int num_original_nodes;
00176 double best_known;
00177 int num_days;
00178 int problem_type;
00179 int total_demand;
00180 int max_veh_capacity;
00181 int orig_max_veh_capacity;
00182 double max_route_length;
00183 double min_route_length;
00184 double orig_max_route_length;
00185 int min_vehicles;
00186 bool has_service_times;
00187 double fixed_service_time;
00188 int edge_weight_type;
00189 int coord_type;
00190 int display_type;
00191 int edge_weight_format;
00192 int matrix_size;
00193 double balance_parameter;
00194 int dummy_index;
00195 int neighbor_list_size;
00196 double temperature;
00197 double cooling_ratio;
00198
00199 bool symmetric;
00200
00201
00202 bool can_display;
00203
00204 double **d;
00205 bool **fixed;
00206
00207 class VRPNode *nodes;
00208
00209
00210 bool depot_normalized;
00211
00212
00213 bool forbid_tiny_moves;
00214
00215
00216
00217 bool create_search_neighborhood(int j, int rules);
00218 int search_size;
00219 int *search_space;
00220
00221
00222 int *next_array;
00223 int *pred_array;
00224 int *route_num;
00225 bool *routed;
00226
00227 class VRPRoute *route;
00228
00229
00230 class VRPTabuList *tabu_list;
00231 bool check_tabu_status(VRPMove *M, int *old_sol);
00232
00233 double record;
00234 double deviation;
00235
00236 double min_theta;
00237 double max_theta;
00238
00239 int *current_sol_buff;
00240
00241
00242 bool before(int a, int b);
00243
00244
00245 bool check_feasibility(VRPViolation *VV);
00246 class VRPViolation violation;
00247 bool is_feasible(VRPMove *M, int rules);
00248
00249
00250 bool postsert_dummy(int i);
00251 bool presert_dummy(int i);
00252 bool remove_dummy();
00253 bool osman_insert(int k, double alpha);
00254 int osman_perturb(int num, double alpha);
00255 bool insert_node(int j, int i, int k);
00256 void perturb_locations(double c);
00257 void find_cheapest_insertion(int j, int *edge, double *costs, int rules);
00258 double insertion_cost(int u, int a, int b);
00259 double ejection_cost(int u);
00260 void update(VRPMove *M);
00261
00262
00263 void compute_route_center(int r);
00264 void find_neighboring_routes();
00265
00266
00267 void capture_best_solution();
00268 void update_solution_wh();
00269
00270
00271 bool get_segment_info(int a, int b, struct VRPSegment *S);
00272 double get_distance_between(int a, int b);
00273 int get_string_end(int a, int len);
00274 int count_num_routes();
00275 void update_arrival_times();
00276 bool check_move(VRPMove *M, int rules);
00277
00278
00279 inline bool check_savings(VRPMove *M, int rules){
00285
00286 #if VRPH_FORBID_TINY_MOVES
00287 if(M->savings>-VRPH_EPSILON && M->savings < VRPH_EPSILON)
00288 return false;
00289 #endif
00290
00291 if( M->savings < -VRPH_EPSILON )
00292 {
00293 M->evaluated_savings=true;
00294 return true;
00295 }
00296
00297
00298
00299 if( (rules & VRPH_FREE) )
00300 return true;
00301
00302
00303 if( (rules & VRPH_DOWNHILL) )
00304 {
00305 if(M->savings>=-VRPH_EPSILON )
00306 {
00307 M->evaluated_savings=true;
00308 return false;
00309 }
00310 }
00311
00312 if( (rules & VRPH_RECORD_TO_RECORD) )
00313 {
00314 if(M->savings<-VRPH_EPSILON)
00315 {
00316 M->evaluated_savings=true;
00317 return true;
00318 }
00319 else
00320 {
00321
00322 if(has_service_times==false)
00323 {
00324 if( (total_route_length+M->savings<= (1+deviation)*record) )
00325 {
00326 M->evaluated_savings=true;
00327 return true;
00328 }
00329 else
00330 return false;
00331 }
00332 else
00333 {
00334
00335
00336 if( ((total_route_length - total_service_time) + M->savings <=
00337 ((1+deviation)*(record-total_service_time))) )
00338 {
00339 M->evaluated_savings=true;
00340 return true;
00341 }
00342 else
00343 return false;
00344 }
00345
00346
00347 }
00348
00349 }
00350
00351 if( rules & VRPH_SIMULATED_ANNEALING )
00352 {
00353 if( exp( - ((M->savings) / this->temperature)) > lcgrand(0) )
00354 {
00355 M->evaluated_savings=true;
00356 return true;
00357 }
00358 else
00359 return false;
00360
00361 }
00362
00363 return false;
00364
00365
00366 };
00367
00368
00369
00370
00371 };
00372
00373 #endif
00374
00375