VRPH  1.0
src/apps/vrp_ej.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 #define RANDOM 0
00016 #define REGRET 1
00017 
00018 int main(int argc, char *argv[])
00019 {
00025 
00026     VRPH_version();
00027 
00028     char infile[VRPH_STRING_SIZE];
00029     char solfile[VRPH_STRING_SIZE];
00030     char outfile[VRPH_STRING_SIZE];
00031     bool has_outfile=false, has_solfile=false;
00032     int i,j,n,num_ejected, num_trials, num_heur_sols, num_improvements;
00033     int *ejected_buff, *heur_solbuff, *ej_solbuff, *best_solbuff;
00034     int method=-1;
00035     clock_t start, stop;
00036 
00037     // Default values
00038     bool verbose=false;
00039 
00040     if(argc < 7 || (strncmp(argv[1],"-help",5)==0 || strcmp(argv[1],"-h")==0 || strcmp(argv[1],"--h")==0))
00041     {        
00042         fprintf(stderr,"Usage: %s -f vrp_file -j num_ejected -t num_trials -m method [-s sol_file -out out_file -n num_heur_sols -v]\n",argv[0]);
00043         fprintf(stderr,
00044             "\t num_ejected should be something less than 20 or so\n"
00045             "\t num_trials can be fairly large as the procedure is fast (say 1000)\n"
00046             "\t method must be 0 (RANDOM search), 1 (REGRET search)\n"
00047             "\t Options:\n"
00048             "\t Can start with a solution in sol_file or it will generate an initial\n"
00049             "\t    solution for you\n"
00050             "\t Can write the final best solution discovered to out_file\n"
00051             "\t Adding -v will print verbose output\n");
00052         exit(-1);
00053     }
00054 
00055     bool has_filename=false;
00056     for(i=1;i<argc;i++)
00057     {
00058         if(strcmp(argv[i],"-f")==0)
00059         {
00060             strcpy(infile,argv[i+1]);
00061             has_filename=true;            
00062         }
00063     }
00064 
00065     if(has_filename==false)
00066         report_error("No input file given\n");
00067 
00068     n=VRPGetDimension(infile);
00069     // Get # of non-VRPH_DEPOT nodes
00070     VRP V(n);
00071 
00072     // Declare some buffers for solutions, nodes to eject, etc.
00073     ejected_buff=new int[n+2];
00074     heur_solbuff=new int[n+2];
00075     ej_solbuff=new int[n+2];
00076     best_solbuff=new int[n+2];
00077     num_ejected=num_trials=0;
00078     num_heur_sols=1;
00079 
00080     // Now process the options
00081     for(i=1;i<argc;i++)
00082     {
00083         if(strcmp(argv[i],"-v")==0)
00084             verbose=true;
00085 
00086         if(strcmp(argv[i],"-j")==0)
00087             num_ejected=atoi(argv[i+1]);
00088 
00089         if(strcmp(argv[i],"-n")==0)
00090             num_heur_sols=atoi(argv[i+1]);
00091 
00092         if(strcmp(argv[i],"-s")==0)
00093         {
00094             has_solfile=true;
00095             num_heur_sols=0;
00096             strcpy(solfile,argv[i+1]);
00097         }
00098 
00099         if(strcmp(argv[i],"-t")==0)
00100             num_trials=atoi(argv[i+1]);
00101 
00102         if(strcmp(argv[i],"-out")==0)
00103         {
00104             has_outfile=true;
00105             strcpy(outfile,argv[i+1]);
00106         }
00107 
00108         if(strcmp(argv[i],"-m")==0)
00109         {
00110             method=atoi(argv[i+1]);
00111             if(method!=RANDOM && method!=REGRET)
00112             {
00113                 fprintf(stderr,"Method must be either 0 (RANDOM search) or 1 (REGRET search)\n");
00114                 exit(-1);
00115             }
00116         }
00117     }
00118 
00119 
00120     // Load the problem data
00121     V.read_TSPLIB_file(infile);    
00122     ClarkeWright CW(n);
00123     double heur1;
00124     double best_heur_sol=VRP_INFINITY;
00125     double best_final_sol=VRP_INFINITY;
00126     double heur_time=0,ej_time=0;
00127     double lambda;
00128     double *heur_sols=new double[num_heur_sols];
00129     double *final_sols=new double[num_heur_sols];
00130 
00131     for(i=0;i<num_heur_sols;i++)
00132     {
00133         // Generate a solution w/ RTR that should be a good starting point for the search
00134         start=clock();
00135         lambda=.5+1.5*lcgrand(0);
00136         // Start with a clean VRP object
00137         V.reset();
00138         CW.Construct(&V, lambda, false);
00139         if(verbose)
00140             printf("CW solution %d[%5.3f]: %f\n",i,lambda,V.get_total_route_length()-V.get_total_service_time());
00141         V.RTR_solve(ONE_POINT_MOVE+TWO_POINT_MOVE+TWO_OPT+VRPH_USE_NEIGHBOR_LIST,30,5,2,.01,30,VRPH_LI_PERTURB,
00142             VRPH_FIRST_ACCEPT,false);
00143         stop=clock();
00144         heur_time+=((double)(stop-start))/CLOCKS_PER_SEC;
00145         heur_sols[i]=V.get_total_route_length()-V.get_total_service_time();
00146         if(verbose)
00147             printf("RTR solution %d: %f\n",i,V.get_total_route_length()-V.get_total_service_time());
00148         
00149         // Record the value of the first solution
00150         if(i==0)
00151             heur1=V.get_total_route_length()-V.get_total_service_time();
00152 
00153         if(i==0 || V.get_total_route_length()-V.get_total_service_time() <= best_heur_sol)
00154         {
00155             best_heur_sol = V.get_total_route_length()-V.get_total_service_time();
00156             if(verbose)
00157                 printf("Found best sol: %f\n",V.get_total_route_length()-V.get_total_service_time());
00158         }
00159         // Export this solution to ej_solbuff
00160         V.export_solution_buff(ej_solbuff);
00161 
00162         double heur_obj=V.get_total_route_length()-V.get_total_service_time();
00163         if(verbose)
00164             printf("Starting ejection routines with solution %f\n",heur_obj);
00165 
00166         num_improvements=0;
00167         double orig_obj=heur_obj;
00168         start=clock();
00169         for(j=0;j<num_trials;j++)
00170         {
00171             // Start with the best solution derived from this RTR run
00172             V.import_solution_buff(ej_solbuff);
00173             // Now pick random nodes to eject - start by finding a random non-VRPH_DEPOT node
00174             int r=VRPH_DEPOT;
00175             while(r==VRPH_DEPOT)
00176                 r=(int)(lcgrand(11)*(n-1));
00177 
00178             // Eject a set of random nodes near node r
00179             V.eject_neighborhood(r,num_ejected,ejected_buff);
00180 
00181             if(method==REGRET)
00182             {
00183                 // Inject them using "cheapest insertion with regret"
00184                 V.inject_set(num_ejected, ejected_buff,VRPH_REGRET_SEARCH, 50);
00185                 double regret_obj=V.get_total_route_length()-V.get_total_service_time();
00186                 if(regret_obj<orig_obj)
00187                 {
00188                     if(verbose)
00189                         printf("Attempt %04d:  REGRET improved original: %f<%f\n",j, regret_obj,orig_obj);
00190                     V.export_solution_buff(ej_solbuff);
00191                     orig_obj=regret_obj;
00192                     num_improvements++;
00193                 }
00194             }
00195 
00196             if(method==RANDOM)
00197             {
00198                 // Inject them again using a random order and cheapest insertion
00199                 V.inject_set(num_ejected, ejected_buff,VRPH_RANDOM_SEARCH, 50);        
00200                 double random_obj=V.get_total_route_length();
00201                 if(random_obj<orig_obj)
00202                 {
00203                    if(verbose)
00204                         printf("Attempt %04d:  RANDOM improved original: %f<%f\n",j, random_obj,orig_obj);
00205                     V.export_solution_buff(ej_solbuff);
00206                     orig_obj=random_obj;
00207                     num_improvements++;
00208                 }
00209             }    
00210         }
00211         // end j loop
00212         stop=clock();
00213         ej_time+=(double)(stop-start)/CLOCKS_PER_SEC;
00214         
00215         // Import the best solution we found
00216         V.import_solution_buff(ej_solbuff);
00217         if(V.get_total_route_length()-V.get_total_service_time()<best_final_sol)
00218         {
00219             best_final_sol=V.get_total_route_length()-V.get_total_service_time();
00220             V.export_solution_buff(best_solbuff);
00221         }
00222         final_sols[i]=V.get_total_route_length()-V.get_total_service_time();
00223     }
00224 
00225     // Restore the best solution found
00226     V.import_solution_buff(best_solbuff);
00227 
00228 
00229     // Output is
00230     // heur[i] ej[i]
00231     // best_heur best_ej heur_time ej_time
00232     for(i=0;i<num_heur_sols;i++)
00233         printf("%5.3f %5.3f\n",heur_sols[i], final_sols[i]);
00234     printf("%5.3f %5.3f %5.3f %5.3f\n",best_heur_sol,
00235         V.get_total_route_length()-V.get_total_service_time(),heur_time,ej_time);
00236 
00237     if(has_outfile)
00238         V.write_solution_file(outfile);
00239 
00240 
00241     // Clean up
00242     delete [] ejected_buff;
00243     delete [] heur_solbuff;
00244     delete [] ej_solbuff;
00245     delete [] best_solbuff;
00246     delete [] heur_sols;
00247     delete [] final_sols;
00248 
00249     return 0;
00250 }