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 #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 //Check for VRPH_DEPOT nodes! 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; // Nothing to reverse! 00054 00055 00056 // Need to compute the old costs and the new cost - 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 // The move satisfies the savings rules - now check feasibility... 00066 00067 route_len= V->route[route_num].length; 00068 00069 // Check feasibility 00070 route_len=route_len+savings; 00071 00072 if(route_len>V->max_route_length) 00073 return false; // infeasible 00074 00075 // Otherwise it's feasible since no load change occurs 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; // no change 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 // evaluate the move 00118 if(evaluate(V,start_point,end_point, &M)==false) 00119 return false; 00120 00121 V->update(&M); 00122 00123 // Now update the arrays 00124 00125 i=0; 00126 00127 start = start_point; 00128 end = end_point; 00129 // Assume the orientation is correct to avoid checking again!! 00130 00131 // Special case! next(start) = end 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 // Otherwise we have only a single case to handle 00159 current= V->next_array[start]; //n1 00160 old_next= V->next_array[current]; //n2 00161 00162 00163 V->next_array[current]=end; //next[n1]=end 00164 V->pred_array[end]=current; //pred[end]=n1; 00165 V->pred_array[current]=old_next; //pred[n1]=n2; 00166 current=old_next; //current=n2 00167 old_next= V->next_array[current]; //old_next=n3 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 }