VRP Class Reference

#include <VRP.h>

List of all members.

Public Member Functions

 VRP (int n)
 VRP (int n, int ndays)
 ~VRP ()
void read_TSPLIB_file (const char *infile)
void write_TSPLIB_file (const char *outfile)
void show_next_array ()
void show_pred_array ()
bool verify_routes (const char *message)
bool check_fixed_edges (const char *message)
void create_pred_array ()
void print_stats ()
void write_solution_file (const char *filename)
void write_solutions (int num_sols, const char *filename)
void write_tex_file (const char *filename)
void read_solution_file (const char *filename)
int read_fixed_edges (const char *filename)
void export_solution_buff (int *sol_buff)
void import_solution_buff (int *sol_buff)
void export_canonical_solution_buff (int *sol_buff)
void show_routes ()
void show_route (int k)
void summary ()
void reset ()
bool plot (const char *filename, int options, int orientation)
bool plot (const char *filename)
bool plot_route (int r, const char *filename)
bool clone (VRP *W)
double RTR_solve (int heuristics, int intensity, int max_stuck, int num_perturbs, double dev, int nlist_size, int perturb_type, int accept_type, bool verbose)
double SA_solve (int heuristics, double start_temp, double cool_ratio, int iters_per_loop, int num_loops, int nlist_size, bool verbose)
void set_daily_demands (int day)
void set_daily_service_times (int day)
bool create_default_routes ()
bool create_default_routes (int day)
bool eject_node (int k)
int inject_set (int num, int *nodelist, int rules, int attempts)
void eject_neighborhood (int j, int num, int *nodelist)
void refresh_routes ()
void normalize_route_numbers ()
void update_route (int j, VRPRoute *R)
void clean_route (int r, int heuristics)
double split (double p)
int split_routes (double p, int **ejected_routes, double *t)
void add_route (int *route_buff)
void append_route (int *sol_buff, int *route_buff)
int intersect_solutions (int *new_sol, int **routes, int *sol1, int *sol2, int min_routes)
int find_common_routes (int *sol1, int *sol2, int *route_nums)
void list_fixed_edges (int *fixed_list)
void unfix_all ()
void fix_edge (int start, int end)
void unfix_edge (int start, int end)
void fix_string (int *node_string, int k)
int get_num_nodes ()
double get_total_route_length ()
double get_total_service_time ()
double get_best_sol_buff (int *sol_buff)
double get_best_total_route_length ()
int get_total_number_of_routes ()
int get_num_original_nodes ()
int get_num_days ()
double get_best_known ()
void set_best_total_route_length (double val)
int get_max_veh_capacity ()
double get_max_route_length ()
void create_distance_matrix (int type)
void create_neighbor_lists (int nsize)
bool perturb ()
bool eject_route (int r, int *route_buff)
bool inject_node (int j)
void reverse_route (int i)

Public Attributes

char name [VRPH_STRING_SIZE]
VRPSolutionWarehousesolution_wh
VRPRouteWarehouseroute_wh
int num_evaluations [NUM_HEURISTICS]
int num_moves [NUM_HEURISTICS]

Private Member Functions

bool create_search_neighborhood (int j, int rules)
bool check_tabu_status (VRPMove *M, int *old_sol)
bool before (int a, int b)
bool check_feasibility (VRPViolation *VV)
bool is_feasible (VRPMove *M, int rules)
bool postsert_dummy (int i)
bool presert_dummy (int i)
bool remove_dummy ()
bool osman_insert (int k, double alpha)
int osman_perturb (int num, double alpha)
bool insert_node (int j, int i, int k)
void perturb_locations (double c)
void find_cheapest_insertion (int j, int *edge, double *costs, int rules)
double insertion_cost (int u, int a, int b)
double ejection_cost (int u)
void update (VRPMove *M)
void compute_route_center (int r)
void find_neighboring_routes ()
void capture_best_solution ()
void update_solution_wh ()
bool get_segment_info (int a, int b, struct VRPSegment *S)
double get_distance_between (int a, int b)
int get_string_end (int a, int len)
int count_num_routes ()
void update_arrival_times ()
bool check_move (VRPMove *M, int rules)
bool check_savings (VRPMove *M, int rules)

Private Attributes

