VRPH  1.0
inc/VRP.h
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 #ifndef _VRP_H
00014 #define _VRP_H
00015 
00016 // VRP class
00017 class VRP
00018 {
00019 
00020     friend class OnePointMove;
00021     friend class TwoPointMove;
00022     friend class ThreePointMove;
00023     friend class TwoOpt;
00024     friend class ThreeOpt;
00025     friend class OrOpt;
00026     friend class CrossExchange;
00027 
00028     friend class Postsert;
00029     friend class Presert;
00030     friend class MoveString;
00031     friend class Swap;
00032     friend class SwapEnds;
00033     friend class Concatenate;
00034     friend class Flip;
00035 
00036     friend class ClarkeWright;
00037     friend class Sweep;
00038 
00039 public:
00040     VRP(int n);
00041     // Constructor for problems with n non-VRPH_DEPOT nodes
00042     VRP(int n, int ndays);
00043     // Construct for problems with n non-VRPH_DEPOT nodes and num_days days
00044 
00045     // Destructor
00046     ~VRP();
00047 
00048     // TSPLIB file processing
00049     void read_TSPLIB_file(const char *infile);
00050     // Write problem instance
00051     void write_TSPLIB_file(const char *outfile);
00052 
00053     // Solution display/debugging
00054     void show_next_array();
00055     void show_pred_array();
00056     bool verify_routes(const char *message);
00057     bool check_fixed_edges(const char *message);
00058     void create_pred_array();
00059     void print_stats();
00060 
00061     // Files (read/write)
00062     void write_solution_file(const char *filename);
00063     void write_solutions(int num_sols, const char *filename);
00064     void write_tex_file(const char *filename);
00065     void read_solution_file(const char *filename);
00066     int read_fixed_edges(const char *filename);
00067 
00068     // Solution buffers (import/export)
00069     void export_solution_buff(int *sol_buff);
00070     void import_solution_buff(int *sol_buff);
00071     void export_canonical_solution_buff(int *sol_buff);
00072 
00073     // Solution display
00074     void show_routes();
00075     void show_route(int k);
00076     void summary();
00077 
00078     // Removes all solutions from memory and sets all nodes to unrouted
00079     void reset();
00080 
00081     // Graphics - only meaningful with PLPlot
00082     bool plot(const char *filename, int options, int orientation);
00083     bool plot(const char *filename);
00084     bool plot_route(int r, const char *filename);
00085 
00086     // Copying
00087     bool clone(VRP *W);
00088 
00089     // Solvers
00090     double RTR_solve(int heuristics, int intensity, int max_stuck, int num_perturbs,
00091         double dev, int nlist_size, int perturb_type, int accept_type, bool verbose);
00092 
00093     double SA_solve(int heuristics, double start_temp, double cool_ratio,
00094         int iters_per_loop, int num_loops, int nlist_size, bool verbose);
00095 
00096     // The name of the problem (from TSPLIB file)
00097     char name[VRPH_STRING_SIZE];
00098 
00099     // For multi-day problems
00100     void set_daily_demands(int day);
00101     void set_daily_service_times(int day);
00102 
00103     // Creating default routes for CW, etc.
00104     bool create_default_routes();
00105     bool create_default_routes(int day);
00106 
00107     // Routines to remove and insert nodes into solution
00108     bool eject_node(int k);
00109     int inject_set(int num, int *nodelist, int rules, int attempts);
00110     void eject_neighborhood(int j, int num, int *nodelist);
00111 
00112     // Route operations
00113     void refresh_routes();
00114     void normalize_route_numbers();
00115     void update_route(int j, VRPRoute *R);
00116     void clean_route(int r, int heuristics);
00117     double split(double p);
00118     int split_routes(double p, int **ejected_routes, double *t);
00119     void add_route(int *route_buff);
00120     void append_route(int *sol_buff, int *route_buff);
00121     int intersect_solutions(int *new_sol, int **routes, int *sol1, int *sol2, int min_routes);
00122     int find_common_routes(int *sol1, int *sol2, int *route_nums);
00123 
00124     // Fixing edges
00125     void list_fixed_edges(int *fixed_list);
00126     void unfix_all();
00127     void fix_edge(int start, int end);
00128     void unfix_edge(int start, int end);
00129     void fix_string(int *node_string, int k);
00130 
00131     // Accessor functions for private data 
00132     int get_num_nodes();
00133     double get_total_route_length();
00134     double get_total_service_time();
00135     double get_best_sol_buff(int *sol_buff);
00136     double get_best_total_route_length();
00137     int get_total_number_of_routes();
00138     int get_num_original_nodes();
00139     int get_num_days();        // For multi-day VRPs
00140     double get_best_known();
00141     void set_best_total_route_length(double val);
00142     int get_max_veh_capacity();
00143     double get_max_route_length();
00144 
00145     // Places to store unique solutions and routes - uses internal hash table
00146     VRPSolutionWarehouse *solution_wh; // To store additional solutions
00147     VRPRouteWarehouse *route_wh;     // To store routes/columns
00148 
00149     // Distance matrix creation
00150     void create_distance_matrix(int type);
00151     // Neighbor list creation
00152     void create_neighbor_lists(int nsize);
00153 
00154     // Node injection/ejection
00155     bool perturb();
00156     bool eject_route(int r, int *route_buff);
00157     bool inject_node(int j);
00158 
00159     // Route reversal
00160     void reverse_route(int i);
00161 
00162     // Statistics
00163     int num_evaluations[NUM_HEURISTICS];
00164     int num_moves[NUM_HEURISTICS];
00165 
00166 private:  
00167 
00168     // Problem parameters, description, etc.
00169     int num_nodes;
00170     double total_route_length;
00171     double total_service_time;
00172     int *best_sol_buff;                // Place for the best solution to live
00173     double best_total_route_length;
00174     int total_number_of_routes;
00175     int num_original_nodes;
00176     double best_known;  // Record of the best known solution for benchmarks
00177     int num_days;        // For multi-day VRPs
00178     int problem_type;
00179     int total_demand;
00180     int max_veh_capacity;
00181     int orig_max_veh_capacity;
00182     double max_route_length;
00183     double min_route_length;
00184     double orig_max_route_length;
00185     int min_vehicles;    // Not currently used    
00186     bool has_service_times;
00187     double fixed_service_time;
00188     int edge_weight_type;
00189     int coord_type;
00190     int display_type;
00191     int edge_weight_format;
00192     int matrix_size;
00193     double balance_parameter;    // For VRPH_BALANCED problems
00194     int dummy_index;
00195     int neighbor_list_size;
00196     double temperature;            // For VRPH_SIMULATED_ANNEALING
00197     double cooling_ratio;
00198     
00199     bool symmetric;                 // To keep track of symmetric/asymmetric instances
00200                                     // Note! Asymmetric instances have received only 
00201                                     // limited testing!
00202     bool can_display;
00203 
00204     double **d;                    // The distance matrix d
00205     bool **fixed;                // Matrix to keep track of fixed edges
00206 
00207     class VRPNode *nodes;        // Array of nodes - contains coordinates, demand
00208     // amounts, etc.
00209 
00210     bool depot_normalized;        // Set to true if VRPH_DEPOT coords normalized to origin
00211     // for Euclidean problem.
00212 
00213     bool forbid_tiny_moves;        // Set to true to prevent potentially nonsense moves
00214     // that have a tiny (perhaps zero) effect on route length
00215 
00216     // Local search neighborhood creation
00217     bool create_search_neighborhood(int j, int rules);    
00218     int search_size;            
00219     int *search_space;            
00220 
00221     // Solution storage
00222     int *next_array;
00223     int *pred_array;
00224     int *route_num;
00225     bool *routed;            // Indicates whether the customer is in a route yet or not
00226 
00227     class VRPRoute *route;    // Array stores useful information about the routes in a solution
00228 
00229     // Tabu search - very limited testing so far!!
00230     class VRPTabuList *tabu_list;
00231     bool check_tabu_status(VRPMove *M, int *old_sol);
00232 
00233     double record;        // For RTR
00234     double deviation;    // For RTR
00235 
00236     double min_theta;
00237     double max_theta;    // Polar min/max
00238 
00239     int *current_sol_buff;  // Place for the current solution if desired
00240 
00241     // Accessing edge information
00242     bool before(int a, int b);
00243 
00244     // To handle infeasibilities
00245     bool check_feasibility(VRPViolation *VV);
00246     class VRPViolation violation;
00247     bool is_feasible(VRPMove *M, int rules);    
00248 
00249     // Solution manipulation
00250     bool postsert_dummy(int i);
00251     bool presert_dummy(int i);
00252     bool remove_dummy();
00253     bool osman_insert(int k, double alpha);
00254     int osman_perturb(int num, double alpha);
00255     bool insert_node(int j, int i, int k);
00256     void perturb_locations(double c);
00257     void find_cheapest_insertion(int j, int *edge, double *costs, int rules);    
00258     double insertion_cost(int u, int a, int b);
00259     double ejection_cost(int u);
00260     void update(VRPMove *M);
00261 
00262     // Splitting VRP instances
00263     void compute_route_center(int r);
00264     void find_neighboring_routes();
00265 
00266     // Solution memory
00267     void capture_best_solution();
00268     void update_solution_wh();    
00269 
00270     // Solution information
00271     bool get_segment_info(int a, int b, struct VRPSegment *S);
00272     double get_distance_between(int a, int b);
00273     int get_string_end(int a, int len);
00274     int count_num_routes();
00275     void update_arrival_times();
00276     bool  check_move(VRPMove *M, int rules);
00277 
00278     // Savings evaluation - inline this to speed things up 
00279     inline bool check_savings(VRPMove *M, int rules){
00285 
00286 #if VRPH_FORBID_TINY_MOVES
00287         if(M->savings>-VRPH_EPSILON && M->savings < VRPH_EPSILON)
00288             return false;
00289 #endif
00290 
00291         if( M->savings < -VRPH_EPSILON )
00292         {
00293             M->evaluated_savings=true;
00294             return true;
00295         }
00296         // The order needs to be changed if we eventually add additional rules
00297         // that do not always accept improving moves!!
00298 
00299         if( (rules & VRPH_FREE)  )
00300             return true;
00301 
00302 
00303         if( (rules & VRPH_DOWNHILL) )
00304         {
00305             if(M->savings>=-VRPH_EPSILON )
00306             {
00307                 M->evaluated_savings=true;
00308                 return false;
00309             }
00310         }
00311 
00312         if( (rules & VRPH_RECORD_TO_RECORD) )
00313         {
00314             if(M->savings<-VRPH_EPSILON)
00315             {
00316                 M->evaluated_savings=true;
00317                 return true;
00318             }
00319             else
00320             {
00321 
00322                 if(has_service_times==false)
00323                 {
00324                     if( (total_route_length+M->savings<= (1+deviation)*record) )
00325                     {
00326                         M->evaluated_savings=true;
00327                         return true;
00328                     }
00329                     else
00330                         return false;
00331                 }
00332                 else
00333                 {
00334                     // We have service times so remove the service time from the
00335                     // deviation calculation
00336                     if( ((total_route_length - total_service_time) + M->savings <= 
00337                         ((1+deviation)*(record-total_service_time))) )
00338                     {
00339                         M->evaluated_savings=true;
00340                         return true;
00341                     }
00342                     else
00343                         return false;
00344                 }
00345 
00346 
00347             }
00348 
00349         }
00350 
00351         if( rules & VRPH_SIMULATED_ANNEALING )
00352         {
00353             if( exp( - ((M->savings) / this->temperature)) > lcgrand(0) )
00354             {
00355                 M->evaluated_savings=true;
00356                 return true;
00357             }
00358             else
00359                 return false;
00360 
00361         }
00362 
00363         return false;
00364 
00365 
00366     };
00367 
00368 
00369 
00370 
00371 };
00372 
00373 #endif
00374 
00375