VRPH
1.0
|
00001 00002 // // 00003 // This file is part of the VRPH software package for // 00004 // generating solutions to vehicle routing problems. // 00005 // VRPH was developed by Chris Groer (cgroer@gmail.com). // 00006 // // 00007 // (c) Copyright 2010 Chris Groer. // 00008 // All Rights Reserved. VRPH is licensed under the // 00009 // Common Public License. See LICENSE file for details. // 00010 // // 00012 00013 #ifndef _VRP_H 00014 #define _VRP_H 00015 00016 // VRP class 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 // Constructor for problems with n non-VRPH_DEPOT nodes 00042 VRP(int n, int ndays); 00043 // Construct for problems with n non-VRPH_DEPOT nodes and num_days days 00044 00045 // Destructor 00046 ~VRP(); 00047 00048 // TSPLIB file processing 00049 void read_TSPLIB_file(const char *infile); 00050 // Write problem instance 00051 void write_TSPLIB_file(const char *outfile); 00052 00053 // Solution display/debugging 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 // Files (read/write) 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 // Solution buffers (import/export) 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 // Solution display 00074 void show_routes(); 00075 void show_route(int k); 00076 void summary(); 00077 00078 // Removes all solutions from memory and sets all nodes to unrouted 00079 void reset(); 00080 00081 // Graphics - only meaningful with PLPlot 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 // Copying 00087 bool clone(VRP *W); 00088 00089 // Solvers 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 // The name of the problem (from TSPLIB file) 00097 char name[VRPH_STRING_SIZE]; 00098 00099 // For multi-day problems 00100 void set_daily_demands(int day); 00101 void set_daily_service_times(int day); 00102 00103 // Creating default routes for CW, etc. 00104 bool create_default_routes(); 00105 bool create_default_routes(int day); 00106 00107 // Routines to remove and insert nodes into solution 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 // Route operations 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 // Fixing edges 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 // Accessor functions for private data 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(); // For multi-day VRPs 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 // Places to store unique solutions and routes - uses internal hash table 00146 VRPSolutionWarehouse *solution_wh; // To store additional solutions 00147 VRPRouteWarehouse *route_wh; // To store routes/columns 00148 00149 // Distance matrix creation 00150 void create_distance_matrix(int type); 00151 // Neighbor list creation 00152 void create_neighbor_lists(int nsize); 00153 00154 // Node injection/ejection 00155 bool perturb(); 00156 bool eject_route(int r, int *route_buff); 00157 bool inject_node(int j); 00158 00159 // Route reversal 00160 void reverse_route(int i); 00161 00162 // Statistics 00163 int num_evaluations[NUM_HEURISTICS]; 00164 int num_moves[NUM_HEURISTICS]; 00165 00166 private: 00167 00168 // Problem parameters, description, etc. 00169 int num_nodes; 00170 double total_route_length; 00171 double total_service_time; 00172 int *best_sol_buff; // Place for the best solution to live 00173 double best_total_route_length; 00174 int total_number_of_routes; 00175 int num_original_nodes; 00176 double best_known; // Record of the best known solution for benchmarks 00177 int num_days; // For multi-day VRPs 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; // Not currently used 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; // For VRPH_BALANCED problems 00194 int dummy_index; 00195 int neighbor_list_size; 00196 double temperature; // For VRPH_SIMULATED_ANNEALING 00197 double cooling_ratio; 00198 00199 bool symmetric; // To keep track of symmetric/asymmetric instances 00200 // Note! Asymmetric instances have received only 00201 // limited testing! 00202 bool can_display; 00203 00204 double **d; // The distance matrix d 00205 bool **fixed; // Matrix to keep track of fixed edges 00206 00207 class VRPNode *nodes; // Array of nodes - contains coordinates, demand 00208 // amounts, etc. 00209 00210 bool depot_normalized; // Set to true if VRPH_DEPOT coords normalized to origin 00211 // for Euclidean problem. 00212 00213 bool forbid_tiny_moves; // Set to true to prevent potentially nonsense moves 00214 // that have a tiny (perhaps zero) effect on route length 00215 00216 // Local search neighborhood creation 00217 bool create_search_neighborhood(int j, int rules); 00218 int search_size; 00219 int *search_space; 00220 00221 // Solution storage 00222 int *next_array; 00223 int *pred_array; 00224 int *route_num; 00225 bool *routed; // Indicates whether the customer is in a route yet or not 00226 00227 class VRPRoute *route; // Array stores useful information about the routes in a solution 00228 00229 // Tabu search - very limited testing so far!! 00230 class VRPTabuList *tabu_list; 00231 bool check_tabu_status(VRPMove *M, int *old_sol); 00232 00233 double record; // For RTR 00234 double deviation; // For RTR 00235 00236 double min_theta; 00237 double max_theta; // Polar min/max 00238 00239 int *current_sol_buff; // Place for the current solution if desired 00240 00241 // Accessing edge information 00242 bool before(int a, int b); 00243 00244 // To handle infeasibilities 00245 bool check_feasibility(VRPViolation *VV); 00246 class VRPViolation violation; 00247 bool is_feasible(VRPMove *M, int rules); 00248 00249 // Solution manipulation 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 // Splitting VRP instances 00263 void compute_route_center(int r); 00264 void find_neighboring_routes(); 00265 00266 // Solution memory 00267 void capture_best_solution(); 00268 void update_solution_wh(); 00269 00270 // Solution information 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 // Savings evaluation - inline this to speed things up 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 // The order needs to be changed if we eventually add additional rules 00297 // that do not always accept improving moves!! 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 // We have service times so remove the service time from the 00335 // deviation calculation 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