VRPH
1.0
|
#include <VRP.h>
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] |
VRPSolutionWarehouse * | solution_wh |
VRPRouteWarehouse * | route_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 VRPNode * | nodes |
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 VRPRoute * | route |
class VRPTabuList * | tabu_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 |
VRP::VRP | ( | int | n, |
int | ndays | ||
) |
void VRP::add_route | ( | int * | route_buff | ) |
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.
bool VRP::before | ( | int | a, |
int | b | ||
) | [private] |
void VRP::capture_best_solution | ( | ) | [private] |
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
bool VRP::check_fixed_edges | ( | const char * | message | ) |
bool VRP::check_move | ( | VRPMove * | M, |
int | rules | ||
) | [private] |
bool VRP::check_savings | ( | VRPMove * | M, |
int | rules | ||
) | [inline, private] |
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.
void VRP::clean_route | ( | int | r, |
int | heuristics | ||
) |
void VRP::compute_route_center | ( | int | r | ) | [private] |
int VRP::count_num_routes | ( | ) | [private] |
bool VRP::create_default_routes | ( | ) |
bool VRP::create_default_routes | ( | int | day | ) |
void VRP::create_distance_matrix | ( | int | type | ) |
void VRP::create_neighbor_lists | ( | int | nsize | ) |
void VRP::create_pred_array | ( | ) |
bool VRP::create_search_neighborhood | ( | int | j, |
int | rules | ||
) | [private] |
void VRP::eject_neighborhood | ( | int | j, |
int | num, | ||
int * | nodelist | ||
) |
bool VRP::eject_node | ( | int | k | ) |
bool VRP::eject_route | ( | int | r, |
int * | route_buff | ||
) |
double VRP::ejection_cost | ( | int | u | ) | [private] |
void VRP::export_canonical_solution_buff | ( | int * | sol_buff | ) |
void VRP::export_solution_buff | ( | int * | sol_buff | ) |
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.
int VRP::find_common_routes | ( | int * | sol1, |
int * | sol2, | ||
int * | route_nums | ||
) |
void VRP::find_neighboring_routes | ( | ) | [private] |
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.
void VRP::fix_string | ( | int * | node_string, |
int | k | ||
) |
double VRP::get_best_sol_buff | ( | int * | sol_buff | ) |
double VRP::get_best_total_route_length | ( | ) |
double VRP::get_distance_between | ( | int | a, |
int | b | ||
) | [private] |
int VRP::get_num_days | ( | ) |
int VRP::get_num_nodes | ( | ) |
int VRP::get_num_original_nodes | ( | ) |
bool VRP::get_segment_info | ( | int | a, |
int | b, | ||
struct VRPSegment * | S | ||
) | [private] |
int VRP::get_string_end | ( | int | a, |
int | len | ||
) | [private] |
int VRP::get_total_number_of_routes | ( | ) |
double VRP::get_total_route_length | ( | ) |
double VRP::get_total_service_time | ( | ) |
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;
bool VRP::inject_node | ( | int | j | ) |
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 !!!!
bool VRP::insert_node | ( | int | j, |
int | i, | ||
int | k | ||
) | [private] |
double VRP::insertion_cost | ( | int | u, |
int | a, | ||
int | b | ||
) | [private] |
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.
bool VRP::is_feasible | ( | VRPMove * | M, |
int | rules | ||
) | [private] |
void VRP::list_fixed_edges | ( | int * | fixed_list | ) |
void VRP::normalize_route_numbers | ( | ) |
bool VRP::osman_insert | ( | int | k, |
double | alpha | ||
) | [private] |
int VRP::osman_perturb | ( | int | num, |
double | alpha | ||
) | [private] |
bool VRP::perturb | ( | ) |
void VRP::perturb_locations | ( | double | c | ) | [private] |
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 | ( | const char * | filename | ) |
Assumes default options and plots the .ps file.
Definition at line 280 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.
void VRP::print_stats | ( | ) |
int VRP::read_fixed_edges | ( | const char * | filename | ) |
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
void VRP::read_TSPLIB_file | ( | const char * | infile | ) |
void VRP::refresh_routes | ( | ) |
void VRP::reset | ( | ) |
void VRP::reverse_route | ( | int | i | ) |
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_daily_demands | ( | int | day | ) |
void VRP::set_daily_service_times | ( | int | day | ) |
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 | ) |
void VRP::show_routes | ( | ) |
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
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.
void VRP::summary | ( | ) |
void VRP::unfix_all | ( | ) |
void VRP::unfix_edge | ( | int | start, |
int | end | ||
) |
void VRP::update | ( | VRPMove * | M | ) | [private] |
void VRP::update_arrival_times | ( | ) | [private] |
void VRP::update_route | ( | int | j, |
VRPRoute * | R | ||
) |
void VRP::update_solution_wh | ( | ) | [private] |
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
void VRP::write_solutions | ( | int | num_sols, |
const char * | filename | ||
) |
void VRP::write_tex_file | ( | const char * | filename | ) |
void VRP::write_TSPLIB_file | ( | const char * | outfile | ) |
friend class ClarkeWright [friend] |
friend class Concatenate [friend] |
friend class CrossExchange [friend] |
friend class MoveString [friend] |
friend class OnePointMove [friend] |
friend class ThreePointMove [friend] |
friend class TwoPointMove [friend] |
double VRP::balance_parameter [private] |
double VRP::best_known [private] |
int* VRP::best_sol_buff [private] |
double VRP::best_total_route_length [private] |
bool VRP::can_display [private] |
double VRP::cooling_ratio [private] |
int VRP::coord_type [private] |
int* VRP::current_sol_buff [private] |
bool VRP::depot_normalized [private] |
double VRP::deviation [private] |
int VRP::display_type [private] |
int VRP::dummy_index [private] |
int VRP::edge_weight_format [private] |
int VRP::edge_weight_type [private] |
bool** VRP::fixed [private] |
double VRP::fixed_service_time [private] |
bool VRP::forbid_tiny_moves [private] |
bool VRP::has_service_times [private] |
int VRP::matrix_size [private] |
double VRP::max_route_length [private] |
double VRP::max_theta [private] |
int VRP::max_veh_capacity [private] |
double VRP::min_route_length [private] |
double VRP::min_theta [private] |
int VRP::min_vehicles [private] |
int VRP::neighbor_list_size [private] |
int* VRP::next_array [private] |
class VRPNode* VRP::nodes [private] |
int VRP::num_days [private] |
int VRP::num_evaluations[NUM_HEURISTICS] |
int VRP::num_moves[NUM_HEURISTICS] |
int VRP::num_nodes [private] |
int VRP::num_original_nodes [private] |
double VRP::orig_max_route_length [private] |
int VRP::orig_max_veh_capacity [private] |
int* VRP::pred_array [private] |
int VRP::problem_type [private] |
double VRP::record [private] |
class VRPRoute* VRP::route [private] |
int* VRP::route_num [private] |
bool* VRP::routed [private] |
int VRP::search_size [private] |
int* VRP::search_space [private] |
bool VRP::symmetric [private] |
class VRPTabuList* VRP::tabu_list [private] |
double VRP::temperature [private] |
int VRP::total_demand [private] |
int VRP::total_number_of_routes [private] |
double VRP::total_route_length [private] |
double VRP::total_service_time [private] |
class VRPViolation VRP::violation [private] |