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 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 // First make sure that the routes are in the correct form 00037 // i must be after the VRPH_DEPOT and j must be before the VRPH_DEPOT 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);//new - old 00064 // Lengths and loads are the same since we merged and there is really only one route now 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;// We destroyed a route! 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 // First, evaluate the move 00098 00099 int rules=0; 00100 if(evaluate(V,i_route,j_route, rules, &M)==false) 00101 return false; // the move is not allowed 00102 00103 // Otherwise, it's feasible - make the move 00104 00105 V->update(&M); 00106 00107 // Modify the arrays 00108 00109 // pre_i is what used to be before i 00110 pre_i= V->pred_array[i]; 00111 // post_i is what used to be after i 00112 post_i= V->next_array[i]; 00113 // pre_j is what used to be before j 00114 pre_j= V->pred_array[j]; 00115 // post_j is what used to be after j 00116 post_j= V->next_array[j]; 00117 00118 // i is the start of its own route! 00119 end_i= V->route[i_route].end; 00120 00121 // j is the end of its own route! 00122 start_j= V->route[j_route].start; 00123 00124 // This is the first node in the route that used to follow i 00125 route_after_i= V->next_array[end_i]; 00126 // This is the last node in the route that used to precede i; 00127 route_before_i=pre_i; 00128 00129 // This is the first node in the route that used to precede j 00130 route_before_j= V->pred_array[start_j]; 00131 // This is the first node in the route that used to follow j 00132 route_after_j=post_j; 00133 00134 // 1-i-a-b-c-...-x-1 00135 // and 00136 // 1-aa-bb-...-zz-j-1 00137 // becomes 00138 // 1-aa-bb-...-zz-j-i-a-b-c-...-x-1 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 // Update i_route information 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 // Must have i in first position of its route 00175 // j is the very next route with j in last position 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 // changed! 00180 V->pred_array[VRPH_ABS(post_j)]=-end_i; 00181 } 00182 00183 // So new start is start(j) and new end is end(i) 00184 // Now update the rest of the start and end arrays 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 // Update route information 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