int num_nodes
double total_route_length
double total_service_time
int * best_sol_buff
double best_total_route_length
int total_number_of_routes
int num_original_nodes
double best_known
int num_days
int problem_type
int total_demand
int max_veh_capacity
int orig_max_veh_capacity
double max_route_length
double min_route_length
double orig_max_route_length
int min_vehicles
bool has_service_times
double fixed_service_time
int edge_weight_type
int coord_type
int display_type
int edge_weight_format
int matrix_size
double balance_parameter
int dummy_index
int neighbor_list_size
double temperature
double cooling_ratio
bool symmetric
bool can_display
double ** d
bool ** fixed
class VRPNodenodes
bool depot_normalized
bool forbid_tiny_moves
int search_size
int * search_space
int * next_array
int * pred_array
int * route_num
bool * routed
class VRPRouteroute
class VRPTabuListtabu_list
double record
double deviation
double min_theta
double max_theta
int * current_sol_buff
class VRPViolation violation

Friends

class OnePointMove
class TwoPointMove
class ThreePointMove
class TwoOpt
class ThreeOpt
class OrOpt
class CrossExchange
class Postsert
class Presert
class MoveString
class Swap
class SwapEnds
class Concatenate
class Flip
class ClarkeWright
class Sweep


Detailed Description

Definition at line 17 of file VRP.h.


Constructor & Destructor Documentation

VRP::VRP ( int  n  ) 

Constructor for an n-node problem.

Definition at line 24 of file VRP.cpp.

VRP::VRP ( int  n,
int  ndays 
)

Constructor for an n-node, ndays-day problem.

Definition at line 107 of file VRP.cpp.

VRP::~VRP (  ) 

Destructor for the VRP.

Definition at line 194 of file VRP.cpp.


Member Function Documentation

void VRP::add_route ( int *  route_buff  ) 

Adds the route in the provided buffer to the solution. The new route should not have any nodes in common with the existing solution! The route_buff[] should be terminated with a -1.

Definition at line 3747 of file VRP.cpp.

void VRP::append_route ( int *  sol_buff,
int *  route_buff 
)

Appends the single route contained in route_buff[] (which ends in a -1) to the solution buffer sol_buff, updating the first entry in sol_buff which is the # of nodes in the solution. Does NOT import the resulting solution and assumes that route_buff and sol_buff are disjoint.

Definition at line 3790 of file VRP.cpp.

bool VRP::before ( int  a,
int  b 
) [private]

This function returns TRUE if a comes before b in their route and FALSE if b is before a. An error is reported if a and b are in different routes. Should be used sparingly as it loops and can be slow for large routes.

Definition at line 3082 of file VRP.cpp.

void VRP::capture_best_solution (  )  [private]

Determines if the current solution is the best found so far.

Definition at line 3242 of file VRP.cpp.

bool VRP::check_feasibility ( VRPViolation VV  )  [private]

The function returns true if the routes are all feasible and false if any of them are infeasible, placing the worst violations in the VRPViolation VV

Definition at line 653 of file VRP.cpp.

bool VRP::check_fixed_edges ( const char *  message  ) 

Makes sure that all fixed edges are still in the solution. If fixed edges are missing from the solution, then some information is displayed and the provided message is printed before exiting.

Definition at line 4051 of file VRP.cpp.

bool VRP::check_move ( VRPMove M,
int  rules 
) [private]

Evaluates the move in terms of the rules. Can consider savings, as well as other aspects of the VRPMove M.

Definition at line 1763 of file VRP.cpp.

bool VRP::check_savings ( VRPMove M,
int  rules 
) [inline, private]

Evaluates the given savings in terms of the rules. The only part of the rules considered are things such as VRPH_DOWNHILL, VRPH_RECORD_TO_RECORD, VRPH_SIMULATED_ANNEALING

Definition at line 279 of file VRP.h.

bool VRP::check_tabu_status ( VRPMove M,
int *  old_sol 
) [private]

The tabu search rules is entirely route-based. We hash each of the affected routes and see if the values are in the tabu list. If the move is tabu, then we revert back to the old solution and return false. Otherwise, we allow the move and return true. When the move is allowed, we update the tabu list using a circular buffer.

Definition at line 4290 of file VRP.cpp.

void VRP::clean_route ( int  r,
int  heuristics 
)

Runs the provided set of heuristics on route r until a local minimum is reached.

Definition at line 2916 of file VRP.cpp.

bool VRP::clone ( VRP W  ) 

