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 // SEARCH 00016 bool OnePointMove::search(class VRP *V, int j, int rules) 00017 { 00023 00024 VRPMove M; 00025 VRPMove BestM; 00026 M.savings=M.new_total_route_length=BestM.savings=BestM.new_total_route_length=VRP_INFINITY; 00027 00028 int i,k; 00029 int best_k=0; 00030 int accept_type; 00031 00032 i=VRPH_MAX(V->pred_array[j],VRPH_DEPOT); 00033 k=VRPH_MAX(V->next_array[j],VRPH_DEPOT); 00034 00035 // Return false if there are two or fewer nodes in i's route 00036 if(V->route[V->route_num[j]].num_customers<=3) 00037 return false; 00038 00039 if( (rules & VRPH_FIXED_EDGES) ) 00040 { 00041 // Make sure we aren't disturbing fixed edges 00042 if( (V->fixed[i][j]) || (V->fixed[j][k]) ) 00043 return false; 00044 00045 } 00046 00047 // Determine acceptance type 00048 //default setting 00049 accept_type=VRPH_FIRST_ACCEPT; 00050 00051 if( rules & VRPH_FIRST_ACCEPT ) 00052 accept_type=VRPH_FIRST_ACCEPT; 00053 if( rules & VRPH_BEST_ACCEPT ) 00054 accept_type=VRPH_BEST_ACCEPT; 00055 if( rules & VRPH_LI_ACCEPT ) 00056 accept_type=VRPH_LI_ACCEPT; 00057 00058 // Create the search_space 00059 V->create_search_neighborhood(j, rules); 00060 00061 int *old_sol=NULL; 00062 if(rules & VRPH_TABU) 00063 { 00064 // Remember the original solution 00065 old_sol=new int[V->num_original_nodes+2]; 00066 V->export_solution_buff(old_sol); 00067 } 00068 00069 for(i=0;i<V->search_size;i++) 00070 { 00071 k=V->search_space[i]; 00072 if(evaluate(V,j,k,rules,&M)==true) 00073 { 00074 // Feasible move found 00075 if(accept_type==VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON) ) 00076 { 00077 if(move(V, &M)==false) 00078 report_error("%s: move error 1\n",__FUNCTION__); 00079 else 00080 { 00081 if(!(rules & VRPH_TABU)) 00082 return true; 00083 else 00084 { 00085 // Check VRPH_TABU status of move - return true if its ok 00086 // or revert to old_sol if not and continue to search. 00087 if(V->check_tabu_status(&M, old_sol)) 00088 { 00089 delete [] old_sol; 00090 return true; // The move was ok 00091 } 00092 // else we reverted back - continue the search for a move 00093 } 00094 } 00095 } 00096 00097 if(accept_type==VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT) 00098 { 00099 // store the move 00100 00101 if(M.is_better(V, &BestM, rules)) 00102 { 00103 best_k=k; 00104 BestM=M; 00105 } 00106 } 00107 } 00108 } 00109 00110 00111 // We've considered all the possibilities now... 00112 if(accept_type==VRPH_FIRST_ACCEPT || BestM.savings==VRP_INFINITY) 00113 { 00114 // No moves found 00115 if(old_sol) 00116 delete [] old_sol; 00117 return false; 00118 } 00119 00120 // else we found a move - try to make it 00121 00122 00123 if(move(V,&BestM)==true) 00124 { 00125 if(!(rules & VRPH_TABU)) 00126 return true; 00127 } 00128 00129 if(rules & VRPH_TABU) 00130 { 00131 // Check VRPH_TABU status of move - return true if its ok 00132 // or revert to old_sol if not and return 00133 if(V->check_tabu_status(&BestM, old_sol))// was &M?? 00134 { 00135 delete [] old_sol; 00136 return true; // The move was ok 00137 } 00138 else 00139 { 00140 delete [] old_sol; 00141 return false; 00142 } 00143 } 00144 00145 // Should have already returned 00146 report_error("%s: move error 4\n",__FUNCTION__); 00147 00148 return false; 00149 } 00150 00151 00152 bool OnePointMove::route_search(class VRP *V, int r1, int r2, int rules) 00153 { 00158 00159 // So search is now ROUTE_BASED - no neighbor_lists 00160 if( (rules & VRPH_USE_NEIGHBOR_LIST) > 0) 00161 report_error("%s: route_searches do not use neighbor list\n",__FUNCTION__); 00162 00163 // Otherwise, we have a route search - look for all moves involving 00164 // route r1 and route r2 00165 00166 VRPMove M; 00167 VRPMove BestM; 00168 int k; 00169 double best_savings=VRP_INFINITY; 00170 int best_k=0; 00171 int accept_type; 00172 00173 00174 //default setting 00175 accept_type=VRPH_FIRST_ACCEPT; 00176 00177 if( (rules & VRPH_FIRST_ACCEPT) > 0) 00178 accept_type=VRPH_FIRST_ACCEPT; 00179 if( (rules & VRPH_BEST_ACCEPT) > 0) 00180 accept_type=VRPH_BEST_ACCEPT; 00181 if( (rules & VRPH_LI_ACCEPT) > 0) 00182 accept_type=VRPH_LI_ACCEPT; 00183 00184 00185 int j; 00186 j= V->route[r1].start; 00187 while(j!=VRPH_DEPOT) 00188 { 00189 // Loop through r1 and r2 00190 k= V->route[r2].start; 00191 while(k!=VRPH_DEPOT) 00192 { 00193 if(evaluate(V,j,k,rules,&M)==true) 00194 { 00195 00196 // Feasible move found 00197 if(accept_type==VRPH_FIRST_ACCEPT) 00198 { 00199 // This is the first move found -- make it and return if VRPH_FIRST_ACCEPT 00200 00201 if(move(V,&M)==true) 00202 return true; 00203 else 00204 report_error("%s: move is false?\n",__FUNCTION__); 00205 00206 } 00207 00208 if(accept_type==VRPH_BEST_ACCEPT) 00209 { 00210 // VRPH_BEST_ACCEPT - store the move 00211 00212 if(M.savings<best_savings) 00213 { 00214 best_savings=M.savings; 00215 best_k=k; 00216 BestM=M; 00217 } 00218 } 00219 00220 if(accept_type==VRPH_LI_ACCEPT) 00221 { 00222 // move if downhill, store otherwise. 00223 00224 if(M.savings<-VRPH_EPSILON) 00225 { 00226 // it's downhill, so make it. 00227 if(move(V,&M)==true) 00228 return true; 00229 else 00230 report_error("%s: false 7\n",__FUNCTION__); 00231 } 00232 00233 if(M.savings<best_savings) 00234 { 00235 best_savings=M.savings; 00236 best_k=k; 00237 BestM=M; 00238 } 00239 } 00240 } 00241 k=VRPH_MAX(V->next_array[k],0); 00242 } 00243 j=VRPH_MAX(V->next_array[j],0); 00244 } 00245 00246 if(accept_type==VRPH_FIRST_ACCEPT) 00247 { 00248 // No moves found 00249 return false; 00250 } 00251 00252 // Otherwise we will make the best move found 00253 if(best_savings==VRP_INFINITY) 00254 return false; 00255 00256 // else we found a move - make it 00257 if(move(V,&BestM)==true) 00258 return true; 00259 else 00260 report_error("%s: false 8\n",__FUNCTION__); 00261 00262 return false; 00263 00264 00265 } 00266 00267 // EVALUATE 00268 bool OnePointMove::evaluate(class VRP *V, int j, int b, int rules, VRPMove *M) 00269 { 00275 00276 V->num_evaluations[ONE_POINT_MOVE_INDEX]++; 00277 00278 int a,c,i,k; 00279 00280 a = VRPH_MAX(V->pred_array[b],VRPH_DEPOT); 00281 c = VRPH_MAX(V->next_array[b],VRPH_DEPOT); 00282 k = VRPH_MAX(V->next_array[j],VRPH_DEPOT); 00283 i = VRPH_MAX(V->pred_array[j],VRPH_DEPOT); 00284 00285 00286 if(rules & VRPH_FIXED_EDGES) 00287 { 00288 // Make sure we aren't disturbing fixed edges 00289 00290 if( V->fixed[i][j]|| V->fixed[j][k] ) 00291 return false; 00292 00293 if(b!=VRPH_DEPOT && (V->fixed[b][c] && V->fixed[a][b]) ) 00294 return false; 00295 } 00296 00297 M->evaluated_savings=false; 00298 00299 if(b==j || V->routed[j]==false || V->routed[b]==false || j==VRPH_DEPOT) 00300 return false; 00301 00302 if(b!=VRPH_DEPOT) 00303 { 00304 if( (rules & VRPH_INTER_ROUTE_ONLY) && (V->route_num[j] ==V->route_num[b]) ) 00305 return false; 00306 00307 if((rules & VRPH_INTRA_ROUTE_ONLY) && (V->route_num[j] !=V->route_num[b]) ) 00308 return false; 00309 00310 // Can quickly check veh capacity: j added to V->route_num[b] 00311 if(V->route_num[j] != V->route_num[b]) 00312 { 00313 if( V->nodes[j].demand + V->route[V->route_num[b]].load > V->max_veh_capacity) 00314 return false; 00315 } 00316 00317 00318 } 00319 00320 double savings1, savings2, best_savings; 00321 Postsert postsert; 00322 Presert presert; 00323 best_savings=VRP_INFINITY; 00324 savings1=VRP_INFINITY; 00325 savings2=VRP_INFINITY; 00326 00327 // First consider the complicated case where b is the VRPH_DEPOT. 00328 // We have 2*r edges to consider where r is the # of routes 00329 // In this case we will find the best possible insertion 00330 if(b==VRPH_DEPOT) 00331 { 00332 int current_start, current_end, current_route; 00333 current_start=abs(V->next_array[VRPH_DEPOT]); 00334 bool allowed, found_move; 00335 VRPMove CurrentM; 00336 found_move=false; 00337 00338 for(;;) 00339 { 00340 // Consider the edge VRPH_DEPOT-current_start 00341 int t=current_start; 00342 allowed=true; 00343 00344 if(j!=t) 00345 { 00346 // Check for fixed edges 00347 if((rules & VRPH_FIXED_EDGES) && V->fixed[VRPH_DEPOT][t]) 00348 allowed=false; 00349 00350 if( (presert.evaluate(V,j,t,&CurrentM)==true)&&(V->check_move(&CurrentM,rules)==true) && allowed ) 00351 { 00352 00353 if(CurrentM.is_better(V,M,rules)) 00354 { 00355 found_move=true; 00356 *M=CurrentM; 00357 } 00358 } 00359 } 00360 00361 // Now try the t-VRPH_DEPOT edge 00362 current_route= V->route_num[current_start]; 00363 current_end= V->route[current_route].end; 00364 t=current_end; 00365 allowed=true; 00366 if(j!=t) 00367 { 00368 // Check for fixed edges 00369 if((rules & VRPH_FIXED_EDGES) && V->fixed[t][VRPH_DEPOT]) 00370 allowed=false; 00371 00372 if( (postsert.evaluate(V,j,t,&CurrentM)==true)&&(V->check_move(&CurrentM,rules)==true) && allowed ) 00373 { 00374 if(CurrentM.is_better(V,M,rules)) 00375 { 00376 found_move=true; 00377 *M=CurrentM; 00378 } 00379 } 00380 00381 } 00382 00383 // Now advance to the next node adjacent to the VRPH_DEPOT 00384 current_start=abs(V->next_array[current_end]); 00385 if(current_start==VRPH_DEPOT) // We're done 00386 break; 00387 } 00388 00389 return found_move; 00390 00391 00392 } 00393 00394 // Special Case 00395 if(c == j) 00396 { 00397 // Only option is to insert j between a and b (b is not VRPH_DEPOT) 00398 00399 if(rules & VRPH_FIXED_EDGES) 00400 { 00401 // Make sure we aren't disturbing fixed edges 00402 00403 if( V->fixed[a][b] )//|| V->fixed[b][c]) 00404 return false; 00405 } 00406 00407 if( (presert.evaluate(V,j,b,M)==true)&&(V->check_move(M,rules)==true) ) 00408 return true; 00409 else 00410 return false; 00411 00412 } 00413 00414 00415 if(a == j) 00416 { 00417 // Only option is to insert j between b and c. b is not VRPH_DEPOT 00418 00419 if(rules & VRPH_FIXED_EDGES) 00420 { 00421 // Make sure we aren't disturbing fixed edges 00422 00423 if( V->fixed[b][c] )//|| V->fixed[a][b] ) 00424 return false; 00425 } 00426 00427 if( (postsert.evaluate(V,j,b,M)==true)&&(V->check_move(M,rules)==true) ) 00428 return true; 00429 else 00430 return false; 00431 00432 } 00433 00434 // No conflicts o/w - can insert j either before or after b 00435 // We will choose the better move always! 00436 00437 // savings = new-old 00438 savings1 = (V->d[a][j]+V->d[j][b]+V->d[i][k]) - (V->d[a][b]+V->d[i][j]+V->d[j][k]) ; 00439 savings2 = (V->d[i][k]+V->d[b][j]+V->d[j][c]) - (V->d[b][c]+V->d[i][j]+V->d[j][k]) ; 00440 00441 best_savings = VRPH_MIN(savings1, savings2); 00442 00443 00444 if( savings1 <= savings2 && (presert.evaluate(V,j,b,M)==true) 00445 &&(V->check_move(M,rules)==true) ) 00446 { 00447 00448 if(rules & VRPH_FIXED_EDGES) 00449 { 00450 // Make sure we aren't disturbing fixed edges 00451 00452 if( V->fixed[a][b] )//|| V->fixed[b][c] ) 00453 return false; 00454 } 00455 return true; 00456 } 00457 00458 // Now check savings2 00459 if( savings2<savings1 && postsert.evaluate(V,j,b,M)==true && 00460 (V->check_move(M,rules)==true) ) 00461 { 00462 00463 if(rules & VRPH_FIXED_EDGES) 00464 { 00465 // Make sure we aren't disturbing fixed edges 00466 00467 if( V->fixed[b][c] )//|| V->fixed[a][b] ) 00468 return false; 00469 } 00470 00471 return true; 00472 } 00473 00474 // Need to check savings1 again in the event that savings2 was better, but the move 00475 // itself was infeasible--not sure if this ever happens... 00476 00477 if( (presert.evaluate(V,j,b,M)==true)&&(V->check_move(M,rules)==true)) 00478 { 00479 if(rules & VRPH_FIXED_EDGES) 00480 { 00481 // Make sure we aren't disturbing fixed edges 00482 00483 if( V->fixed[a][b] )//|| V->fixed[b][c]) 00484 return false; 00485 } 00486 00487 return true; 00488 } 00489 00490 00491 00492 // ELSE no feasible moves found 00493 return false; 00494 } 00495 00496 bool OnePointMove::move(class VRP *V, VRPMove *M) 00497 { 00501 00502 00503 if(M->move_type==PRESERT) 00504 { 00505 Presert presert; 00506 if(presert.move(V,M->move_arguments[0],M->move_arguments[1])) 00507 { 00508 V->num_moves[ONE_POINT_MOVE_INDEX]++; 00509 V->capture_best_solution(); 00510 00511 return true; 00512 } 00513 else 00514 report_error("%s: presert move is false\n",__FUNCTION__); 00515 00516 00517 } 00518 else 00519 { 00520 if(M->move_type==POSTSERT) 00521 { 00522 Postsert postsert; 00523 if(postsert.move(V,M->move_arguments[0],M->move_arguments[1])) 00524 { 00525 V->num_moves[ONE_POINT_MOVE_INDEX]++; 00526 V->capture_best_solution(); 00527 return true; 00528 } 00529 else 00530 report_error("%s: postsert move is false\n",__FUNCTION__); 00531 } 00532 } 00533 00534 return false; 00535 00536 }