00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00012
00013 #include "VRPH.h"
00014
00015 bool Presert::evaluate(class VRP *V, int u, int i, VRPMove *M)
00016 {
00024
00025 int start_u,end_u, start_i, end_i;
00026 int t,v,h,demand_change, i_load, u_load, i_route, u_route;
00027 double tu, uv, tv, ui, hu, hi, u_loss, i_gain, i_change, i_length, u_length, savings;
00028
00029 if(V->routed[u]==false || V->routed[i]==false)
00030 return false;
00031
00032 if(i==u)
00033 report_error("%s: PRESERT::called with u=i\n",__FUNCTION__);
00034
00035 i_route = V->route_num[i];
00036 u_route = V->route_num[u];
00037
00038 if(V->next_array[u]==i)
00039 {
00040
00041 return false;
00042 }
00043
00044
00045 if(u_route != i_route)
00046 {
00047 if(V->route[i_route].load+V->nodes[u].demand>V->max_veh_capacity)
00048 return false;
00049 }
00050
00051
00052
00053
00054
00055
00056 t=VRPH_MAX(V->pred_array[u],0);
00057 v=VRPH_MAX(V->next_array[u],0);
00058 h=VRPH_MAX(V->pred_array[i],0);
00059
00060 tu= V->d[t][u];
00061 uv= V->d[u][v];
00062 tv= V->d[t][v];
00063 ui= V->d[u][i];
00064 hu= V->d[h][u];
00065 hi= V->d[h][i];
00066
00067 u_loss = tu+uv-tv;
00068 i_gain = ui+hu-hi;
00069
00070
00071 savings = (tv + hu + ui) - (tu + uv + hi);
00072
00073 start_u= V->route[u_route].start;
00074 start_i= V->route[i_route].start;
00075 end_u= V->route[u_route].end;
00076 end_i= V->route[i_route].end;
00077
00078
00079 if(start_u==start_i)
00080 {
00081
00082
00083 demand_change = 0;
00084
00085 i_change = i_gain - u_loss;
00086 i_length = V->route[i_route].length + i_change;
00087 i_load = V->route[i_route].load + demand_change;
00088 u_length = i_length;
00089 u_load = i_load;
00090 }
00091 else
00092 {
00093
00094 i_change = i_gain;
00095 demand_change = V->nodes[u].demand;
00096 i_length = V->route[i_route].length + i_change;
00097 i_load = V->route[i_route].load + demand_change;
00098 u_length = V->route[u_route].length - u_loss;
00099 u_load = V->route[u_route].load - demand_change;
00100 }
00101
00102
00103
00104 if( (i_length > V->max_route_length) || (u_length > V->max_route_length) ||
00105 (i_load > V->max_veh_capacity) || (u_load > V->max_veh_capacity) )
00106 {
00107 return false;
00108 }
00109
00110
00111
00112
00113
00114 if(start_u==end_u)
00115 M->total_number_of_routes = V->total_number_of_routes-1;
00116 else
00117 M->total_number_of_routes = V->total_number_of_routes;
00118
00119 if(u_route==i_route)
00120 {
00121
00122 M->num_affected_routes=1;
00123 M->savings=i_gain-u_loss;
00124 M->route_nums[0]=u_route;
00125 M->route_lens[0]=u_length;
00126 M->route_loads[0]=u_load;
00127 M->route_custs[0]= V->route[u_route].num_customers;
00128 M->new_total_route_length= V->total_route_length+M->savings;
00129 M->move_type=PRESERT;
00130 M->num_arguments=2;
00131 M->move_arguments[0]=u;
00132 M->move_arguments[1]=i;
00133 }
00134 else
00135 {
00136
00137 M->num_affected_routes=2;
00138 M->savings=i_gain-u_loss;
00139 M->route_nums[0]=u_route;
00140 M->route_nums[1]=i_route;
00141 M->route_lens[0]=u_length;
00142 M->route_lens[1]=i_length;
00143 M->route_loads[0]=u_load;
00144 M->route_loads[1]=i_load;
00145 if(u!= V->dummy_index)
00146 {
00147 M->route_custs[0] = V->route[u_route].num_customers-1;
00148 M->route_custs[1]= V->route[i_route].num_customers+1;
00149 }
00150 else
00151 {
00152 M->route_custs[0] = V->route[u_route].num_customers;
00153 M->route_custs[1]= V->route[i_route].num_customers;
00154 }
00155
00156 M->new_total_route_length= V->total_route_length+M->savings;
00157 M->move_type=PRESERT;
00158 M->num_arguments=2;
00159 M->move_arguments[0]=u;
00160 M->move_arguments[1]=i;
00161
00162 }
00163
00164 return true;
00165
00166 }
00167 bool Presert::move(VRP *V, int u, int i)
00168 {
00169
00175
00176 int pre_i, post_i, pre_u, post_u;
00177 int start_u,end_u, start_i, end_i;
00178 int i_route, u_route;
00179 int new_u_start, new_u_end, new_i_start, new_i_end;
00180 VRPMove M;
00181
00182 if(V->next_array[u]==i)
00183 {
00184
00185 return true;
00186 }
00187
00188 if(evaluate(V,u,i, &M)==false)
00189 return false;
00190
00191 #if PRESERT_VERIFY
00192 V->verify_routes("Before presert move\n");
00193 #endif
00194
00195
00196
00197
00198
00199
00200 V->update(&M);
00201
00202
00203
00204 i_route= V->route_num[i];
00205 u_route= V->route_num[u];
00206
00207
00208 pre_i= V->pred_array[i];
00209
00210 post_i= V->next_array[i];
00211
00212 pre_u= V->pred_array[u];
00213
00214 post_u= V->next_array[u];
00215
00216
00217
00218 start_i= V->route[i_route].start;
00219 end_i= V->route[i_route].end;
00220
00221 start_u= V->route[u_route].start;
00222 end_u= V->route[u_route].end;
00223
00224
00225 if(start_i==i)
00226
00227 new_i_start=u;
00228 else
00229 {
00230 if(start_i==u)
00231 new_i_start=post_u;
00232 else
00233 new_i_start=start_i;
00234 }
00235
00236 if(end_i == u)
00237
00238 new_i_end=pre_u;
00239 else
00240 new_i_end=end_i;
00241
00242 if(start_u==u)
00243
00244 new_u_start=post_u;
00245 else
00246 new_u_start=start_u;
00247
00248 if(end_u==u)
00249 new_u_end=pre_u;
00250 else
00251 new_u_end=end_u;
00252
00253
00254
00255
00256
00257 if(pre_i==-u)
00258 {
00259
00260
00261
00262
00263
00264
00265 V->next_array[u]=i;
00266 V->pred_array[i]=u;
00267
00268 V->next_array[VRPH_ABS(pre_u)]=-u;
00269 V->pred_array[u]=-VRPH_ABS(pre_u);
00270
00271
00272 V->route_num[u]=i_route;
00273 V->route[i_route].end=new_i_end;
00274 V->route[i_route].start=new_i_start;
00275
00276
00277
00278
00279 if(start_u==end_u)
00280 return true;
00281
00282
00283
00284 V->route[u_route].end=new_u_end;
00285 V->route[u_route].start=new_u_start;
00286
00287 return true;
00288 }
00289
00290
00291 if(V->next_array[end_i] == -u)
00292 {
00293 V->next_array[end_i] = -VRPH_ABS(post_u);
00294 V->pred_array[VRPH_ABS(post_u)] = -end_i;
00295 V->next_array[u]=i;
00296 V->pred_array[i]=u;
00297 V->pred_array[u]=pre_i;
00298
00299 if(pre_i>0)
00300 V->next_array[pre_i]=u;
00301 else
00302
00303 V->next_array[VRPH_ABS(pre_i)]=-u;
00304
00305
00306 V->route_num[u]=i_route;
00307 V->route[i_route].end=new_i_end;
00308 V->route[i_route].start=new_i_start;
00309
00310
00311
00312 if(start_u==end_u)
00313 return true;
00314
00315
00316
00317 start_u= V->next_array[u];
00318
00319
00320 V->route[u_route].end=new_u_end;
00321 V->route[u_route].start=new_u_start;
00322
00323 return true;
00324
00325 }
00326
00327
00328 V->next_array[u]=i;
00329 V->pred_array[i]=u;
00330 V->pred_array[u]=pre_i;
00331
00332
00333
00334
00335
00336 if(pre_u<=0 || post_u<=0)
00337 {
00338
00339 V->next_array[VRPH_ABS(pre_u)]=-VRPH_ABS(post_u);
00340 V->pred_array[VRPH_ABS(post_u)]=-VRPH_ABS(pre_u);
00341 }
00342 else
00343 {
00344 V->next_array[pre_u]=post_u;
00345 V->pred_array[VRPH_ABS(post_u)]=pre_u;
00346 }
00347
00348
00349
00350
00351 if(pre_i>0)
00352 V->next_array[pre_i]=u;
00353 else
00354
00355 V->next_array[VRPH_ABS(pre_i)]=-u;
00356
00357
00358 V->route_num[u]=i_route;
00359 V->route[i_route].end=new_i_end;
00360 V->route[i_route].start=new_i_start;
00361
00362
00363 if(start_u==end_u)
00364 return true;
00365
00366
00367
00368 if(u==start_u)
00369 {
00370
00371 start_u=VRPH_ABS(post_u);
00372 }
00373 if(u==end_u)
00374 {
00375
00376 end_u=VRPH_ABS(pre_u);
00377 }
00378 if(u_route == i_route)
00379 {
00380 new_u_end=new_i_end;
00381 new_u_start=new_i_start;
00382 }
00383
00384 V->route[u_route].end=new_u_end;
00385 V->route[u_route].start=new_u_start;
00386
00387 return true;
00388
00389 }
00390
00391