VRPH  1.0
src/apps/vrp_rtr.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 <time.h>
00015 
00016 int main(int argc, char *argv[])
00017 {
00023 
00024     VRPH_version();
00025 
00026     char out[VRPH_STRING_SIZE];
00027     char plot_file[VRPH_STRING_SIZE];
00028     char sol_file[VRPH_STRING_SIZE];
00029     char fixed_edges_file[VRPH_STRING_SIZE];
00030     int i,n;
00031     clock_t start, stop;
00032     double elapsed;
00033 
00034     // Default  parameter settings
00035     bool verbose=false;
00036     int intensity =30;
00037     int max_tries=5;
00038     int num_lambdas=3;
00039     int num_perturbs=1;
00040     int nlist_size=40;
00041     int perturb_type=VRPH_LI_PERTURB ;
00042     int accept_type=VRPH_FIRST_ACCEPT;
00043     int neighbor_lists=VRPH_USE_NEIGHBOR_LIST;
00044     int tabu=0;
00045     int tabu_list_size=0;
00046 
00047 
00048     double lambda_vals[VRPH_MAX_NUM_LAMBDAS];
00049     bool new_lambdas=false;
00050     bool has_heuristics=false;
00051     bool has_outfile=false;
00052     bool has_plot_file=false;
00053     bool has_sol_file=false;
00054     bool has_fixed_edges_file=false;
00055     int heuristics=0;
00056     double dev=.01;
00057     int *final_sol;
00058     double final_obj=VRP_INFINITY;
00059     bool do_pdf=false;
00060     int *my_sol_buff;
00061 
00062 
00063     if(argc<2 || (strncmp(argv[1],"-help",5)==0)||(strncmp(argv[1],"--help",6)==0)||(strncmp(argv[1],"-h",2)==0))
00064     {        
00065         fprintf(stderr,"Usage: %s -f <vrp_input_file> [options]\n",argv[0]);
00066         fprintf(stderr,"Options:\n");
00067         
00068         fprintf(stderr,"\t-help prints this help message\n"); 
00069         
00070         fprintf(stderr,"\t-a <accept_type> 0 for VRPH_FIRST_ACCEPT or 1 for VRPH_BEST_ACCEPT\n\t\t(default is VRPH_FIRST_ACCEPT)\n");
00071         
00072         fprintf(stderr,"\t-d <deviation> runs the RTR search with given deviation\n");
00073         fprintf(stderr,"\t\t default is dev=.01\n");
00074 
00075         fprintf(stderr,"\t-fix <fixed_edge_file> will fix all of the edges in the provided file\n");
00076                 
00077         fprintf(stderr,"\t-h <heuristic> applies the specified heuristics (can be repeated)\n");
00078         fprintf(stderr,"\t\t default is ONE_POINT_MOVE, TWO_POINT_MOVE, and TWO_OPT\n");
00079         fprintf(stderr,"\t\t others available are OR_OPT, THREE_OPT, and CROSS_EXCHANGE\n");
00080         fprintf(stderr,"\t\t Example: -h OR_OPT -h THREE_OPT -h TWO_OPT -h ONE_POINT_MOVE\n");
00081         fprintf(stderr,"\t\t Setting -h KITCHEN_SINK applies all heuristics in the \n");
00082         fprintf(stderr,"\t\t improvement phase\n");
00083         
00084         fprintf(stderr,"\t-sol <sol_file> begins with an existing solution contained\n");
00085         fprintf(stderr,"\t\t in sol_file\n");
00086         
00087         fprintf(stderr,"\t-v prints verbose output to stdout\n");
00088         
00089         fprintf(stderr,"\t-k <intensity> runs the RTR search with the provided intensity\n\t\t(default is 30)\n");
00090 
00091         fprintf(stderr,"\t-L <num_lambdas> runs the RTR procedure from num_lambdas\n");
00092         fprintf(stderr,"\t\t different initial solutions using a random lambda chosen\n");
00093         fprintf(stderr,"\t\t from (0.5,2.0)\n");
00094         fprintf(stderr,"\t\t default is to use lambda in {.6, 1.4, 1.6}.\n");
00095         
00096         fprintf(stderr,"\t-m <max_tries> gives up after not beating a local minimum after\n");
00097         fprintf(stderr,"\t\t max_tries consecutive attempts (default is 5)\n");
00098 
00099         fprintf(stderr,"\t-N <nlist_size> uses the nlist_size nearest neighbors in the search\n");
00100         fprintf(stderr,"\t\t default is 25. Using -N 0 will not use neighbor lists at all\n");
00101         
00102         fprintf(stderr,"\t-P <num_perturbs> perturbs the current solution num_perturbs times\n\t\t(default is 1)\n");
00103 
00104         fprintf(stderr,"\t-p <perturb_type> 0 for VRPH_LI_PERTURB or 1 for VRPH_OSMAN_PERTURB\n");
00105 
00106         fprintf(stderr,"\t-plot <plot_file> plots the best solution to the provided file.\n");
00107         fprintf(stderr,"\t\t This requires a working PLPlot installation\n");
00108 
00109         fprintf(stderr,"\t-pdf will create a .pdf from the .ps file created by -plot\n");
00110 
00111         fprintf(stderr,"\t-r will search the neighborhood in a random fashion\n");
00112 
00113         fprintf(stderr,"\t-t <tabu_list_size> will use a primitive Tabu Search in the uphill phase\n");
00114         
00115         fprintf(stderr,"\t-out <out_file> writes the solution to the provided file\n");
00116         
00117         
00118         
00119         exit(-1);
00120     }
00121 
00122     bool has_filename=false;
00123     char *infile=NULL;
00124     for(i=1;i<argc;i++)
00125     {
00126         if(strcmp(argv[i],"-f")==0)
00127         {
00128             // Get the input file name
00129             has_filename=true;
00130             infile=argv[i+1];
00131         }
00132     }
00133     if(has_filename==false)
00134     {
00135         fprintf(stderr,"No input file given\nUsage: %s -f <filename> [options]\n",argv[0]);
00136         exit(-1);
00137     }
00138 
00139     // Get # of non-VRPH_DEPOT nodes
00140     n=VRPGetDimension(infile);
00141     int num_days=VRPGetNumDays(infile);
00142     my_sol_buff=new int[n+2];
00143 
00144 
00145     VRP V(n,num_days);
00146        
00147         
00148 
00149     // Allocate the buffer for the final solution
00150     final_sol=new int[n+2];    
00151 
00152     // Parse command line
00153     for(i=2;i<argc;i++)
00154     {
00155         if(strcmp(argv[i],"-a")==0)
00156         {
00157             accept_type=atoi(argv[i+1]);
00158             if( (accept_type!=0) && (accept_type !=1))
00159                 report_error("%s: %s: accept_type must be 0 or 1\n");
00160 
00161             if(accept_type==1)
00162                 accept_type=VRPH_BEST_ACCEPT;
00163             else
00164                 accept_type=VRPH_FIRST_ACCEPT;
00165         }
00166 
00167         if(strcmp(argv[i],"-d")==0)
00168             dev=atof(argv[i+1]);
00169 
00170         if(strcmp(argv[i],"-D")==0)
00171             intensity=atoi(argv[i+1]);
00172 
00173         if(strcmp(argv[i],"-fix")==0)
00174         {
00175             has_fixed_edges_file=true;
00176             strcpy(fixed_edges_file,argv[i+1]);
00177         }
00178 
00179         if(strcmp(argv[i],"-h")==0)
00180         {
00181             has_heuristics=true;
00182             if(strcmp(argv[i+1],"ONE_POINT_MOVE")==0)
00183                 heuristics|=ONE_POINT_MOVE;
00184             if(strcmp(argv[i+1],"TWO_POINT_MOVE")==0)
00185                 heuristics|=TWO_POINT_MOVE;
00186             if(strcmp(argv[i+1],"TWO_OPT")==0)
00187                 heuristics|=TWO_OPT;
00188             if(strcmp(argv[i+1],"OR_OPT")==0)
00189                 heuristics|=OR_OPT;
00190             if(strcmp(argv[i+1],"THREE_OPT")==0)
00191                 heuristics|=THREE_OPT;
00192             if(strcmp(argv[i+1],"CROSS_EXCHANGE")==0)
00193                 heuristics|=CROSS_EXCHANGE;
00194             if(strcmp(argv[i+1],"THREE_POINT_MOVE")==0)
00195                 heuristics|=THREE_POINT_MOVE;
00196             if(strcmp(argv[i+1],"KITCHEN_SINK")==0)
00197                 heuristics|=KITCHEN_SINK;
00198         }
00199 
00200         if(strcmp(argv[i],"-k")==0)
00201             max_tries=atoi(argv[i+1]);
00202 
00203         if(strcmp(argv[i],"-L")==0)
00204         {
00205             new_lambdas=true;
00206             num_lambdas = atoi(argv[i+1]);
00207 
00208             if(num_lambdas>VRPH_MAX_NUM_LAMBDAS)
00209             {
00210                 fprintf(stderr,"%d>VRPH_MAX_NUM_LAMBDAS\n",num_lambdas);
00211                 exit(-1);
00212             }
00213 
00214             for(int j=0;j<num_lambdas;j++)
00215             {
00216                 // Generate a random lambda
00217                 lambda_vals[j] = 0.5 + 1.5*((double)lcgrand(1));
00218             }
00219         }
00220 
00221         if(strcmp(argv[i],"-N")==0)
00222             nlist_size=atoi(argv[i+1]);
00223 
00224         if(strcmp(argv[i],"-out")==0)
00225         {
00226             has_outfile=true;
00227             strcpy(out,argv[i+1]);
00228         }
00229 
00230         if(strcmp(argv[i],"-plot")==0)
00231         {
00232             has_plot_file=true;
00233             strcpy(plot_file,argv[i+1]);
00234         }
00235 
00236         if(strcmp(argv[i],"-p")==0)
00237         {
00238             perturb_type=atoi(argv[i+1]);
00239             if(perturb_type!=0 && perturb_type!=1)
00240             {
00241                 fprintf(stderr,"Perturb type must be 0 or 1!\n");
00242                 exit(-1);
00243             }
00244         }
00245 
00246         if(strcmp(argv[i],"-P")==0)
00247             num_perturbs=atoi(argv[i+1]);
00248 
00249         if(strcmp(argv[i],"-pdf")==0)
00250             do_pdf=true;
00251 
00252 
00253 
00254         if(strcmp(argv[i],"-sol")==0)
00255         {
00256             has_sol_file=true;
00257             strcpy(sol_file,argv[i+1]);
00258         }
00259 
00260         if(strcmp(argv[i],"-t")==0)
00261         {
00262             tabu=VRPH_TABU;    
00263             tabu_list_size=atoi(argv[i+1]);
00264         }        
00265 
00266         if(strcmp(argv[i],"-v")==0)
00267             verbose=true;
00268         
00269     }
00270 
00271     // Load the problem data
00272     V.read_TSPLIB_file(infile);
00273     // If we have more than one day, just run alg. on day 1
00274     if(num_days>1)
00275     {
00276         printf("Multi-day problem loaded (%d days). Will run only on day 1\n",
00277             num_days);
00278         V.set_daily_demands(1);
00279         V.set_daily_service_times(1);
00280     }
00281    
00282 
00283     // Start processing the input options
00284     if(new_lambdas==false)
00285     {
00286         // Use .6, 1.4, 1.6
00287         num_lambdas=3;
00288         lambda_vals[0]=.6;
00289         lambda_vals[1]=1.4;
00290         lambda_vals[2]=1.6;
00291     }
00292 
00293     // Start constructing the list of optional heuristics we will we use 
00294     if(nlist_size==0)
00295         // No neighbor lists
00296         neighbor_lists=0;
00297     else     
00298         neighbor_lists=VRPH_USE_NEIGHBOR_LIST;
00299     heuristics|=neighbor_lists;
00300 
00301     if(has_heuristics==false)
00302         // Use default set of operators
00303         heuristics|=(ONE_POINT_MOVE|TWO_POINT_MOVE|TWO_OPT);
00304     
00305 
00306     // Add in Tabu Search if requested
00307     heuristics+=tabu;
00308 
00309     // Declare a CW object of the right size
00310     ClarkeWright CW(n);
00311 
00312     if(has_fixed_edges_file)
00313     {
00314         V.read_fixed_edges(fixed_edges_file);
00315         if(has_fixed_edges_file)
00316             heuristics |= VRPH_FIXED_EDGES;
00317     }
00318 
00319     start=clock();
00320     if(!has_sol_file)
00321     {
00322         // No solution imported - start from scratch
00323         for(i=0;i<num_lambdas;i++)
00324         {
00325             // Empty the solution warehouse and set nodes to unrouted
00326             V.reset();
00327 
00328             // Construct a new Clarke Wright solution
00329             CW.Construct(&V,lambda_vals[i], false);
00330             CW.has_savings_matrix=false;    
00331 
00332             if(V.get_total_route_length()-V.get_total_service_time() < final_obj)
00333             {
00334                 final_obj=V.get_total_route_length()-V.get_total_service_time();
00335                 V.export_canonical_solution_buff(final_sol);
00336             }
00337 
00338             if(verbose)
00339                 printf("CW solution %d[L=%1.4f]: %5.4f\n",i,lambda_vals[i], V.get_total_route_length());
00340 
00341             // Run the record-to-record travel algorithm with the given parameters
00342             V.RTR_solve(heuristics, intensity, max_tries, num_perturbs, dev, nlist_size, 
00343                 perturb_type, accept_type, verbose);
00344         
00345             // Check for a new global best solution - recall the best solution found
00346             V.get_best_sol_buff(my_sol_buff);
00347             V.import_solution_buff(my_sol_buff);
00348             if(V.get_total_route_length()-V.get_total_service_time() < final_obj)
00349             {
00350                 final_obj = V.get_total_route_length()-V.get_total_service_time();
00351                 V.export_canonical_solution_buff(final_sol);
00352             }
00353             
00354             if(verbose)
00355                 printf("%5.2f\n",V.get_best_total_route_length()-V.get_total_service_time());
00356 
00357             // Reset best
00358             V.set_best_total_route_length(VRP_INFINITY);
00359         }
00360     }
00361     else
00362     {
00363         // Import a solution from the file and call it the best so far
00364         V.read_solution_file(sol_file);
00365         printf("Read in solution:\n");
00366         V.show_routes();
00367         // CSG - is the line below necessary?
00368         //V.export_solution_buff(V.best_sol_buff);
00369         V.set_best_total_route_length(V.get_total_route_length());
00370 
00371         // Now improve it
00372         V.RTR_solve(heuristics, intensity, max_tries, num_perturbs, dev, nlist_size, 
00373             perturb_type, accept_type,verbose);
00374 
00375         V.export_canonical_solution_buff(final_sol);
00376     }
00377 
00378     stop=clock();
00379    
00380     // Restore the best solution found
00381     V.import_solution_buff(final_sol);
00382     
00383     elapsed=(double)(stop-start)/CLOCKS_PER_SEC;
00384   
00385     if(verbose)
00386     {
00387         V.summary();
00388         V.show_routes();
00389         V.print_stats();
00390         printf("\n");
00391     }
00392 
00393     if(has_outfile)
00394         V.write_solution_file(out);
00395 
00396     if(has_plot_file)
00397     {
00398 #if !HAS_PLPLOT
00399         fprintf(stderr,"Need PLPLOT to plot solution\n");
00400         exit(-1);
00401 #endif
00402 
00403         bool plot_success=V.plot(plot_file);
00404         if(plot_success && do_pdf)
00405         {
00406             char pdf_string[VRPH_STRING_SIZE];
00407             sprintf(pdf_string,"%s %s",VRPH_EPS_EXE,plot_file);
00408             system(pdf_string);
00409         }
00410     }
00411 
00412     // Print results to stdout
00413     printf("%d %5.3f %5.2f",V.get_total_number_of_routes(),
00414         V.get_total_route_length()-V.get_total_service_time(),
00415         elapsed);
00416     if(V.get_best_known()>0 && V.get_best_known()<VRP_INFINITY)
00417         printf(" %1.3f\n",(V.get_total_route_length()-V.get_total_service_time())/V.get_best_known());
00418     else
00419         printf("\n");
00420 
00421     delete [] my_sol_buff;
00422     delete [] final_sol;
00423 
00424     return 0;
00425 
00426     
00427 
00428 }
00429 
00430