00001
00002
00003
00004
00005
00006
00007
00008
00009
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
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;
00035 int j1, j2, l1, l2;
00036
00037 VRPMove M, BestM;
00038
00039 BestM.savings=VRP_INFINITY;
00040
00041 int accept_type;
00042
00043
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
00054 if(V->route[r1].num_customers < 4 || V->route[r2].num_customers < 4)
00055
00056 return false;
00057
00058 int *old_sol=NULL;
00059 if(rules & VRPH_TABU)
00060 {
00061
00062 old_sol=new int[V->num_original_nodes+2];
00063 V->export_solution_buff(old_sol);
00064 }
00065
00066
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;
00080 i2 = V->next_array[i1];
00081
00082 while(i2 != end_i)
00083 {
00084
00085
00086
00087 k1 = V->next_array[i2];
00088
00089
00090 if(k1==end_1)
00091 break;
00092
00093 k2 = V->next_array[k1];
00094 while(k2 != end_1)
00095 {
00096
00097
00098
00099
00100 j1 = start_2;
00101 j2 = V->next_array[j1];
00102
00103 while(j2 != end_j)
00104 {
00105
00106
00107
00108
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
00119
00120
00121
00122 if(this->evaluate(V,i1,i2,k1,k2,j1,j2,l1,l2,rules,&M) == true)
00123 {
00124
00125
00126 if(accept_type == VRPH_FIRST_ACCEPT || (accept_type==VRPH_LI_ACCEPT && M.savings<-VRPH_EPSILON) )
00127 {
00128
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
00139
00140 if(V->check_tabu_status(&M, old_sol))
00141 {
00142 delete [] old_sol;
00143 return true;
00144 }
00145
00146 }
00147 }
00148 }
00149
00150
00151 if(accept_type == VRPH_LI_ACCEPT || accept_type == VRPH_BEST_ACCEPT)
00152 {
00153
00154 if(M.is_better(V, &BestM, rules))
00155 BestM=M;
00156
00157 }
00158
00159 }
00160
00161
00162
00163 l1 = l2;
00164 l2 = V->next_array[l1];
00165
00166 }
00167
00168
00169
00170
00171 j1 = j2;
00172 j2= V->next_array[j1];
00173
00174 }
00175
00176
00177
00178 k1 = k2;
00179 k2 = V->next_array[k1];
00180
00181 }
00182
00183
00184
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;
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
00217
00218 if(V->check_tabu_status(&BestM, old_sol))
00219 {
00220 delete [] old_sol;
00221 return true;
00222 }
00223
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
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
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
00265 if(V->check_savings(M,rules)==false)
00266 return false;
00267
00268
00269
00270
00271
00272
00273
00274
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
00289
00290 double new_i_len, new_j_len;
00291
00292
00293
00294
00295
00296
00297
00298
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
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
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