Copy Constructor for VRP.

Definition at line 317 of file VRP.cpp.

void VRP::compute_route_center ( int  r  )  [private]

Computes the mean x and y coord's of the nodes in a route, storing the information in the VRPRoute[] array

Definition at line 3158 of file VRP.cpp.

int VRP::count_num_routes (  )  [private]

Manually counts the # of routes in the current solution.

Definition at line 1452 of file VRP.cpp.

bool VRP::create_default_routes ( int  day  ) 

This function creates routes VRPH_DEPOT-i-VRPH_DEPOT for all nodes that require service on the provided day. Returns true if successful, false if the default routes violate some capacity or route length constraint.

Definition at line 1334 of file VRP.cpp.

bool VRP::create_default_routes (  ) 

This function creates routes VRPH_DEPOT-i-VRPH_DEPOT for all nodes i and properly initializes all the associated arrays. Returns true if successful, false if the default routes violate some capacity or route length constraint.

Definition at line 1208 of file VRP.cpp.

void VRP::create_distance_matrix ( int  type  ) 

Creates the O(n^2) size distance matrix for the provided data using the distance function referenced by type. If the type is EXPLICIT, then the entire distance matrix should be provided in the actual TSPLIB file.

Definition at line 370 of file VRP.cpp.

void VRP::create_neighbor_lists ( int  nsize  ) 

Creates the neighbor list of size nsize for each node including the VRPH_DEPOT.

Definition at line 406 of file VRP.cpp.

void VRP::create_pred_array (  ) 

This function creates a pred_array from the existing next_array

Definition at line 813 of file VRP.cpp.

bool VRP::create_search_neighborhood ( int  j,
int  rules 
) [private]

Creates the search_size and search_space fields for the current VRP in terms of the given node j and the rules.

Definition at line 2642 of file VRP.cpp.

void VRP::eject_neighborhood ( int  j,
int  num,
int *  nodelist 
)

Ejects num different randomly selected nodes that are in the vicinity of node j, placing the list of ejected nodes in the nodelist[] array. Node j is also ejected! The candidates for ejection are randomly chosen from the 2*num nearest neighbors of j.

Definition at line 2469 of file VRP.cpp.

bool VRP::eject_node ( int  k  ) 

This function removes node j from the current solution and adjusts the solution information appropriately.

Definition at line 1627 of file VRP.cpp.

bool VRP::eject_route ( int  r,
int *  route_buff 
)

Ejects all nodes from the current solution that are in route r. Places an ordered list of the ejected nodes in route_buff[].

Definition at line 1732 of file VRP.cpp.

double VRP::ejection_cost ( int  u  )  [private]

Returns the reduction in the objective function value obtained by ejecting u from the current solution.

Definition at line 2896 of file VRP.cpp.

void VRP::export_canonical_solution_buff ( int *  sol_buff  ) 

Puts the solution into the buffer in a "canonical form". The orientation of each route is such that start<end. Also, the ordering of the different routes is determined so that route i precedes route j in the ordering if start_i < start_j.

Definition at line 1238 of file VRPIO.cpp.

void VRP::export_solution_buff ( int *  sol_buff  ) 

Exports the solution to sol_buff.

Definition at line 1213 of file VRPIO.cpp.

void VRP::find_cheapest_insertion ( int  j,
int *  edge,
double *  costs,
int  rules 
) [private]

Finds the cheapest insertion of node j into the current solution. We store both the best feasible insertion as well as the best overall insertion. The value of edge[0] is the start node of the best feasible edge to be broken and edge[1] is the end node. Similarly, edge[2] and edge[3] represent the start and end of the best overall edge, disregarding feasibility (may be the same as edge[0] and edge[1]). The costs of these insertions are placed in costs[0] and costs[1]. If rules==VRPH_USE_NEIGHBOR_LIST, then only the neighbor list (plus the VRPH_DEPOT to guarantee a singleton route) is searched. If rules==VRPH_NO_NEW_ROUTE, then we do not allow the customer to be added in a new singleton route.

Definition at line 2026 of file VRP.cpp.

int VRP::find_common_routes ( int *  sol1,
int *  sol2,
int *  route_nums 
)

Finds the routes that are shared by the two solutions sol1 and sol2. Places the numbers of these routes (numbers from sol1 which are 1-based) into the route_nums[] buffer and returns the number of shared routes.

