|
| Generated on: Thu Mar 29 07:46:58 PDT 2012 for custom file set | ||
|
||
| // doxy/ or-tools/ src/ constraint_solver/ |
#include <routing.h>
Public Types | |
| enum | RoutingStrategy { ROUTING_DEFAULT_STRATEGY, ROUTING_GLOBAL_CHEAPEST_ARC, ROUTING_LOCAL_CHEAPEST_ARC, ROUTING_PATH_CHEAPEST_ARC, ROUTING_EVALUATOR_STRATEGY, ROUTING_ALL_UNPERFORMED, ROUTING_BEST_INSERTION } |
| First solution strategies, used as starting point of local search. More... | |
| enum | RoutingMetaheuristic { ROUTING_GREEDY_DESCENT, ROUTING_GUIDED_LOCAL_SEARCH, ROUTING_SIMULATED_ANNEALING, ROUTING_TABU_SEARCH } |
| Metaheuristics used to guide the search. More... | |
| enum | Status { ROUTING_NOT_SOLVED, ROUTING_SUCCESS, ROUTING_FAIL, ROUTING_FAIL_TIMEOUT } |
| Status of the search. More... | |
| typedef _RoutingModel_NodeIndex | NodeIndex |
| typedef ResultCallback2< int64, NodeIndex, NodeIndex > | NodeEvaluator2 |
| typedef std::vector< std::pair < int, int > > | NodePairs |
Public Member Functions | |
| RoutingModel (int nodes, int vehicles) | |
| Supposes a single depot. | |
| RoutingModel (int nodes, int vehicles, const std::vector< std::pair< NodeIndex, NodeIndex > > &start_end) | |
| Constructor taking a vector of (start node, end node) pairs for each vehicle route. | |
| RoutingModel (int nodes, int vehicles, const std::vector< NodeIndex > &starts, const std::vector< NodeIndex > &ends) | |
| Constructor taking vectors of start nodes and end nodes for each vehicle route. | |
| ~RoutingModel () | |
| void | AddDimension (NodeEvaluator2 *evaluator, int64 slack_max, int64 capacity, const string &name) |
| Model creation. | |
| void | AddConstantDimension (int64 value, int64 capacity, const string &name) |
| Creates a dimension where the transit variable is constrained to be equal to 'value'; 'capacity' is the upper bound of the cumul variables. | |
| void | AddVectorDimension (const int64 *values, int64 capacity, const string &name) |
| Creates a dimension where the transit variable is constrained to be equal to 'values[i]' for node i; 'capacity' is the upper bound of the cumul variables. | |
| void | AddMatrixDimension (const int64 *const *values, int64 capacity, const string &name) |
| Creates a dimension where the transit variable is constrained to be equal to 'values[i][next[i]' for node i; 'capacity' is the upper bound of the cumul variables. | |
| void | AddAllActive () |
| Constrains all nodes to be active (to belong to a route). | |
| void | AddDisjunction (const std::vector< NodeIndex > &nodes) |
| Adds a disjunction constraint on the nodes: exactly one of the nodes is active. | |
| void | AddDisjunction (const std::vector< NodeIndex > &nodes, int64 penalty) |
| Adds a penalized disjunction constraint on the nodes: at most one of the nodes is active; if none are active a penalty cost is applied (this cost is added to the global cost function). | |
| void | AddPickupAndDelivery (NodeIndex node1, NodeIndex node2) |
| void | SetDepot (NodeIndex depot) |
| Makes 'depot' the starting node of all routes. | |
| void | SetCost (NodeEvaluator2 *evaluator) |
| Sets the cost function of the model such that the cost of a segment of a route between node 'from' and 'to' is evaluator(from, to), whatever the route or vehicle performing the route. | |
| void | SetVehicleCost (int vehicle, NodeEvaluator2 *evaluator) |
| Sets the cost function for a given vehicle route. | |
| int64 | GetRouteFixedCost () const |
| The fixed cost of a route is taken into account if the route is not empty, aka there's at least one node on the route other than the first and last nodes. | |
| void | SetRouteFixedCost (int64 cost) |
| Sets the fixed cost of all vehicle routes. | |
| int64 | GetVehicleFixedCost (int vehicle) const |
| Returns the route fixed cost taken into account if the route of the vehicle is not empty, aka there's at least one node on the route other than the first and last nodes. | |
| void | SetVehicleFixedCost (int vehicle, int64 cost) |
| Sets the fixed cost of one vehicle route. | |
| RoutingStrategy | first_solution_strategy () const |
| Search Returns the strategy used to build a first solution. | |
| void | set_first_solution_strategy (RoutingStrategy strategy) |
| Sets the strategy used to build a first solution. | |
| Solver::IndexEvaluator2 * | first_solution_evaluator () const |
| Gets/sets the evaluator used when the first solution heuristic is set to ROUTING_EVALUATOR_STRATEGY (variant of ROUTING_PATH_CHEAPEST_ARC using 'evaluator' to sort node segments). | |
| void | SetFirstSolutionEvaluator (Solver::IndexEvaluator2 *evaluator) |
| Takes ownership of evaluator. | |
| RoutingStrategy | GetSelectedFirstSolutionStrategy () const |
| If a first solution flag has been set (to a value different than Default), returns the corresponding strategy, otherwise returns the strategy which was set. | |
| void | AddLocalSearchOperator (LocalSearchOperator *ls_operator) |
| Adds a local search operator to the set of operators used to solve the vehicle routing problem. | |
| RoutingMetaheuristic | metaheuristic () const |
| Returns the metaheuristic used. | |
| void | set_metaheuristic (RoutingMetaheuristic metaheuristic) |
| Sets the metaheuristic to be used. | |
| RoutingMetaheuristic | GetSelectedMetaheuristic () const |
| If a metaheuristic flag has been set, returns the corresponding metaheuristic, otherwise returns the metaheuristic which was set. | |
| void | AddSearchMonitor (SearchMonitor *const monitor) |
| Adds a search monitor to the search used to solve the routing model. | |
| void | CloseModel () |
| Closes the current routing model; after this method is called, no modification to the model can be done, but RoutesToAssignment becomes available. | |
| const Assignment * | Solve (const Assignment *assignment=NULL) |
| Solves the current routing model; closes the current model. | |
| int64 | ComputeLowerBound () |
| Computes a lower bound to the routing problem solving a linear assignment problem. | |
| Status | status () const |
| Returns the current status of the routing model. | |
| IntVar * | ApplyLocks (const std::vector< int > &locks) |
| Applies a lock chain to the next search. | |
| bool | ApplyLocksToAllVehicles (const std::vector< std::vector< NodeIndex > > &locks, bool close_routes) |
| Applies lock chains to all vehicles to the next search, such that locks[p] is the lock chain for route p. | |
| const Assignment *const | PreAssignment () const |
| Returns an assignment used to fix some of the variables of the problem. | |
| bool | WriteAssignment (const string &file_name) const |
| Writes the current solution to a file containing an AssignmentProto. | |
| Assignment * | ReadAssignment (const string &file_name) |
| Reads an assignment from a file and returns the current solution. | |
| Assignment * | RestoreAssignment (const Assignment &solution) |
| Restores an assignment as a solution in the routing model and returns the new solution. | |
| Assignment * | ReadAssignmentFromRoutes (const std::vector< std::vector< NodeIndex > > &routes, bool ignore_inactive_nodes) |
| Restores the routes as the current solution. | |
| bool | RoutesToAssignment (const std::vector< std::vector< NodeIndex > > &routes, bool ignore_inactive_nodes, bool close_routes, Assignment *const assignment) const |
| Fills an assignment from a specification of the routes of the vehicles. | |
| void | AssignmentToRoutes (const Assignment &assignment, std::vector< std::vector< NodeIndex > > *const routes) const |
| Converts the solution in the given assignment to routes for all vehicles. | |
| Assignment * | CompactAssignment (const Assignment &assignment) const |
| Returns a compacted version of the given assignment, in which all vehicles with id lower or equal to some N have non-empty routes, and all vehicles with id greater than N have empty routes. | |
| void | AddToAssignment (IntVar *const var) |
| Adds an extra variable to the vehicle routing assignment. | |
| int | Start (int vehicle) const |
| Model inspection. | |
| int | End (int vehicle) const |
| Returns the variable index of the ending node of a vehicle route. | |
| bool | IsStart (int64 index) const |
| Returns true if 'index' represents the first node of a route. | |
| bool | IsEnd (int64 index) const |
| Returns true if 'index' represents the last node of a route. | |
| int64 | GetFirstSolutionCost (int64 i, int64 j) |
| Return high cost if connecting to end node; used in cost-based first solution. | |
| bool | homogeneous_costs () const |
| int | Next (const Assignment &assignment, int index) const |
| Assignment inspection Returns the variable index of the node directly after the node corresponding to 'index' in 'assignment'. | |
| bool | IsVehicleUsed (const Assignment &assignment, int vehicle) const |
| Returns true if the route of 'vehicle' is non empty in 'assignment'. | |
| IntVar ** | Nexts () const |
| Variables Returns all next variables of the model, such that Nexts(i) is the next variable of the node corresponding to i. | |
| IntVar ** | VehicleVars () const |
| Returns all vehicle variables of the model, such that VehicleVars(i) is the vehicle variable of the node corresponding to i. | |
| IntVar * | NextVar (int64 index) const |
| Returns the next variable of the node corresponding to index. | |
| IntVar * | ActiveVar (int64 index) const |
| Returns the active variable of the node corresponding to index. | |
| IntVar * | VehicleVar (int64 index) const |
| Returns the vehicle variable of the node corresponding to index. | |
| IntVar * | CumulVar (int64 index, const string &name) const |
| Returns the cumul variable for the dimension named 'name'. | |
| IntVar * | TransitVar (int64 index, const string &name) const |
| Returns the transit variable for the dimension named 'name'. | |
| IntVar * | CostVar () const |
| Returns the global cost variable which is being minimized. | |
| int64 | GetCost (int64 from_index, int64 to_index, int64 vehicle) |
| Returns the cost of the segment between two nodes for a given vehicle route. | |
| int64 | GetHomogeneousCost (int64 i, int64 j) |
| Returns the cost of the segment between two nodes supposing all vehicle costs are the same (returns the cost for the first vehicle otherwise). | |
| Solver * | solver () const |
| Returns the underlying constraint solver. | |
| int | nodes () const |
| Sizes and indices Returns the number of nodes in the model. | |
| int | vehicles () const |
| Returns the number of vehicle routes in the model. | |
| int | Size () const |
| Returns the number of next variables in the model. | |
| NodeIndex | IndexToNode (int64 index) const |
| Returns the node index from an index value resulting fron a next variable. | |
| int64 | NodeToIndex (NodeIndex node) const |
| Returns the variable index from a node value. | |
| void | GetDisjunctionIndicesFromIndex (int64 index, std::vector< int > *indices) const |
| Returns the variable indices of the nodes in the same disjunction as the node corresponding to the variable of index 'index'. | |
| int64 | TimeLimit () const |
| Time limits Returns the current time limit used in the search. | |
| void | UpdateTimeLimit (int64 limit_ms) |
| Updates the time limit used in the search. | |
| void | UpdateLNSTimeLimit (int64 limit_ms) |
| Updates the time limit used in the Large Neighborhood search tree. | |
| void | SetCommandLineOption (const string &name, const string &value) |
| Utilities for swig to set flags in python or java. | |
Static Public Attributes | |
| static const NodeIndex | kFirstNode |
| Constants with an index of the first node (to be used in for loops for iteration), and a special index to signalize an invalid/unused value. | |
| static const NodeIndex | kInvalidNodeIndex |
Classes | |
| struct | CostCacheElement |
| struct | Disjunction |
Definition at line 178 of file routing.h.
| typedef _RoutingModel_NodeIndex operations_research::RoutingModel::NodeIndex |
| typedef ResultCallback2<int64, NodeIndex, NodeIndex> operations_research::RoutingModel::NodeEvaluator2 |
| typedef std::vector<std::pair<int, int> > operations_research::RoutingModel::NodePairs |
First solution strategies, used as starting point of local search.
| ROUTING_DEFAULT_STRATEGY |
Select the first node with an unbound successor and connect it to the first available node.
This is equivalent to the CHOOSE_FIRST_UNBOUND strategy combined with ASSIGN_MIN_VALUE (cf. constraint_solver.h). |
| ROUTING_GLOBAL_CHEAPEST_ARC | Iteratively connect two nodes which produce the cheapest route segment. |
| ROUTING_LOCAL_CHEAPEST_ARC |
Select the first node with an unbound successor and connect it to the node which produces the cheapest route segment.
|
| ROUTING_PATH_CHEAPEST_ARC |
Starting from a route "start" node, connect it to the node which produces the cheapest route segment, then extend the route by iterating on the last node added to the route.
|
| ROUTING_EVALUATOR_STRATEGY |
Same as ROUTING_PATH_CHEAPEST_ARC, except that arc costs are evaluated using the function passed to RoutingModel::SetFirstSolutionEvaluator().
|
| ROUTING_ALL_UNPERFORMED |
Make all node inactive.
Only finds a solution if nodes are optional (are element of a disjunction constraint with a finite penalty cost). |
| ROUTING_BEST_INSERTION |
Iteratively build a solution by inserting nodes at their cheapest (best) position.
As of 2/2012, only works on models with optional nodes (with finite penalty costs). |
Metaheuristics used to guide the search.
Apart greedy descent, they will try to escape local minima.
| ROUTING_GREEDY_DESCENT |
Accepts improving (cost-reducing) local search neighbors until a local minimum is reached.
This is the default heuristic. |
| ROUTING_GUIDED_LOCAL_SEARCH |
Uses guided local search to escape local minima (cf.
http://en.wikipedia.org/wiki/Guided_Local_Search); this is generally the most efficient metaheuristic for vehicle routing. |
| ROUTING_SIMULATED_ANNEALING | Uses simulated annealing to escape local minima (cf. |
| ROUTING_TABU_SEARCH | Uses tabu search to escape local minima (cf. |
Status of the search.
| ROUTING_NOT_SOLVED | Problem not solved yet (before calling RoutingModel::Solve()). |
| ROUTING_SUCCESS | Problem solved successfully after calling RoutingModel::Solve(). |
| ROUTING_FAIL | No solution found to the problem after calling RoutingModel::Solve(). |
| ROUTING_FAIL_TIMEOUT | Time limit reached before finding a solution with RoutingModel::Solve(). |
| operations_research::RoutingModel::RoutingModel | ( | int | nodes, | |
| int | vehicles | |||
| ) |
Supposes a single depot.
A depot is the start and end node of the route of a vehicle.
Definition at line 680 of file routing.cc.
| operations_research::RoutingModel::RoutingModel | ( | int | nodes, | |
| int | vehicles, | |||
| const std::vector< std::pair< NodeIndex, NodeIndex > > & | start_end | |||
| ) |
Constructor taking a vector of (start node, end node) pairs for each vehicle route.
Used to model multiple depots.
Definition at line 714 of file routing.cc.
| operations_research::RoutingModel::RoutingModel | ( | int | nodes, | |
| int | vehicles, | |||
| const std::vector< NodeIndex > & | starts, | |||
| const std::vector< NodeIndex > & | ends | |||
| ) |
Constructor taking vectors of start nodes and end nodes for each vehicle route.
Used to model multiple depots.
Definition at line 757 of file routing.cc.
| operations_research::RoutingModel::~RoutingModel | ( | ) |
Definition at line 831 of file routing.cc.
| void operations_research::RoutingModel::AddDimension | ( | NodeEvaluator2 * | evaluator, | |
| int64 | slack_max, | |||
| int64 | capacity, | |||
| const string & | name | |||
| ) |
Model creation.
Methods to add dimensions to routes; dimensions represent quantities accumulated at nodes along the routes. They represent quantities such as weights or volumes carried along the route, or distance or times. Quantities at a node are represented by "cumul" variables and the increase or decrease of quantities between nodes are represented by "transit" variables. These variables are linked as follows: if j == next(i), cumul(j) = cumul(i) + transit(i) + slack(i) where slack is a positive slack variable (can represent waiting times for a time dimension). Creates a dimension where the transit variable is constrained to be equal to evaluator(i, next(i)); 'slack_max' is the upper bound of the slack variable and 'capacity' is the upper bound of the cumul variables. 'name' is the name used to reference the dimension; this name is used to get cumul and transit variables from the routing model.
Definition at line 847 of file routing.cc.
| void operations_research::RoutingModel::AddConstantDimension | ( | int64 | value, | |
| int64 | capacity, | |||
| const string & | name | |||
| ) |
Creates a dimension where the transit variable is constrained to be equal to 'value'; 'capacity' is the upper bound of the cumul variables.
'name' is the name used to reference the dimension; this name is used to get cumul and transit variables from the routing model.
Definition at line 868 of file routing.cc.
| void operations_research::RoutingModel::AddVectorDimension | ( | const int64 * | values, | |
| int64 | capacity, | |||
| const string & | name | |||
| ) |
Creates a dimension where the transit variable is constrained to be equal to 'values[i]' for node i; 'capacity' is the upper bound of the cumul variables.
'name' is the name used to reference the dimension; this name is used to get cumul and transit variables from the routing model.
Definition at line 877 of file routing.cc.
| void operations_research::RoutingModel::AddMatrixDimension | ( | const int64 *const * | values, | |
| int64 | capacity, | |||
| const string & | name | |||
| ) |
Creates a dimension where the transit variable is constrained to be equal to 'values[i][next[i]' for node i; 'capacity' is the upper bound of the cumul variables.
'name' is the name used to reference the dimension; this name is used to get cumul and transit variables from the routing model.
Definition at line 886 of file routing.cc.
| void operations_research::RoutingModel::AddAllActive | ( | ) |
Constrains all nodes to be active (to belong to a route).
Definition at line 895 of file routing.cc.
| void operations_research::RoutingModel::AddDisjunction | ( | const std::vector< NodeIndex > & | nodes | ) |
Adds a disjunction constraint on the nodes: exactly one of the nodes is active.
Start and end nodes of any vehicle cannot be part of a disjunction.
Definition at line 944 of file routing.cc.
| void operations_research::RoutingModel::AddDisjunction | ( | const std::vector< NodeIndex > & | nodes, | |
| int64 | penalty | |||
| ) |
Adds a penalized disjunction constraint on the nodes: at most one of the nodes is active; if none are active a penalty cost is applied (this cost is added to the global cost function).
This is equivalent to adding the constraint: p + Sum(i)active[i] == 1, where p is a boolean variable and the following cost to the cost function: p * penalty. "penalty" must be positive. Note: passing a vector with a single node will model an optional node with a penalty cost if it is not visited. SWIGPYTHON Notifies that node1 and node2 form a pair of nodes which should belong to the same route. This methods helps the search find better solutions, especially in the local search phase. It should be called each time you have an equality constraint linking the vehicle variables of two node (including for instance pickup and delivery problems): Solver* const solver = routing.solver(); solver->AddConstraint(solver->MakeEquality( routing.VehicleVar(routing.NodeToIndex(node1)), routing.VehicleVar(routing.NodeToIndex(node2)))); solver->AddPickupAndDelivery(node1, node2);
Definition at line 948 of file routing.cc.
| void operations_research::RoutingModel::SetDepot | ( | NodeIndex | depot | ) |
| void operations_research::RoutingModel::SetCost | ( | NodeEvaluator2 * | evaluator | ) |
Sets the cost function of the model such that the cost of a segment of a route between node 'from' and 'to' is evaluator(from, to), whatever the route or vehicle performing the route.
Definition at line 903 of file routing.cc.
| void operations_research::RoutingModel::SetVehicleCost | ( | int | vehicle, | |
| NodeEvaluator2 * | evaluator | |||
| ) |
| int64 operations_research::RoutingModel::GetRouteFixedCost | ( | ) | const |
The fixed cost of a route is taken into account if the route is not empty, aka there's at least one node on the route other than the first and last nodes.
Gets the fixed cost of all vehicle routes if they are all the same; otherwise returns the fixed cost of the first vehicle route. Deprecated by GetVehicleFixedCost().
Definition at line 912 of file routing.cc.
| void operations_research::RoutingModel::SetRouteFixedCost | ( | int64 | cost | ) |
Sets the fixed cost of all vehicle routes.
It is equivalent to calling SetVehicleFixedCost on all vehicle routes.
Definition at line 928 of file routing.cc.
| int64 operations_research::RoutingModel::GetVehicleFixedCost | ( | int | vehicle | ) | const |
Returns the route fixed cost taken into account if the route of the vehicle is not empty, aka there's at least one node on the route other than the first and last nodes.
Definition at line 934 of file routing.cc.
| void operations_research::RoutingModel::SetVehicleFixedCost | ( | int | vehicle, | |
| int64 | cost | |||
| ) |
| RoutingStrategy operations_research::RoutingModel::first_solution_strategy | ( | ) | const [inline] |
| void operations_research::RoutingModel::set_first_solution_strategy | ( | RoutingStrategy | strategy | ) | [inline] |
| Solver::IndexEvaluator2* operations_research::RoutingModel::first_solution_evaluator | ( | ) | const [inline] |
| void operations_research::RoutingModel::SetFirstSolutionEvaluator | ( | Solver::IndexEvaluator2 * | evaluator | ) | [inline] |
| RoutingModel::RoutingStrategy operations_research::RoutingModel::GetSelectedFirstSolutionStrategy | ( | ) | const |
If a first solution flag has been set (to a value different than Default), returns the corresponding strategy, otherwise returns the strategy which was set.
Flags override strategy selection.
Definition at line 1314 of file routing.cc.
| void operations_research::RoutingModel::AddLocalSearchOperator | ( | LocalSearchOperator * | ls_operator | ) |
Adds a local search operator to the set of operators used to solve the vehicle routing problem.
Definition at line 992 of file routing.cc.
| RoutingMetaheuristic operations_research::RoutingModel::metaheuristic | ( | ) | const [inline] |
| void operations_research::RoutingModel::set_metaheuristic | ( | RoutingMetaheuristic | metaheuristic | ) | [inline] |
| RoutingModel::RoutingMetaheuristic operations_research::RoutingModel::GetSelectedMetaheuristic | ( | ) | const |
If a metaheuristic flag has been set, returns the corresponding metaheuristic, otherwise returns the metaheuristic which was set.
Definition at line 1330 of file routing.cc.
| void operations_research::RoutingModel::AddSearchMonitor | ( | SearchMonitor *const | monitor | ) |
Adds a search monitor to the search used to solve the routing model.
Definition at line 1341 of file routing.cc.
| void operations_research::RoutingModel::CloseModel | ( | ) |
Closes the current routing model; after this method is called, no modification to the model can be done, but RoutesToAssignment becomes available.
Note that CloseModel() is automatically called by Solve() and other methods that produce solution.
Definition at line 1082 of file routing.cc.
| const Assignment * operations_research::RoutingModel::Solve | ( | const Assignment * | assignment = NULL |
) |
Solves the current routing model; closes the current model.
Definition at line 1345 of file routing.cc.
| int64 operations_research::RoutingModel::ComputeLowerBound | ( | ) |
Computes a lower bound to the routing problem solving a linear assignment problem.
Computing a lower bound to the cost of a vehicle routing problem solving a a linear assignment problem (minimum-cost perfect bipartite matching).
The routing model must be closed before calling this method. Note that problems with node disjunction constraints (including optional nodes) and non-homogenous costs are not supported (the method returns 0 in these cases).
A bipartite graph is created with left nodes representing the nodes of the routing problem and right nodes representing possible node successors; an arc between a left node l and a right node r is created if r can be the node folowing l in a route (Next(l) = r); the cost of the arc is the transit cost between l and r in the routing problem. This is a lower bound given the solution to assignment problem does not necessarily produce a (set of) closed route(s) from a starting node to an ending node.Definition at line 1378 of file routing.cc.
| Status operations_research::RoutingModel::status | ( | ) | const [inline] |
| IntVar * operations_research::RoutingModel::ApplyLocks | ( | const std::vector< int > & | locks | ) |
Applies a lock chain to the next search.
'locks' represents an ordered vector of nodes representing a partial route which will be fixed during the next search; it will constrain next variables such that: next[locks[i]] == locks[i+1]. Returns the next variable at the end of the locked chain; this variable is not locked. An assignment containing the locks can be obtained by calling PreAssignment().
Definition at line 1604 of file routing.cc.
| bool operations_research::RoutingModel::ApplyLocksToAllVehicles | ( | const std::vector< std::vector< NodeIndex > > & | locks, | |
| bool | close_routes | |||
| ) |
Applies lock chains to all vehicles to the next search, such that locks[p] is the lock chain for route p.
Returns false if the locks do not contain valid routes; expects that the routes do not contain the depots, i.e. there are empty vectors in place of empty routes. If close_routes is set to true, adds the end nodes to the route of each vehicle and deactivates other nodes. An assignment containing the locks can be obtained by calling PreAssignment().
Definition at line 1626 of file routing.cc.
| const Assignment* const operations_research::RoutingModel::PreAssignment | ( | ) | const [inline] |
Returns an assignment used to fix some of the variables of the problem.
In practice, this assignment locks partial routes of the problem. This can be used in the context of locking the parts of the routes which have already been driven in online routing problems.
| bool operations_research::RoutingModel::WriteAssignment | ( | const string & | file_name | ) | const |
Writes the current solution to a file containing an AssignmentProto.
Returns false if the file cannot be opened or if there is no current solution.
Definition at line 1666 of file routing.cc.
| Assignment * operations_research::RoutingModel::ReadAssignment | ( | const string & | file_name | ) |
Reads an assignment from a file and returns the current solution.
Returns NULL if the file cannot be opened or if the assignment is not valid.
Definition at line 1675 of file routing.cc.
| Assignment * operations_research::RoutingModel::RestoreAssignment | ( | const Assignment & | solution | ) |
Restores an assignment as a solution in the routing model and returns the new solution.
Returns NULL if the assignment is not valid.
Definition at line 1684 of file routing.cc.
| Assignment * operations_research::RoutingModel::ReadAssignmentFromRoutes | ( | const std::vector< std::vector< NodeIndex > > & | routes, | |
| bool | ignore_inactive_nodes | |||
| ) |
Restores the routes as the current solution.
Returns NULL if the solution cannot be restored (routes do not contain a valid solution). Note that calling this method will run the solver to assign values to the dimension variables; this may take considerable amount of time, especially when using dimensions with slack.
Definition at line 1825 of file routing.cc.
| bool operations_research::RoutingModel::RoutesToAssignment | ( | const std::vector< std::vector< NodeIndex > > & | routes, | |
| bool | ignore_inactive_nodes, | |||
| bool | close_routes, | |||
| Assignment *const | assignment | |||
| ) | const |
Fills an assignment from a specification of the routes of the vehicles.
The routes are specified as lists of nodes that appear on the routes of the vehicles. The indices of the outer vector in 'routes' correspond to vehicles IDs, the inner vector contain the nodes on the routes for the given vehicle. The inner vectors must not contain the start and end nodes, as these are determined by the routing model. Sets the value of NextVars in the assignment, adding the variables to the assignment if necessary. The method does not touch other variables in the assignment. The method can only be called after the model is closed. With ignore_inactive_nodes set to false, this method will fail (return NULL) in case some of the route contain nodes that are deactivated in the model; when set to true, these nodes will be skipped. Returns true if the route was successfully loaded. However, such assignment still might not be a valid solution to the routing problem due to more complex constraints; it is advisible to call solver()->CheckSolution() afterwards.
Definition at line 1703 of file routing.cc.
| void operations_research::RoutingModel::AssignmentToRoutes | ( | const Assignment & | assignment, | |
| std::vector< std::vector< NodeIndex > > *const | routes | |||
| ) | const |
Converts the solution in the given assignment to routes for all vehicles.
Expects that assignment contains a valid solution (i.e. routes for all vehicles end with an end node for that vehicle).
Definition at line 1838 of file routing.cc.
| Assignment * operations_research::RoutingModel::CompactAssignment | ( | const Assignment & | assignment | ) | const |
Returns a compacted version of the given assignment, in which all vehicles with id lower or equal to some N have non-empty routes, and all vehicles with id greater than N have empty routes.
Does not take ownership of the returned object. If found, the cost of the compact assignment is the same as in the original assignment and it preserves the values of 'active' variables. Returns NULL if a compact assignment was not found. This method only works in homogenous mode, and it only swaps equivalent vehicles (vehicles with the same start and end nodes). When creating the compact assignment, the empty plan is replaced by the route assigned to the compatible vehicle with the highest id. Note that with more complex constraints on vehicle variables, this method might fail even if a compact solution exists. This method changes the vehicle and dimension variables as necessary. While compacting the solution, only basic checks on vehicle variables are performed; the complete solution is checked at the end and if it is not valid, no attempts to repair it are made (instead, the method returns NULL).
Definition at line 1527 of file routing.cc.
| void operations_research::RoutingModel::AddToAssignment | ( | IntVar *const | var | ) |
Adds an extra variable to the vehicle routing assignment.
Definition at line 2487 of file routing.cc.
| int operations_research::RoutingModel::Start | ( | int | vehicle | ) | const [inline] |
| int operations_research::RoutingModel::End | ( | int | vehicle | ) | const [inline] |
| bool operations_research::RoutingModel::IsStart | ( | int64 | index | ) | const |
Returns true if 'index' represents the first node of a route.
Definition at line 1944 of file routing.cc.
| bool operations_research::RoutingModel::IsEnd | ( | int64 | index | ) | const [inline] |
| int64 operations_research::RoutingModel::GetFirstSolutionCost | ( | int64 | i, | |
| int64 | j | |||
| ) |
Return high cost if connecting to end node; used in cost-based first solution.
Definition at line 1984 of file routing.cc.
| bool operations_research::RoutingModel::homogeneous_costs | ( | ) | const [inline] |
| int operations_research::RoutingModel::Next | ( | const Assignment & | assignment, | |
| int | index | |||
| ) | const |
Assignment inspection Returns the variable index of the node directly after the node corresponding to 'index' in 'assignment'.
Definition at line 1958 of file routing.cc.
| bool operations_research::RoutingModel::IsVehicleUsed | ( | const Assignment & | assignment, | |
| int | vehicle | |||
| ) | const |
Returns true if the route of 'vehicle' is non empty in 'assignment'.
Definition at line 1948 of file routing.cc.
| IntVar** operations_research::RoutingModel::Nexts | ( | ) | const [inline] |
| IntVar** operations_research::RoutingModel::VehicleVars | ( | ) | const [inline] |
| IntVar* operations_research::RoutingModel::NextVar | ( | int64 | index | ) | const [inline] |
| IntVar* operations_research::RoutingModel::ActiveVar | ( | int64 | index | ) | const [inline] |
| IntVar* operations_research::RoutingModel::VehicleVar | ( | int64 | index | ) | const [inline] |
| IntVar * operations_research::RoutingModel::CumulVar | ( | int64 | index, | |
| const string & | name | |||
| ) | const |
Returns the cumul variable for the dimension named 'name'.
Definition at line 2469 of file routing.cc.
| IntVar * operations_research::RoutingModel::TransitVar | ( | int64 | index, | |
| const string & | name | |||
| ) | const |
Returns the transit variable for the dimension named 'name'.
Definition at line 2478 of file routing.cc.
| IntVar* operations_research::RoutingModel::CostVar | ( | ) | const [inline] |
| int64 operations_research::RoutingModel::GetCost | ( | int64 | from_index, | |
| int64 | to_index, | |||
| int64 | vehicle | |||
| ) |
Returns the cost of the segment between two nodes for a given vehicle route.
Input are variable indices of node.
Definition at line 1967 of file routing.cc.
| int64 operations_research::RoutingModel::GetHomogeneousCost | ( | int64 | i, | |
| int64 | j | |||
| ) | [inline] |
| Solver* operations_research::RoutingModel::solver | ( | ) | const [inline] |
| int operations_research::RoutingModel::nodes | ( | ) | const [inline] |
| int operations_research::RoutingModel::vehicles | ( | ) | const [inline] |
| int operations_research::RoutingModel::Size | ( | ) | const [inline] |
| RoutingModel::NodeIndex operations_research::RoutingModel::IndexToNode | ( | int64 | index | ) | const |
Returns the node index from an index value resulting fron a next variable.
Definition at line 1871 of file routing.cc.
| int64 operations_research::RoutingModel::NodeToIndex | ( | NodeIndex | node | ) | const |
Returns the variable index from a node value.
Should not be used for nodes at the start / end of a route, because of node multiplicity. These cases return -1, which is considered a failure case. Clients who need start and end variable indices should use RoutingModel::Start and RoutingModel::End.
Definition at line 1876 of file routing.cc.
| void operations_research::RoutingModel::GetDisjunctionIndicesFromIndex | ( | int64 | index, | |
| std::vector< int > * | indices | |||
| ) | const |
Returns the variable indices of the nodes in the same disjunction as the node corresponding to the variable of index 'index'.
Definition at line 1882 of file routing.cc.
| int64 operations_research::RoutingModel::TimeLimit | ( | ) | const [inline] |
| void operations_research::RoutingModel::UpdateTimeLimit | ( | int64 | limit_ms | ) |
| void operations_research::RoutingModel::UpdateLNSTimeLimit | ( | int64 | limit_ms | ) |
Updates the time limit used in the Large Neighborhood search tree.
Definition at line 1650 of file routing.cc.
| void operations_research::RoutingModel::SetCommandLineOption | ( | const string & | name, | |
| const string & | value | |||
| ) |