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 ThreeOpt::route_search(class VRP *V, int r, int rules) 00017 { 00023 00024 VRPMove M, BestM; 00025 int ii,a,b,c,d,e,f; 00026 00027 BestM.savings=VRP_INFINITY; 00028 00029 int e11, e12, e21, e22, e31, e32; 00030 // The edges involved in the move: e1, e2, e3 00031 00032 00033 int accept_type=VRPH_FIRST_ACCEPT; 00034 00035 // Initialize to null edges 00036 e11=e12=e21=e22=e31=e32=0; 00037 00038 if( (rules & VRPH_USE_NEIGHBOR_LIST) > 0) 00039 report_error("%s: neighbor_list not used in 3OPT search--searches all nodes in route\n",__FUNCTION__); 00040 00041 accept_type = VRPH_FIRST_ACCEPT; //default 00042 00043 if( (rules & VRPH_LI_ACCEPT) == VRPH_LI_ACCEPT) 00044 accept_type=VRPH_LI_ACCEPT; 00045 00046 if( (rules & VRPH_BEST_ACCEPT) == VRPH_BEST_ACCEPT) 00047 accept_type=VRPH_BEST_ACCEPT; 00048 00049 ii=0; 00050 00051 b= V->route[r].start; 00052 a=VRPH_MAX(V->pred_array[b],0); 00053 // edge 1 is a-b 00054 c=VRPH_MAX(V->next_array[b],0); 00055 if(c==VRPH_DEPOT) 00056 return false; 00057 d=VRPH_MAX(V->next_array[c],0); 00058 if(d==VRPH_DEPOT) 00059 return false; 00060 e=VRPH_MAX(V->next_array[d],0); 00061 if(e==VRPH_DEPOT) 00062 return false; 00063 f=VRPH_MAX(V->next_array[e],0); 00064 if(f==VRPH_DEPOT) 00065 return false; 00066 00067 int a_end, c_end, e_end; 00068 // Set the a_end to 3 hops back from the route's end since 00069 // we will have searched all possible moves by this point. 00070 // This is ugly... 00071 a_end = VRPH_MAX(VRPH_DEPOT,V->pred_array[VRPH_MAX(VRPH_DEPOT,V->pred_array[VRPH_MAX(VRPH_DEPOT, V->pred_array[V->route[r].end])])]); 00072 c_end = VRPH_MAX(VRPH_DEPOT, V->pred_array[V->route[r].end]); 00073 e_end = V->route[r].end; 00074 00075 int *old_sol=NULL; 00076 if(rules & VRPH_TABU) 00077 { 00078 // Remember the original solution 00079 old_sol=new int[V->num_original_nodes+2]; 00080 V->export_solution_buff(old_sol); 00081 } 00082 00083 00084 00085 // Evaluate the first move and then enter the loop 00086 // We begin with the edges a-b, c-d, and e-f 00087 if(evaluate(V,a,b,c,d,e,f,rules,&M)==true) 00088 { 00089 if(accept_type==VRPH_FIRST_ACCEPT || ((accept_type==VRPH_LI_ACCEPT)&&M.savings<-VRPH_EPSILON)) 00090 { 00091 // Make the move 00092 if(move(V, &M)==false) 00093 report_error("%s: move error 1\n",__FUNCTION__); 00094 else 00095 { 00096 if(!(rules & VRPH_TABU)) 00097 return true; 00098 else 00099 { 00100 // Check VRPH_TABU status of move - return true if its ok 00101 // or revert to old_sol if not and continue to search. 00102 if(V->check_tabu_status(&M, old_sol)) 00103 { 00104 delete [] old_sol; 00105 return true; // The move was ok 00106 } 00107 // else we reverted back - continue the search for a move 00108 } 00109 } 00110 } 00111 00112 if(accept_type==VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT) 00113 { 00114 if(M.is_better(V, &BestM, rules))//if(M.savings<BestM.savings) 00115 BestM=M; 00116 } 00117 } 00118 00119 a=b; 00120 00121 00122 while(a!=a_end) 00123 { 00124 b=VRPH_MAX(V->next_array[a],0); 00125 c=VRPH_MAX(V->next_array[b],0); 00126 while(c!=c_end) 00127 { 00128 d=VRPH_MAX(V->next_array[c],0); 00129 e=VRPH_MAX(V->next_array[d],0); 00130 while(e!=e_end) 00131 { 00132 f=VRPH_MAX(V->next_array[e],0); 00133 00134 // Evaluate the move! 00135 if(evaluate(V,a,b,c,d,e,f,rules,&M)==true) 00136 { 00137 if(accept_type==VRPH_FIRST_ACCEPT || ((accept_type==VRPH_LI_ACCEPT)&&M.savings<-VRPH_EPSILON)) 00138 { 00139 // Make the move 00140 if(move(V, &M)==false) 00141 report_error("%s: move error 1\n",__FUNCTION__); 00142 else 00143 { 00144 if(!(rules & VRPH_TABU)) 00145 return true; 00146 else 00147 { 00148 // Check VRPH_TABU status of move - return true if its ok 00149 // or revert to old_sol if not and continue to search. 00150 if(V->check_tabu_status(&M, old_sol)) 00151 { 00152 delete [] old_sol; 00153 return true; // The move was ok 00154 } 00155 // else we reverted back - continue the search for a move 00156 } 00157 } 00158 } 00159 00160 if(accept_type==VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT) 00161 { 00162 if(M.is_better(V, &BestM, rules)) 00163 BestM=M; 00164 00165 } 00166 } 00167 e=f; 00168 } 00169 c=d; 00170 } 00171 a=b; 00172 } 00173 00174 00175 if(accept_type==VRPH_FIRST_ACCEPT || BestM.savings==VRP_INFINITY) 00176 return false; 00177 00178 if(accept_type==VRPH_BEST_ACCEPT || accept_type==VRPH_LI_ACCEPT) 00179 { 00180 if(move(V,&BestM)==false) 00181 { 00182 report_error("%s: best move evaluates to false\n",__FUNCTION__); 00183 } 00184 else 00185 { 00186 if(!(rules & VRPH_TABU)) 00187 return true; 00188 else 00189 { 00190 // Check VRPH_TABU status of move - return true if its ok 00191 // or revert to old_sol if not and continue to search. 00192 if(V->check_tabu_status(&BestM, old_sol)) 00193 { 00194 delete [] old_sol; 00195 return true; // The move was ok 00196 } 00197 // else we reverted back - search over 00198 delete [] old_sol; 00199 return false; 00200 00201 } 00202 } 00203 } 00204 00205 if(move(V,&BestM)==false)//best_e11,best_e12,best_e21,best_e22, best_e31, best_e32,rules)==false) 00206 report_error("%s: first move is false!\n",__FUNCTION__); 00207 else 00208 return true; 00209 00210 00211 return false; 00212 } 00213 00214 bool ThreeOpt::evaluate(class VRP *V, int a, int b, int c, int d, int e, int f, 00215 int rules, VRPMove *M) 00216 { 00224 00225 V->num_evaluations[THREE_OPT_INDEX]++; 00226 M->evaluated_savings=false; 00227 00228 if(V->routed[a]==false || V->routed[b]==false || V->routed[c]==false 00229 || V->routed[d]==false|| V->routed[e]==false|| V->routed[f]==false) 00230 return false; 00231 00232 if(rules & VRPH_FIXED_EDGES) 00233 { 00234 // Make sure we aren't disturbing fixed edges 00235 if( V->fixed[a][b] || V->fixed[c][d] || V->fixed[e][f]) 00236 return false; 00237 00238 } 00239 00240 int a_route; 00241 00242 if(a!=VRPH_DEPOT) 00243 a_route = V->route_num[a]; 00244 else 00245 a_route = V->route_num[b]; 00246 00247 M->eval_arguments[0]=a;M->eval_arguments[1]=b;M->eval_arguments[2]=c; 00248 M->eval_arguments[3]=d;M->eval_arguments[4]=e;M->eval_arguments[5]=f; 00249 00250 // IMPORTANT!! Assume that edges are in order and have no conflicts 00251 00252 double s1, s2, s3, s4, s5, s6, s7, old; 00253 00254 00255 // savings = new-old 00256 double minval=VRP_INFINITY; 00257 int type=0; 00258 old= V->d[a][b]+V->d[c][d]+V->d[e][f]; 00259 s1=(V->d[a][b]+V->d[c][e]+V->d[d][f])-old; // 2-opt move 00260 minval=s1; type=1; 00261 s2=(V->d[a][c]+V->d[b][d]+V->d[e][f])-old; // 2-opt move 00262 if(s2<minval){ minval=s2; type=2;} 00263 s3=(V->d[a][c]+V->d[b][e]+V->d[d][f])-old; // 3-opt move 00264 if(s3<minval){ minval=s3; type=3;} 00265 s4=(V->d[a][d]+V->d[b][e]+V->d[c][f])-old; // 3-opt move 00266 if(s4<minval){ minval=s4; type=4;} 00267 s5=(V->d[a][d]+V->d[c][e]+V->d[b][f])-old; // 3-opt move 00268 if(s5<minval){ minval=s5; type=5;} 00269 s6=(V->d[a][e]+V->d[b][d]+V->d[c][f])-old; // 3-opt move 00270 if(s6<minval){ minval=s6; type=6;} 00271 s7=(V->d[a][e]+V->d[c][d]+V->d[b][f])-old; // 2-opt move 00272 if(s7<minval){ minval=s7; type=7;} 00273 00274 // No need to check load here since it's INTRA only 00275 00276 // Now check route feasibility of the best savings 00277 if(minval + V->route[a_route].length > V->max_route_length ) 00278 // The move is infeasible 00279 return false; 00280 00281 // else the move is feasible - store the results in the move struct 00282 00283 M->savings=minval; 00284 M->num_affected_routes=1; 00285 M->route_lens[0]=minval+V->route[a_route].length; 00286 M->route_nums[0]=a_route; 00287 M->route_custs[0]=V->route[a_route].num_customers; 00288 M->route_loads[0]=V->route[a_route].load; 00289 M->total_number_of_routes=V->total_number_of_routes; 00290 M->new_total_route_length=V->total_route_length+M->savings; 00291 M->eval_arguments[0]=a;M->eval_arguments[1]=b;M->eval_arguments[2]=c; 00292 M->eval_arguments[3]=d;M->eval_arguments[4]=e;M->eval_arguments[5]=f; 00293 M->move_type=type; 00294 00295 // Now check the move 00296 if(V->check_move(M,rules)==true) 00297 { 00298 return true; 00299 } 00300 else 00301 return false; 00302 00303 } 00304 00305 bool ThreeOpt::move(class VRP *V, VRPMove *M)// int a, int b, int c, int d, int e, int f, int rules) 00306 { 00311 00312 int a,b,c,d,e,f; 00313 a=M->eval_arguments[0];b=M->eval_arguments[1];c=M->eval_arguments[2]; 00314 d=M->eval_arguments[3];e=M->eval_arguments[4];f=M->eval_arguments[5]; 00315 00316 // Two cases: 1) all in one route; 2) 3 different routes (not considered!) 00317 00318 int a_route,c_route,e_route; 00319 00320 if(a!=VRPH_DEPOT) 00321 a_route= V->route_num[a]; 00322 else 00323 a_route= V->route_num[b]; 00324 00325 if(c!=VRPH_DEPOT) 00326 c_route= V->route_num[c]; 00327 else 00328 c_route= V->route_num[d]; 00329 00330 if(e!=VRPH_DEPOT) 00331 e_route= V->route_num[e]; 00332 else 00333 e_route= V->route_num[f]; 00334 00335 00336 00337 // INTRAROUTE CASE: 00338 if(a_route==c_route && c_route==e_route) 00339 { 00340 int type = M->move_type; 00341 00342 00344 00345 // 00346 double oldlen, oldobj; 00347 double temp_maxlen; 00348 int temp_vehcap, a_route; 00349 00350 // Remember the actual maximums as we may need to artificially inflate them. 00351 temp_maxlen= V->max_route_length; 00352 temp_vehcap= V->max_veh_capacity; 00353 00354 Flip flip; 00355 00356 a_route= V->route_num[b];// b is not VRPH_DEPOT 00357 00358 oldlen= V->route[a_route].length; 00359 oldobj= V->total_route_length; 00360 00361 if(type==1) 00362 { 00363 00364 if(f==VRPH_DEPOT) 00365 { 00366 V->postsert_dummy(e); 00367 flip.move(V,c,V->dummy_index); 00368 V->remove_dummy(); 00369 } 00370 else 00371 flip.move(V,c,f); 00372 00373 00374 V->num_moves[THREE_OPT_INDEX]++; 00375 V->capture_best_solution(); 00376 return true; 00377 00378 } 00379 00380 if(type==2) 00381 { 00382 00383 00384 if(a==VRPH_DEPOT) 00385 { 00386 00387 V->presert_dummy(b); 00388 flip.move(V,V->dummy_index,d); 00389 V->remove_dummy(); 00390 } 00391 else 00392 flip.move(V,a,d); 00393 00394 V->num_moves[THREE_OPT_INDEX]++; 00395 V->capture_best_solution(); 00396 return true; 00397 } 00398 00399 if(type==3) 00400 { 00401 V->max_route_length=VRP_INFINITY; 00402 V->max_veh_capacity=VRP_INFINITY; 00403 00404 if(a==VRPH_DEPOT) 00405 { 00406 00407 V->presert_dummy(b); 00408 flip.move(V,V->dummy_index,d); 00409 V->remove_dummy(); 00410 } 00411 else 00412 flip.move(V,a,d); 00413 00414 if(f==VRPH_DEPOT) 00415 { 00416 00417 V->postsert_dummy(e); 00418 flip.move(V,b,V->dummy_index); 00419 V->remove_dummy(); 00420 00421 } 00422 else 00423 flip.move(V,b,f); 00424 00425 V->max_route_length=temp_maxlen; 00426 V->max_veh_capacity=temp_vehcap; 00427 00428 V->num_moves[THREE_OPT_INDEX]++; 00429 V->capture_best_solution(); 00430 return true; 00431 } 00432 00433 00434 if(type==4) 00435 { 00436 a_route= V->route_num[b]; // b not VRPH_DEPOT! 00437 00438 if(a!=VRPH_DEPOT && f!=VRPH_DEPOT) 00439 { 00440 V->next_array[a]=d; 00441 V->pred_array[d]=a; 00442 00443 V->next_array[e]=b; 00444 V->pred_array[b]=e; 00445 00446 V->next_array[c]=f; 00447 V->pred_array[f]=c; 00448 } 00449 00450 if(a==VRPH_DEPOT && f!=VRPH_DEPOT) 00451 { 00452 int prev_end=VRPH_ABS(V->pred_array[b]); 00453 V->next_array[prev_end] = -d; 00454 V->pred_array[d] = -prev_end; 00455 00456 V->next_array[e]=b; 00457 V->pred_array[b]=e; 00458 00459 V->next_array[c]=f; 00460 V->pred_array[f]=c; 00461 00462 V->route[a_route].start=d; 00463 } 00464 00465 if(a!=VRPH_DEPOT && f==VRPH_DEPOT) 00466 { 00467 int prev_start=VRPH_ABS(V->next_array[e]); 00468 V->pred_array[prev_start] = -c; 00469 V->next_array[c] = -prev_start; 00470 00471 V->next_array[e]=b; 00472 V->pred_array[b]=e; 00473 00474 V->next_array[a]=d; 00475 V->pred_array[d]=a; 00476 } 00477 00478 if(a==VRPH_DEPOT && f==VRPH_DEPOT) 00479 { 00480 int prev_end=VRPH_ABS(V->pred_array[b]); 00481 int prev_start=VRPH_ABS(V->next_array[e]); 00482 00483 00484 V->next_array[prev_end]=-b; 00485 V->pred_array[b]=-prev_end; 00486 00487 V->next_array[e]=b; 00488 V->pred_array[b]=e; 00489 00490 V->next_array[c]=-prev_start; 00491 V->pred_array[prev_start]=-c; 00492 00493 V->route[a_route].start=d; 00494 00495 00496 } 00497 00498 //Now manually adjust the route_len and obj. value 00499 00500 00501 V->route[a_route].length=oldlen+M->savings;//s4; 00502 V->total_route_length=oldobj+M->savings;//s4; 00503 00504 V->num_moves[THREE_OPT_INDEX]++; 00505 V->capture_best_solution(); 00506 return true; 00507 00508 00509 } 00510 00511 if(type==5) 00512 { 00513 V->max_route_length=VRP_INFINITY; 00514 V->max_veh_capacity=VRP_INFINITY; 00515 00516 int prev_end=-1; 00517 00518 // Remember: flip changes the obj. value!!!! 00519 if(a==VRPH_DEPOT) 00520 { 00521 prev_end=VRPH_ABS(V->pred_array[b]); 00522 V->presert_dummy(b); 00523 flip.move(V,V->dummy_index,d); 00524 V->remove_dummy(); 00525 00526 } 00527 else 00528 flip.move(V,a,d); 00529 00530 if(a==VRPH_DEPOT) 00531 { 00532 00533 V->next_array[prev_end]=-d; 00534 V->pred_array[d]=-prev_end; 00535 V->route[a_route].start=d; 00536 } 00537 else 00538 { 00539 V->next_array[a]=d; 00540 V->pred_array[d]=a; 00541 } 00542 00543 if(f==VRPH_DEPOT) 00544 { 00545 int prev_start=VRPH_ABS(V->next_array[e]); 00546 V->next_array[b]=-prev_start; 00547 V->pred_array[prev_start]=-b; 00548 00549 } 00550 else 00551 { 00552 V->next_array[b]=f; 00553 V->pred_array[f]=b; 00554 } 00555 00556 V->next_array[e]=c; 00557 V->pred_array[c]=e; 00558 00559 00560 00561 //Now manually adjust the route_len and obj. value 00562 00563 V->max_route_length=temp_maxlen; 00564 V->max_veh_capacity=temp_vehcap; 00565 00566 00567 a_route= V->route_num[b]; 00568 00569 V->route[a_route].length=oldlen+M->savings;//s5; 00570 V->total_route_length=oldobj+M->savings;//s5; 00571 00572 V->num_moves[THREE_OPT_INDEX]++; 00573 V->capture_best_solution(); 00574 return true; 00575 } 00576 00577 if(type==6) 00578 { 00579 V->max_route_length=VRP_INFINITY; 00580 V->max_veh_capacity=VRP_INFINITY; 00581 00582 int prev_end=VRPH_ABS(V->pred_array[b]); 00583 00584 if(f==VRPH_DEPOT) 00585 { 00586 V->postsert_dummy(e); 00587 flip.move(V,c,V->dummy_index); 00588 V->remove_dummy(); 00589 } 00590 else 00591 flip.move(V,c,f); 00592 00593 00594 if(a==VRPH_DEPOT) 00595 { 00596 00597 V->next_array[prev_end]=-e; 00598 V->pred_array[e]=-prev_end; 00599 V->route[V->route_num[b]].start=e; 00600 } 00601 else 00602 { 00603 V->next_array[a]=e; 00604 V->pred_array[e]=a; 00605 } 00606 00607 V->next_array[d]=b; 00608 V->pred_array[b]=d; 00609 00610 if(f==VRPH_DEPOT) 00611 { 00612 int prev_start=VRPH_ABS(V->next_array[e]); 00613 V->next_array[c]=-prev_start; 00614 V->pred_array[prev_start]=-c; 00615 00616 } 00617 else 00618 { 00619 V->next_array[c]=f; 00620 V->pred_array[f]=c; 00621 } 00622 00623 //Now manually adjust the route_len and obj. value 00624 00625 a_route= V->route_num[b]; 00626 V->route[a_route].length=oldlen+M->savings;//s6; 00627 V->total_route_length=oldobj+M->savings;//s6; 00628 00629 V->max_route_length=temp_maxlen; 00630 V->max_veh_capacity=temp_vehcap; 00631 00632 V->num_moves[THREE_OPT_INDEX]++; 00633 V->capture_best_solution(); 00634 return true; 00635 00636 } 00637 00638 if(type==7) 00639 { 00640 00641 //ae,dc,bf 00642 if(a==VRPH_DEPOT && f==VRPH_DEPOT) 00643 { 00644 // This is just a route reversal - should have no savings!! 00645 report_error("%s: route reversal??\n",__FUNCTION__); 00646 } 00647 00648 if(a==VRPH_DEPOT) 00649 { 00650 V->presert_dummy(b); 00651 flip.move(V,V->dummy_index,f); 00652 V->remove_dummy(); 00653 } 00654 else 00655 { 00656 if(f==VRPH_DEPOT) 00657 { 00658 V->postsert_dummy(e); 00659 flip.move(V,a,V->dummy_index); 00660 V->remove_dummy(); 00661 } 00662 else 00663 flip.move(V,a,f); 00664 00665 } 00666 00667 V->num_moves[THREE_OPT_INDEX]++; 00668 V->capture_best_solution(); 00669 return true; 00670 00671 00672 } 00673 00674 } 00675 00676 00677 return false; 00678 00679 } 00680 00681