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 #include <stdarg.h> 00015 00016 void VRP::show_next_array() 00017 { 00021 int i,n; 00022 00023 n= num_original_nodes; 00024 00025 printf("Next Array:\n"); 00026 for(i=0;i<=n;i++) 00027 printf("%03d -> %03d\n",i,next_array[i]); 00028 00029 return; 00030 } 00031 00032 void VRP::show_pred_array() 00033 { 00037 00038 int i,n; 00039 00040 n= num_original_nodes; 00041 printf("Pred Array:\n"); 00042 00043 for(i=0;i<=n;i++) 00044 printf("%03d -> %03d\n",i,pred_array[i]); 00045 00046 00047 return; 00048 } 00049 00050 bool VRP::verify_routes(const char *message) 00051 { 00058 00059 int i, n, cnt; 00060 double len=0; 00061 double rlen=0; 00062 double tot_len=0; 00063 int next_node; 00064 int current_node, current_route, route_start, flag, current_start, current_end; 00065 int total_load = 0; 00066 int current_load = 0; 00067 int num_in_route=0; 00068 int counted_routes=0; 00069 00070 00071 // First check the pred/next arrays for consistency 00072 current_node=VRPH_DEPOT; 00073 next_node=VRPH_ABS(this->next_array[current_node]); 00074 while(next_node!=VRPH_DEPOT) 00075 { 00076 if(VRPH_ABS(this->pred_array[next_node])!=current_node) 00077 { 00078 fprintf(stderr,"%d->%d??\nNext: %d->%d\nPred:%d->%d",current_node,next_node, 00079 current_node,this->next_array[current_node],next_node,this->pred_array[next_node]); 00080 00081 report_error("%s: Next/pred inconsistency\n",__FUNCTION__); 00082 } 00083 current_node=next_node; 00084 next_node=VRPH_ABS(this->next_array[current_node]); 00085 } 00086 00087 if(VRPH_ABS(this->pred_array[next_node])!=current_node) 00088 { 00089 fprintf(stderr,"%d->%d??\nNext: %d->%d\nPred:%d->%d",current_node,next_node, 00090 current_node,this->next_array[current_node],next_node,this->pred_array[next_node]); 00091 00092 report_error("%s: Next/pred inconsistency\n",__FUNCTION__); 00093 } 00094 00095 n=num_nodes; 00096 // Only consider the nodes in the solution! 00097 00098 flag=0; 00099 i = 1; 00100 cnt = 0; 00101 route_start = -next_array[VRPH_DEPOT]; 00102 if(route_start < 0) 00103 { 00104 fprintf(stderr,"next[VRPH_DEPOT] is incorrect\n"); 00105 report_error(message,__FUNCTION__); 00106 00107 } 00108 00109 current_node = route_start; 00110 current_route = route_num[current_node]; 00111 current_start = route[current_route].start; 00112 current_end = route[current_route].end; 00113 counted_routes++; 00114 00115 if(route_start != current_start) 00116 { 00117 fprintf(stderr,"Error in initial route start: %d != %d\n",route_start, current_start); 00118 report_error(message,__FUNCTION__); 00119 } 00120 00121 00122 00123 total_load+=nodes[current_node].demand; 00124 current_load+=nodes[current_node].demand; 00125 len+=d[VRPH_DEPOT][current_node]; 00126 rlen+=d[VRPH_DEPOT][current_node]; 00127 if(current_node!= dummy_index) 00128 num_in_route++; 00129 00130 while(route_start != 0 && i<num_nodes+1) 00131 { 00132 // When we finally get a route beginning at 0, this is the last route 00133 // and there is no next route, so break out 00134 00135 if(next_array[current_node]==current_node) 00136 { 00137 // We've entered a loop 00138 fprintf(stderr,"Self loop found in next array(%d)\n",current_node); 00139 report_error("%s: Self loop!\n",__FUNCTION__); 00140 } 00141 00142 if(next_array[current_node]==VRPH_DEPOT) 00143 { 00144 // We're at the end of the Solution! 00145 len+=d[current_node][VRPH_DEPOT]; 00146 rlen+=d[current_node][VRPH_DEPOT]; 00147 current_route=route_num[current_node]; 00148 tot_len+=rlen; 00149 if(num_in_route != route[current_route].num_customers) 00150 { 00151 fprintf(stderr,"Customer count error!!\nCounted(%d)!=Claimed(%d) in final route %d\n",num_in_route, 00152 route[current_route].num_customers,current_route); 00153 show_route(current_route); 00154 report_error(message); 00155 } 00156 00157 // Now check the # of routes 00158 if(counted_routes != total_number_of_routes) 00159 { 00160 // error in # of routes 00161 fprintf(stderr, "Incorrect # of routes recorded %d!=%d\n",counted_routes, 00162 total_number_of_routes); 00163 report_error(message); 00164 00165 } 00166 if(VRPH_ABS(len-total_route_length)<.01 && flag==0 ) 00167 { 00168 // everything looks good 00169 return true; 00170 } 00171 else 00172 { 00173 if(VRPH_ABS(len-total_route_length)>=.01) 00174 { 00175 fprintf(stderr,"Objective function error: calculated(%f)!=claimed(%f)\n",len, 00176 total_route_length); 00177 report_error(message); 00178 } 00179 00180 00181 report_error(message); 00182 00183 } 00184 00185 } 00186 00187 if(next_array[current_node]>0) 00188 { 00189 // Next node is somewhere in the middle of a route 00190 00191 next_node = next_array[current_node]; 00192 // Make sure current_node and next_node have the same route # 00193 if(route_num[current_node]!=route_num[next_node]) 00194 { 00195 fprintf(stderr,"Route # error for %d and %d: %d!=%d\n",current_node, next_node, 00196 route_num[current_node],route_num[next_node]); 00197 00198 report_error(message); 00199 } 00200 len+=d[current_node][next_node]; 00201 rlen+=d[current_node][next_node]; 00202 00203 00204 current_node=next_node; 00205 00206 if(current_node!= dummy_index) 00207 num_in_route++; 00208 00209 total_load+=nodes[current_node].demand; 00210 current_load+=nodes[current_node].demand; 00211 cnt++; 00212 } 00213 else 00214 { 00215 // We must have a non-positive "next" node indicating the beginning of a new route 00216 00217 len+=d[current_node][VRPH_DEPOT]; 00218 00219 rlen+=d[current_node][VRPH_DEPOT]; 00220 tot_len+=rlen; 00221 current_route=route_num[current_node]; 00222 current_end = route[current_route].end; 00223 00224 if(num_in_route != route[current_route].num_customers) 00225 { 00226 fprintf(stderr,"%d (calculated) != %d (claimed) in route %d\n",num_in_route, 00227 route[current_route].num_customers,current_route); 00228 show_route(current_route); 00229 00230 // Report this now.. 00231 report_error(message); 00232 } 00233 00234 if(current_node != current_end) 00235 { 00236 fprintf(stderr,"Error in route ends: %d!=%d\n",current_node, current_end); 00237 report_error(message); 00238 } 00239 if(VRPH_ABS(rlen-route[current_route].length)>.1) 00240 { 00241 fprintf(stderr,"Route Lengths: Calculated(%f)!=Claimed(%f)\n",rlen,route[current_route].length); 00242 00243 int ii=route[current_route].start; 00244 int jj; 00245 fprintf(stderr,"0->%d = %f[%f]\n",ii, d[VRPH_DEPOT][ii], nodes[ii].service_time); 00246 while(ii != 0) 00247 { 00248 jj=VRPH_MAX(VRPH_DEPOT,next_array[ii]); 00249 fprintf(stderr,"%d->%d = %f[%f]\n",ii,jj,d[ii][jj], nodes[jj].service_time); 00250 ii=jj; 00251 00252 } 00253 00254 report_error(message); 00255 } 00256 00257 00258 00259 if(current_load != route[current_route].load) 00260 { 00261 fprintf(stderr,"Route Loads: %d!=%d\n",current_load, route[current_route].load); 00262 report_error(message); 00263 } 00264 00265 i++; 00266 route_start = - (next_array[current_node]); 00267 current_route = route_num[route_start]; 00268 current_start = route[current_route].start; 00269 current_end = route[current_route].end; 00270 counted_routes++; 00271 00272 if(route_start != current_start) 00273 { 00274 fprintf(stderr,"Route %d: %d != %d\n",current_route, route_start, current_start); 00275 report_error(message); 00276 } 00277 00278 current_node = route_start; 00279 total_load+=nodes[current_node].demand; 00280 // reset current_load to 0 00281 current_load=nodes[current_node].demand; 00282 //len+=nodes[current_node].depot_distance; 00283 len+=d[VRPH_DEPOT][current_node]; 00284 // reset rlen to 0 00285 //rlen=nodes[current_node].depot_distance; 00286 rlen=d[VRPH_DEPOT][current_node]; 00287 if(current_node!= dummy_index) 00288 num_in_route=1; 00289 else 00290 num_in_route=0; 00291 cnt++; 00292 } 00293 } 00294 00295 return true; 00296 } 00297 00298 void report_error(const char* format, ...) 00299 { 00303 00304 va_list args; 00305 00306 va_start(args, format); 00307 vfprintf(stderr, format, args); 00308 va_end(args); 00309 00310 fprintf(stderr,"Exiting\n"); 00311 exit(-1); 00312 } 00313