00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00012
00013 #include "VRPH.h"
00014
00015 double VRP::RTR_solve(int heuristics, int intensity, int max_stuck, int max_perturbs,
00016 double dev, int nlist_size, int perturb_type, int accept_type, bool verbose)
00017 {
00025
00026
00027
00028
00029 if(accept_type!=VRPH_BEST_ACCEPT && accept_type!=VRPH_FIRST_ACCEPT)
00030 report_error("%s: accept_type must be VRPH_BEST_ACCEPT or VRPH_FIRST_ACCEPT\n");
00031
00032 int ctr, n, j, i, R, random, fixed, neighbor_list, objective, tabu;
00033
00034 random=fixed=neighbor_list=0;
00035
00036 if(heuristics & VRPH_RANDOMIZED)
00037 random=VRPH_RANDOMIZED;
00038
00039 if(heuristics & VRPH_FIXED_EDGES)
00040 fixed=VRPH_FIXED_EDGES;
00041
00042 if(heuristics & VRPH_USE_NEIGHBOR_LIST)
00043 neighbor_list=VRPH_USE_NEIGHBOR_LIST;
00044
00045 objective=VRPH_SAVINGS_ONLY;
00046
00047
00048 if(heuristics & VRPH_MINIMIZE_NUM_ROUTES)
00049 objective=VRPH_MINIMIZE_NUM_ROUTES;
00050
00051
00052 if(heuristics & VRPH_TABU)
00053 {
00054 tabu=VRPH_TABU;
00055
00056 this->tabu_list->empty();
00057 }
00058 else
00059 tabu=0;
00060
00061 n=num_nodes;
00062
00063
00064
00065 OnePointMove OPM;
00066 TwoPointMove TPM;
00067 TwoOpt TO;
00068 OrOpt OR;
00069 ThreeOpt ThreeO;
00070 CrossExchange CE;
00071 ThreePointMove ThreePM;
00072
00073 double start_val;
00074 int *perm;
00075 perm=new int[this->num_nodes];
00076
00077
00078 j=VRPH_ABS(this->next_array[VRPH_DEPOT]);
00079 for(i=0;i<this->num_nodes;i++)
00080 {
00081 perm[i]=j;
00082 if(!routed[j])
00083 report_error("%s: Unrouted node in solution!!\n");
00084
00085 j=VRPH_ABS(this->next_array[j]);
00086 }
00087 if(j!=VRPH_DEPOT)
00088 report_error("%s: VRPH_DEPOT is not last node in solution!!\n");
00089
00090
00091 int rules;
00092
00093
00094 neighbor_list_size=VRPH_MIN(nlist_size, this->num_nodes);
00095
00096
00097 deviation=dev;
00098
00099 int num_perturbs=0;
00100
00101 record=this->total_route_length;
00102 this->best_total_route_length=this->total_route_length;
00103 this->export_solution_buff(this->current_sol_buff);
00104 this->export_solution_buff(this->best_sol_buff);
00105
00106 normalize_route_numbers();
00107
00108 ctr=0;
00109
00110
00111 uphill:
00112
00113 double beginning_best=this->best_total_route_length;
00114 rules=VRPH_LI_ACCEPT+VRPH_RECORD_TO_RECORD+objective+random+fixed+neighbor_list+tabu;
00115
00116 if(verbose)
00117 printf("Uphill starting at %5.2f\n",this->total_route_length);
00118
00119 for(int k=1;k<intensity;k++)
00120 {
00121 start_val=total_route_length;
00122
00123 if(heuristics & ONE_POINT_MOVE)
00124 {
00125 if(random)
00126 random_permutation(perm, this->num_nodes);
00127
00128 for(i=1;i<=n;i++)
00129 {
00130 #if FIXED_DEBUG
00131 if(fixed && !check_fixed_edges("Before 1PM\n"))
00132 fprintf(stderr,"Error before OPM search(%d)\n",perm[i-1]);
00133 #endif
00134 OPM.search(this,perm[i-1],rules);
00135
00136 #if FIXED_DEBUG
00137 if(fixed && !check_fixed_edges("After 1PM\n"))
00138 {
00139 fprintf(stderr,"Error after OPM search(%d)\n",perm[i-1]);
00140 this->show_route(this->route_num[perm[i-1]]);
00141 }
00142 #endif
00143 }
00144 }
00145
00146
00147 if(heuristics & TWO_POINT_MOVE)
00148 {
00149 if(random)
00150 random_permutation(perm, this->num_nodes);
00151
00152 for(i=1;i<=n;i++)
00153 TPM.search(this,perm[i-1],rules + VRPH_INTER_ROUTE_ONLY);
00154
00155
00156
00157 }
00158
00159
00160 if(heuristics & THREE_POINT_MOVE)
00161 {
00162 if(random)
00163 random_permutation(perm, this->num_nodes);
00164
00165 for(i=1;i<=n;i++)
00166 ThreePM.search(this,perm[i-1],rules + VRPH_INTER_ROUTE_ONLY);
00167
00168
00169
00170 }
00171
00172
00173
00174 if(heuristics & TWO_OPT)
00175 {
00176 if(random)
00177 random_permutation(perm, this->num_nodes);
00178
00179 for(i=1;i<=n;i++)
00180 TO.search(this,perm[i-1],rules);
00181
00182
00183
00184
00185 }
00186
00187
00188 if(heuristics & OR_OPT)
00189 {
00190 if(random)
00191 random_permutation(perm, this->num_nodes);
00192
00193 for(i=1;i<=n;i++)
00194 OR.search(this,perm[i-1],4,rules);
00195
00196 for(i=1;i<=n;i++)
00197 OR.search(this,perm[i-1],3,rules);
00198
00199 for(i=1;i<=n;i++)
00200 OR.search(this,perm[i-1],2,rules);
00201
00202
00203
00204 }
00205
00206 if(heuristics & THREE_OPT)
00207 {
00208 normalize_route_numbers();
00209 R=total_number_of_routes;
00210
00211 for(i=1; i<=R; i++)
00212 ThreeO.route_search(this,i,rules-neighbor_list);
00213
00214
00215
00216 }
00217
00218 if(heuristics & CROSS_EXCHANGE)
00219 {
00220 normalize_route_numbers();
00221 this->find_neighboring_routes();
00222 R=total_number_of_routes;
00223
00224 for(i=1; i<=R-1; i++)
00225 {
00226 for(j=0;j<1;j++)
00227 CE.route_search(this,i, route[i].neighboring_routes[j],rules-neighbor_list);
00228 }
00229
00230
00231 }
00232 }
00233
00234 if(total_route_length<record)
00235 record = total_route_length;
00236
00237 if(verbose)
00238 {
00239 printf("Uphill complete\t(%d,%5.2f,%5.2f)\n",count_num_routes(),total_route_length, record);
00240 printf("# of recorded routes: %d[%d]\n",total_number_of_routes,count_num_routes());
00241
00242 }
00243
00244 if(this->best_total_route_length<beginning_best-VRPH_EPSILON)
00245 {
00246 if(verbose)
00247 printf("New best found in uphill!\n");
00248
00249
00250
00251
00252
00253 }
00254
00255 downhill:
00256
00257
00258 double orig_val=total_route_length;
00259 if(verbose)
00260 printf("Downhill starting at %f (best=%f)\n",orig_val,this->best_total_route_length);
00261
00262
00263 if((heuristics & ONE_POINT_MOVE)|| (heuristics & KITCHEN_SINK) )
00264 {
00265 rules=VRPH_DOWNHILL+objective+random+fixed+neighbor_list+accept_type;
00266 for(;;)
00267 {
00268
00269 start_val=total_route_length;
00270
00271 if(random)
00272 random_permutation(perm, this->num_nodes);
00273
00274 for(i=1;i<=n;i++)
00275 OPM.search(this,perm[i-1],rules );
00276
00277
00278 if(VRPH_ABS(total_route_length-start_val)<VRPH_EPSILON)
00279 break;
00280
00281 }
00282
00283 }
00284
00285
00286
00287 if((heuristics & TWO_POINT_MOVE) || (heuristics & KITCHEN_SINK) )
00288 {
00289 rules=VRPH_DOWNHILL+VRPH_INTER_ROUTE_ONLY+objective+random+fixed+neighbor_list+accept_type;
00290 for(;;)
00291 {
00292
00293 start_val=total_route_length;
00294
00295 if(random)
00296 random_permutation(perm, this->num_nodes);
00297
00298 for(i=1;i<=n;i++)
00299 TPM.search(this,perm[i-1],rules);
00300
00301 if(VRPH_ABS(total_route_length-start_val)<VRPH_EPSILON)
00302 break;
00303
00304 }
00305
00306 }
00307
00308
00309
00310 if((heuristics & TWO_OPT)|| (heuristics & KITCHEN_SINK) )
00311 {
00312
00313 rules=VRPH_DOWNHILL+VRPH_INTER_ROUTE_ONLY+objective+random+fixed+neighbor_list+accept_type;
00314 for(;;)
00315 {
00316
00317 start_val=total_route_length;
00318
00319 if(random)
00320 random_permutation(perm, this->num_nodes);
00321
00322 for(i=1;i<=n;i++)
00323 TO.search(this,perm[i-1],rules);
00324
00325 if(VRPH_ABS(total_route_length-start_val)<VRPH_EPSILON)
00326 break;
00327 }
00328
00329
00330 rules=VRPH_DOWNHILL+objective+random+fixed+neighbor_list+accept_type;
00331
00332 for(;;)
00333 {
00334
00335 start_val=total_route_length;
00336
00337 if(random)
00338 random_permutation(perm, this->num_nodes);
00339
00340 for(i=1;i<=n;i++)
00341 TO.search(this,perm[i-1],rules);
00342
00343 if(VRPH_ABS(total_route_length-start_val)<VRPH_EPSILON)
00344 break;
00345 }
00346 }
00347
00348 if((heuristics & THREE_POINT_MOVE) || (heuristics & KITCHEN_SINK) )
00349 {
00350 rules=VRPH_DOWNHILL+VRPH_INTER_ROUTE_ONLY+objective+random+fixed+accept_type+neighbor_list;
00351 for(;;)
00352 {
00353
00354 start_val=total_route_length;
00355
00356 if(random)
00357 random_permutation(perm, this->num_nodes);
00358
00359 for(i=1;i<=n;i++)
00360 ThreePM.search(this,perm[i-1],rules);
00361
00362 if(VRPH_ABS(total_route_length-start_val)<VRPH_EPSILON)
00363 break;
00364
00365 }
00366 }
00367
00368
00369 if((heuristics & OR_OPT) || (heuristics & KITCHEN_SINK))
00370 {
00371
00372 rules=VRPH_DOWNHILL+ objective +random +fixed + accept_type + neighbor_list;
00373
00374 for(;;)
00375 {
00376
00377 start_val=total_route_length;
00378 if(random)
00379 random_permutation(perm, this->num_nodes);
00380
00381 for(i=1;i<=n;i++)
00382 OR.search(this,perm[i-1],4,rules);
00383 for(i=1;i<=n;i++)
00384 OR.search(this,perm[i-1],3,rules);
00385 for(i=1;i<=n;i++)
00386 OR.search(this,perm[i-1],2,rules);
00387
00388
00389 if(VRPH_ABS(total_route_length-start_val)<VRPH_EPSILON)
00390 break;
00391 }
00392 }
00393
00394 if((heuristics & THREE_OPT) || (heuristics & KITCHEN_SINK) )
00395 {
00396 normalize_route_numbers();
00397 R= total_number_of_routes;
00398 rules=VRPH_DOWNHILL+objective+VRPH_INTRA_ROUTE_ONLY+ random +fixed + accept_type;
00399 for(;;)
00400 {
00401
00402 start_val=total_route_length;
00403
00404 for(i=1;i<=R;i++)
00405 ThreeO.route_search(this,i,rules);
00406
00407 if(VRPH_ABS(total_route_length-start_val)<VRPH_EPSILON)
00408 break;
00409 }
00410 }
00411
00412
00413 if( (heuristics & CROSS_EXCHANGE) )
00414 {
00415 normalize_route_numbers();
00416 this->find_neighboring_routes();
00417 R=total_number_of_routes;
00418
00419 rules=VRPH_DOWNHILL+objective+VRPH_INTRA_ROUTE_ONLY+ random +fixed + accept_type;
00420
00421 for(i=1; i<=R-1; i++)
00422 {
00423 for(j=0;j<=1;j++)
00424 CE.route_search(this,i, route[i].neighboring_routes[j], rules);
00425 }
00426 }
00427
00428
00429
00430 if(total_route_length<orig_val-VRPH_EPSILON)
00431 goto downhill;
00432 if(verbose)
00433 printf("Downhill complete: %5.2f[downhill started at %f] (%5.2f)\n",total_route_length,orig_val,
00434 this->best_total_route_length);
00435
00436
00437 if(total_route_length < record-VRPH_EPSILON)
00438 {
00439
00440 ctr=1;
00441 record=total_route_length;
00442 }
00443 else
00444 ctr++;
00445
00446 if(ctr<max_stuck)
00447 goto uphill;
00448
00449 if(ctr==max_stuck)
00450 {
00451 if(num_perturbs<max_perturbs)
00452 {
00453 if(verbose)
00454 printf("perturbing\n");
00455 if(perturb_type==VRPH_LI_PERTURB)
00456 perturb();
00457 else
00458 osman_perturb(VRPH_MAX(20,num_nodes/10),.5+lcgrand(20));
00459
00460
00461 this->record=this->total_route_length;
00462 if(tabu)
00463 this->tabu_list->empty();
00464
00465 ctr=1;
00466 num_perturbs++;
00467 goto uphill;
00468 }
00469 }
00470
00471
00472 if(verbose)
00473 {
00474 if(has_service_times==false)
00475 printf("BEST OBJ: %f\n",best_total_route_length);
00476 else
00477 printf("BEST OBJ: %f\n",best_total_route_length-total_service_time);
00478 }
00479
00480 delete [] perm;
00481
00482
00483 this->import_solution_buff(best_sol_buff);
00484
00485 if(has_service_times==false)
00486 return best_total_route_length;
00487 else
00488 return best_total_route_length-total_service_time;
00489
00490
00491 }
00492
00493 double VRP::SA_solve(int heuristics, double start_temp, double cool_ratio,
00494 int iters_per_loop, int num_loops, int nlist_size, bool verbose)
00495 {
00501
00502 this->temperature = start_temp;
00503 this->cooling_ratio = cool_ratio;
00504
00505 int ctr, n, j, i, R, rules, random, fixed, neighbor_list, objective;
00506
00507 if(heuristics & VRPH_RANDOMIZED)
00508 random=VRPH_RANDOMIZED;
00509 else
00510 random=0;
00511
00512 if(heuristics & VRPH_FIXED_EDGES)
00513 fixed=VRPH_FIXED_EDGES;
00514 else
00515 fixed=0;
00516
00517 if(heuristics & VRPH_USE_NEIGHBOR_LIST)
00518 neighbor_list=VRPH_USE_NEIGHBOR_LIST;
00519 else
00520 neighbor_list=0;
00521
00522 objective=VRPH_SAVINGS_ONLY;
00523
00524
00525 if(heuristics & VRPH_MINIMIZE_NUM_ROUTES)
00526 objective=VRPH_MINIMIZE_NUM_ROUTES;
00527
00528 n=num_nodes;
00529
00530
00531 int *perm;
00532 perm=new int[this->num_nodes];
00533 j=VRPH_ABS(this->next_array[VRPH_DEPOT]);
00534 for(i=0;i<this->num_nodes;i++)
00535 {
00536 perm[i]=j;
00537 if(!routed[j])
00538 report_error("%s: Unrouted node in solution!!\n");
00539
00540 j=VRPH_ABS(this->next_array[j]);
00541 }
00542 if(j!=VRPH_DEPOT)
00543 report_error("%s: VRPH_DEPOT is not last node in solution!!\n");
00544
00545
00546
00547 OnePointMove OPM;
00548 TwoPointMove TPM;
00549 TwoOpt TO;
00550 OrOpt OR;
00551 ThreeOpt ThreeO;
00552 CrossExchange CE;
00553 ThreePointMove ThreePM;
00554
00555 double start_val;
00556
00557 this->export_solution_buff(this->best_sol_buff);
00558
00559
00560
00561 this->neighbor_list_size=VRPH_MIN(nlist_size, num_nodes);
00562
00563 best_total_route_length=this->total_route_length;
00564 normalize_route_numbers();
00565
00566 ctr=0;
00567
00568
00569
00570
00571
00572 rules=VRPH_USE_NEIGHBOR_LIST+VRPH_FIRST_ACCEPT+VRPH_SIMULATED_ANNEALING+VRPH_SAVINGS_ONLY;
00573
00574 double worst_obj=0;
00575 for(ctr=0;ctr<num_loops;ctr++)
00576 {
00577 if(verbose)
00578 {
00579 printf("\nctr=%d of %d, temp=%f, obj=%f (overall best=%f; worst=%f)\n",ctr,num_loops,
00580 this->temperature,
00581 this->total_route_length,this->best_total_route_length,worst_obj);
00582 fflush(stdout);
00583 }
00584
00585 worst_obj=0;
00586
00587
00588 this->temperature = this->cooling_ratio * this->temperature;
00589
00590
00591 for(int k=0; k < iters_per_loop; k++)
00592 {
00593 start_val=total_route_length;
00594 if(heuristics & THREE_OPT)
00595 {
00596 rules=VRPH_SIMULATED_ANNEALING+VRPH_INTRA_ROUTE_ONLY+random+fixed+objective;
00597 normalize_route_numbers();
00598 R=total_number_of_routes;
00599 for(i=1; i<=R; i++)
00600 {
00601 ThreeO.route_search(this,i,rules);
00602 if(this->total_route_length > worst_obj)
00603 worst_obj=this->total_route_length;
00604 }
00605
00606 }
00607
00608
00609 if(heuristics & ONE_POINT_MOVE)
00610 {
00611 rules=VRPH_SIMULATED_ANNEALING+neighbor_list+random+fixed+objective;
00612 if(random)
00613 random_permutation(perm, this->num_nodes);
00614
00615 for(i=1;i<=n;i++)
00616 {
00617
00618 OPM.search(this,perm[i-1],rules);
00619 if(this->total_route_length > worst_obj)
00620 worst_obj=this->total_route_length;
00621 }
00622
00623 }
00624
00625
00626
00627 if(heuristics & TWO_POINT_MOVE)
00628 {
00629 rules=VRPH_SIMULATED_ANNEALING+neighbor_list+random+fixed+objective;
00630 if(random)
00631 random_permutation(perm, this->num_nodes);
00632
00633 for(i=1;i<=n;i++)
00634 {
00635 TPM.search(this,perm[i-1],rules);
00636 if(this->total_route_length > worst_obj)
00637 worst_obj=this->total_route_length;
00638 }
00639
00640
00641 }
00642
00643
00644
00645 if(heuristics & TWO_OPT)
00646 {
00647
00648 rules=VRPH_SIMULATED_ANNEALING+neighbor_list+random+fixed+objective;
00649 if(random)
00650 random_permutation(perm, this->num_nodes);
00651
00652 for(i=1;i<=n;i++)
00653 {
00654 TO.search(this,perm[i-1],rules);
00655 if(this->total_route_length > worst_obj)
00656 worst_obj=this->total_route_length;
00657 }
00658
00659
00660 }
00661
00662 if(heuristics & THREE_POINT_MOVE)
00663 {
00664 rules=VRPH_SIMULATED_ANNEALING+VRPH_INTER_ROUTE_ONLY+neighbor_list+random+fixed+objective;
00665 if(random)
00666 random_permutation(perm, this->num_nodes);
00667
00668
00669 for(i=1;i<=n;i++)
00670 {
00671 ThreePM.search(this,perm[i-1],rules);
00672 if(this->total_route_length > worst_obj)
00673 worst_obj=this->total_route_length;
00674 }
00675 }
00676
00677 if(heuristics & OR_OPT)
00678 {
00679 rules=VRPH_SIMULATED_ANNEALING+neighbor_list+random+fixed+objective;
00680 if(random)
00681 random_permutation(perm, this->num_nodes);
00682
00683 for(i=1;i<=n;i++)
00684 {
00685 OR.search(this,perm[i-1],3,rules);
00686 if(this->total_route_length > worst_obj)
00687 worst_obj=this->total_route_length;
00688 }
00689
00690 for(i=1;i<=n;i++)
00691 {
00692 OR.search(this,perm[i-1],2,rules);
00693 if(this->total_route_length > worst_obj)
00694 worst_obj=this->total_route_length;
00695 }
00696
00697
00698 }
00699
00700 if(heuristics & CROSS_EXCHANGE)
00701 {
00702 normalize_route_numbers();
00703 this->find_neighboring_routes();
00704 R=total_number_of_routes;
00705 rules=VRPH_SIMULATED_ANNEALING+fixed+objective;
00706 if(random)
00707 random_permutation(perm, this->num_nodes);
00708
00709
00710 for(i=1; i<=R-1; i++)
00711 {
00712 for(j=0;j<=1;j++)
00713 {
00714 CE.route_search(this,i, route[i].neighboring_routes[j],rules);
00715 if(this->total_route_length > worst_obj)
00716 worst_obj=this->total_route_length;
00717 }
00718 }
00719 }
00720 }
00721 }
00722
00723 delete [] perm;
00724
00725
00726 this->import_solution_buff(this->best_sol_buff);
00727
00728
00729 if(has_service_times==false)
00730 return this->best_total_route_length;
00731 else
00732 return this->best_total_route_length-total_service_time;
00733
00734 }
00735
00736