Definition at line 4113 of file VRP.cpp.

void VRP::find_neighboring_routes (  )  [private]

Finds the nearest set of neighboring routes, placing the corresponding set of route numbers in each route's neighboring_routes[] array.

Definition at line 3180 of file VRP.cpp.

void VRP::fix_edge ( int  start,
int  end 
)

Forces that the provided edge always remains in the solution. The edge may not currently be in the solution, but once it is encountered it will remain in the solution until the edge is unfixed. Note that the fixing of edges is only relevant if you use the heuristics with a VRPH_FIXED_EDGES rules.

Definition at line 3529 of file VRP.cpp.

void VRP::fix_string ( int *  node_string,
int  k 
)

Fixes all edges in the node_string[] array. For example, given the array {1,3,5,4,2}, the edges 1-3, 3-5, 5-4, 4-2 will be fixed. The value of k is the number of nodes in the string.

Definition at line 3597 of file VRP.cpp.

double VRP::get_best_known (  ) 

Definition at line 295 of file VRP.cpp.

double VRP::get_best_sol_buff ( int *  sol_buff  ) 

Copies the best solution buffer found so far into the sol_buff[] array. Assumes that sol_buff[] is of sufficient size. Returns the total route length of this solution.

Definition at line 247 of file VRP.cpp.

double VRP::get_best_total_route_length (  ) 

Returns the total route length of the best solution discovered so far.

Definition at line 259 of file VRP.cpp.

double VRP::get_distance_between ( int  a,
int  b 
) [private]

double VRP::get_max_route_length (  ) 

Definition at line 306 of file VRP.cpp.

int VRP::get_max_veh_capacity (  ) 

Definition at line 301 of file VRP.cpp.

int VRP::get_num_days (  ) 

Returns the number of days in the currently loaded instance.

Definition at line 286 of file VRP.cpp.

int VRP::get_num_nodes (  ) 

Returns the number of nodes in the instance.

Definition at line 220 of file VRP.cpp.

int VRP::get_num_original_nodes (  ) 

Returns the number of original nodes in the instance.

Definition at line 277 of file VRP.cpp.

bool VRP::get_segment_info ( int  a,
int  b,
struct VRPSegment S 
) [private]

Calculates the length, load, and # of customers on the segment of the route between nodes a and b. Assumes that a is before b in the route - this is not checked! Example: a-i-j-b has length: d(a,i)+d(i,j)+d(j,b) load: a + i + j + b #: 4

Definition at line 856 of file VRP.cpp.

int VRP::get_string_end ( int  a,
int  len 
) [private]

Finds the node that is (len-1) hops from a so that the string from a to the end contains len nodes. Returns -1 if not possible to get such a string.

Definition at line 935 of file VRP.cpp.

int VRP::get_total_number_of_routes (  ) 

Returns the number of routes in the current solution.

Definition at line 268 of file VRP.cpp.

double VRP::get_total_route_length (  ) 

Returns the total route length of the current solution.

Definition at line 229 of file VRP.cpp.

double VRP::get_total_service_time (  ) 

Returns the total service time of all customers in the instance.

Definition at line 238 of file VRP.cpp.

void VRP::import_solution_buff ( int *  sol_buff  ) 

Imports a solution from buffer produced by something like export_solution_buff(). Can be a partial solution if the first element in sol_buff[] is less than num_original_nodes;

Definition at line 1093 of file VRPIO.cpp.

bool VRP::inject_node ( int  j  ) 

Takes the node with index j that is currently NOT in the current solution and adds it to the VRP in the best possible feasible position.

Definition at line 1877 of file VRP.cpp.

int VRP::inject_set ( int  num,
int *  nodelist,
int  rules,
int  attempts 
)

Injects num different nodes in the nodelist[] array into the current solution. If rules=VRPH_RANDOM_SEARCH, then we try attempts different random permutations. If rules=VRPH_REGRET_SEARCH, then we try attempts different permutations and can backtrack by undoing certain moves that we end up regretting.

!! The eventual sol_buff is larger !!!!

Definition at line 2279 of file VRP.cpp.

bool VRP::insert_node ( int  j,
int  i,
int  k 
) [private]

Inserts j in between nodes i and k. Both i and k are assumed to be routed while j is not routed.

Definition at line 1897 of file VRP.cpp.

