VRPH  1.0
src/VRPIO.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 
00015 void VRP::read_TSPLIB_file(const char *node_file)
00016 {
00023 
00024 
00025     char *temp;
00026     char line[VRPH_STRING_SIZE];
00027     char *temp2;
00028     int max_id = -VRP_INFINITY;
00029 
00030     int ans;
00031     int x,y,i,j;
00032     float a, b;
00033     double s;
00034 
00035     bool has_depot=false;
00036     bool has_nodes=false;
00037 
00038     FILE *infile;
00039 
00040     infile  = fopen(node_file, "r");
00041 
00042     if (infile==NULL)
00043         report_error("%s: file error\n",__FUNCTION__);
00044 
00045 
00046     this->edge_weight_format=-1;
00047     this->edge_weight_type=-1;
00048 
00049     for(;;)
00050     {
00051         fgets(line, 100, infile);
00052 
00053 #if TSPLIB_DEBUG
00054         printf("Next line is %s\n",line);
00055 #endif
00056 
00057         temp=strtok(line,":");
00058 
00059 
00060 
00061 #if TSPLIB_DEBUG
00062         printf("line begins with %s\n",temp);
00063 #endif
00064 
00065         if( (ans=VRPCheckTSPLIBString(temp))<=0 )
00066         {
00067             if(ans==0)
00068                 fprintf(stderr,"Unknown string %s found\n",temp);
00069             else
00070                 fprintf(stderr,"TSPLIB string %s not supported\n",temp);
00071 
00072             report_error("%s\n",__FUNCTION__);
00073         }
00074 
00075 #if TSPLIB_DEBUG
00076         printf("ans is %d\n",ans);
00077 #endif
00078 
00079         // Otherwise, we know the string - process it accordingly
00080         switch(ans)
00081         {
00082         case 1:
00083             // NAME
00084 
00085             temp2=strtok(NULL," ");
00086             strcpy(name,temp2);        
00087             // Trim the ANNOYING \n if necessary...
00088             for(i=0;i<(int)strlen(name);i++)
00089             {
00090                 if(name[i]=='\n' || name[i]=='\r')
00091                 {
00092                     name[i]=0x00;
00093                     break;
00094                 }
00095             }
00096         
00097 
00098 
00099 #if TSPLIB_DEBUG
00100             printf("Name is %s\n",name);
00101 #endif
00102             break;
00103 
00104         case 2:
00105             // TYPE
00106             temp2=strtok(NULL," ");
00107 
00108 #if TSPLIB_DEBUG
00109             printf("Problem type is\n%s\n",temp2);
00110 #endif
00111             if( (strncmp(temp2,"TSP",3)!= 0) && (strncmp(temp2,"CVRP",4)!=0)
00112                 && (strncmp(temp2,"DCVRP",5)!=0) )
00113             {
00114                 fprintf(stderr,"Unknown type %s encountered\n",temp2);
00115                 report_error("%s\n",__FUNCTION__);
00116             }
00117 
00118             if( strncmp(temp2,"TSP",3)== 0) 
00119                 problem_type=VRPH_TSP;
00120             if(strncmp(temp2,"CVRP",4)==0 || (strncmp(temp2,"DCVRP",5)!=0) )
00121                 problem_type=VRPH_CVRP;
00122 
00123             break;
00124 
00125 
00126         case 3:
00127             // BEST_KNOWN
00128             temp2=strtok(NULL,"");
00129             this->best_known=atof(temp2);
00130             break;
00131         case 4:
00132             // DIMENSION
00133             num_nodes=atoi(strtok(NULL,""));
00134             num_nodes--;
00135             matrix_size= num_nodes;
00136             // num_nodes is the # of non-VRPH_DEPOT nodes
00137             // The value of DIMENSION includes the VRPH_DEPOT!
00138             dummy_index = 1+num_nodes;
00139 
00140             break;
00141 
00142         case 5:
00143             // CAPACITY
00144             max_veh_capacity=atoi(strtok(NULL,""));
00145             orig_max_veh_capacity=max_veh_capacity;
00146 
00147 #if TSPLIB_DEBUG
00148             printf("veh capacity is %d\n",max_veh_capacity);
00149 #endif
00150             break;
00151         case 6:
00152             // DISTANCE
00153             max_route_length=(double)atof(strtok(NULL,""));
00154             orig_max_route_length=max_route_length;
00155 
00156 #if TSPLIB_DEBUG
00157             printf("max length is %f\n",max_route_length);
00158 #endif
00159             break;
00160         case 7:
00161             // EDGE_WEIGHT_FORMAT - sets edge_weight_format
00162             temp2=strtok(NULL," ");
00163             edge_weight_format=-1;
00164 
00165             if(strncmp(temp2,"UPPER_ROW",9)==0)
00166             {
00167                 edge_weight_format=VRPH_UPPER_ROW;
00168             }
00169 
00170             if(strncmp(temp2,"FULL_MATRIX",11)==0)
00171             {
00172                 edge_weight_format=VRPH_FULL_MATRIX;
00173             }
00174             
00175             if(strncmp(temp2,"FUNCTION",8)==0)
00176             {
00177                 edge_weight_format=VRPH_FUNCTION;
00178 
00179             }
00180             if(strncmp(temp2,"LOWER_ROW",9)==0)
00181             {
00182                 edge_weight_format=VRPH_LOWER_ROW;
00183 
00184             }
00185             if(strncmp(temp2,"UPPER_DIAG_ROW",14)==0)
00186             {
00187                 edge_weight_format=VRPH_UPPER_DIAG_ROW;
00188 
00189             }
00190             if(strncmp(temp2,"LOWER_DIAG_ROW",14)==0)
00191             {
00192                 edge_weight_format=VRPH_LOWER_DIAG_ROW;
00193 
00194             }
00195 
00196             if(edge_weight_format == -1)
00197             {
00198                 // We didn't find a known type
00199                 fprintf(stderr,"Unknown/Unsupported EDGE_WEIGHT_FORMAT %s encountered\n",temp2);
00200                 report_error("%s\n",__FUNCTION__);
00201             }
00202             break;
00203         case 8:  
00204             // EDGE_WEIGHT_TYPE
00205             edge_weight_type    = -1;
00206             temp2=strtok(NULL," ");
00207 
00208 
00209 #if TSPLIB_DEBUG
00210             printf("Weight type is %s\n",temp2);
00211 #endif
00212             
00213             // Determine the type of weight format
00214             if(strncmp(temp2,"EXPLICIT",8)==0)
00215             {
00216                 edge_weight_type=VRPH_EXPLICIT;
00217             }
00218 
00219             if(strncmp(temp2,"EUC_2D",6)==0)
00220             {
00221                 edge_weight_type=VRPH_EUC_2D;
00222             }
00223 
00224             if(strncmp(temp2,"EUC_3D",6)==0)
00225             {
00226                 edge_weight_type=VRPH_EUC_3D;
00227 
00228             }
00229 
00230             if(strncmp(temp2,"MAX_2D",6)==0)
00231             {
00232                 edge_weight_type=VRPH_MAX_2D;
00233 
00234             }
00235 
00236             if(strncmp(temp2,"MAX_3D",6)==0)
00237             {
00238                 edge_weight_type=VRPH_MAX_3D;
00239 
00240             }
00241 
00242             if(strncmp(temp2,"MAN_2D",6)==0)
00243             {
00244                 edge_weight_type=VRPH_MAN_2D;
00245 
00246             }
00247 
00248             if(strncmp(temp2,"MAN_3D",6)==0)
00249             {
00250                 edge_weight_type=VRPH_MAN_3D;
00251 
00252             }
00253 
00254             if(strncmp(temp2,"MAN_3D",6)==0)
00255             {
00256                 edge_weight_type=VRPH_MAN_3D;
00257 
00258             }
00259 
00260             if(strncmp(temp2,"CEIL_2D",7)==0)
00261             {
00262                 edge_weight_type=VRPH_CEIL_2D;
00263             }
00264 
00265             if(strncmp(temp2,"GEO",3)==0)
00266             {
00267                 edge_weight_type=VRPH_GEO;
00268 
00269             }
00270 
00271             if(strncmp(temp2,"EXACT_2D",8)==0)
00272             {
00273                 edge_weight_type=VRPH_EXACT_2D;
00274 
00275             }
00276 
00277             if(edge_weight_type == -1)
00278             {
00279                 // We didn't find a known type
00280                 fprintf(stderr,"Unknown/Unsupported EDGE_WEIGHT_TYPE %s encountered\n",temp2);
00281                 report_error("%s\n",__FUNCTION__);
00282             }        
00283 
00284             break;
00285         case 9:
00286             // NODE_COORD_TYPE - we don't really care about this one
00287             temp2=strtok(NULL," ");
00288             if( (strncmp(temp2,"TWOD_COORDS",11)!=0) && (strncmp(temp2,"THREED_COORDS",13)!=0) )
00289             {
00290                 fprintf(stderr,"Unknown coordinate type %s encountered",temp2);
00291                 report_error("%s\n",__FUNCTION__);
00292             }
00293 
00294             break;
00295         case 10:
00296             // EOF - clean up and exit
00297             fclose(infile);
00298 
00299 #if TSPLIB_DEBUG
00300             fprintf(stderr,"Found EOF completing calculations...\n");
00301 #endif
00302 
00303             this->max_theta= -VRP_INFINITY;
00304             this->min_theta=  VRP_INFINITY;
00305 
00306             // Now normalize everything to put the VRPH_DEPOT at the origin
00307             // if it is a standard EXACT_2D problem or EUC_2D problem
00308             if( (this->edge_weight_type==VRPH_EXACT_2D || this->edge_weight_type==VRPH_EUC_2D) && has_nodes && has_depot && true)
00309             {
00310 
00311                 this->depot_normalized=true;
00312                 double depot_x=nodes[0].x;
00313                 double depot_y=nodes[0].y;
00314 
00315 #if TSPLIB_DEBUG
00316                 fprintf(stderr,"Normalizing...(%f,%f)\n",depot_x,depot_y);
00317 #endif
00318 
00319                 for(i=0;i<=this->num_nodes+1;i++)
00320                 {
00321                     nodes[i].x -= depot_x;
00322                     nodes[i].y -= depot_y;
00323                     // Translate everyone
00324 
00325                     // Calculate the polar coordinates as well
00326                     if(nodes[i].x==0 && nodes[i].y==0)
00327                     {
00328                         nodes[i].r=0;
00329                         nodes[i].theta=0;
00330                     }
00331                     else
00332                     {
00333 
00334                         nodes[i].r=sqrt( ((nodes[i].x)*(nodes[i].x)) + ((nodes[i].y)*(nodes[i].y)) );
00335                         nodes[i].theta=atan2(nodes[i].y,nodes[i].x);
00336                         // We want theta in [0 , 2pi]
00337                         // If y<0, add 2pi
00338                         if(nodes[i].y<0)
00339                             nodes[i].theta+=2*VRPH_PI;
00340                     }
00341 
00342                     // Update min/max theta across all nodes - don't include the VRPH_DEPOT/dummy
00343                     if(i!=0 && i!=(this->num_nodes+1))
00344                     {
00345                         if(nodes[i].theta>this->max_theta)
00346                             max_theta=nodes[i].theta;
00347                         if(nodes[i].theta<this->min_theta)
00348                             min_theta=nodes[i].theta;
00349                     }
00350 
00351                 }
00352             }
00353 
00354 #if TSPLIB_DEBUG
00355                 fprintf(stderr,"Creating neighbor lists...\n");
00356 #endif
00357 
00358             // Create the neighbor_lists-we may use a smaller size depending on the parameter
00359             // but we will construct the largest possible here...
00360             this->create_neighbor_lists(VRPH_MIN(MAX_NEIGHBORLIST_SIZE,num_nodes));
00361 
00362 #if TSPLIB_DEBUG
00363             fprintf(stderr,"Done w/ calculations...\n");
00364 #endif
00365             return;
00366 
00367         case 11:
00368             // NODE_COORD_SECTION
00369             // Import the data 
00370             this->can_display=true;
00371 
00372 #if TSPLIB_DEBUG
00373             printf("num_nodes is %d\n",num_nodes);
00374 #endif
00375 
00376             i=0;
00377             x=0;
00378             while(i<=num_nodes)
00379             {
00380                 fscanf(infile,"%d",&x);
00381                 fscanf(infile,"%f",&a);
00382                 fscanf(infile,"%f\n",&b);
00383 
00384                 nodes[i].id= x;
00385 
00386                 nodes[i].x=(double) a;
00387                 nodes[i].y=(double) b;
00388 
00389                 
00390                 i++;
00391 
00392             }
00393             has_nodes=true;
00394 
00395             break;
00396 
00397         case 12:
00398             // DEPOT_SECTION
00399             // Load in the Depot Coordinates
00400             fscanf(infile,"%d\n",&x);
00401             if(x!=1)
00402             {
00403                 fprintf(stderr,"Expected VRPH_DEPOT to be entry 1 - VRPH does not currently support"
00404                     " multiple DEPOTs\n");
00405                 report_error("%s\n",__FUNCTION__);
00406             }
00407                     
00408 #if TSPLIB_DEBUG
00409             printf("VRPH_DEPOT has coordinates: %f, %f\n",a,b);
00410 #endif
00411             //nodes[0].x=a;
00412             //nodes[0].y=b;
00413             //nodes[0].id=0;
00414 
00415             has_depot=true;
00416             fscanf(infile,"%d\n",&x);
00417             if(x!= -1)
00418             {
00419                 fprintf(stderr, "Expected -1 at end of DEPOT_SECTION.  Encountered %d instead\n",x);
00420                 report_error("%s\n",__FUNCTION__);
00421             }
00422 
00423             // Now set the dummy node id to the VRPH_DEPOT!
00424             nodes[num_nodes+1].x=nodes[0].x;
00425             nodes[num_nodes+1].y=nodes[0].y;
00426             nodes[num_nodes+1].id=0;
00427 
00428             // Now calculate distance matrix
00429             if(edge_weight_format==VRPH_FUNCTION || edge_weight_type!=VRPH_EXPLICIT)
00430             {
00431 
00432 #if TSPLIB_DEBUG
00433                 printf("Creating distance matrix using edge_weight_type %d\n",edge_weight_type);
00434 #endif
00435 
00436                 //Allocate memory for the distance matrix
00437                 if(d==NULL)
00438                 {
00439                     int n= num_nodes;
00440                     
00441                     d = new double* [n+2];
00442                     d[0] = new double [(n+2)*(n+2)];
00443                     for(i = 1; i < n+2; i++)
00444                         d[i] = d[i-1] + (n+2) ;
00445                 }
00446 
00447 
00448 
00449                 // Create the distance matrix using the appropriate 
00450                 // distance function...
00451                 create_distance_matrix(edge_weight_type);
00452             }
00453 
00454             break;
00455         case 13:
00456 
00457 #if TSPLIB_DEBUG
00458             printf("in case 13: DEMAND_SECTION w/ problem type %d # num_days=%d\n",problem_type,
00459                 this->num_days);
00460 #endif
00461             // DEMAND_SECTION
00462             // Read in the demands
00463                 
00464             if(this->num_days<=1)
00465             {
00466                 i=0;
00467                 while(i<= num_nodes+1)
00468                 {
00469 
00470                     fscanf(infile,"%d %d\n",&x,&y);
00471                     nodes[i].id=x;
00472                     nodes[i].demand=y;                
00473 
00474                     if(nodes[i].id>max_id)
00475                         max_id=nodes[i].id;
00476 
00477                     if(has_service_times==false)
00478                         nodes[i].service_time=0;
00479                     i++;
00480                 }
00481                 nodes[num_nodes+1].demand=0;
00482                 if(has_service_times==false)
00483                     nodes[num_nodes+1].service_time=0;
00484 
00485             }
00486             else
00487             {
00488                 // We have multiple days worth of demands
00489                 i=0;
00490                 while(i<=num_nodes+1)
00491                 {
00492                     fscanf(infile,"%d",&x);
00493                     nodes[i].id=x;
00494                     for(j=1;j<this->num_days;j++)
00495                     {
00496                         fscanf(infile,"%d",&y);
00497                         this->nodes[i].daily_demands[j]=y;
00498                         
00499                     }
00500                     fscanf(infile,"%d\n",&y);
00501                     this->nodes[i].daily_demands[this->num_days]=y;
00502                     i++;
00503                     
00504                 }
00505                 this->nodes[num_nodes+1].demand=0;
00506                 for(j=1;j<=this->num_days;j++)
00507                     this->nodes[num_nodes+1].daily_demands[j]=0;// Dummmy node
00508                 
00509 #if TSPLIB_DEBUG
00510                 printf("Done with multiple day demands\n");
00511 #endif
00512             }            
00513 
00514 
00515             break;
00516 
00517         case 14:
00518 
00519 #if TSPLIB_DEBUG
00520             printf("Case 14\n");
00521 #endif
00522            
00523             // EDGE_WEIGHT_SECTION
00524 
00525             // Make sure distance matrix is allocated
00526             if(d==NULL)
00527             {                
00528                 d = new double* [num_nodes+2];
00529                 d[0] = new double [(num_nodes+2)*(num_nodes+2)];
00530                 for(i = 1; i < num_nodes+2; i++)    
00531                     d[i] = d[i-1] + (num_nodes+2) ;
00532             }
00533 
00534             if(edge_weight_format==VRPH_UPPER_DIAG_ROW)
00535             {
00536                 // The zeros on the diagonal should be in the matrix!
00537                 for(i=0;i<= num_nodes;i++)
00538                 {
00539                     for(j=i;j<= num_nodes;j++)
00540                     {
00541                         fscanf(infile,"%lf",&(d[i][j]));
00542                         d[j][i]=d[i][j];
00543                     }
00544                     // Add in column for the dummy-assumed to live at the VRPH_DEPOT
00545                     d[i][num_nodes+1]=d[i][0];
00546                 }
00547                 // Now add a row for the dummy
00548                 for(j=0;j<=num_nodes+1;j++)
00549                     d[num_nodes+1][j]=d[0][j];
00550 
00551             }                
00552 
00553             if(edge_weight_format==VRPH_FULL_MATRIX)
00554             {
00555                 this->symmetric=false;
00556 
00557                 for(i=0;i<= num_nodes;i++)
00558                 {
00559                     for(j=0;j<= num_nodes;j++)
00560                     {
00561                         fscanf(infile,"%lf",&(d[i][j]));
00562                     }
00563                     // Add in column for the dummy-assumed to live at the VRPH_DEPOT
00564                     d[i][num_nodes+1]=d[i][0];
00565 
00566                 }
00567                 // Now add a row for the dummy
00568                 for(j=0;j<=num_nodes+1;j++)
00569                     d[num_nodes+1][j]=d[0][j];
00570 
00571             }
00572             
00573             // LOWER_DIAG_ROW format
00574             if(edge_weight_format==VRPH_LOWER_DIAG_ROW)
00575             {
00576                 // The zeros on the diagonal should be in the matrix!
00577                 for(i=0;i<= num_nodes;i++)
00578                 {
00579                     for(j=0;j<= i;j++)
00580                     {
00581                         fscanf(infile,"%lf",&(d[i][j]));
00582                         d[j][i]=d[i][j];
00583                     }
00584                     // Add in column for the dummy-assumed to live at the VRPH_DEPOT
00585                     d[i][num_nodes+1]=d[i][0];
00586 
00587                 }
00588                 // Now add a row for the dummy
00589                 for(j=0;j<=num_nodes+1;j++)
00590                     d[num_nodes+1][j]=d[0][j];
00591 
00592             }
00593 
00594             // UPPER_ROW format - no diagonal
00595             if(edge_weight_format==VRPH_UPPER_ROW)
00596             {
00597                 for(i=0;i<=num_nodes;i++)
00598                 {
00599                     for(j=i+1;j<= num_nodes;j++)
00600                     {
00601                         fscanf(infile,"%lf",&(d[i][j]));
00602                         d[j][i]=d[i][j];
00603                     }
00604                     // Add in column for the dummy-assumed to live at the VRPH_DEPOT
00605                     d[i][num_nodes+1]=d[i][0];
00606                     d[i][i]=0;
00607 
00608                 }
00609                 // Now add a row for the dummy
00610                 for(j=0;j<=num_nodes+1;j++)
00611                     d[num_nodes+1][j]=d[0][j];
00612 
00613             }
00614 
00615              // LOWER_ROW format
00616             if(edge_weight_format==VRPH_LOWER_ROW)
00617             {
00618                 for(i=0;i<= num_nodes;i++)
00619                 {
00620                     for(j=0;j<i;j++)
00621                     {
00622                         fscanf(infile,"%lf",&(d[i][j]));
00623                         d[j][i]=d[i][j];
00624                     }
00625                     d[i][i]=0;
00626                     // Add in column for the dummy-assumed to live at the VRPH_DEPOT
00627                     d[i][num_nodes+1]=d[i][0];
00628 
00629                 }
00630                 // Now add a row for the dummy
00631                 for(j=0;j<=num_nodes+1;j++)
00632                     d[num_nodes+1][j]=d[0][j];
00633             }
00634 
00635             // The last fscanf doesn't get the newline...
00636             fscanf(infile,"\n");
00637             break;
00638 
00639         case 15:
00640 
00641 #if TSPLIB_DEBUG
00642             printf("Case 15\n");
00643 #endif
00644 
00645             // SERVICE_TIME
00646 
00647             s =(double)(atof(strtok(NULL,"")));
00648             fixed_service_time=s;
00649 #if TSPLIB_DEBUG
00650             printf("Setting service time to %f for all nodes\n");
00651 #endif
00652             total_service_time=0;
00653             for(i=1;i<=num_nodes;i++)
00654             {
00655                 // Set the service time to s for each non-depot node
00656                 nodes[i].service_time=s;//+lcgrand(0) - use to test service times!
00657                 total_service_time+=nodes[i].service_time;
00658             }
00659             nodes[VRPH_DEPOT].service_time=0;
00660             nodes[num_nodes+1].service_time=0;
00661 
00662             has_service_times=true;
00663 
00664             break;
00665 
00666         case 16:
00667 
00668 #if TSPLIB_DEBUG
00669             printf("Case 16\n");
00670 #endif
00671 
00672             // VEHICLES
00673 
00674             min_vehicles=atoi(strtok(NULL,""));
00675             // This is not currently used
00676 #if TSPLIB_DEBUG
00677             printf("Setting min_vehicles to %d\n",min_vehicles);
00678 
00679 #endif
00680             break;
00681 
00682         case 17:
00683         
00684             // NUM_DAYS
00685             this->num_days=atoi(strtok(NULL,""));
00686             break;
00687 
00688         case 18:
00689             // SVC_TIME_SECTION
00690                         has_service_times=true;
00691 
00692             if(this->num_days<=1)// 8/15/2010 - used to be ==0 !
00693             {
00694                 i=0;
00695                 while(i<= num_nodes)
00696                 {
00697 
00698                     fscanf(infile,"%d %lf\n",&x,&s);
00699                     nodes[i].id=x;
00700                     nodes[i].service_time=s;
00701                     total_service_time+=nodes[i].service_time;
00702 
00703                     if(nodes[i].id>max_id)
00704                         max_id=nodes[i].id;
00705                     i++;
00706                 }
00707                 nodes[num_nodes+1].service_time=0;
00708 
00709                 
00710             }
00711             else
00712             {
00713                 // We have multiple days worth of service times
00714                 i=0;
00715                 while(i<=num_nodes)
00716                 {
00717                     fscanf(infile,"%d",&x);
00718                     nodes[i].id=x;
00719                     for(j=1;j<this->num_days;j++)
00720                     {
00721                         fscanf(infile,"%lf",&s);
00722                         this->nodes[i].daily_service_times[j]=s;
00723                     }
00724                     fscanf(infile,"%lf\n",&s);
00725                     this->nodes[i].daily_service_times[this->num_days]=s;
00726                     i++;
00727                     
00728                 }
00729                 this->nodes[num_nodes+1].service_time=0;
00730                 for(j=1;j<=this->num_days;j++)
00731                     this->nodes[num_nodes+1].daily_service_times[j]=0;// Dummmy node
00732                 
00733             }        
00734 
00735             
00736             break;
00737         case 19:
00738             // TIME_WINDOW_SECTION
00739             i=0;
00740             while(i<= num_nodes+1)
00741             {
00742                 fscanf(infile,"%d %f %f\n",&x,&a,&b);
00743                 nodes[i].start_tw=a;
00744                 nodes[i].end_tw=b;
00745                 i++;
00746             }
00747 
00748             break;
00749         case 20:
00750             // COMMENT
00751             // Don't care
00752             break;
00753         case 21:
00754             // DISPLAY_DATA_SECTION
00755             // Overwrite node's x and y coords with this data
00756 
00757             this->can_display=true;
00758             i=0;
00759             x=0;
00760             while(i<=num_nodes)
00761             {
00762                 fscanf(infile,"%d",&x);
00763                 fscanf(infile,"%f",&a);
00764                 fscanf(infile,"%f\n",&b);
00765 
00766                 nodes[x-1].x=(double) a;
00767                 nodes[x-1].y=(double) b;                
00768                 i++;
00769 
00770             }
00771 
00772             break;
00773         case 22:
00774             // TWOD_DISPLAY
00775             break;
00776         case 23:
00777             // DISPLAY_DATA_TYPE
00778 
00779             break;
00780         case 24:
00781             // NO_DISPLAY
00782             break;
00783         case 25:
00784             // COORD_DISPLAY
00785             break;
00786         }
00787     }
00788 
00789 }    
00790 
00791 
00792 void VRP::write_TSPLIB_file(const char *outfile)
00793 {
00798 
00799     FILE *out;
00800     int i;
00801 
00802     if( (out=fopen(outfile,"w"))==NULL)
00803     {
00804         report_error("%s: Can't open file for writing...\n",__FUNCTION__);
00805     }
00806 
00807     fprintf(out,"NAME: %s\n",name);
00808     fprintf(out,"TYPE: CVRP\n");
00809     if(this->best_known!=-1)
00810         fprintf(out,"BEST_KNOWN: %5.3f\n", this->best_known);
00811     fprintf(out,"DIMENSION: %d\n",num_nodes+1);
00812     fprintf(out,"CAPACITY: %d\n",max_veh_capacity);
00813     if(max_route_length!=VRP_INFINITY)
00814         fprintf(out,"DISTANCE: %4.5f\n",max_route_length);
00815     if(min_vehicles!=-1)
00816         fprintf(out,"VEHICLES: %d\n",min_vehicles);
00817     fprintf(out,"EDGE_WEIGHT_TYPE: FUNCTION\n");
00818     fprintf(out,"EDGE_WEIGHT_FORMAT: EXACT_2D\n");
00819     fprintf(out,"NODE_COORD_TYPE: TWOD_COORDS\n");
00820     fprintf(out,"NODE_COORD_SECTION\n");
00821 
00822     // Start numbering at 1!!
00823     fprintf(out,"%d %4.5f %4.5f\n",1,nodes[0].x,nodes[0].y);
00824     for(i=1;i<=num_nodes;i++)
00825     {
00826         fprintf(out,"%d %4.5f %4.5f\n",i+1,nodes[i].x,nodes[i].y);
00827     }
00828 
00829     fprintf(out,"DEMAND_SECTION\n");
00830     // Start numbering at 1!!
00831     fprintf(out,"1 0\n");
00832     for(i=1;i<=num_nodes;i++)
00833     {
00834         fprintf(out,"%d %d\n",i+1,nodes[i].demand);
00835     }
00836 
00837     fprintf(out,"DEPOT_SECTION\n");
00838     fprintf(out,"1\n-1\n");
00839 
00840     fprintf(out,"EOF\n");
00841 
00842     fclose(out);
00843 
00844 }
00845 
00846 
00847 
00848 void VRP::write_solution_file(const char *filename)
00849 {
00862 
00863 
00864 
00865     int n, current;
00866     FILE *out;
00867 
00868     int *sol;
00869 
00870     // Open the file
00871     if( (out = fopen(filename,"w"))==NULL)
00872     {
00873         fprintf(stderr,"Error opening %s for writing\n",filename);
00874         report_error("%s\n",__FUNCTION__);
00875     }
00876 
00877     // First, determine the # of nodes in the Solution -- this could be different than the
00878     // VRP.num_nodes value if we are solving a subproblem
00879 
00880     n=0;
00881     current=VRPH_ABS(next_array[VRPH_DEPOT]);
00882     while(current!=VRPH_DEPOT)
00883     {
00884         current=VRPH_ABS(next_array[current]);
00885         n++;
00886     }
00887     // We have n non-VRPH_DEPOT nodes in the problem
00888     sol=new int[n+2];
00889     // Canonicalize
00890     this->export_canonical_solution_buff(sol);
00891     this->import_solution_buff(sol);
00892     fprintf(out,"%d ",n);
00893 
00894 
00895     // Now output the ordering - this is actually just the sol buffer
00896     current=next_array[VRPH_DEPOT];
00897     fprintf(out,"%d ",current);
00898     while(current!=VRPH_DEPOT)
00899     {
00900         current=next_array[VRPH_ABS(current)];
00901         fprintf(out,"%d ",current);
00902 
00903     }
00904 
00905     fprintf(out,"\n\n\n");
00906 
00907 
00908     fflush(out);
00909     fprintf(out,"\n\n\nOBJ=\n%5.3f\nBEST_KNOWN=\n%5.3f",this->total_route_length-this->total_service_time,
00910         this->best_known);
00911 
00912     fflush(out);
00913     fclose(out);
00914 
00915     delete [] sol;
00916     return;
00917 }
00918 
00919 void VRP::write_solutions(int num_sols, const char *filename)
00920 {
00925 
00926     int i,n, current;
00927     FILE *out;
00928     int *sol;
00929 
00930     sol=new int[this->num_original_nodes+2]; // should be big enough
00931 
00932     // Open the file
00933     if( (out = fopen(filename,"w"))==NULL)
00934     {
00935         fprintf(stderr,"Error opening %s for writing\n",filename);
00936         report_error("%s\n",__FUNCTION__);
00937     }
00938 
00939     for(i=0;i<num_sols;i++)
00940     {
00941         if(i>this->solution_wh->num_sols)
00942             report_error("%s: too many solutions!\n",__FUNCTION__);
00943 
00944         // Import this solution and then write it out
00945         this->import_solution_buff(this->solution_wh->sols[i].sol);
00946         this->export_canonical_solution_buff(sol);
00947         this->import_solution_buff(sol);
00948 
00949 
00950         // First, determine the # of nodes in the Solution -- this could be different than the
00951         // VRP.num_nodes value if we are solving a subproblem
00952 
00953         n=0;
00954         current=VRPH_ABS(next_array[VRPH_DEPOT]);
00955         while(current!=VRPH_DEPOT)
00956         {
00957             current=VRPH_ABS(next_array[current]);
00958             n++;
00959         }
00960         // We have n non-VRPH_DEPOT nodes in the problem
00961         fprintf(out,"%d ",n);
00962 
00963         // Now output the ordering
00964         current=next_array[VRPH_DEPOT];
00965         fprintf(out,"%d ",current);
00966         while(current!=VRPH_DEPOT)
00967         {
00968             current=next_array[VRPH_ABS(current)];
00969             fprintf(out,"%d ",current);
00970 
00971         }
00972         fprintf(out,"\n");
00973     }
00974 
00975     fflush(out);
00976     fclose(out);
00977     return;
00978 
00979 }
00980 
00981 
00982 void VRP::write_tex_file(const char *filename)
00983 {
00989 
00990     int i;
00991 
00992     FILE *out;
00993     if( (out=fopen(filename,"w"))==NULL)
00994     {
00995         fprintf(stderr,"Error opening %s for writing\n",filename);
00996         report_error("%s\n",__FUNCTION__);
00997         
00998     }    
00999 
01000     // The headers for the first page and pages thereafter
01001     fprintf(out,"%% TeX file automatically generated by VRPH for problem %s\n\n",this->name);
01002     fprintf(out,"\\renewcommand{\\baselinestretch}{1}\n");
01003     fprintf(out,"\\footnotesize\n");
01004     fprintf(out,"\\begin{center}\n");
01005     fprintf(out,"\\begin{longtable}{|c|r|r|p{4 in}|}\n");
01006 
01007     fprintf(out,"\\hline\n");
01008     fprintf(out,"Route&\\multicolumn{1}{c|}{Length}&\\multicolumn{1}{c|}{Load}&\\multicolumn{1}{c|}{Ordering}\\\\\n");
01009     fprintf(out,"\\hline\n");
01010     fprintf(out,"\\endhead\n");
01011     fprintf(out,"\\hline\n");
01012     fprintf(out,"\\multicolumn{3}{|l|}{Problem}&%s\\\\\n",this->name);
01013     fprintf(out,"\\hline\n");
01014     fprintf(out,"\\endfirsthead\n");
01015     fprintf(out,"\\endfoot\n");
01016     fprintf(out,"\\endlastfoot\n");
01017     fprintf(out,"\\multicolumn{3}{|l|}{Vehicle capacity}&%d\\\\\n",this->max_veh_capacity);
01018     if(this->max_route_length!=VRP_INFINITY)
01019         fprintf(out,"\\multicolumn{3}{|l|}{Maximum route length}&%5.3f\\\\\n",this->max_route_length);
01020     else
01021         fprintf(out,"\\multicolumn{3}{|l|}{Maximum route length}&N/A\\\\\n");
01022     if(this->total_service_time>0)
01023         fprintf(out,"\\multicolumn{3}{|l|}{Total service time}&%5.3f\\\\\n",this->total_service_time);
01024     fprintf(out,"\\multicolumn{3}{|l|}{Number of nodes}&%d\\\\\n",this->num_nodes);
01025     fprintf(out,"\\multicolumn{3}{|l|}{Total route length}&%5.3f\\\\\n",this->total_route_length-
01026         this->total_service_time);
01027     fprintf(out,"\\multicolumn{3}{|l|}{Total number of routes}&%d\\\\\n",this->total_number_of_routes);
01028     fprintf(out,"\\hline\n");
01029     fprintf(out,"Route&\\multicolumn{1}{c|}{Length}&\\multicolumn{1}{c|}{Load}&\\multicolumn{1}{c|}{Ordering}\\\\\n");
01030     fprintf(out,"\\hline\n");
01031 
01032     for(i=1;i<=this->total_number_of_routes;i++)
01033     {
01034         fprintf(out,"%d&%5.3f&%d&(0",i,this->route[i].length,this->route[i].load);
01035         int current=this->route[i].start;
01036         while(current>=0)
01037         {
01038             fprintf(out,", %d",current);
01039             current=this->next_array[current];
01040 
01041         }
01042         fprintf(out,", 0)\\\\\n");
01043         fprintf(out,"\\hline\n");
01044     }
01045     fprintf(out,"\\caption{The best solution found for problem %s}\n",this->name);
01046     fprintf(out,"\\end{longtable}\n");
01047     fprintf(out,"\\end{center}\n");
01048     fprintf(out,"\\renewcommand{\\baselinestretch}{2}\n");
01049     fprintf(out,"\\normalsize\n");
01050     fclose(out);
01051 }
01052 
01053 
01054 void VRP::read_solution_file(const char *filename)
01055 {
01060 
01061     FILE *in;
01062 
01063     if( (in=fopen(filename,"r"))==NULL)
01064     {
01065         fprintf(stderr,"Error opening %s for reading\n",filename);
01066         report_error("%s\n",__FUNCTION__);
01067     }
01068 
01069     int *new_sol;
01070     int i,n;
01071     fscanf(in,"%d",&n);
01072     new_sol=new int[n+2];
01073     new_sol[0]=n;
01074     for(i=1;i<=n+1;i++)
01075         fscanf(in,"%d",new_sol+i);
01076     
01077     // Import the buffer
01078     this->import_solution_buff(new_sol);
01079     fclose(in);
01080     delete [] new_sol;
01081 
01082     this->verify_routes("After read_solution_file\n");
01083 
01084     memcpy(this->best_sol_buff,this->current_sol_buff,(this->num_nodes+2)*sizeof(int));
01085 
01086     return;
01087 
01088 }
01089 
01090 
01091 
01092 void VRP::import_solution_buff(int *sol_buff)
01093 {
01099 
01100 
01101     int i, n, rnum, current, next, load, num_in_route;
01102     double len;
01103 
01104     next=-1; //to avoid warning...
01105 
01106     // Set all nodes to unrouted
01107     for(i=1;i<=this->num_original_nodes;i++)
01108         routed[i]=false;
01109 
01110     len=0;
01111     load=0;
01112 
01113     total_route_length=0;
01114 
01115     this->num_nodes = sol_buff[0];
01116 
01117     n=this->num_nodes;
01118     num_in_route=0;
01119 
01120     rnum=1;
01121 
01122     current=VRPH_ABS(sol_buff[1]);
01123     routed[current]=true;
01124     next_array[VRPH_DEPOT]=sol_buff[1];
01125     route_num[VRPH_ABS(current)]=rnum;
01126     route[rnum].start=VRPH_ABS(current);
01127     load+=nodes[VRPH_ABS(current)].demand;
01128     len+=d[VRPH_DEPOT][VRPH_ABS(current)];
01129     num_in_route++;
01130 
01131     for(i=2;i<=n;i++)
01132     {
01133         next=sol_buff[i];
01134         routed[VRPH_ABS(next)]=true;
01135 
01136         if(next<0)
01137         {
01138             // end of route - current is the last node in this route
01139             // next is the first node in the next route
01140 
01141             len+=d[VRPH_ABS(current)][VRPH_DEPOT];
01142 
01143             route[rnum].end=VRPH_ABS(current);
01144             route[rnum].length=len;
01145             route[rnum].load=load;
01146             route[rnum].num_customers=num_in_route;
01147             total_route_length+=len;
01148 
01149             if(rnum>n)
01150             {
01151                 fprintf(stderr,"%d>%d:  rnum too big in import solution buff!\n",rnum,n);
01152                 for(i=0;i<=n;i++)
01153                     fprintf(stderr,"%d ",sol_buff[i]);
01154         
01155                 report_error("%s\n",__FUNCTION__);
01156             }
01157 
01158 
01159             rnum++;
01160             num_in_route=0;
01161             len=0;
01162             load=0;
01163             len+=d[VRPH_DEPOT][VRPH_ABS(next)];
01164             route_num[VRPH_ABS(next)]=rnum;
01165             route[rnum].start=VRPH_ABS(next);
01166         }
01167         else
01168             // Not at the end of a route
01169             len+=d[VRPH_ABS(current)][VRPH_ABS(next)];
01170 
01171 
01172 
01173         next_array[VRPH_ABS(current)]=next;
01174         current=next;
01175 
01176         load+=nodes[VRPH_ABS(current)].demand;
01177         num_in_route++;
01178 
01179         route_num[VRPH_ABS(current)]=rnum;
01180     }
01181 
01182 
01183     next_array[VRPH_ABS(next)]=VRPH_DEPOT;
01184     route_num[VRPH_ABS(next)]=rnum;
01185 
01186     len+=d[VRPH_ABS(next)][VRPH_DEPOT];
01187 
01188     route[rnum].end=VRPH_ABS(next);
01189     route[rnum].length=len;
01190     route[rnum].load=load;
01191     route[rnum].num_customers=num_in_route;
01192     total_route_length+=len;
01193     total_number_of_routes=rnum;
01194     create_pred_array();
01195 
01196     // Make sure everything imported successfully!
01197     verify_routes("After import sol_buff\n");
01198 
01199     // Mark all the nodes as "routed"
01200     for(i=1;i<=sol_buff[0];i++)
01201         routed[VRPH_ABS(sol_buff[i])]=true;
01202 
01203     routed[VRPH_DEPOT]=true;
01204 
01205     route_num[VRPH_DEPOT]=0;
01206 
01207     memcpy(this->current_sol_buff,sol_buff,(this->num_nodes+2)*sizeof(int));
01208 
01209     return;
01210 
01211 }
01212 void VRP::export_solution_buff(int *sol_buff)
01213 {
01217 
01218     int i, current;
01219 
01220     sol_buff[0]=num_nodes;    
01221 
01222     // Now output the ordering
01223     current=next_array[VRPH_DEPOT];
01224     sol_buff[1]=current;
01225     i=2;
01226 
01227     while(current!=VRPH_DEPOT)
01228     {
01229         current=next_array[VRPH_ABS(current)];
01230         sol_buff[i]=current;
01231         i++;
01232     }
01233 
01234     return;
01235 }
01236 
01237 void VRP::export_canonical_solution_buff(int *sol_buff)
01238 {
01246 
01247     int i,j,next;
01248     int *start_buff;
01249 
01250     start_buff=new int[total_number_of_routes];
01251     
01252     this->normalize_route_numbers();
01253 
01254     // First orient each route properly
01255     for(i=1;i<=total_number_of_routes;i++)
01256     {
01257         if(route[i].end<route[i].start)
01258             reverse_route(i);
01259 
01260         start_buff[i-1]=route[i].start;
01261     }
01262 
01263 
01264     // Sort the start_buff
01265     qsort(start_buff, total_number_of_routes, sizeof(int), VRPIntCompare);
01266 
01267     sol_buff[0]=this->num_nodes;
01268 
01269     // Now order the routes themselves
01270     j=1;
01271     for(i=0;i<total_number_of_routes;i++)
01272     {
01273         sol_buff[j]=-start_buff[i];
01274         for(;;)
01275         {
01276             next=this->next_array[VRPH_ABS(sol_buff[j])];
01277             if(next<=0)
01278                 break; // next route
01279 
01280             j++;
01281             sol_buff[j]=next;
01282         }
01283         j++;
01284     }
01285     
01286     sol_buff[j]=VRPH_DEPOT;
01287 
01288     delete [] start_buff;
01289 
01290     return;
01291 
01292 }
01293 
01294 void VRP::show_routes()
01295 {
01299 
01300 
01301     int i, cnt;
01302     int route_start;
01303     int next_node_number;
01304     int current_node, current_route;
01305     int total_load = 0;
01306 
01307 
01308     printf("-----------------------------------------------\n");
01309     printf("Total route length:  %5.2f\n",total_route_length);
01310     i = 1;
01311     cnt = 0;
01312     route_start = -next_array[VRPH_DEPOT];
01313     current_node = route_start;
01314     current_route = route_num[current_node];
01315     total_load+= route[current_route].load;
01316 
01317 
01318     printf("\nRoute %04d(routenum=%d)[0-%d...%d-0, %5.2f, %d, %d]: \n",i,current_route,
01319         nodes[route[current_route].start].id,
01320         nodes[route[current_route].end].id,
01321         route[current_route].length,
01322         route[current_route].load,
01323         route[current_route].num_customers);
01324 
01325     printf("%d-%d-",VRPH_DEPOT,nodes[route_start].id);
01326 
01327     cnt++;
01328 
01329     while(route_start != 0 && i<num_nodes+1)
01330     {
01331         // When we finally get a route beginning at 0, this is the last route 
01332         // and there is no next route, so break out
01333         if(next_array[current_node]==0)
01334         {
01335             printf("%d\n",VRPH_DEPOT);
01336             printf("End of routes.  Totals: (%d routes,%d nodes,%d total load)\n",i,cnt,total_load);
01337             printf("-----------------------------------------------\n");
01338             if(cnt!= num_nodes)
01339             {
01340                 fprintf(stderr,"Not enough nodes! counted=%d; claimed=%d\n",cnt,num_nodes);
01341                 report_error("%s\n",__FUNCTION__);
01342             }
01343 
01344             return;
01345         }
01346 
01347         if(next_array[current_node]>0)
01348         {
01349             // Next node is somewhere in the middle of a route
01350             next_node_number = next_array[current_node];
01351             printf("%d-",nodes[next_node_number].id);
01352 
01353             current_node=next_node_number;
01354             cnt++;
01355 
01356             if(cnt>num_nodes)
01357             {
01358                 fprintf(stderr,"Too many nodes--cycle?\n");
01359                 fprintf(stderr,"Count is %d, num_nodes is %d\n",cnt,num_nodes);
01360                 show_next_array();
01361                 report_error("%s\n",__FUNCTION__);
01362             }
01363         }
01364         else
01365         {
01366             // We must have a non-positive "next" node indicating the beginning of a new route
01367             i++;
01368             printf("%d",VRPH_DEPOT);
01369 
01370             route_start = - (next_array[current_node]);    
01371             current_route = route_num[route_start];
01372             current_node = route_start;
01373 
01374             printf("\n\nRoute %04d(routenum=%d)[0-%d...%d-0, %3.2f, %d, %d]: \n",i,current_route,
01375                 nodes[route[current_route].start].id,
01376                 nodes[route[current_route].end].id,
01377                 route[current_route].length,
01378                 route[current_route].load,
01379                 route[current_route].num_customers);
01380 
01381 
01382             // Print out the beginning of this route
01383             total_load += route[current_route].load;
01384             printf("%d-%d-",VRPH_DEPOT,nodes[current_node].id);
01385             cnt++;
01386         }
01387     }
01388 
01389     
01390 }
01391 
01392 
01393 
01394 
01395 void VRP::show_route(int k)
01396 {
01400 
01401     int current_node;
01402     int i=0;
01403     if(k<=0)
01404         report_error("%s: called with non-positive route number\n",__FUNCTION__);
01405 
01406     printf("\nRoute %03d[0-%03d...%03d-0, %5.3f, %d, %d]: \n",k,
01407         route[k].start,
01408         route[k].end,
01409         route[k].length,
01410         route[k].load,
01411         route[k].num_customers);
01412 
01413     printf("%d-",VRPH_DEPOT);
01414 
01415     current_node= route[k].start;
01416     while(current_node != route[k].end)
01417     {
01418         printf("%03d-",current_node);
01419         current_node= next_array[current_node];
01420         i++;
01421         if(i>num_nodes)
01422             report_error("%s: encountered too many nodes!!\n",__FUNCTION__);
01423     }
01424     printf("%03d-%d\n\n",current_node,VRPH_DEPOT);
01425 
01426 }
01427 
01428 void VRP::summary()
01429 {
01433 
01434     int i, cnt;
01435     int route_start;
01436     int next_node_number;
01437     int current_node, current_route;
01438     int total_load = 0;
01439     int num_in_route=0;
01440     int total_nodes=0;
01441     int cust_count=0;
01442     bool feasible=true;
01443 
01444     printf("\n------------------------------------------------\n");
01445     printf("Solution for problem %s\n",this->name);
01446     printf("Total route length:       %5.2f\n",total_route_length-this->total_service_time);
01447     if(this->best_known!=VRP_INFINITY)
01448         printf("Best known solution:      %5.2f\n",this->best_known);
01449     printf("Total service time:       %5.2f\n",this->total_service_time);
01450     if(this->max_route_length!=VRP_INFINITY)
01451         printf("Vehicle max route length: %5.2f\n",this->max_route_length);
01452     else
01453         printf("Vehicle max route length: N/A\n");
01454     printf("Vehicle capacity:         %d\n",this->max_veh_capacity);
01455     printf("Number of nodes visited:  %d\n",this->num_nodes);
01456     printf("------------------------------------------------\n");
01457     i = 1;
01458     cnt = 0;
01459     route_start = -next_array[VRPH_DEPOT];
01460     current_node = route_start;
01461     current_route = route_num[current_node];
01462     total_load+= route[current_route].load;
01463 
01464 
01465     printf("\nRoute %03d[0-%03d...%03d-0\tlen=%03.2f\tload=%04d\t#=%03d]",i,route[current_route].start,
01466         route[current_route].end,route[current_route].length,
01467         route[current_route].load,route[current_route].num_customers);
01468     // Check feasibility
01469     if(route[current_route].length>this->max_route_length || 
01470         route[current_route].load > this->max_veh_capacity)
01471         feasible=false;
01472     cust_count+= route[current_route].num_customers;
01473 
01474     if(current_node!= dummy_index)
01475         num_in_route=1;
01476 
01477     total_nodes++;
01478 
01479     cnt++;
01480 
01481     while(route_start != 0 && i<num_nodes+1)
01482     {
01483         // When we finally get a route beginning at 0, this is the last route 
01484         // and there is no next route, so break out
01485         if(next_array[current_node]==0)
01486         {
01487             num_in_route=0;
01488             if(cnt!= num_nodes)
01489             {
01490                 fprintf(stderr,"Not enough nodes:  counted=%d; claimed=%d!\n",cnt,num_nodes);
01491                 report_error("%s\n",__FUNCTION__);
01492             }
01493 
01494             printf("\n\n");
01495             if(!feasible)
01496                 printf("\nWARNING:  Solution appears to be infeasible!\n");
01497             return;
01498         }
01499 
01500         if(next_array[current_node]>0)
01501         {
01502             // Next node is somewhere in the middle of a route
01503             next_node_number = next_array[current_node];
01504             if(current_node!= dummy_index)
01505                 num_in_route++;
01506 
01507             total_nodes++;
01508             current_node=next_node_number;
01509             cnt++;
01510         }
01511         else
01512         {
01513             // We must have a non-positive "next" node indicating the beginning of a new route
01514             i++;
01515             total_nodes++;
01516             num_in_route=0;
01517 
01518             route_start = - (next_array[current_node]);    
01519             current_route = route_num[route_start];
01520             current_node = route_start;
01521 
01522             printf("\nRoute %03d[0-%03d...%03d-0\tlen=%03.2f\tload=%04d\t#=%03d]",i,route[current_route].start,
01523                 route[current_route].end,route[current_route].length,
01524                 route[current_route].load,route[current_route].num_customers);
01525             cust_count+= route[current_route].num_customers;
01526 
01527             if(route[current_route].length>this->max_route_length || 
01528                 route[current_route].load > this->max_veh_capacity)
01529                 feasible=false;
01530 
01531             total_load += route[current_route].load;
01532             cnt++;
01533             if(current_node!= dummy_index)
01534                 num_in_route++;
01535         }
01536     }
01537 }
01538