VRPH
1.0
|
00001 00002 // // 00003 // This file is part of the VRPH software package for // 00004 // generating solutions to vehicle routing problems. // 00005 // VRPH was developed by Chris Groer (cgroer@gmail.com). // 00006 // // 00007 // (c) Copyright 2010 Chris Groer. // 00008 // All Rights Reserved. VRPH is licensed under the // 00009 // Common Public License. See LICENSE file for details. // 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 // We violate some capacity constraint & the move is infeasible 00072 return false; 00073 00074 00075 // else the move is feasible and meets rules - record the move; 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;//none destroyed here 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; // move is infeasible 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 // Now update the start, end, length, and load info for V->route_num[a] and V->route_num[v] 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 // Now update the route_num-looping... 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 // Now we have to update the routes following the modified a and v routes 00225 00226 // Get the new start and end values 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 // Simple case - just switch the two 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 // If we don't change anything here, then the new V->route_num[v] will point to itself! 00280 // To fix this, make the new_v_route point 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 // If we don't change anything here, then the new V->route_num[v] will point to itself! 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 // If we don't change anything here, then the new V->route_num[a] will point to itself! 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 }