00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00012
00013 #include "VRPH.h"
00014
00015
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
00031
00032
00033 int accept_type=VRPH_FIRST_ACCEPT;
00034
00035
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;
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
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
00069
00070
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
00079 old_sol=new int[V->num_original_nodes+2];
00080 V->export_solution_buff(old_sol);
00081 }
00082
00083
00084
00085
00086
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
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
00101
00102 if(V->check_tabu_status(&M, old_sol))
00103 {
00104 delete [] old_sol;
00105 return true;
00106 }
00107
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))
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
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
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
00149
00150 if(V->check_tabu_status(&M, old_sol))
00151 {
00152 delete [] old_sol;
00153 return true;
00154 }
00155
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
00191
00192 if(V->check_tabu_status(&BestM, old_sol))
00193 {
00194 delete [] old_sol;
00195 return true;
00196 }
00197
00198 delete [] old_sol;
00199 return false;
00200
00201 }
00202 }
00203 }
00204
00205 if(move(V,&BestM)==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
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
00251
00252 double s1, s2, s3, s4, s5, s6, s7, old;
00253
00254
00255
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;
00260 minval=s1; type=1;
00261 s2=(V->d[a][c]+V->d[b][d]+V->d[e][f])-old;
00262 if(s2<minval){ minval=s2; type=2;}
00263 s3=(V->d[a][c]+V->d[b][e]+V->d[d][f])-old;
00264 if(s3<minval){ minval=s3; type=3;}
00265 s4=(V->d[a][d]+V->d[b][e]+V->d[c][f])-old;
00266 if(s4<minval){ minval=s4; type=4;}
00267 s5=(V->d[a][d]+V->d[c][e]+V->d[b][f])-old;
00268 if(s5<minval){ minval=s5; type=5;}
00269 s6=(V->d[a][e]+V->d[b][d]+V->d[c][f])-old;
00270 if(s6<minval){ minval=s6; type=6;}
00271 s7=(V->d[a][e]+V->d[c][d]+V->d[b][f])-old;
00272 if(s7<minval){ minval=s7; type=7;}
00273
00274
00275
00276
00277 if(minval + V->route[a_route].length > V->max_route_length )
00278
00279 return false;
00280
00281
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
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)
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
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
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
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];
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];
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
00499
00500
00501 V->route[a_route].length=oldlen+M->savings;
00502 V->total_route_length=oldobj+M->savings;
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
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
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;
00570 V->total_route_length=oldobj+M->savings;
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
00624
00625 a_route= V->route_num[b];
00626 V->route[a_route].length=oldlen+M->savings;
00627 V->total_route_length=oldobj+M->savings;
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
00642 if(a==VRPH_DEPOT && f==VRPH_DEPOT)
00643 {
00644
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