VRPH  1.0
src/VRPDebug.cpp
Go to the documentation of this file.
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