double VRP::insertion_cost ( int  u,
int  a,
int  b 
) [private]

Returns the increased cost to the route containing a-b of inserting node u in between a and b (assumed to be adjacent!)

Definition at line 2840 of file VRP.cpp.

int VRP::intersect_solutions ( int *  new_sol,
int **  routes,
int *  sol1,
int *  sol2,
int  min_routes 
)

Takes the two solutions sol1 and sol2 and constructs a smaller instance by ejecting the routes that are in both sol1 and sol2. If the resulting solution contains less than min_routes routes, then we add more random routes from sol1 until the solution has min_routes. Returns the number of routes ejected from sol1 and places these route buffers in the route_list[][] array which is a 0-based array of routes. Note that sol1 and sol2 are assumed to be full solutions to the VRP instance. Imports the smaller solution new_sol before returning.

Definition at line 3826 of file VRP.cpp.

bool VRP::is_feasible ( VRPMove M,
int  rules 
) [private]

Determines whether a proposed move is feasible or not. Could add time window feasibility checks here, etc. The rules is currently not used.

Definition at line 1860 of file VRP.cpp.

void VRP::list_fixed_edges ( int *  fixed_list  ) 

Looks through the current solution and places all edges that are currently fixed and in the solution in the fixed_list[] array. So if fixed[2][3]==true and fixed[3][7]==true, the array fixed_list[] is {2,3,3,7}.

Definition at line 3658 of file VRP.cpp.

void VRP::normalize_route_numbers (  ) 

Renumbers the routes so that with R total routes, they are numbered 1,2, ..., R instead of all over the place as they typically are after Clarke Wright.

Definition at line 2537 of file VRP.cpp.

bool VRP::osman_insert ( int  k,
double  alpha 
) [private]

Inserts node k into a new location in the solution according to Osman's savings heuristic. Given existing edges i-k-j and l-m, with parameter alpha, we move k to new location l-k-m such that the quantity ( ik+kj-lm ) - alpha*(lk+km-ij) is minimized.

Definition at line 3903 of file VRP.cpp.

int VRP::osman_perturb ( int  num,
double  alpha 
) [private]

Perturbs the existing solution by attempting to move num different random nodes into new positions using Osman parameter alpha. Gives up after attempting 2*V.num_nodes moves.

Definition at line 4014 of file VRP.cpp.

bool VRP::perturb (  ) 

Perturbs the current solution as suggested in Li, et al.

Definition at line 1482 of file VRP.cpp.

void VRP::perturb_locations ( double  c  )  [private]

Perturbs the current problem instance by moving each node slightly as in the TSP paper of Codenotti. The perturbations are scaled in terms of the value c. The distance matrix is recomputed after all locations have been perturbed.

Definition at line 3706 of file VRP.cpp.

bool VRP::plot ( const char *  filename  ) 

Assumes default options and plots the .ps file.

Definition at line 280 of file VRPGraphics.cpp.

bool VRP::plot ( const char *  filename,
int  options,
int  orientation 
)

Uses PLPLOT to draw the solution in a .ps file (no other formats supported). Valid options are VRPH_BLACK_AND_WHITE, VRPH_COLOR, VRPH_BARE_BONES, AXES, VRPH_BOXED, TITLED, VRPH_NO_POINTS, VRPH_NO_DEPOT_EDGES, VRPH_WEIGHTED. If options==0, then the default is to draw a VRPH_BOXED, COLORed plot, with AXES and a TITLE. Setting VRPH_BOXED draws a box around the plot with no axes, and setting VRPH_BARE_BONES draws no BOX or AXES. If VRPH_NO_POINTS is set, then the nodes are not drawn on the plot (default is to plot the points). Setting the option VRPH_NO_DEPOT_EDGES will draw each route with the first and last edges of each route not shown and a VRPH_WEIGHTED plot will make the size of the points proportional to their demand. The value of orientation should be 0, 1, 2, or 3, indicating that the image should be rotated through an angle of Pi/2 times orientation. A very primitive attempt is made to scale the line width and point size based on the problem size (number of nodes)

Definition at line 15 of file VRPGraphics.cpp.

bool VRP::plot_route ( int  r,
const char *  filename 
)

Uses PLPLOT to plot the individual route number r in a colored .ps file.

Definition at line 300 of file VRPGraphics.cpp.

bool VRP::postsert_dummy ( int  i  )  [private]

