00001
00002
00003
00004
00005
00006
00007
00008
00009
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
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
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
00133
00134
00135 if(next_array[current_node]==current_node)
00136 {
00137
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
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
00158 if(counted_routes != total_number_of_routes)
00159 {
00160
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
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
00190
00191 next_node = next_array[current_node];
00192
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
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
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
00281 current_load=nodes[current_node].demand;
00282
00283 len+=d[VRPH_DEPOT][current_node];
00284
00285
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