00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00012
00013 #include "VRPH.h"
00014
00015 bool SwapEnds::evaluate(class VRP *V, int a, int v, VRPMove *M)
00016 {
00017
00025
00026
00027 int load_after_a, load_after_v, new_a_load, new_v_load, added_to_a, added_to_v, n, b, w;
00028 double new_a_len, new_v_len ;
00029 double savings;
00030 VRPSegment Sa, Sv;
00031
00032
00033 if(a==VRPH_DEPOT || v==VRPH_DEPOT)
00034 report_error("%s: Swap ends called with depot; Move doesn't make sense\n",__FUNCTION__);
00035
00036 n = V->num_nodes;
00037
00038
00039 if(V->route_num[a] == V->route_num[v])
00040 {
00041 fprintf(stderr,"a=%d; v=%d; %d==%d!!\n",a,v,V->route_num[a], V->route_num[v]);
00042 report_error("%s: swap ends called with a and v in same route!\n",__FUNCTION__);
00043 }
00044
00045 w = VRPH_MAX(V->next_array[v],0);
00046 b = VRPH_MAX(V->next_array[a],0);
00047
00048 savings = ((V->d[a][w] + V->d[v][b]) - (V->d[a][b] + V->d[v][w]));
00049
00050 V->get_segment_info(VRPH_DEPOT, a, &Sa);
00051 added_to_v= V->route[V->route_num[a]].num_customers-Sa.num_custs;
00052
00053 load_after_a = V->route[V->route_num[a]].load - Sa.load;
00054
00055 V->get_segment_info(VRPH_DEPOT, v, &Sv);
00056 added_to_a=V->route[V->route_num[v]].num_customers-Sv.num_custs;
00057
00058 load_after_v = V->route[V->route_num[v]].load - Sv.load;
00059
00060
00063
00064 new_a_len = Sa.len + V->route[V->route_num[v]].length - Sv.len + V->d[a][w]-V->d[v][w];
00065 new_a_load = Sa.load + load_after_v;
00066 new_v_len = Sv.len + V->route[V->route_num[a]].length - Sa.len + V->d[v][b]-V->d[a][b];
00067 new_v_load = Sv.load + load_after_a;
00068
00069 if(new_a_len > V->max_route_length || new_v_len > V->max_route_length
00070 || new_a_load > V->max_veh_capacity || new_v_load > V->max_veh_capacity )
00071
00072 return false;
00073
00074
00075
00076
00077 M->num_affected_routes=2;
00078 M->route_nums[0]=V->route_num[a];
00079 M->route_nums[1]=V->route_num[v];
00080 M->savings=savings;
00081 M->route_lens[0]=new_a_len;
00082 M->route_lens[1]=new_v_len;
00083 M->route_loads[0]=new_a_load;
00084 M->route_loads[1]=new_v_load;
00085 M->route_custs[0]=V->route[V->route_num[a]].num_customers-added_to_v+added_to_a;
00086 M->route_custs[1]=V->route[V->route_num[v]].num_customers-added_to_a+added_to_v;
00087 M->new_total_route_length= V->total_route_length+M->savings;
00088 M->total_number_of_routes=V->total_number_of_routes;
00089 M->move_type=SWAP_ENDS;
00090 M->num_arguments=2;
00091 M->move_arguments[0]=a;
00092 M->move_arguments[1]=v;
00093
00094
00095 return true;
00096
00097 }
00098
00099 bool SwapEnds::move(VRP *V, int a, int v)
00100 {
00110
00111
00112 VRPMove M;
00113
00114 if(evaluate(V,a,v,&M)==false)
00115 return false;
00116
00117 int current_node, a_start, a_end, v_start, v_end;
00118 int route_after_a, route_before_a, route_before_v, route_after_v;
00119 int n, u, b;
00120
00121
00122 #if SWAP_ENDS_DEBUG>0
00123 printf("Calling swap ends(%d,%d)\n",a,v);
00124 #endif
00125
00126
00127 if(a==VRPH_DEPOT || v==VRPH_DEPOT)
00128 report_error("%s: Swap ends called with depot; Move doesn't make sense\n",__FUNCTION__);
00129
00130
00131 n = V->num_nodes;
00132
00133 if(V->route_num[a] == V->route_num[v])
00134 report_error("%s: swap ends called with a and v in same route!\n",__FUNCTION__);
00135
00136 #if SWAP_VERIFY
00137 V->verify_routes("SWAP_ENDS::prior to move\n");
00138 #endif
00139
00140 V->update(&M);
00141
00142 a_end = V->route[V->route_num[a]].end;
00143 a_start = V->route[V->route_num[a]].start;
00144
00145 route_after_a = V->route_num[-V->next_array[a_end]];
00146 route_before_a = V->route_num[-V->pred_array[a_start]];
00147
00148 v_end = V->route[V->route_num[v]].end;
00149 v_start = V->route[V->route_num[v]].start;
00150
00151 route_after_v = V->route_num[-V->next_array[v_end]];
00152 route_before_v = V->route_num[-V->pred_array[v_start]];
00153
00154 u = V->next_array[v];
00155 b = V->next_array[a];
00156
00157 if(u==VRPH_DEPOT || b==VRPH_DEPOT)
00158 {
00159 report_error("%s: u=0 or b=0 in swap_ends\n",__FUNCTION__);
00160
00161 }
00162
00163 if(u>0 && b>0)
00164 {
00165 V->next_array[a]=u;
00166 V->pred_array[u]=a;
00167 V->next_array[v]=b;
00168 V->pred_array[b]=v;
00169 }
00170 else
00171 {
00172 if(u>0 && b<0)
00173 {
00174 V->next_array[a]=u;
00175 V->pred_array[u]=a;
00176 V->next_array[v]=b;
00177 V->pred_array[-b]=-v;
00178 }
00179 else
00180 {
00181
00182 if(u<0 && b>0)
00183 {
00184 V->next_array[a]=u;
00185 V->pred_array[-u]=-a;
00186 V->next_array[v]=-b;
00187 V->pred_array[b]=v;
00188 }
00189 else
00190 report_error("%s: Reached strange place...\n",__FUNCTION__);
00191 }
00192 }
00193
00194
00195
00196
00197
00198
00199 V->route[V->route_num[a]].start = a_start;
00200 V->route[V->route_num[a]].end = v_end;
00201
00202
00203 V->route[V->route_num[v]].start = v_start;
00204 V->route[V->route_num[v]].end = a_end;
00205
00206
00207
00208 current_node = a;
00209 while(current_node > 0)
00210 {
00211 V->route_num[current_node] = V->route_num[a];
00212 current_node = V->next_array[current_node];
00213
00214 }
00215
00216 current_node = v;
00217 while(current_node > 0)
00218 {
00219 V->route_num[current_node] = V->route_num[v];
00220 current_node = V->next_array[current_node];
00221
00222 }
00223
00224
00225
00226
00227 a_start = V->route[V->route_num[a]].start;
00228 v_start = V->route[V->route_num[v]].start;
00229 a_end = V->route[V->route_num[a]].end;
00230 v_end = V->route[V->route_num[v]].end;
00231
00232
00233 if(route_after_a != V->route_num[v] && route_after_v != V->route_num[a])
00234 {
00235
00236
00237
00238 if(route_after_a != 0 && route_after_v!=0)
00239 {
00240
00241 V->next_array[a_end] = -V->route[route_after_a].start;
00242 V->pred_array[V->route[route_after_a].start] = -a_end;
00243
00244 V->next_array[v_end] = -V->route[route_after_v].start;
00245 V->pred_array[V->route[route_after_v].start] = -v_end;
00246
00247 return true;
00248 }
00249
00250 if(route_after_a == 0)
00251 {
00252 V->next_array[a_end] = VRPH_DEPOT;
00253 V->pred_array[VRPH_DEPOT] = -a_end;
00254
00255 V->next_array[v_end] = -V->route[route_after_v].start;
00256 V->pred_array[V->route[route_after_v].start] = -v_end;
00257
00258
00259 return true;
00260 }
00261
00262 if(route_after_v == 0)
00263 {
00264
00265 V->next_array[v_end] = VRPH_DEPOT;
00266 V->pred_array[VRPH_DEPOT] = -v_end;
00267
00268 V->next_array[a_end] = -V->route[route_after_a].start;
00269
00270 V->pred_array[V->route[route_after_a].start] = -a_end;
00271
00272 return true;
00273 }
00274 }
00275
00276
00277 if(route_after_a == V->route_num[v] && route_after_v == V->route_num[a])
00278 {
00279
00280
00281
00282 V->next_array[a_end] = -v_start;
00283 V->pred_array[v_start] = -a_end;
00284
00285 V->next_array[v_end] = -a_start;
00286 V->pred_array[a_start] = -v_end;
00287
00288 return true;
00289
00290
00291 }
00292
00293
00294 if(route_after_a == V->route_num[v])
00295 {
00296
00297
00298
00299 V->next_array[a_end] = -v_start;
00300 V->pred_array[v_start] = -a_end;
00301
00302 if(route_after_v != VRPH_DEPOT)
00303 {
00304 V->next_array[v_end] = -V->route[route_after_v].start;
00305 V->pred_array[V->route[route_after_v].start] = -v_end;
00306 }
00307 else
00308 {
00309 V->next_array[v_end] = VRPH_DEPOT;
00310 V->pred_array[VRPH_DEPOT] = -v_end;
00311 }
00312
00313 #if SWAP_ENDS_VERIFY
00314 V->verify_routes("SwapEnds 5\n");
00315 #endif
00316
00317 return true;
00318
00319
00320 }
00321
00322 if(route_after_v == V->route_num[a])
00323 {
00324
00325
00326
00327 V->next_array[v_end] = -a_start;
00328 V->pred_array[a_start] = -v_end;
00329
00330 if(route_after_a!=VRPH_DEPOT)
00331 {
00332 V->next_array[a_end] = -V->route[route_after_a].start;
00333 V->pred_array[V->route[route_after_a].start] = -a_end;
00334 }
00335 else
00336 {
00337 V->next_array[a_end] = VRPH_DEPOT;
00338 V->pred_array[VRPH_DEPOT] = -a_end;
00339 }
00340
00341
00342
00343 return true;
00344
00345
00346 }
00347
00348 report_error("%s: should never be here\n",__FUNCTION__);
00349
00350 return false;
00351
00352
00353 }