Definition at line 1037 of file VRP.cpp.

bool VRP::presert_dummy ( int  i  )  [private]

Definition at line 1097 of file VRP.cpp.

void VRP::print_stats (  ) 

Prints the # of evaluations and moves performed for each heuristic operator.

Definition at line 4368 of file VRP.cpp.

int VRP::read_fixed_edges ( const char *  filename  ) 

Reads a file of edges to be fixed. Letting k be the number of edges to be fixed, the file has the format

k start_1 end_1 start_2 end_2 ... start_k end_k

Returns the number of edges that are fixed.

Definition at line 3617 of file VRP.cpp.

void VRP::read_solution_file ( const char *  filename  ) 

Imports a solution from filename. File is assumed to be in the format produced by VRP.write_solution_file

Definition at line 1055 of file VRPIO.cpp.

void VRP::read_TSPLIB_file ( const char *  infile  ) 

Processes each section of the provided TSPLIB file and records the relevant data in the VRP structure. See the example files for information on my interpretation of the TSPLIB standard as it applies to VRP's.

Definition at line 15 of file VRPIO.cpp.

void VRP::refresh_routes (  ) 

Ignores the current route length and load values and recalculates them directly from the next_array.

Definition at line 700 of file VRP.cpp.

bool VRP::remove_dummy (  )  [private]

Definition at line 1155 of file VRP.cpp.

void VRP::reset (  ) 

Liquidates the solution memory and sets all nodes to unrouted.

Definition at line 4396 of file VRP.cpp.

void VRP::reverse_route ( int  i  ) 

This function reverses route number i - does no error checking since we don't know if the routes have normalized numbers or not...

Definition at line 962 of file VRP.cpp.

double VRP::RTR_solve ( int  heuristics,
int  intensity,
int  max_stuck,
int  num_perturbs,
double  dev,
int  nlist_size,
int  perturb_type,
int  accept_type,
bool  verbose 
)

Uses the given parameters to generate a VRP solution via record-to-record travel. Assumes that data has already been imported into V and that we have some existing solution. Returns the objective function value of the best solution found

Definition at line 15 of file VRPSolvers.cpp.

double VRP::SA_solve ( int  heuristics,
double  start_temp,
double  cool_ratio,
int  iters_per_loop,
int  num_loops,
int  nlist_size,
bool  verbose 
)

Uses the given parameters to generate a VRP solution using Simulated Annealing. Assumes that data has already been imported into V and that we have some existing solution. Returns the total route length of the best solution found.

Definition at line 493 of file VRPSolvers.cpp.

void VRP::set_best_total_route_length ( double  val  ) 

Definition at line 311 of file VRP.cpp.

void VRP::set_daily_demands ( int  day  ) 

Sets the demand of each node equal to the daily demand value for the given day. Used for period VRPs. The day should be a positive integer. If a day of 0 is given, then we set the demand to the mean value.

Definition at line 4180 of file VRP.cpp.

void VRP::set_daily_service_times ( int  day  ) 

Sets the service time of each node equal to the daily service time for the given day. Used for period VRPs.

Definition at line 4226 of file VRP.cpp.

void VRP::show_next_array (  ) 

Debugging function that shows the current next_array[]

Definition at line 16 of file VRPDebug.cpp.

void VRP::show_pred_array (  ) 

Debugging function that shows the pred_array.

Definition at line 32 of file VRPDebug.cpp.

void VRP::show_route ( int  k  ) 

Displays information about route number k.

Definition at line 1396 of file VRPIO.cpp.

void VRP::show_routes (  ) 

Displays all routes in the solution.

Definition at line 1295 of file VRPIO.cpp.

double VRP::split ( double  p  ) 

Splits an existing VRP into two parts by drawing a random ray from the VRPH_DEPOT. We repeatedly try to split the problem in this way until we have two sets of nodes that each has k nodes where k is between p*num_nodes and (1-p)*num_nodes. The value of p must be less than .5. Returns the angle theta used to split the problem

Definition at line 3371 of file VRP.cpp.

int VRP::split_routes ( double  p,
int **  ejected_routes,
double *  t 
)

