VRPH  1.0
src/apps/vrp_sa.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 int main(int argc, char *argv[])
00016 {
00021 
00022     VRPH_version();
00023 
00024     char in[VRPH_STRING_SIZE];
00025     char out[VRPH_STRING_SIZE];
00026     char plotfile[VRPH_STRING_SIZE];
00027     char solfile[VRPH_STRING_SIZE];
00028     int i;
00029     int n;
00030 
00031     // Default values
00032     bool verbose=false;
00033     double starting_temperature = 2;
00034     double cooling_ratio = .99;
00035     int num_loops=200;
00036     int num_lambdas=3;
00037     int iters_per_loop=2;
00038     int nlist_size=10;
00039     int perturb_type=VRPH_LI_PERTURB ;
00040 
00041     double lambda_vals[VRPH_MAX_NUM_LAMBDAS];
00042     bool new_lambdas=false;
00043     bool has_heuristics=false;
00044     bool has_outfile=false;
00045     bool has_plotfile=false;
00046     bool has_solfile=false;
00047     int heuristics=0;
00048 
00049     if(argc<2 || (strncmp(argv[1],"-help",5)==0)||(strncmp(argv[1],"--help",6)==0)||(strncmp(argv[1],"-h",2)==0))
00050     {        
00051         fprintf(stderr,"Usage: %s -f <vrp_input_file> [options]\n",argv[0]);
00052         fprintf(stderr,"Options:\n");
00053 
00054         fprintf(stderr,"\t-help prints this help message\n"); 
00055 
00056         fprintf(stderr,"\t-sol <solfile> begins with an existing solution contained\n");
00057         fprintf(stderr,"\t\t in solfile.\n");
00058 
00059         fprintf(stderr,"\t-v prints verbose output to stdout\n");
00060 
00061         fprintf(stderr,"\t-i <num_iters> runs the SA procedure for num_iters iterations\n");
00062         fprintf(stderr,"\t\t before cooling\n");
00063 
00064         fprintf(stderr,"\t-n <num_loops> runs the SA procedure a total of num_loops times\n");
00065 
00066         fprintf(stderr,"\t-t <starting_temperature> runs the SA procedure starting at\n");
00067         fprintf(stderr,"\t\t this temperature\n");
00068 
00069         fprintf(stderr,"\t-c <cooling_ratio> runs the SA by decreasing the temperature by a\n");
00070         fprintf(stderr,"\t\t multiplicative factor of cooling_ratio every num_iters moves\n");
00071 
00072         fprintf(stderr,"\t-h <heuristic> applies the specified heuristics (can be repeated)\n");
00073         fprintf(stderr,"\t\t default is ONE_POINT_MOVE, TWO_POINT_MOVE, and TWO_OPT\n");
00074         fprintf(stderr,"\t\t others available are OR_OPT, THREE_OPT, and CROSS_EXCHANGE\n");
00075         fprintf(stderr,"\t\t Example: -h OR_OPT -h THREE_OPT -h TWO_OPT\n");
00076 
00077         fprintf(stderr,"\t-l <num_lambdas> runs the SA procedure from num_lambdas\n");
00078         fprintf(stderr,"\t\t different initial CW solutions using a random lambda chosen\n");
00079         fprintf(stderr,"\t\t from (0.5,2.0)\n");
00080         fprintf(stderr,"\t\t default is to use lambda in (.6, 1.4, 1.6).\n");
00081 
00082         fprintf(stderr,"\t-s <nlist_size> uses the nlist_size nearest neighbors in the search\n");
00083         fprintf(stderr,"\t\t (default is 40).\n");
00084 
00085         fprintf(stderr,"\t-o <out_file> writes the solution to the provided file\n");
00086         fprintf(stderr,"\t-plot <plot_file> plots the best solution to the provided file\n");
00087         exit(-1);
00088     }
00089 
00090 
00091     bool has_filename=false;
00092     for(i=1;i<argc;i++)
00093     {
00094         if(strcmp(argv[i],"-f")==0)
00095         {
00096             // Get the input file name
00097             strncpy(in,argv[i+1],strlen(argv[i+1]));
00098             in[strlen(argv[i+1])]='\0';
00099             has_filename=true;
00100         }
00101     }
00102     if(has_filename==false)
00103     {
00104         fprintf(stderr,"No input file given\nUsage: %s -f <filename> [options]\n",argv[0]);
00105         exit(-1);
00106     }
00107 
00108     n=VRPGetDimension(in);
00109     VRP V(n);
00110 
00111     // Now process the options
00112     for(i=1;i<argc;i++)
00113     {
00114         if(strcmp(argv[i],"-v")==0)
00115             verbose=true;
00116 
00117         if(strcmp(argv[i],"-t")==0)
00118             starting_temperature=(double)(atof(argv[i+1]));
00119 
00120         if(strcmp(argv[i],"-i")==0)
00121             iters_per_loop=atoi(argv[i+1]);
00122 
00123         if(strcmp(argv[i],"-n")==0)
00124             num_loops=atoi(argv[i+1]);
00125 
00126         if(strcmp(argv[i],"-h")==0)
00127         {
00128             has_heuristics=true;
00129             if(strcmp(argv[i+1],"ONE_POINT_MOVE")==0)
00130                 heuristics+=ONE_POINT_MOVE;
00131             if(strcmp(argv[i+1],"TWO_POINT_MOVE")==0)
00132                 heuristics+=TWO_POINT_MOVE;
00133             if(strcmp(argv[i+1],"TWO_OPT")==0)
00134                 heuristics+=TWO_OPT;
00135             if(strcmp(argv[i+1],"OR_OPT")==0)
00136                 heuristics+=OR_OPT;
00137             if(strcmp(argv[i+1],"THREE_OPT")==0)
00138                 heuristics+=THREE_OPT;
00139             if(strcmp(argv[i+1],"CROSS_EXCHANGE")==0)
00140                 heuristics+=CROSS_EXCHANGE;
00141             if(strcmp(argv[i+1],"THREE_POINT_MOVE")==0)
00142                 heuristics+=THREE_POINT_MOVE;
00143         }
00144 
00145         if(strcmp(argv[i],"-l")==0)
00146         {
00147             new_lambdas=true;
00148             num_lambdas = atoi(argv[i+1]);
00149 
00150             if(num_lambdas>VRPH_MAX_NUM_LAMBDAS)
00151             {
00152                 fprintf(stderr,"%d>VRPH_MAX_NUM_LAMBDAS\n",num_lambdas);
00153                 exit(-1);
00154             }
00155 
00156             // Fill the array with random values
00157             printf("Creating %d random lambdas\n",num_lambdas);
00158             for(int j=0;j<num_lambdas;j++)
00159             {
00160                 // Generate a random lambda in (0.5,2)
00161                 lambda_vals[j] = 0.5 + 1.5*((double)lcgrand(0));
00162             }
00163         }
00164 
00165         if(strcmp(argv[i],"-sol")==0)
00166         {
00167             has_solfile=true;
00168             strcpy(solfile,argv[i+1]);
00169         }
00170 
00171         if(strcmp(argv[i],"-c")==0)
00172             cooling_ratio=(double)(atof(argv[i+1]));
00173 
00174         if(strcmp(argv[i],"-s")==0)
00175             nlist_size=atoi(argv[i+1]);
00176 
00177         if(strcmp(argv[i],"-p")==0)
00178         {
00179             perturb_type=atoi(argv[i+1]);
00180             if(perturb_type!=0 && perturb_type!=1)
00181             {
00182                 fprintf(stderr,"Perturb type must be 0 or 1!\n");
00183                 exit(-1);
00184             }
00185         }
00186 
00187         if(strcmp(argv[i],"-o")==0)
00188         {
00189             has_outfile=true;
00190             strcpy(out,argv[i+1]);
00191 
00192         }
00193 
00194         if(strcmp(argv[i],"-plot")==0)
00195         {
00196             has_plotfile=true;
00197             strcpy(plotfile,argv[i+1]);
00198 
00199         }
00200 
00201     }
00202 
00203     if(new_lambdas==false)
00204     {
00205         num_lambdas=3;
00206         lambda_vals[0]=.6;
00207         lambda_vals[1]=1.4;
00208         lambda_vals[2]=1.6;
00209     }
00210 
00211     if(has_heuristics==false)
00212         heuristics=ONE_POINT_MOVE+TWO_POINT_MOVE+TWO_OPT; //default
00213 
00214 
00215     // Load the problem data
00216     V.read_TSPLIB_file(in);
00217 
00218     // Create the neighbor_lists-we may use a smaller size depending on the parameter
00219     // but we have the largest possible here...
00220     V.create_neighbor_lists(VRPH_MIN(MAX_NEIGHBORLIST_SIZE,n));
00221     ClarkeWright CW(n);
00222 
00223     double best_obj=VRP_INFINITY;
00224     double this_obj, start_obj;
00225     int *best_sol=new int[n+2];
00226 
00227     time_t start=clock();
00228     if(has_solfile == false)
00229     {
00230         for(i=0;i<num_lambdas;i++)
00231         {
00232             CW.Construct(&V,lambda_vals[i], false);
00233 
00234             if(verbose)
00235                 printf("CW[%f] solution: %f\n",lambda_vals[i], V.get_total_route_length());
00236 
00237             this_obj = V.SA_solve(heuristics, starting_temperature, cooling_ratio, iters_per_loop,
00238                 num_loops, nlist_size, verbose);
00239 
00240             if(V.get_best_total_route_length()<best_obj)
00241             {
00242                 best_obj=V.get_best_total_route_length();
00243                 V.export_canonical_solution_buff(best_sol);
00244             }
00245 
00246             if(verbose)
00247                 printf("Improved solution: %f\n",this_obj);        
00248 
00249         }
00250     }
00251     else
00252     {
00253         V.read_solution_file(solfile);
00254         start_obj=V.get_total_route_length();
00255         this_obj = V.SA_solve(heuristics, starting_temperature, cooling_ratio, iters_per_loop,
00256             num_loops, nlist_size, verbose);
00257         if(V.get_best_total_route_length()<best_obj)
00258         {
00259             best_obj=V.get_best_total_route_length();
00260             V.export_canonical_solution_buff(best_sol);
00261         }
00262         if(verbose)
00263             printf("Improved solution: %f\n",this_obj);    
00264 
00265     }
00266 
00267     // Restore the best solution found
00268     V.import_solution_buff(best_sol);
00269 
00270     delete [] best_sol;
00271 
00272     if(has_outfile)
00273         V.write_solution_file(out);
00274     best_obj=this_obj;
00275 
00276     if(verbose)
00277         printf("Solution before cleaning individual routes: %5.3f\n",V.get_total_route_length()-
00278         V.get_total_service_time());
00279     // Clean up the individual routes since the SA routine doesn't do this for us
00280     for(i=1;i<=V.get_total_number_of_routes();i++)
00281         V.clean_route(i,ONE_POINT_MOVE+TWO_POINT_MOVE+TWO_OPT+THREE_OPT+THREE_POINT_MOVE);
00282     if(verbose)
00283     {
00284         printf("Solution after cleaning individual routes: %5.3f\n",V.get_total_route_length()-
00285             V.get_total_service_time());
00286         V.summary();
00287         V.print_stats();
00288     }
00289 
00290     if(has_plotfile)
00291     {
00292 #if !HAS_PLPLOT
00293         fprintf(stderr,"Need PLPLOT to plot solution\n");
00294         exit(-1);
00295 #endif
00296 
00297         V.plot(plotfile);
00298 
00299     }
00300 
00301     time_t stop=clock();
00302     double elapsed=(double)(stop-start)/CLOCKS_PER_SEC;
00303     // Print results to stdout
00304     printf("%d %5.3f %5.2f",V.get_total_number_of_routes(),
00305         V.get_total_route_length()-V.get_total_service_time(),
00306         elapsed);
00307     if(V.get_best_known()>0 && V.get_best_known()<VRP_INFINITY)
00308         printf(" %1.3f\n",(V.get_total_route_length()-V.get_total_service_time())/V.get_best_known());
00309     else
00310         printf("\n");
00311 
00312     return 0;
00313 }
00314 
00315