00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00012
00013 #include "VRPH.h"
00014
00015 bool Concatenate::evaluate(VRP *V, int i_route, int j_route, int rules, VRPMove *M)
00016 {
00017
00030
00031
00032 double new_length, i_length, j_length;
00033 int new_load, i_load, j_load;
00034 int i,j;
00035
00036
00037
00038
00039 i= V->route[i_route].start;
00040 j= V->route[j_route].end;
00041
00042
00043 if(VRPH_MAX(V->pred_array[i],0) != VRPH_DEPOT || VRPH_MAX(V->next_array[j],0)!=VRPH_DEPOT)
00044 {
00045 report_error("%s: Concatenate::error in the start/end nodes!\n");
00046 }
00047
00048 i_length = V->route[i_route].length;
00049 j_length = V->route[j_route].length;
00050 i_load = V->route[i_route].load;
00051 j_load = V->route[j_route].load;
00052
00053 new_length = j_length + i_length + V->d[j][i] - (V->d[VRPH_DEPOT][i] +
00054 V->d[j][VRPH_DEPOT]);
00055
00056 new_load = i_load + j_load;
00057
00058
00059
00060 M->num_affected_routes=2;
00061 M->route_nums[0]=i_route;
00062 M->route_nums[1]=j_route;
00063 M->savings = new_length - (i_length+j_length);
00064
00065 M->route_lens[0]=new_length;
00066 M->route_lens[1]=0;
00067 M->route_loads[0]=new_load;
00068 M->route_loads[1]=0;
00069 M->route_custs[0]= V->route[i_route].num_customers+V->route[j_route].num_customers;
00070 M->route_custs[1]=0;
00071 M->new_total_route_length= V->total_route_length+M->savings;
00072 M->total_number_of_routes= V->total_number_of_routes-1;
00073 M->move_type=CONCATENATE;
00074 M->num_arguments=2;
00075 M->move_arguments[0]=i_route;
00076 M->move_arguments[1]=j_route;
00077
00078 if(V->is_feasible(M, rules)==true)
00079 return true;
00080 else
00081 return false;
00082
00083 }
00084
00085 bool Concatenate::move(VRP *V, int i_route, int j_route)
00086 {
00090
00091 VRPMove M;
00092 int i,j, pre_i, pre_j, post_i, post_j, end_i, start_j, route_after_i,
00093 route_after_j, route_before_i, route_before_j, current_node, next_node;
00094
00095 i= V->route[i_route].start;
00096 j= V->route[j_route].end;
00097
00098
00099 int rules=0;
00100 if(evaluate(V,i_route,j_route, rules, &M)==false)
00101 return false;
00102
00103
00104
00105 V->update(&M);
00106
00107
00108
00109
00110 pre_i= V->pred_array[i];
00111
00112 post_i= V->next_array[i];
00113
00114 pre_j= V->pred_array[j];
00115
00116 post_j= V->next_array[j];
00117
00118
00119 end_i= V->route[i_route].end;
00120
00121
00122 start_j= V->route[j_route].start;
00123
00124
00125 route_after_i= V->next_array[end_i];
00126
00127 route_before_i=pre_i;
00128
00129
00130 route_before_j= V->pred_array[start_j];
00131
00132 route_after_j=post_j;
00133
00134
00135
00136
00137
00138
00139
00140 V->next_array[j]=i;
00141 V->pred_array[i]=j;
00142
00143 if(VRPH_ABS(route_after_j)==i)
00144 {
00145 current_node=start_j;
00146 while( (next_node= V->next_array[current_node]) > 0)
00147 {
00148 V->route_num[current_node]=i_route;
00149
00150 current_node=next_node;
00151 }
00152
00153 V->route_num[current_node]=i_route;
00154
00155 V->route[i_route].end=end_i;
00156 V->route[i_route].start=start_j;
00157
00158 #if CONCATENATE_VERIFY
00159 V->verify_routes("Concatenate 1\n");
00160 #endif
00161
00162 return true;
00163 }
00164
00165 if(VRPH_ABS(route_after_i)!=start_j)
00166 {
00167 V->next_array[VRPH_ABS(route_before_i)]=route_after_i;
00168 V->pred_array[VRPH_ABS(route_after_i)]=route_before_i;
00169 V->next_array[VRPH_ABS(end_i)]=route_after_j;
00170 V->pred_array[VRPH_ABS(route_after_j)]=-end_i;
00171 }
00172 else
00173 {
00174
00175
00176 V->next_array[VRPH_ABS(route_before_i)]=-start_j;
00177 V->pred_array[VRPH_ABS(start_j)]=route_before_i;
00178 V->next_array[VRPH_ABS(end_i)]=post_j;
00179
00180 V->pred_array[VRPH_ABS(post_j)]=-end_i;
00181 }
00182
00183
00184
00185 current_node=start_j;
00186 while( (next_node= V->next_array[current_node]) > 0)
00187 {
00188 V->route_num[current_node]=i_route;
00189 current_node=next_node;
00190 }
00191
00192 V->route_num[current_node]=i_route;
00193
00194 V->route[i_route].end=end_i;
00195 V->route[i_route].start=start_j;
00196
00197
00198
00199 #if CONCATENATE_VERIFY
00200 V->verify_routes("CWConcatenate 2\n");
00201 #endif
00202
00203 return true;
00204
00205 }
00206
00207