Splits an existing VRP into two parts by drawing a random ray from the VRPH_DEPOT. We repeatedly try to split the problem in this way until we have two sets of nodes that each has k nodes where k is between p*num_nodes and (1-p)*num_nodes. Next, we take the larger part of the split solution and then keep all the routes that have at least one node in the larger part. The route-based decisions are based on the currently loaded solution. The ejected routes are placed in the ejected_routes[][] array and the function returns the number of routes ejected. The final value of theta that splits the problem is placed in t.

Definition at line 3436 of file VRP.cpp.

void VRP::summary (  ) 

This function prints out a summary of the current solution and the individual routes.

Definition at line 1429 of file VRPIO.cpp.

void VRP::unfix_all (  ) 

Unfixes any and all edges that may be currently fixed.

Definition at line 3586 of file VRP.cpp.

void VRP::unfix_edge ( int  start,
int  end 
)

Unfixes an edge that is already fixed.

Definition at line 3558 of file VRP.cpp.

void VRP::update ( VRPMove M  )  [private]

Updates the solution information in terms of the move M.

Definition at line 3122 of file VRP.cpp.

void VRP::update_arrival_times (  )  [private]

Computes the arrival time at all customers.

Definition at line 4246 of file VRP.cpp.

void VRP::update_route ( int  j,
VRPRoute R 
)

Copies the fields of route j in the current solution to the VRPRoute R, also updating the ordering, x, and y arrays. The ordering is normalized by having start<end.

Definition at line 3301 of file VRP.cpp.

void VRP::update_solution_wh (  )  [private]

Attempts to add the given solution to the warehouse.

Definition at line 3277 of file VRP.cpp.

bool VRP::verify_routes ( const char *  message  ) 

This debugging function will manually calculate the objective function of the current solution and the route values, etc., and compare with the claimed value. Returns false if any inconsistencies are found and prints the message. Returns true with no output otherwise.

Definition at line 50 of file VRPDebug.cpp.

void VRP::write_solution_file ( const char *  filename  ) 

Exports a solution to the designated filename in canonical form. Let N be the # of non-VRPH_DEPOT nodes in the problem. Then the first entry in the file is N and the following N+1 entries simply traverse the solution in order where we enter a node's negative index if it is the first node in a route. The solution is put into canonical form - the routes are traversed in the orientation where the start index is less than the end index, and the routes are sorted by the start index. Example: Route 1: 0-3-2-0, Route 2: 0-4-1-0 File is then: 4 -1 4 -2 3 0

Definition at line 849 of file VRPIO.cpp.

void VRP::write_solutions ( int  num_sols,
const char *  filename 
)

Writes num_sols solutions from the solution warehouse to the designated filename. The format is the same as for write_solution_file.

Definition at line 920 of file VRPIO.cpp.

void VRP::write_tex_file ( const char *  filename  ) 

Writes the solution in a TeX tabular format using the longtable package in case the solution spans multiple pages.

Definition at line 983 of file VRPIO.cpp.

void VRP::write_TSPLIB_file ( const char *  outfile  ) 

Exports the data from an already loaded instance to a CVRP outfile in TSPLIB format (using EXACT_2D distance).

Definition at line 793 of file VRPIO.cpp.


Friends And Related Function Documentation

friend class ClarkeWright [friend]

Definition at line 36 of file VRP.h.

friend class Concatenate [friend]

Definition at line 33 of file VRP.h.

friend class CrossExchange [friend]

Definition at line 26 of file VRP.h.

friend class Flip [friend]

Definition at line 34 of file VRP.h.

friend class MoveString [friend]

Definition at line 30 of file VRP.h.

friend class OnePointMove [friend]

Definition at line 20 of file VRP.h.

friend class OrOpt [friend]

Definition at line 25 of file VRP.h.

friend class Postsert [friend]

Definition at line 28 of file VRP.h.

friend class Presert [friend]

Definition at line 29 of file VRP.h.

friend class Swap [friend]

Definition at line 31 of file VRP.h.

friend class SwapEnds [friend]

Definition at line 32 of file VRP.h.

friend class Sweep [friend]

Definition at line 37 of file VRP.h.

friend class ThreeOpt [friend]

Definition at line 24 of file VRP.h.

friend class ThreePointMove [friend]

Definition at line 22 of file VRP.h.

friend class TwoOpt [friend]

Definition at line 23 of file VRP.h.

friend class TwoPointMove [friend]

Definition at line 21 of file VRP.h.


Member Data Documentation

double VRP::balance_parameter [private]

Definition at line 193 of file VRP.h.

