00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00012 #include "VRPH.h"
00013
00014
00015
00016 bool Flip::evaluate(class VRP *V, int start_point, int end_point, VRPMove *M)
00017 {
00027
00028 int post_start, pre_end, route_num;
00029 double old_cost, new_cost;
00030 double savings, route_len;
00031
00032
00033 if(start_point==VRPH_DEPOT || end_point==VRPH_DEPOT)
00034 report_error("%s: flip::called with VRPH_DEPOT node-ambiguous\n");
00035
00036 route_num= V->route_num[start_point];
00037
00038 if(V->route_num[end_point]!=route_num)
00039 {
00040 fprintf(stderr,"%d(route #=%d), %d(route #=%d)\n",start_point, route_num,
00041 end_point, V->route_num[end_point]);
00042
00043 report_error("%s: flip attempted using different routes!\n");
00044 }
00045
00046 if(V->next_array[start_point]==end_point)
00047 return false;
00048
00049 post_start= VRPH_MAX(V->next_array[start_point],VRPH_DEPOT);
00050 pre_end= VRPH_MAX(V->pred_array[end_point],VRPH_DEPOT);
00051
00052 if(post_start == pre_end || post_start==end_point || pre_end==start_point)
00053 return false;
00054
00055
00056
00057
00058 old_cost=(V->d[start_point][post_start]-1*V->nodes[post_start].service_time) +
00059 (V->d[pre_end][end_point] - 1*V->nodes[end_point].service_time) ;
00060 new_cost=(V->d[start_point][pre_end]-1*V->nodes[pre_end].service_time) +
00061 (V->d[post_start][end_point] - 1*V->nodes[end_point].service_time);
00062
00063 savings=new_cost - old_cost;
00064
00065
00066
00067 route_len= V->route[route_num].length;
00068
00069
00070 route_len=route_len+savings;
00071
00072 if(route_len>V->max_route_length)
00073 return false;
00074
00075
00076 M->num_affected_routes=1;
00077 M->savings=savings;
00078 M->route_nums[0]=route_num;
00079 M->route_lens[0]=route_len;
00080 M->route_loads[0]=V->route[route_num].load;
00081 M->route_custs[0]= V->route[route_num].num_customers;
00082 M->new_total_route_length= V->total_route_length+savings;
00083 M->total_number_of_routes = V->total_number_of_routes;
00084 M->move_type=FLIP;
00085 M->num_arguments=2;
00086 M->move_arguments[0]=start_point;
00087 M->move_arguments[1]=end_point;
00088
00089
00090 return true;
00091
00092 }
00093
00094 bool Flip::move(VRP *V, int start_point, int end_point)
00095 {
00101
00102 int current, old_next, cnt;
00103 int start, end, i, route_num;
00104 VRPMove M;
00105
00106 if(start_point<=VRPH_DEPOT || end_point<=VRPH_DEPOT )
00107 report_error("%s: flip::reverse_partial_route called with VRPH_DEPOT or negative index\n");
00108
00109 if(start_point==end_point)
00110 report_error("%s: flip::reverse_partial_route called with start==end\n");
00111
00112 route_num= V->route_num[start_point];
00113
00114 if(route_num!= V->route_num[end_point])
00115 report_error("%s: flip::not in the same route\n");
00116
00117
00118 if(evaluate(V,start_point,end_point, &M)==false)
00119 return false;
00120
00121 V->update(&M);
00122
00123
00124
00125 i=0;
00126
00127 start = start_point;
00128 end = end_point;
00129
00130
00131
00132 if(VRPH_MAX(VRPH_DEPOT,V->next_array[start])==end)
00133 {
00134 int pre_start= V->pred_array[start];
00135
00136 if(pre_start<0)
00137 report_error("%s: flip::pre_start <0 in special case!!\n");
00138
00139 old_next= V->next_array[end];
00140
00141 V->next_array[end]=start;
00142 V->pred_array[start]=end;
00143
00144 V->next_array[start]=old_next;
00145 V->pred_array[old_next]=start;
00146
00147 V->next_array[pre_start]=end;
00148 V->pred_array[end]=pre_start;
00149
00150 #if FLIP_VERIFY
00151 V->verify_routes("flip 1\n");
00152 #endif
00153
00154 return true;
00155
00156 }
00157
00158
00159 current= V->next_array[start];
00160 old_next= V->next_array[current];
00161
00162
00163 V->next_array[current]=end;
00164 V->pred_array[end]=current;
00165 V->pred_array[current]=old_next;
00166 current=old_next;
00167 old_next= V->next_array[current];
00168
00169 cnt=0;
00170
00171 while(old_next != end)
00172 {
00173
00174 V->next_array[current] = V->pred_array[current];
00175 V->pred_array[current]=old_next;
00176 current = old_next;
00177 old_next = V->next_array[current];
00178 cnt++;
00179 if(cnt>V->num_nodes)
00180 report_error("%s: flip::Impossible loop encountered\n");
00181
00182 }
00183 V->next_array[current]= V->pred_array[current];
00184 V->pred_array[current]=start;
00185 V->next_array[start]=current;
00186
00187 return true;
00188 }