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 #include "VRPH.h" 00014 00015 00016 bool CrossExchange::route_search(class VRP *V, int r1, int r2, int rules) 00017 { 00023 00024 // Make sure we have two diff. routes! 00025 if(r1==r2) 00026 return false; 00027 00028 #if CROSS_EXCHANGE_DEBUG > 1 00029 printf("Evaluating CE move b/w routes %d and %d\n",r1,r2); 00030 #endif 00031 00032 00033 int start_1, end_1, start_2, end_2; 00034 int i1, i2, k1, k2; // Route r1 nodes 00035 int j1, j2, l1, l2; // Route r2 nodes 00036 00037 VRPMove M, BestM; 00038 00039 BestM.savings=VRP_INFINITY; 00040 00041 int accept_type; 00042 00043 // Default 00044 accept_type = VRPH_FIRST_ACCEPT; 00045 00046 if( (rules & VRPH_LI_ACCEPT) == VRPH_LI_ACCEPT) 00047 accept_type = VRPH_LI_ACCEPT; 00048 00049 00050 if( (rules & VRPH_BEST_ACCEPT) == VRPH_BEST_ACCEPT) 00051 accept_type = VRPH_BEST_ACCEPT; 00052 00053 // Use current_1a/b and next_1a/b for route r1 and current_2a/b and next_2a/b for route r2 00054 if(V->route[r1].num_customers < 4 || V->route[r2].num_customers < 4) 00055 // Not possible to find a CE move 00056 return false; 00057 00058 int *old_sol=NULL; 00059 if(rules & VRPH_TABU) 00060 { 00061 // Remember the original solution 00062 old_sol=new int[V->num_original_nodes+2]; 00063 V->export_solution_buff(old_sol); 00064 } 00065 00066 // Get route starts and ends 00067 00068 start_1= V->route[r1].start; 00069 end_1= V->route[r1].end; 00070 00071 int end_i=V->pred_array[end_1]; 00072 00073 00074 start_2= V->route[r2].start; 00075 end_2= V->route[r2].end; 00076 00077 int end_j=V->pred_array[end_2]; 00078 00079 i1 = start_1; // don't allow VRPH_DEPOT edges for now... 00080 i2 = V->next_array[i1]; 00081 00082 while(i2 != end_i) 00083 { 00084 // First edge in route 1 is i1-i2 00085 00086 // Now find the second edge in route r1 00087 k1 = V->next_array[i2]; 00088 00089 00090 if(k1==end_1) 00091 break; // VRPH_DEPOT edge not allowed 00092 00093 k2 = V->next_array[k1]; 00094 while(k2 != end_1) 00095 { 00096 // Second edge in route 1 is k1-k2 00097 00098 // Now find edges in the second route 00099 00100 j1 = start_2; 00101 j2 = V->next_array[j1]; 00102 00103 while(j2 != end_j) 00104 { 00105 00106 // First edge in route 2 is j1-j2 00107 00108 // Now find the second edge in route r2: l1-l2 00109 l1 = V->next_array[j2]; 00110 00111 if(l1==end_2) 00112 break; 00113 00114 l2 = V->next_array[l1]; 00115 00116 while(l2 != end_2) 00117 { 00118 // Now evaluate the cross exchange move involving 00119 // i1-i2, k1-k2, and 00120 // j1-j2, l1-l2 00121 00122 if(this->evaluate(V,i1,i2,k1,k2,j1,j2,l1,l2,rules,&M) == true) 00123 { 00124 00125 // We have found a valid move. 00126 if(accept_type == VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON) ) 00127 { 00128 // Make the move 00129 00130 if(move(V, &M)==false) 00131 report_error("%s: move error 1\n"); 00132 else 00133 { 00134 if(!(rules & VRPH_TABU)) 00135 return true; 00136 else 00137 { 00138 // Check VRPH_TABU status of move - return true if its ok 00139 // or revert to old_sol if not and continue to search. 00140 if(V->check_tabu_status(&M, old_sol)) 00141 { 00142 delete [] old_sol; 00143 return true; // The move was ok 00144 } 00145 // else we reverted back - continue the search for a move 00146 } 00147 } 00148 } 00149 00150 00151 if(accept_type == VRPH_LI_ACCEPT || accept_type == VRPH_BEST_ACCEPT) 00152 { 00153 // Check for new best move 00154 if(M.is_better(V, &BestM, rules)) 00155 BestM=M; 00156 00157 } 00158 00159 } 00160 00161 // Now advance the second edge in route r2 00162 00163 l1 = l2; 00164 l2 = V->next_array[l1]; 00165 00166 } 00167 // end route r2 edge 2 loop 00168 00169 // Now advance the first edge in route r2 00170 00171 j1 = j2; 00172 j2= V->next_array[j1]; 00173 00174 } 00175 // end route r2 edge 1 loop 00176 00177 // Now advance the second edge in route r1 00178 k1 = k2; 00179 k2 = V->next_array[k1]; 00180 00181 } 00182 // end route r1 edge 2 loop 00183 00184 // Now advance the first edge in route r1 00185 00186 i1 = i2; 00187 i2 = V->next_array[i1]; 00188 00189 } 00190 00191 #if CROSS_EXCHANGE_DEBUG > 1 00192 printf("END OF LOOP: %f\n",BestM.savings); 00193 #endif 00194 if(BestM.savings == VRP_INFINITY || accept_type == VRPH_FIRST_ACCEPT) 00195 return false; 00196 00197 if(accept_type==VRPH_FIRST_ACCEPT || BestM.savings==VRP_INFINITY) 00198 { 00199 if(rules&VRPH_TABU) 00200 delete [] old_sol; 00201 return false; // No moves found 00202 } 00203 00204 if(accept_type==VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT) 00205 { 00206 if(move(V,&BestM)==false) 00207 { 00208 report_error("%s: best move evaluates to false\n"); 00209 } 00210 else 00211 { 00212 if(!(rules & VRPH_TABU)) 00213 return true; 00214 else 00215 { 00216 // Check VRPH_TABU status of move - return true if its ok 00217 // or revert to old_sol if not and continue to search. 00218 if(V->check_tabu_status(&BestM, old_sol)) 00219 { 00220 delete [] old_sol; 00221 return true; // The move was ok 00222 } 00223 // else we reverted back - search over 00224 delete [] old_sol; 00225 return false; 00226 00227 } 00228 } 00229 } 00230 00231 report_error("%s: should have returned already...\n",__FUNCTION__); 00232 return false; 00233 } 00234 00235 00236 00237 // EVALUATE 00238 bool CrossExchange::evaluate(class VRP *V, int i1, int i2, int k1, int k2, int j1, int j2, int l1, int l2, 00239 int rules, VRPMove *M) 00240 { 00245 00246 V->num_evaluations[CROSS_EXCHANGE_INDEX]++; 00247 00248 #if CROSS_EXCHANGE_DEBUG > 1 00249 printf("Evaluting CE move: %d-%d, %d-%d, %d-%d, %d-%d\n",i1,i2,k1,k2,j1,j2,l1,l2); 00250 #endif 00251 if(V->routed[i1]==false|| V->routed[i2]==false|| V->routed[k1]==false|| V->routed[k2]==false 00252 || V->routed[j1]==false|| V->routed[j2]==false|| V->routed[l1]==false|| V->routed[l2]==false) 00253 return false; 00254 00255 00256 M->evaluated_savings=false; 00257 double savings; 00258 00259 // savings = new - old 00260 00261 M->savings = savings = (V->d[i1][j2]+V->d[j1][i2]+V->d[k1][l2]+V->d[l1][k2]) - 00262 (V->d[i1][i2]+V->d[j1][j2]+V->d[k1][k2]+V->d[l1][l2]); 00263 00264 // Check the savings now 00265 if(V->check_savings(M,rules)==false) 00266 return false; 00267 00268 00269 // else the move has potential -- now check feasibility 00270 // Assume that edge i1-i2 is before k1-k2 in one route and that j1-j2 is before l1-l2 00271 // in the second route - this is not checked!! 00272 00273 00274 // Move seems to make sense 00275 int i_route, j_route ; 00276 00277 i_route= V->route_num[i2]; 00278 j_route= V->route_num[j2]; 00279 00280 if(i_route==j_route) 00281 { 00282 fprintf(stderr,"i1=%d;i2=%d;k1=%d;k2=%d;j1=%d;j2=%d;l1=%d;l2=%d\n",i1,i2,k1,k2,j1,j2,l1,l2); 00283 fprintf(stderr,"i_route=%d; j_route=%d\n",i_route,j_route); 00284 V->show_route(i_route); 00285 report_error("%s: i_route==j_route!!\n",__FUNCTION__); 00286 } 00287 00288 // Otherwise, the move appears to make sense 00289 00290 double new_i_len, new_j_len; 00291 00292 // savings = new_i_len + new_i_len - (old_i_len + old_j_len) 00293 00294 //new_i_len= route distance to (i1) + d(i1,j2)+ route distance between j2 and l1 00295 // + d(l1,k2) + route distance from (k2) to depot at end of route 00296 00297 //new_j_len= route distance to (j1) + d(j1,i2) + route distance between i2 and k1 00298 // + d(k1,l2) + route distance from (l2) to depot at end of route 00299 00300 00301 VRPSegment S_0_i1, S_j2_l1, S_k2_0; 00302 V->get_segment_info(VRPH_DEPOT, i1, &S_0_i1); 00303 V->get_segment_info(j2, l1, &S_j2_l1); 00304 V->get_segment_info(k2, VRPH_DEPOT, &S_k2_0); 00305 00306 new_i_len = S_0_i1.len + V->d[i1][j2] + S_j2_l1.len + V->d[l1][k2] + S_k2_0.len; 00307 00308 if(new_i_len>V->max_route_length) 00309 return false; 00310 00311 new_j_len = savings + V->route[i_route].length + V->route[j_route].length - new_i_len; 00312 00313 if(new_j_len>V->max_route_length) 00314 return false; 00315 00316 int new_i_load, new_j_load; 00317 00318 new_i_load = S_0_i1.load + S_j2_l1.load + S_k2_0.load; 00319 00320 if(new_i_load>V->max_veh_capacity) 00321 return false; 00322 00323 00324 new_j_load = V->route[i_route].load + V->route[j_route].load - new_i_load; 00325 00326 00327 if(new_j_load > V->max_veh_capacity) 00328 return false; 00329 00330 // The move is feasible - check the rules 00331 00332 M->savings=savings; 00333 00334 #if CROSS_EXCHANGE_DEBUG>1 00335 printf("CROSS_EXCHANGE::savings is %f\n", savings); 00336 #endif 00337 00338 M->num_affected_routes=2; 00339 M->route_nums[0] = i_route; 00340 M->route_nums[1] = j_route; 00341 M->route_custs[0]= S_0_i1.num_custs + S_j2_l1.num_custs + S_k2_0.num_custs; 00342 00343 #if CROSS_EXCHANGE_DEBUG > 1 00344 printf("%d + %d + %d = %d\n",S_0_i1.num_custs, S_j2_l1.num_custs, S_k2_0.num_custs, 00345 M->route_custs[0]); 00346 #endif 00347 M->route_custs[1]= V->route[i_route].num_customers + V->route[j_route].num_customers- 00348 M->route_custs[0]; 00349 M->route_lens[0]=new_i_len; 00350 M->route_lens[1]=new_j_len; 00351 M->route_loads[0]=new_i_load; 00352 M->route_loads[1]=new_j_load; 00353 M->savings=savings; 00354 M->new_total_route_length= V->total_route_length+savings; 00355 M->num_arguments=9; 00356 M->move_arguments[0]=i1; M->move_arguments[1]=i2; M->move_arguments[2]=k1; M->move_arguments[3]=k2; 00357 M->move_arguments[4]=j1; M->move_arguments[5]=j2; M->move_arguments[6]=l1; M->move_arguments[7]=l2; 00358 M->move_arguments[8]=rules; 00359 M->total_number_of_routes = V->total_number_of_routes; 00360 00361 #if CROSS_EXCHANGE_DEBUG > 1 00362 printf("CROSS_EXCHANGE::\nlengths: %f, %f\nloads: %d, %d\ncusts: %d, %d\n",M->route_lens[0], 00363 M->route_lens[1], M->route_loads[0], M->route_loads[1], M->route_custs[0], M->route_custs[1]); 00364 #endif 00365 00366 00367 if(V->check_move(M,rules)==true) 00368 return true; 00369 else 00370 return false; 00371 00372 } 00373 00374 00375 bool CrossExchange::move(class VRP *V, VRPMove *M) 00376 { 00381 00382 int i1, i2, k1, k2, j1, j2, l1, l2; 00383 00384 i1=M->move_arguments[0];i2=M->move_arguments[1];k1=M->move_arguments[2];k2=M->move_arguments[3]; 00385 j1=M->move_arguments[4];j2=M->move_arguments[5];l1=M->move_arguments[6];l2=M->move_arguments[7]; 00386 00387 00388 #if CROSS_EXCHANGE_DEBUG 00389 printf("Routes before cross (%d-%d, %d-%d) (%d-%d, %d-%d)\n",i1,i2,k1,k2,j1,j2,l1,l2); 00390 V->show_route(V->route_num[i1]); 00391 V->show_route(V->route_num[j1]); 00392 #endif 00393 00394 V->next_array[j1]=i2; 00395 V->pred_array[i2]=j1; 00396 00397 V->next_array[k1]=l2; 00398 V->pred_array[l2]=k1; 00399 00400 V->next_array[i1]=j2; 00401 V->pred_array[j2]=i1; 00402 00403 V->next_array[l1]=k2; 00404 V->pred_array[k2]=l1; 00405 00406 00407 00408 // Now update the route_num and the start and ends 00409 int current_node; 00410 00411 current_node= V->route[M->route_nums[0]].start; 00412 00413 while(current_node!=VRPH_DEPOT) 00414 { 00415 V->route[M->route_nums[0]].end=current_node; 00416 V->route_num[current_node] = M->route_nums[0]; 00417 current_node= VRPH_MAX(VRPH_DEPOT,V->next_array[current_node]); 00418 } 00419 00420 current_node= V->route[M->route_nums[1]].start; 00421 00422 while(current_node!=VRPH_DEPOT) 00423 { 00424 V->route[M->route_nums[1]].end=current_node; 00425 V->route_num[current_node] = M->route_nums[1]; 00426 current_node= VRPH_MAX(VRPH_DEPOT, V->next_array[current_node]); 00427 } 00428 00429 V->update(M); 00430 00431 00432 #if CROSS_EXCHANGE_DEBUG 00433 printf("Routes after CrossExchange move (%d-%d, %d-%d), (%d-%d, %d-%d)\n", 00434 i1,i2,k1,k2, j1,j2,l1,l2); 00435 V->show_route(M->route_nums[0]); 00436 V->show_route(M->route_nums[1]); 00437 #endif 00438 00439 #if CROSS_EXCHANGE_VERIFY 00440 V->verify_routes("After CrossExchange move\n"); 00441 #endif 00442 00443 V->num_moves[CROSS_EXCHANGE_INDEX]++; 00444 00445 V->capture_best_solution(); 00446 00447 return true; 00448 00449 } 00450