double VRP::best_known [private]

Definition at line 176 of file VRP.h.

int* VRP::best_sol_buff [private]

Definition at line 172 of file VRP.h.

double VRP::best_total_route_length [private]

Definition at line 173 of file VRP.h.

bool VRP::can_display [private]

Definition at line 202 of file VRP.h.

double VRP::cooling_ratio [private]

Definition at line 197 of file VRP.h.

int VRP::coord_type [private]

Definition at line 189 of file VRP.h.

int* VRP::current_sol_buff [private]

Definition at line 239 of file VRP.h.

double** VRP::d [private]

Definition at line 204 of file VRP.h.

bool VRP::depot_normalized [private]

Definition at line 210 of file VRP.h.

double VRP::deviation [private]

Definition at line 234 of file VRP.h.

int VRP::display_type [private]

Definition at line 190 of file VRP.h.

int VRP::dummy_index [private]

Definition at line 194 of file VRP.h.

int VRP::edge_weight_format [private]

Definition at line 191 of file VRP.h.

int VRP::edge_weight_type [private]

Definition at line 188 of file VRP.h.

bool** VRP::fixed [private]

Definition at line 205 of file VRP.h.

double VRP::fixed_service_time [private]

Definition at line 187 of file VRP.h.

bool VRP::forbid_tiny_moves [private]

Definition at line 213 of file VRP.h.

bool VRP::has_service_times [private]

Definition at line 186 of file VRP.h.

int VRP::matrix_size [private]

Definition at line 192 of file VRP.h.

double VRP::max_route_length [private]

Definition at line 182 of file VRP.h.

double VRP::max_theta [private]

Definition at line 237 of file VRP.h.

int VRP::max_veh_capacity [private]

Definition at line 180 of file VRP.h.

double VRP::min_route_length [private]

Definition at line 183 of file VRP.h.

double VRP::min_theta [private]

Definition at line 236 of file VRP.h.

int VRP::min_vehicles [private]

Definition at line 185 of file VRP.h.

char VRP::name[VRPH_STRING_SIZE]

Definition at line 97 of file VRP.h.

int VRP::neighbor_list_size [private]

Definition at line 195 of file VRP.h.

int* VRP::next_array [private]

Definition at line 222 of file VRP.h.

class VRPNode* VRP::nodes [private]

Definition at line 207 of file VRP.h.

int VRP::num_days [private]

Definition at line 177 of file VRP.h.

int VRP::num_evaluations[NUM_HEURISTICS]

Definition at line 163 of file VRP.h.

int VRP::num_moves[NUM_HEURISTICS]

Definition at line 164 of file VRP.h.

int VRP::num_nodes [private]

Definition at line 169 of file VRP.h.

int VRP::num_original_nodes [private]

Definition at line 175 of file VRP.h.

double VRP::orig_max_route_length [private]

Definition at line 184 of file VRP.h.

Definition at line 181 of file VRP.h.

int* VRP::pred_array [private]

Definition at line 223 of file VRP.h.

int VRP::problem_type [private]

Definition at line 178 of file VRP.h.

double VRP::record [private]

Definition at line 233 of file VRP.h.

class VRPRoute* VRP::route [private]

Definition at line 227 of file VRP.h.

int* VRP::route_num [private]

Definition at line 224 of file VRP.h.

Definition at line 147 of file VRP.h.

bool* VRP::routed [private]

Definition at line 225 of file VRP.h.

int VRP::search_size [private]

Definition at line 218 of file VRP.h.

int* VRP::search_space [private]

Definition at line 219 of file VRP.h.

Definition at line 146 of file VRP.h.

bool VRP::symmetric [private]

Definition at line 199 of file VRP.h.

class VRPTabuList* VRP::tabu_list [private]

Definition at line 230 of file VRP.h.

double VRP::temperature [private]

Definition at line 196 of file VRP.h.

int VRP::total_demand [private]

Definition at line 179 of file VRP.h.

Definition at line 174 of file VRP.h.

double VRP::total_route_length [private]

Definition at line 170 of file VRP.h.

double VRP::total_service_time [private]

Definition at line 171 of file VRP.h.

class VRPViolation VRP::violation [private]

Definition at line 246 of file VRP.h.


The documentation for this class was generated from the following files:

Generated on Thu Mar 10 11:08:49 2011 for VRPH by  doxygen 1.5.9