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