00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00012 #include "VRPH.h"
00013
00014 bool MoveString::evaluate(VRP *V, int a, int b, int u, int v, VRPMove *M)
00015 {
00021
00022
00023
00024 if(u==VRPH_DEPOT || v==VRPH_DEPOT || u==v)
00025 {
00026 fprintf(stderr,"(%d,%d,%d,%d)\n",a,b,u,v);
00027 report_error("%s: evaluate called with u or v as VRPH_DEPOT or u==v\n",__FUNCTION__);
00028
00029 }
00030
00031 int t,w;
00032
00033 t=VRPH_MAX(V->pred_array[u],0);
00034 w=VRPH_MAX(V->next_array[v],0);
00035
00036 int a_route, u_route;
00037
00038 u_route = V->route_num[u];
00039 if(u_route!= V->route_num[v])
00040 report_error("%s: u and v not in same route\n",__FUNCTION__);
00041
00042 if(a!=VRPH_DEPOT)
00043 a_route = V->route_num[a];
00044 else
00045 a_route = V->route_num[b];
00046
00047 double tu, vw, ab, au, vb, tw, savings, new_a_len=0, new_u_len=0;
00048 int new_a_load=0, new_u_load=0;
00049
00050 ab= V->d[a][b];
00051 tu= V->d[t][u];
00052 vw= V->d[v][w];
00053 au= V->d[a][u];
00054 vb= V->d[v][b];
00055 tw= V->d[t][w];
00056
00057
00058 savings = (au+vb+tw) - (ab+tu+vw);
00059
00060
00061
00062
00063 VRPSegment S;
00064 V->get_segment_info(u,v,&S);
00065
00066
00067 # if(STRING_DEBUG>1)
00068 printf("STRING::string_len: %f; string_load: %d; string_custs: %d\n",string_len, string_load);
00069 #endif
00070
00071
00072 if(a_route==u_route)
00073 {
00074
00075 new_a_len= V->route[a_route].length + savings;
00076 if(new_a_len > V->max_route_length)
00077 {
00078 # if(STRING_DEBUG>1)
00079 printf("STRING::a_len too long: %f\n",new_a_len);
00080 #endif
00081
00082 return false;
00083 }
00084
00085 M->num_affected_routes=1;
00086 M->route_nums[0]=a_route;
00087 M->savings = savings;
00088 M->route_lens[0]=new_a_len;
00089 M->route_loads[0]=V->route[a_route].load;
00090 M->route_custs[0]= V->route[a_route].num_customers;
00091 M->move_type=MOVE_STRING;
00092 M->num_arguments=4;
00093 M->move_arguments[0]=a;
00094 M->move_arguments[1]=b;
00095 M->move_arguments[2]=u;
00096 M->move_arguments[3]=v;
00097 M->new_total_route_length=V->total_route_length+savings;
00098
00099
00100
00101 return true;
00102
00103
00104 }
00105 else
00106 {
00107
00108 new_a_len = V->route[a_route].length + ( (au+vb+S.len)-ab);
00109 if(new_a_len > V->max_route_length)
00110 {
00111 # if STRING_DEBUG>1
00112 printf("STRING::a_len too long: %f\n",new_a_len);
00113 #endif
00114
00115 return false;
00116 }
00117
00118 new_u_len = V->route[u_route].length + ( (tw)-(tu+vw+S.len) );
00119 if(new_u_len > V->max_route_length)
00120 {
00121 # if(STRING_DEBUG>1)
00122 printf("STRING::u_len too long: %f\n",new_u_len);
00123 #endif
00124
00125 return false;
00126 }
00127
00128
00129
00130 new_a_load = V->route[a_route].load + S.load;
00131 if(new_a_load > V->max_veh_capacity)
00132 {
00133 # if(STRING_DEBUG>1)
00134 printf("STRING::a_load too big: %f\n",new_a_load);
00135 #endif
00136
00137 return false;
00138 }
00139
00140 new_u_load = V->route[u_route].load - S.load;
00141
00142
00143
00144
00145 M->num_affected_routes=2;
00146 M->route_nums[0]=a_route;
00147 M->route_nums[1]=u_route;
00148 M->savings = savings;
00149 M->route_lens[0]=new_a_len;
00150 M->route_lens[1]=new_u_len;
00151 M->route_loads[0]=new_a_load;
00152 M->route_loads[1]=new_u_load;
00153 M->route_custs[0]= V->route[a_route].num_customers+S.num_custs;
00154 M->route_custs[1]= V->route[u_route].num_customers-S.num_custs;
00155 M->new_total_route_length= V->total_route_length+M->savings;
00156 M->move_type=MOVE_STRING;
00157 M->num_arguments=4;
00158 M->move_arguments[0]=a;
00159 M->move_arguments[1]=b;
00160 M->move_arguments[2]=u;
00161 M->move_arguments[3]=v;
00162
00163
00164
00165 if(u== V->route[u_route].start && v== V->route[u_route].end)
00166 {
00167
00168 M->total_number_of_routes = V->total_number_of_routes - 1;
00169 }
00170 else
00171 M->total_number_of_routes= V->total_number_of_routes;
00172
00173
00174 return true;
00175 }
00176
00177 }
00178
00179 bool MoveString::move(VRP *V, int a, int b, int u, int v)
00180 {
00184
00185 VRPMove M;
00186
00187 if(evaluate(V,a,b,u,v, &M)==false)
00188 {
00189 report_error("%s: evaluate is false in MoveString.move\n",__FUNCTION__);
00190
00191 }
00192
00193
00194 if(a!=VRPH_DEPOT)
00195 {
00196
00197 Postsert postsert;
00198
00199 int string[100];
00200 int len=1;
00201 int i;
00202
00203
00204
00205 int current=u;
00206 while(current!=v)
00207 {
00208 current= VRPH_MAX(VRPH_DEPOT,V->next_array[current]);
00209 len++;
00210 }
00211
00212 string[0]=u;
00213 for(i=1;i<len;i++)
00214 {
00215 string[i]= VRPH_MAX(V->next_array[string[i-1]],0);
00216
00217 }
00218
00219
00220 double real_max_len= V->max_route_length;
00221 int real_veh_max= V->max_veh_capacity;
00222
00223 V->max_route_length=VRP_INFINITY;
00224 V->max_veh_capacity=VRP_INFINITY;
00225
00226 postsert.move(V,string[0],a);
00227 for(i=1;i<len;i++)
00228 {
00229 postsert.move(V,string[i],string[i-1]);
00230 }
00231
00232 V->max_route_length=real_max_len;
00233 V->max_veh_capacity=real_veh_max;
00234
00235 #if STRING_DEBUG
00236 printf("Routes after move:\n");
00237 V->show_route(u_route);
00238 V->show_route(V->route_num[a]);
00239
00240 #endif
00241
00242
00243 #if STRING_VERIFY
00244 V->verify_routes("After Postsert move string\n");
00245 #endif
00246 }
00247 else
00248 {
00249
00250 Presert presert;
00251
00252 int next_to_presert=v;
00253 int next_node=b;
00254 int t=VRPH_MAX(V->pred_array[u],0);
00255
00256
00257 double real_max_len= V->max_route_length;
00258 int real_veh_max= V->max_veh_capacity;
00259
00260 V->max_route_length=VRP_INFINITY;
00261 V->max_veh_capacity=VRP_INFINITY;
00262
00263
00264 while(next_to_presert!=t)
00265 {
00266 presert.move(V,next_to_presert,next_node);
00267 next_node=next_to_presert;
00268 next_to_presert= VRPH_MAX(VRPH_DEPOT, V->pred_array[next_to_presert]);
00269
00270 }
00271
00272 V->max_route_length=real_max_len;
00273 V->max_veh_capacity=real_veh_max;
00274
00275
00276
00277
00278 #if STRING_VERIFY
00279 V->verify_routes("After movestring\n");
00280 #endif
00281 }
00282
00283 return true;
00284 }
00285
00286
00287