OR-Tools  8.2
RoutingModel

Detailed Description

Definition at line 213 of file routing.h.

Classes

struct  CostClass
 
struct  StateDependentTransit
 What follows is relevant for models with time/state dependent transits. More...
 
struct  VehicleClass
 
struct  VehicleTypeContainer
 Struct used to sort and store vehicles by their type. More...
 

Public Types

enum  Status {
  ROUTING_NOT_SOLVED , ROUTING_SUCCESS , ROUTING_FAIL , ROUTING_FAIL_TIMEOUT ,
  ROUTING_INVALID
}
 Status of the search. More...
 
enum  PickupAndDeliveryPolicy { PICKUP_AND_DELIVERY_NO_ORDER , PICKUP_AND_DELIVERY_LIFO , PICKUP_AND_DELIVERY_FIFO }
 Types of precedence policy applied to pickup and delivery pairs. More...
 
enum  VisitTypePolicy { TYPE_ADDED_TO_VEHICLE , ADDED_TYPE_REMOVED_FROM_VEHICLE , TYPE_ON_VEHICLE_UP_TO_VISIT , TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED }
 Set the node visit types and incompatibilities/requirements between the types (see below). More...
 
typedef RoutingCostClassIndex CostClassIndex
 
typedef RoutingDimensionIndex DimensionIndex
 
typedef RoutingDisjunctionIndex DisjunctionIndex
 
typedef RoutingVehicleClassIndex VehicleClassIndex
 
typedef RoutingTransitCallback1 TransitCallback1
 
typedef RoutingTransitCallback2 TransitCallback2
 
typedef RoutingIndexPair IndexPair
 
typedef RoutingIndexPairs IndexPairs
 
typedef std::function< StateDependentTransit(int64, int64)> VariableIndexEvaluator2
 
using GetTabuVarsCallback = std::function< std::vector< operations_research::IntVar * >(RoutingModel *)>
 Sets the callback returning the variable to use for the Tabu Search metaheuristic. More...
 

Public Member Functions

 RoutingModel (const RoutingIndexManager &index_manager)
 Constructor taking an index manager. More...
 
 RoutingModel (const RoutingIndexManager &index_manager, const RoutingModelParameters &parameters)
 
 ~RoutingModel ()
 
int RegisterUnaryTransitVector (std::vector< int64 > values)
 Registers 'callback' and returns its index. More...
 
int RegisterUnaryTransitCallback (TransitCallback1 callback)
 
int RegisterPositiveUnaryTransitCallback (TransitCallback1 callback)
 
int RegisterTransitMatrix (std::vector< std::vector< int64 > > values)
 
int RegisterTransitCallback (TransitCallback2 callback)
 
int RegisterPositiveTransitCallback (TransitCallback2 callback)
 
int RegisterStateDependentTransitCallback (VariableIndexEvaluator2 callback)
 
const TransitCallback2TransitCallback (int callback_index) const
 
const TransitCallback1UnaryTransitCallbackOrNull (int callback_index) const
 
const VariableIndexEvaluator2StateDependentTransitCallback (int callback_index) const
 
bool AddDimension (int evaluator_index, int64 slack_max, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
 Model creation. More...
 
bool AddDimensionWithVehicleTransits (const std::vector< int > &evaluator_indices, int64 slack_max, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
 
bool AddDimensionWithVehicleCapacity (int evaluator_index, int64 slack_max, std::vector< int64 > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
 
bool AddDimensionWithVehicleTransitAndCapacity (const std::vector< int > &evaluator_indices, int64 slack_max, std::vector< int64 > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
 
std::pair< int, bool > AddConstantDimensionWithSlack (int64 value, int64 capacity, int64 slack_max, bool fix_start_cumul_to_zero, const std::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. More...
 
std::pair< int, bool > AddConstantDimension (int64 value, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
 
std::pair< int, bool > AddVectorDimension (std::vector< int64 > values, int64 capacity, bool fix_start_cumul_to_zero, const std::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. More...
 
std::pair< int, bool > AddMatrixDimension (std::vector< std::vector< int64 > > values, int64 capacity, bool fix_start_cumul_to_zero, const std::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. More...
 
bool AddDimensionDependentDimensionWithVehicleCapacity (const std::vector< int > &pure_transits, const std::vector< int > &dependent_transits, const RoutingDimension *base_dimension, int64 slack_max, std::vector< int64 > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
 Creates a dimension with transits depending on the cumuls of another dimension. More...
 
bool AddDimensionDependentDimensionWithVehicleCapacity (const std::vector< int > &transits, const RoutingDimension *base_dimension, int64 slack_max, std::vector< int64 > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
 As above, but pure_transits are taken to be zero evaluators. More...
 
bool AddDimensionDependentDimensionWithVehicleCapacity (int transit, const RoutingDimension *base_dimension, int64 slack_max, int64 vehicle_capacity, bool fix_start_cumul_to_zero, const std::string &name)
 Homogeneous versions of the functions above. More...
 
bool AddDimensionDependentDimensionWithVehicleCapacity (int pure_transit, int dependent_transit, const RoutingDimension *base_dimension, int64 slack_max, int64 vehicle_capacity, bool fix_start_cumul_to_zero, const std::string &name)
 
ConstraintMakePathSpansAndTotalSlacks (const RoutingDimension *dimension, std::vector< IntVar * > spans, std::vector< IntVar * > total_slacks)
 For every vehicle of the routing model: More...
 
std::vector< std::string > GetAllDimensionNames () const
 Outputs the names of all dimensions added to the routing engine. More...
 
const std::vector< RoutingDimension * > & GetDimensions () const
 Returns all dimensions of the model. More...
 
std::vector< RoutingDimension * > GetDimensionsWithSoftOrSpanCosts () const
 Returns dimensions with soft or vehicle span costs. More...
 
const std::vector< std::unique_ptr< GlobalDimensionCumulOptimizer > > & GetGlobalDimensionCumulOptimizers () const
 Returns [global|local]_dimension_optimizers_, which are empty if the model has not been closed. More...
 
const std::vector< std::unique_ptr< LocalDimensionCumulOptimizer > > & GetLocalDimensionCumulOptimizers () const
 
const std::vector< std::unique_ptr< LocalDimensionCumulOptimizer > > & GetLocalDimensionCumulMPOptimizers () const
 
GlobalDimensionCumulOptimizerGetMutableGlobalCumulOptimizer (const RoutingDimension &dimension) const
 Returns the global/local dimension cumul optimizer for a given dimension, or nullptr if there is none. More...
 
LocalDimensionCumulOptimizerGetMutableLocalCumulOptimizer (const RoutingDimension &dimension) const
 
LocalDimensionCumulOptimizerGetMutableLocalCumulMPOptimizer (const RoutingDimension &dimension) const
 
bool HasDimension (const std::string &dimension_name) const
 Returns true if a dimension exists for a given dimension name. More...
 
const RoutingDimensionGetDimensionOrDie (const std::string &dimension_name) const
 Returns a dimension from its name. Dies if the dimension does not exist. More...
 
RoutingDimensionGetMutableDimension (const std::string &dimension_name) const
 Returns a dimension from its name. More...
 
void SetPrimaryConstrainedDimension (const std::string &dimension_name)
 Set the given dimension as "primary constrained". More...
 
const std::string & GetPrimaryConstrainedDimension () const
 Get the primary constrained dimension, or an empty string if it is unset. More...
 
DisjunctionIndex AddDisjunction (const std::vector< int64 > &indices, int64 penalty=kNoPenalty, int64 max_cardinality=1)
 Adds a disjunction constraint on the indices: exactly 'max_cardinality' of the indices are active. More...
 
const std::vector< DisjunctionIndex > & GetDisjunctionIndices (int64 index) const
 Returns the indices of the disjunctions to which an index belongs. More...
 
template<typename F >
void ForEachNodeInDisjunctionWithMaxCardinalityFromIndex (int64 index, int64 max_cardinality, F f) const
 Calls f for each variable index of indices in the same disjunctions as the node corresponding to the variable index 'index'; only disjunctions of cardinality 'cardinality' are considered. More...
 
const std::vector< int64 > & GetDisjunctionIndices (DisjunctionIndex index) const
 Returns the variable indices of the nodes in the disjunction of index 'index'. More...
 
int64 GetDisjunctionPenalty (DisjunctionIndex index) const
 Returns the penalty of the node disjunction of index 'index'. More...
 
int64 GetDisjunctionMaxCardinality (DisjunctionIndex index) const
 Returns the maximum number of possible active nodes of the node disjunction of index 'index'. More...
 
int GetNumberOfDisjunctions () const
 Returns the number of node disjunctions in the model. More...
 
std::vector< std::pair< int64, int64 > > GetPerfectBinaryDisjunctions () const
 Returns the list of all perfect binary disjunctions, as pairs of variable indices: a disjunction is "perfect" when its variables do not appear in any other disjunction. More...
 
void IgnoreDisjunctionsAlreadyForcedToZero ()
 SPECIAL: Makes the solver ignore all the disjunctions whose active variables are all trivially zero (i.e. More...
 
void AddSoftSameVehicleConstraint (const std::vector< int64 > &indices, int64 cost)
 Adds a soft constraint to force a set of variable indices to be on the same vehicle. More...
 
void SetAllowedVehiclesForIndex (const std::vector< int > &vehicles, int64 index)
 Sets the vehicles which can visit a given node. More...
 
bool IsVehicleAllowedForIndex (int vehicle, int64 index)
 Returns true if a vehicle is allowed to visit a given node. More...
 
void AddPickupAndDelivery (int64 pickup, int64 delivery)
 Notifies that index1 and index2 form a pair of nodes which should belong to the same route. More...
 
void AddPickupAndDeliverySets (DisjunctionIndex pickup_disjunction, DisjunctionIndex delivery_disjunction)
 Same as AddPickupAndDelivery but notifying that the performed node from the disjunction of index 'pickup_disjunction' is on the same route as the performed node from the disjunction of index 'delivery_disjunction'. More...
 
const std::vector< std::pair< int, int > > & GetPickupIndexPairs (int64 node_index) const
 Returns pairs for which the node is a pickup; the first element of each pair is the index in the pickup and delivery pairs list in which the pickup appears, the second element is its index in the pickups list. More...
 
const std::vector< std::pair< int, int > > & GetDeliveryIndexPairs (int64 node_index) const
 Same as above for deliveries. More...
 
void SetPickupAndDeliveryPolicyOfAllVehicles (PickupAndDeliveryPolicy policy)
 Sets the Pickup and delivery policy of all vehicles. More...
 
void SetPickupAndDeliveryPolicyOfVehicle (PickupAndDeliveryPolicy policy, int vehicle)
 
PickupAndDeliveryPolicy GetPickupAndDeliveryPolicyOfVehicle (int vehicle) const
 
int GetNumOfSingletonNodes () const
 Returns the number of non-start/end nodes which do not appear in a pickup/delivery pair. More...
 
const IndexPairsGetPickupAndDeliveryPairs () const
 Returns pickup and delivery pairs currently in the model. More...
 
const std::vector< std::pair< DisjunctionIndex, DisjunctionIndex > > & GetPickupAndDeliveryDisjunctions () const
 
const IndexPairsGetImplicitUniquePickupAndDeliveryPairs () const
 Returns implicit pickup and delivery pairs currently in the model. More...
 
void SetVisitType (int64 index, int type, VisitTypePolicy type_policy)
 
int GetVisitType (int64 index) const
 
const std::vector< int > & GetSingleNodesOfType (int type) const
 
const std::vector< int > & GetPairIndicesOfType (int type) const
 
VisitTypePolicy GetVisitTypePolicy (int64 index) const
 
void CloseVisitTypes ()
 This function should be called once all node visit types have been set and prior to adding any incompatibilities/requirements. More...
 
int GetNumberOfVisitTypes () const
 
const std::vector< std::vector< int > > & GetTopologicallySortedVisitTypes () const
 
void AddHardTypeIncompatibility (int type1, int type2)
 Incompatibilities: Two nodes with "hard" incompatible types cannot share the same route at all, while with a "temporal" incompatibility they can't be on the same route at the same time. More...
 
void AddTemporalTypeIncompatibility (int type1, int type2)
 
const absl::flat_hash_set< int > & GetHardTypeIncompatibilitiesOfType (int type) const
 Returns visit types incompatible with a given type. More...
 
const absl::flat_hash_set< int > & GetTemporalTypeIncompatibilitiesOfType (int type) const
 
bool HasHardTypeIncompatibilities () const
 Returns true iff any hard (resp. More...
 
bool HasTemporalTypeIncompatibilities () const
 
void AddSameVehicleRequiredTypeAlternatives (int dependent_type, absl::flat_hash_set< int > required_type_alternatives)
 Requirements: NOTE: As of 2019-04, cycles in the requirement graph are not supported, and lead to the dependent nodes being skipped if possible (otherwise the model is considered infeasible). More...
 
void AddRequiredTypeAlternativesWhenAddingType (int dependent_type, absl::flat_hash_set< int > required_type_alternatives)
 If type_D depends on type_R when adding type_D, any node_D of type_D and VisitTypePolicy TYPE_ADDED_TO_VEHICLE or TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED requires at least one type_R on its vehicle at the time node_D is visited. More...
 
void AddRequiredTypeAlternativesWhenRemovingType (int dependent_type, absl::flat_hash_set< int > required_type_alternatives)
 The following requirements apply when visiting dependent nodes that remove their type from the route, i.e. More...
 
const std::vector< absl::flat_hash_set< int > > & GetSameVehicleRequiredTypeAlternativesOfType (int type) const
 Returns the set of same-vehicle requirement alternatives for the given type. More...
 
const std::vector< absl::flat_hash_set< int > > & GetRequiredTypeAlternativesWhenAddingType (int type) const
 Returns the set of requirement alternatives when adding the given type. More...
 
const std::vector< absl::flat_hash_set< int > > & GetRequiredTypeAlternativesWhenRemovingType (int type) const
 Returns the set of requirement alternatives when removing the given type. More...
 
bool HasSameVehicleTypeRequirements () const
 Returns true iff any same-route (resp. More...
 
bool HasTemporalTypeRequirements () const
 
bool HasTypeRegulations () const
 Returns true iff the model has any incompatibilities or requirements set on node types. More...
 
int64 UnperformedPenalty (int64 var_index) const
 Get the "unperformed" penalty of a node. More...
 
int64 UnperformedPenaltyOrValue (int64 default_value, int64 var_index) const
 Same as above except that it returns default_value instead of 0 when penalty is not well defined (default value is passed as first argument to simplify the usage of the method in a callback). More...
 
int64 GetDepot () const
 Returns the variable index of the first starting or ending node of all routes. More...
 
void SetMaximumNumberOfActiveVehicles (int max_active_vehicles)
 Constrains the maximum number of active vehicles, aka the number of vehicles which do not have an empty route. More...
 
int GetMaximumNumberOfActiveVehicles () const
 Returns the maximum number of active vehicles. More...
 
void SetArcCostEvaluatorOfAllVehicles (int evaluator_index)
 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. More...
 
void SetArcCostEvaluatorOfVehicle (int evaluator_index, int vehicle)
 Sets the cost function for a given vehicle route. More...
 
void SetFixedCostOfAllVehicles (int64 cost)
 Sets the fixed cost of all vehicle routes. More...
 
void SetFixedCostOfVehicle (int64 cost, int vehicle)
 Sets the fixed cost of one vehicle route. More...
 
int64 GetFixedCostOfVehicle (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. More...
 
void SetAmortizedCostFactorsOfAllVehicles (int64 linear_cost_factor, int64 quadratic_cost_factor)
 The following methods set the linear and quadratic cost factors of vehicles (must be positive values). More...
 
void SetAmortizedCostFactorsOfVehicle (int64 linear_cost_factor, int64 quadratic_cost_factor, int vehicle)
 Sets the linear and quadratic cost factor of the given vehicle. More...
 
const std::vector< int64 > & GetAmortizedLinearCostFactorOfVehicles () const
 
const std::vector< int64 > & GetAmortizedQuadraticCostFactorOfVehicles () const
 
void ConsiderEmptyRouteCostsForVehicle (bool consider_costs, int vehicle)
 
bool AreEmptyRouteCostsConsideredForVehicle (int vehicle) const
 
const Solver::IndexEvaluator2first_solution_evaluator () const
 Gets/sets the evaluator used during the search. More...
 
void SetFirstSolutionEvaluator (Solver::IndexEvaluator2 evaluator)
 Takes ownership of evaluator. More...
 
void AddLocalSearchOperator (LocalSearchOperator *ls_operator)
 Adds a local search operator to the set of operators used to solve the vehicle routing problem. More...
 
void AddSearchMonitor (SearchMonitor *const monitor)
 Adds a search monitor to the search used to solve the routing model. More...
 
void AddAtSolutionCallback (std::function< void()> callback)
 Adds a callback called each time a solution is found during the search. More...
 
void AddVariableMinimizedByFinalizer (IntVar *var)
 Adds a variable to minimize in the solution finalizer. More...
 
void AddVariableMaximizedByFinalizer (IntVar *var)
 Adds a variable to maximize in the solution finalizer (see above for information on the solution finalizer). More...
 
void AddWeightedVariableMinimizedByFinalizer (IntVar *var, int64 cost)
 Adds a variable to minimize in the solution finalizer, with a weighted priority: the higher the more priority it has. More...
 
void AddVariableTargetToFinalizer (IntVar *var, int64 target)
 Add a variable to set the closest possible to the target value in the solution finalizer. More...
 
void CloseModel ()
 Closes the current routing model; after this method is called, no modification to the model can be done, but RoutesToAssignment becomes available. More...
 
void CloseModelWithParameters (const RoutingSearchParameters &search_parameters)
 Same as above taking search parameters (as of 10/2015 some the parameters have to be set when closing the model). More...
 
const AssignmentSolve (const Assignment *assignment=nullptr)
 Solves the current routing model; closes the current model. More...
 
const AssignmentSolveWithParameters (const RoutingSearchParameters &search_parameters, std::vector< const Assignment * > *solutions=nullptr)
 Solves the current routing model with the given parameters. More...
 
const AssignmentSolveFromAssignmentWithParameters (const Assignment *assignment, const RoutingSearchParameters &search_parameters, std::vector< const Assignment * > *solutions=nullptr)
 
void SetAssignmentFromOtherModelAssignment (Assignment *target_assignment, const RoutingModel *source_model, const Assignment *source_assignment)
 Given a "source_model" and its "source_assignment", resets "target_assignment" with the IntVar variables (nexts_, and vehicle_vars_ if costs aren't homogeneous across vehicles) of "this" model, with the values set according to those in "other_assignment". More...
 
int64 ComputeLowerBound ()
 Computes a lower bound to the routing problem solving a linear assignment problem. More...
 
Status status () const
 Returns the current status of the routing model. More...
 
IntVarApplyLocks (const std::vector< int64 > &locks)
 Applies a lock chain to the next search. More...
 
bool ApplyLocksToAllVehicles (const std::vector< std::vector< int64 > > &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. More...
 
const Assignment *const PreAssignment () const
 Returns an assignment used to fix some of the variables of the problem. More...
 
AssignmentMutablePreAssignment ()
 
bool WriteAssignment (const std::string &file_name) const
 Writes the current solution to a file containing an AssignmentProto. More...
 
AssignmentReadAssignment (const std::string &file_name)
 Reads an assignment from a file and returns the current solution. More...
 
AssignmentRestoreAssignment (const Assignment &solution)
 Restores an assignment as a solution in the routing model and returns the new solution. More...
 
AssignmentReadAssignmentFromRoutes (const std::vector< std::vector< int64 > > &routes, bool ignore_inactive_indices)
 Restores the routes as the current solution. More...
 
bool RoutesToAssignment (const std::vector< std::vector< int64 > > &routes, bool ignore_inactive_indices, bool close_routes, Assignment *const assignment) const
 Fills an assignment from a specification of the routes of the vehicles. More...
 
void AssignmentToRoutes (const Assignment &assignment, std::vector< std::vector< int64 > > *const routes) const
 Converts the solution in the given assignment to routes for all vehicles. More...
 
std::vector< std::vector< int64 > > GetRoutesFromAssignment (const Assignment &assignment)
 Converts the solution in the given assignment to routes for all vehicles. More...
 
AssignmentCompactAssignment (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. More...
 
AssignmentCompactAndCheckAssignment (const Assignment &assignment) const
 Same as CompactAssignment() but also checks the validity of the final compact solution; if it is not valid, no attempts to repair it are made (instead, the method returns nullptr). More...
 
void AddToAssignment (IntVar *const var)
 Adds an extra variable to the vehicle routing assignment. More...
 
void AddIntervalToAssignment (IntervalVar *const interval)
 
const AssignmentPackCumulsOfOptimizerDimensionsFromAssignment (const Assignment *original_assignment, absl::Duration duration_limit)
 For every dimension in the model with an optimizer in local/global_dimension_optimizers_, this method tries to pack the cumul values of the dimension, such that: More...
 
void SetSweepArranger (SweepArranger *sweep_arranger)
 
SweepArrangersweep_arranger () const
 Returns the sweep arranger to be used by routing heuristics. More...
 
void AddLocalSearchFilter (LocalSearchFilter *filter)
 Adds a custom local search filter to the list of filters used to speed up local search by pruning unfeasible variable assignments. More...
 
int64 Start (int vehicle) const
 Model inspection. More...
 
int64 End (int vehicle) const
 Returns the variable index of the ending node of a vehicle route. More...
 
bool IsStart (int64 index) const
 Returns true if 'index' represents the first node of a route. More...
 
bool IsEnd (int64 index) const
 Returns true if 'index' represents the last node of a route. More...
 
int VehicleIndex (int64 index) const
 Returns the vehicle of the given start/end index, and -1 if the given index is not a vehicle start/end. More...
 
int64 Next (const Assignment &assignment, int64 index) const
 Assignment inspection Returns the variable index of the node directly after the node corresponding to 'index' in 'assignment'. More...
 
bool IsVehicleUsed (const Assignment &assignment, int vehicle) const
 Returns true if the route of 'vehicle' is non empty in 'assignment'. More...
 
const std::vector< IntVar * > & Nexts () const
 Returns all next variables of the model, such that Nexts(i) is the next variable of the node corresponding to i. More...
 
const std::vector< IntVar * > & VehicleVars () const
 Returns all vehicle variables of the model, such that VehicleVars(i) is the vehicle variable of the node corresponding to i. More...
 
IntVarNextVar (int64 index) const
 !defined(SWIGPYTHON) More...
 
IntVarActiveVar (int64 index) const
 Returns the active variable of the node corresponding to index. More...
 
IntVarActiveVehicleVar (int vehicle) const
 Returns the active variable of the vehicle. More...
 
IntVarVehicleCostsConsideredVar (int vehicle) const
 Returns the variable specifying whether or not costs are considered for vehicle. More...
 
IntVarVehicleVar (int64 index) const
 Returns the vehicle variable of the node corresponding to index. More...
 
IntVarCostVar () const
 Returns the global cost variable which is being minimized. More...
 
int64 GetArcCostForVehicle (int64 from_index, int64 to_index, int64 vehicle) const
 Returns the cost of the transit arc between two nodes for a given vehicle. More...
 
bool CostsAreHomogeneousAcrossVehicles () const
 Whether costs are homogeneous across all vehicles. More...
 
int64 GetHomogeneousCost (int64 from_index, int64 to_index) const
 Returns the cost of the segment between two nodes supposing all vehicle costs are the same (returns the cost for the first vehicle otherwise). More...
 
int64 GetArcCostForFirstSolution (int64 from_index, int64 to_index) const
 Returns the cost of the arc in the context of the first solution strategy. More...
 
int64 GetArcCostForClass (int64 from_index, int64 to_index, int64 cost_class_index) const
 Returns the cost of the segment between two nodes for a given cost class. More...
 
CostClassIndex GetCostClassIndexOfVehicle (int64 vehicle) const
 Get the cost class index of the given vehicle. More...
 
bool HasVehicleWithCostClassIndex (CostClassIndex cost_class_index) const
 Returns true iff the model contains a vehicle with the given cost_class_index. More...
 
int GetCostClassesCount () const
 Returns the number of different cost classes in the model. More...
 
int GetNonZeroCostClassesCount () const
 Ditto, minus the 'always zero', built-in cost class. More...
 
VehicleClassIndex GetVehicleClassIndexOfVehicle (int64 vehicle) const
 
int GetVehicleClassesCount () const
 Returns the number of different vehicle classes in the model. More...
 
const std::vector< int > & GetSameVehicleIndicesOfIndex (int node) const
 Returns variable indices of nodes constrained to be on the same route. More...
 
const VehicleTypeContainerGetVehicleTypeContainer () const
 
bool ArcIsMoreConstrainedThanArc (int64 from, int64 to1, int64 to2)
 Returns whether the arc from->to1 is more constrained than from->to2, taking into account, in order: More...
 
std::string DebugOutputAssignment (const Assignment &solution_assignment, const std::string &dimension_to_print) const
 Print some debugging information about an assignment, including the feasible intervals of the CumulVar for dimension "dimension_to_print" at each step of the routes. More...
 
std::vector< std::vector< std::pair< int64, int64 > > > GetCumulBounds (const Assignment &solution_assignment, const RoutingDimension &dimension)
 Returns a vector cumul_bounds, for which cumul_bounds[i][j] is a pair containing the minimum and maximum of the CumulVar of the jth node on route i. More...
 
Solversolver () const
 Returns the underlying constraint solver. More...
 
bool CheckLimit ()
 Returns true if the search limit has been crossed. More...
 
absl::Duration RemainingTime () const
 Returns the time left in the search limit. More...
 
int nodes () const
 Sizes and indices Returns the number of nodes in the model. More...
 
int vehicles () const
 Returns the number of vehicle routes in the model. More...
 
int64 Size () const
 Returns the number of next variables in the model. More...
 
int64 GetNumberOfDecisionsInFirstSolution (const RoutingSearchParameters &search_parameters) const
 Returns statistics on first solution search, number of decisions sent to filters, number of decisions rejected by filters. More...
 
int64 GetNumberOfRejectsInFirstSolution (const RoutingSearchParameters &search_parameters) const
 
operations_research::FirstSolutionStrategy::Value GetAutomaticFirstSolutionStrategy () const
 Returns the automatic first solution strategy selected. More...
 
bool IsMatchingModel () const
 Returns true if a vehicle/node matching problem is detected. More...
 
void SetTabuVarsCallback (GetTabuVarsCallback tabu_var_callback)
 
DecisionBuilderMakeGuidedSlackFinalizer (const RoutingDimension *dimension, std::function< int64(int64)> initializer)
 The next few members are in the public section only for testing purposes. More...
 
DecisionBuilderMakeSelfDependentDimensionFinalizer (const RoutingDimension *dimension)
 SWIG More...
 

Static Public Member Functions

static RoutingModel::StateDependentTransit MakeStateDependentTransit (const std::function< int64(int64)> &f, int64 domain_start, int64 domain_end)
 Creates a cached StateDependentTransit from an std::function. More...
 
static std::unique_ptr< LocalSearchOperatorMakeGreedyDescentLSOperator (std::vector< IntVar * > variables)
 Perhaps move it to constraint_solver.h. More...
 

Static Public Attributes

static const int64 kNoPenalty = -1
 Constant used to express a hard constraint instead of a soft penalty. More...
 
static const DisjunctionIndex kNoDisjunction
 Constant used to express the "no disjunction" index, returned when a node does not appear in any disjunction. More...
 
static const DimensionIndex kNoDimension
 Constant used to express the "no dimension" index, returned when a dimension name does not correspond to an actual dimension. More...
 

Member Typedef Documentation

◆ CostClassIndex

typedef RoutingCostClassIndex CostClassIndex

Definition at line 238 of file routing.h.

◆ DimensionIndex

typedef RoutingDimensionIndex DimensionIndex

Definition at line 239 of file routing.h.

◆ DisjunctionIndex

typedef RoutingDisjunctionIndex DisjunctionIndex

Definition at line 240 of file routing.h.

◆ GetTabuVarsCallback

using GetTabuVarsCallback = std::function<std::vector<operations_research::IntVar*>(RoutingModel*)>

Sets the callback returning the variable to use for the Tabu Search metaheuristic.

Definition at line 1367 of file routing.h.

◆ IndexPair

Definition at line 247 of file routing.h.

◆ IndexPairs

Definition at line 248 of file routing.h.

◆ TransitCallback1

Definition at line 242 of file routing.h.

◆ TransitCallback2

Definition at line 243 of file routing.h.

◆ VariableIndexEvaluator2

Definition at line 269 of file routing.h.

◆ VehicleClassIndex

typedef RoutingVehicleClassIndex VehicleClassIndex

Definition at line 241 of file routing.h.

Member Enumeration Documentation

◆ PickupAndDeliveryPolicy

Types of precedence policy applied to pickup and delivery pairs.

Enumerator
PICKUP_AND_DELIVERY_NO_ORDER 

Any precedence is accepted.

PICKUP_AND_DELIVERY_LIFO 

Deliveries must be performed in reverse order of pickups.

PICKUP_AND_DELIVERY_FIFO 

Deliveries must be performed in the same order as pickups.

Definition at line 230 of file routing.h.

◆ Status

enum Status

Status of the search.

Enumerator
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().

ROUTING_INVALID 

Model, model parameters or flags are not valid.

Definition at line 216 of file routing.h.

◆ VisitTypePolicy

Set the node visit types and incompatibilities/requirements between the types (see below).

NOTE: Before adding any incompatibilities and/or requirements on types: 1) All corresponding node types must have been set. 2) CloseVisitTypes() must be called so all containers are resized accordingly.

The following enum is used to describe how a node with a given type 'T' impacts the number of types 'T' on the route when visited, and thus determines how temporal incompatibilities and requirements take effect.

Enumerator
TYPE_ADDED_TO_VEHICLE 

When visited, the number of types 'T' on the vehicle increases by one.

ADDED_TYPE_REMOVED_FROM_VEHICLE 

When visited, one instance of type 'T' previously added to the route (TYPE_ADDED_TO_VEHICLE), if any, is removed from the vehicle.

If the type was not previously added to the route or all added instances have already been removed, this visit has no effect on the types.

TYPE_ON_VEHICLE_UP_TO_VISIT 

With the following policy, the visit enforces that type 'T' is considered on the route from its start until this node is visited.

TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED 

The visit doesn't have an impact on the number of types 'T' on the route, as it's (virtually) added and removed directly.

This policy can be used for visits which are part of an incompatibility or requirement set without affecting the type count on the route.

Definition at line 773 of file routing.h.

Constructor & Destructor Documentation

◆ RoutingModel() [1/2]

RoutingModel ( const RoutingIndexManager index_manager)
explicit

Constructor taking an index manager.

The version which does not take RoutingModelParameters is equivalent to passing DefaultRoutingModelParameters().

Definition at line 645 of file routing.cc.

◆ RoutingModel() [2/2]

RoutingModel ( const RoutingIndexManager index_manager,
const RoutingModelParameters &  parameters 
)

Definition at line 648 of file routing.cc.

◆ ~RoutingModel()

Definition at line 738 of file routing.cc.

Member Function Documentation

◆ ActiveVar()

IntVar * ActiveVar ( int64  index) const
inline

Returns the active variable of the node corresponding to index.

Definition at line 1209 of file routing.h.

◆ ActiveVehicleVar()

IntVar * ActiveVehicleVar ( int  vehicle) const
inline

Returns the active variable of the vehicle.

It will be equal to 1 iff the route of the vehicle is not empty, 0 otherwise.

Definition at line 1212 of file routing.h.

◆ AddAtSolutionCallback()

void AddAtSolutionCallback ( std::function< void()>  callback)

Adds a callback called each time a solution is found during the search.

This is a shortcut to creating a monitor to call the callback on AtSolution() and adding it with AddSearchMonitor.

Definition at line 3126 of file routing.cc.

◆ AddConstantDimension()

std::pair< int, bool > AddConstantDimension ( int64  value,
int64  capacity,
bool  fix_start_cumul_to_zero,
const std::string &  name 
)
inline

Definition at line 473 of file routing.h.

◆ AddConstantDimensionWithSlack()

std::pair< int, bool > AddConstantDimensionWithSlack ( int64  value,
int64  capacity,
int64  slack_max,
bool  fix_start_cumul_to_zero,
const std::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. Returns a pair consisting of an index to the registered unary transit callback and a bool denoting whether the dimension has been created. It is false if a dimension with the same name has already been created (and doesn't create the new dimension but still register a new callback).

Definition at line 952 of file routing.cc.

◆ AddDimension()

bool AddDimension ( int  evaluator_index,
int64  slack_max,
int64  capacity,
bool  fix_start_cumul_to_zero,
const std::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). Setting the value of fix_start_cumul_to_zero to true will force the "cumul" variable of the start node of all vehicles to be equal to 0. 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. Returns false if a dimension with the same name has already been created (and doesn't create the new dimension). Takes ownership of the callback 'evaluator'.

Definition at line 875 of file routing.cc.

◆ AddDimensionDependentDimensionWithVehicleCapacity() [1/4]

bool AddDimensionDependentDimensionWithVehicleCapacity ( const std::vector< int > &  pure_transits,
const std::vector< int > &  dependent_transits,
const RoutingDimension base_dimension,
int64  slack_max,
std::vector< int64 vehicle_capacities,
bool  fix_start_cumul_to_zero,
const std::string &  name 
)
inline

Creates a dimension with transits depending on the cumuls of another dimension.

'pure_transits' are the per-vehicle fixed transits as above. 'dependent_transits' is a vector containing for each vehicle an index to a registered state dependent transit callback. 'base_dimension' indicates the dimension from which the cumul variable is taken. If 'base_dimension' is nullptr, then the newly created dimension is self-based.

Definition at line 510 of file routing.h.

◆ AddDimensionDependentDimensionWithVehicleCapacity() [2/4]

bool AddDimensionDependentDimensionWithVehicleCapacity ( const std::vector< int > &  transits,
const RoutingDimension base_dimension,
int64  slack_max,
std::vector< int64 vehicle_capacities,
bool  fix_start_cumul_to_zero,
const std::string &  name 
)

As above, but pure_transits are taken to be zero evaluators.

Definition at line 1058 of file routing.cc.

◆ AddDimensionDependentDimensionWithVehicleCapacity() [3/4]

bool AddDimensionDependentDimensionWithVehicleCapacity ( int  pure_transit,
int  dependent_transit,
const RoutingDimension base_dimension,
int64  slack_max,
int64  vehicle_capacity,
bool  fix_start_cumul_to_zero,
const std::string &  name 
)

Definition at line 1098 of file routing.cc.

◆ AddDimensionDependentDimensionWithVehicleCapacity() [4/4]

bool AddDimensionDependentDimensionWithVehicleCapacity ( int  transit,
const RoutingDimension base_dimension,
int64  slack_max,
int64  vehicle_capacity,
bool  fix_start_cumul_to_zero,
const std::string &  name 
)

Homogeneous versions of the functions above.

Definition at line 1069 of file routing.cc.

◆ AddDimensionWithVehicleCapacity()

bool AddDimensionWithVehicleCapacity ( int  evaluator_index,
int64  slack_max,
std::vector< int64 vehicle_capacities,
bool  fix_start_cumul_to_zero,
const std::string &  name 
)

Definition at line 894 of file routing.cc.

◆ AddDimensionWithVehicleTransitAndCapacity()

bool AddDimensionWithVehicleTransitAndCapacity ( const std::vector< int > &  evaluator_indices,
int64  slack_max,
std::vector< int64 vehicle_capacities,
bool  fix_start_cumul_to_zero,
const std::string &  name 
)

Definition at line 903 of file routing.cc.

◆ AddDimensionWithVehicleTransits()

bool AddDimensionWithVehicleTransits ( const std::vector< int > &  evaluator_indices,
int64  slack_max,
int64  capacity,
bool  fix_start_cumul_to_zero,
const std::string &  name 
)

Definition at line 885 of file routing.cc.

◆ AddDisjunction()

RoutingModel::DisjunctionIndex AddDisjunction ( const std::vector< int64 > &  indices,
int64  penalty = kNoPenalty,
int64  max_cardinality = 1 
)

Adds a disjunction constraint on the indices: exactly 'max_cardinality' of the indices are active.

Start and end indices of any vehicle cannot be part of a disjunction.

If a penalty is given, at most 'max_cardinality' of the indices can be active, and if less are active, 'penalty' is payed per inactive index. This is equivalent to adding the constraint: p + Sum(i)active[i] == max_cardinality where p is an integer variable, and the following cost to the cost function: p * penalty. 'penalty' must be positive to make the disjunction optional; a negative penalty will force 'max_cardinality' indices of the disjunction to be performed, and therefore p == 0. Note: passing a vector with a single index will model an optional index with a penalty cost if it is not visited.

Definition at line 1575 of file routing.cc.

◆ AddHardTypeIncompatibility()

void AddHardTypeIncompatibility ( int  type1,
int  type2 
)

Incompatibilities: Two nodes with "hard" incompatible types cannot share the same route at all, while with a "temporal" incompatibility they can't be on the same route at the same time.

Definition at line 4103 of file routing.cc.

◆ AddIntervalToAssignment()

void AddIntervalToAssignment ( IntervalVar *const  interval)

Definition at line 5594 of file routing.cc.

◆ AddLocalSearchFilter()

void AddLocalSearchFilter ( LocalSearchFilter filter)
inline

Adds a custom local search filter to the list of filters used to speed up local search by pruning unfeasible variable assignments.

Calling this method after the routing model has been closed (CloseModel() or Solve() has been called) has no effect. The routing model does not take ownership of the filter.

Definition at line 1169 of file routing.h.

◆ AddLocalSearchOperator()

void AddLocalSearchOperator ( LocalSearchOperator ls_operator)

Adds a local search operator to the set of operators used to solve the vehicle routing problem.

Definition at line 1781 of file routing.cc.

◆ AddMatrixDimension()

std::pair< int, bool > AddMatrixDimension ( std::vector< std::vector< int64 > >  values,
int64  capacity,
bool  fix_start_cumul_to_zero,
const std::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. Returns a pair consisting of an index to the registered transit callback and a bool denoting whether the dimension has been created. It is false if a dimension with the same name has already been created (and doesn't create the new dimension but still register a new callback).

Definition at line 972 of file routing.cc.

◆ AddPickupAndDelivery()

void AddPickupAndDelivery ( int64  pickup,
int64  delivery 
)

Notifies that index1 and index2 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(); int64 index1 = manager.NodeToIndex(node1); int64 index2 = manager.NodeToIndex(node2); solver->AddConstraint(solver->MakeEquality( routing.VehicleVar(index1), routing.VehicleVar(index2))); routing.AddPickupAndDelivery(index1, index2);

Definition at line 1671 of file routing.cc.

◆ AddPickupAndDeliverySets()

void AddPickupAndDeliverySets ( DisjunctionIndex  pickup_disjunction,
DisjunctionIndex  delivery_disjunction 
)

Same as AddPickupAndDelivery but notifying that the performed node from the disjunction of index 'pickup_disjunction' is on the same route as the performed node from the disjunction of index 'delivery_disjunction'.

Definition at line 1676 of file routing.cc.

◆ AddRequiredTypeAlternativesWhenAddingType()

void AddRequiredTypeAlternativesWhenAddingType ( int  dependent_type,
absl::flat_hash_set< int >  required_type_alternatives 
)

If type_D depends on type_R when adding type_D, any node_D of type_D and VisitTypePolicy TYPE_ADDED_TO_VEHICLE or TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED requires at least one type_R on its vehicle at the time node_D is visited.

Definition at line 4159 of file routing.cc.

◆ AddRequiredTypeAlternativesWhenRemovingType()

void AddRequiredTypeAlternativesWhenRemovingType ( int  dependent_type,
absl::flat_hash_set< int >  required_type_alternatives 
)

The following requirements apply when visiting dependent nodes that remove their type from the route, i.e.

type_R must be on the vehicle when type_D of VisitTypePolicy ADDED_TYPE_REMOVED_FROM_VEHICLE, TYPE_ON_VEHICLE_UP_TO_VISIT or TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED is visited.

Definition at line 4180 of file routing.cc.

◆ AddSameVehicleRequiredTypeAlternatives()

void AddSameVehicleRequiredTypeAlternatives ( int  dependent_type,
absl::flat_hash_set< int >  required_type_alternatives 
)

Requirements: NOTE: As of 2019-04, cycles in the requirement graph are not supported, and lead to the dependent nodes being skipped if possible (otherwise the model is considered infeasible).

The following functions specify that "dependent_type" requires at least one of the types in "required_type_alternatives".

For same-vehicle requirements, a node of dependent type type_D requires at least one node of type type_R among the required alternatives on the same route.

Definition at line 4137 of file routing.cc.

◆ AddSearchMonitor()

void AddSearchMonitor ( SearchMonitor *const  monitor)

Adds a search monitor to the search used to solve the routing model.

Definition at line 3107 of file routing.cc.

◆ AddSoftSameVehicleConstraint()

void AddSoftSameVehicleConstraint ( const std::vector< int64 > &  indices,
int64  cost 
)

Adds a soft constraint to force a set of variable indices to be on the same vehicle.

If all nodes are not on the same vehicle, each extra vehicle used adds 'cost' to the cost function.

Definition at line 1650 of file routing.cc.

◆ AddTemporalTypeIncompatibility()

void AddTemporalTypeIncompatibility ( int  type1,
int  type2 
)

Definition at line 4112 of file routing.cc.

◆ AddToAssignment()

void AddToAssignment ( IntVar *const  var)

Adds an extra variable to the vehicle routing assignment.

Definition at line 5590 of file routing.cc.

◆ AddVariableMaximizedByFinalizer()

void AddVariableMaximizedByFinalizer ( IntVar var)

Adds a variable to maximize in the solution finalizer (see above for information on the solution finalizer).

Definition at line 5576 of file routing.cc.

◆ AddVariableMinimizedByFinalizer()

void AddVariableMinimizedByFinalizer ( IntVar var)

Adds a variable to minimize in the solution finalizer.

The solution finalizer is called each time a solution is found during the search and allows to instantiate secondary variables (such as dimension cumul variables).

Definition at line 5580 of file routing.cc.

◆ AddVariableTargetToFinalizer()

void AddVariableTargetToFinalizer ( IntVar var,
int64  target 
)

Add a variable to set the closest possible to the target value in the solution finalizer.

Definition at line 5569 of file routing.cc.

◆ AddVectorDimension()

std::pair< int, bool > AddVectorDimension ( std::vector< int64 values,
int64  capacity,
bool  fix_start_cumul_to_zero,
const std::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. Returns a pair consisting of an index to the registered unary transit callback and a bool denoting whether the dimension has been created. It is false if a dimension with the same name has already been created (and doesn't create the new dimension but still register a new callback).

Definition at line 963 of file routing.cc.

◆ AddWeightedVariableMinimizedByFinalizer()

void AddWeightedVariableMinimizedByFinalizer ( IntVar var,
int64  cost 
)

Adds a variable to minimize in the solution finalizer, with a weighted priority: the higher the more priority it has.

Definition at line 5556 of file routing.cc.

◆ ApplyLocks()

IntVar * ApplyLocks ( const std::vector< int64 > &  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 3594 of file routing.cc.

◆ ApplyLocksToAllVehicles()

bool ApplyLocksToAllVehicles ( const std::vector< std::vector< int64 > > &  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 3615 of file routing.cc.

◆ ArcIsMoreConstrainedThanArc()

bool ArcIsMoreConstrainedThanArc ( int64  from,
int64  to1,
int64  to2 
)

Returns whether the arc from->to1 is more constrained than from->to2, taking into account, in order:

  • whether the destination node isn't an end node
  • whether the destination node is mandatory
  • whether the destination node is bound to the same vehicle as the source
  • the "primary constrained" dimension (see SetPrimaryConstrainedDimension) It then breaks ties using, in order:
  • the arc cost (taking unperformed penalties into account)
  • the size of the vehicle vars of "to1" and "to2" (lowest size wins)
  • the value: the lowest value of the indices to1 and to2 wins. See the .cc for details. The more constrained arc is typically preferable when building a first solution. This method is intended to be used as a callback for the BestValueByComparisonSelector value selector. Args: from: the variable index of the source node to1: the variable index of the first candidate destination node. to2: the variable index of the second candidate destination node.

Definition at line 3972 of file routing.cc.

◆ AreEmptyRouteCostsConsideredForVehicle()

bool AreEmptyRouteCostsConsideredForVehicle ( int  vehicle) const
inline

Definition at line 955 of file routing.h.

◆ AssignmentToRoutes()

void AssignmentToRoutes ( const Assignment assignment,
std::vector< std::vector< int64 > > *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 index for that vehicle).

Definition at line 3802 of file routing.cc.

◆ CheckLimit()

bool CheckLimit ( )
inline

Returns true if the search limit has been crossed.

Definition at line 1330 of file routing.h.

◆ CloseModel()

void 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. This is equivalent to calling CloseModelWithParameters(DefaultRoutingSearchParameters()).

Definition at line 1884 of file routing.cc.

◆ CloseModelWithParameters()

void CloseModelWithParameters ( const RoutingSearchParameters &  search_parameters)

Same as above taking search parameters (as of 10/2015 some the parameters have to be set when closing the model).

Definition at line 2062 of file routing.cc.

◆ CloseVisitTypes()

void CloseVisitTypes ( )

This function should be called once all node visit types have been set and prior to adding any incompatibilities/requirements.

"close" types.

Definition at line 4094 of file routing.cc.

◆ CompactAndCheckAssignment()

Assignment * CompactAndCheckAssignment ( const Assignment assignment) const

Same as CompactAssignment() but also checks the validity of the final compact solution; if it is not valid, no attempts to repair it are made (instead, the method returns nullptr).

Definition at line 3508 of file routing.cc.

◆ CompactAssignment()

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.

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 nullptr 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; if one of these checks fails no attempts to repair it are made (instead, the method returns nullptr).

Definition at line 3503 of file routing.cc.

◆ ComputeLowerBound()

int64 ComputeLowerBound ( )

Computes a lower bound to the routing problem solving a linear assignment problem.

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).

Definition at line 3359 of file routing.cc.

◆ ConsiderEmptyRouteCostsForVehicle()

void ConsiderEmptyRouteCostsForVehicle ( bool  consider_costs,
int  vehicle 
)
inline

Definition at line 950 of file routing.h.

◆ CostsAreHomogeneousAcrossVehicles()

bool CostsAreHomogeneousAcrossVehicles ( ) const
inline

Whether costs are homogeneous across all vehicles.

Definition at line 1231 of file routing.h.

◆ CostVar()

IntVar * CostVar ( ) const
inline

Returns the global cost variable which is being minimized.

Definition at line 1224 of file routing.h.

◆ DebugOutputAssignment()

std::string DebugOutputAssignment ( const Assignment solution_assignment,
const std::string &  dimension_to_print 
) const

Print some debugging information about an assignment, including the feasible intervals of the CumulVar for dimension "dimension_to_print" at each step of the routes.

If "dimension_to_print" is omitted, all dimensions will be printed.

Definition at line 4241 of file routing.cc.

◆ End()

int64 End ( int  vehicle) const
inline

Returns the variable index of the ending node of a vehicle route.

Definition at line 1182 of file routing.h.

◆ first_solution_evaluator()

const Solver::IndexEvaluator2 & first_solution_evaluator ( ) const
inline

Gets/sets the evaluator used during the search.

Only relevant when RoutingSearchParameters.first_solution_strategy = EVALUATOR_STRATEGY.

Definition at line 963 of file routing.h.

◆ ForEachNodeInDisjunctionWithMaxCardinalityFromIndex()

void ForEachNodeInDisjunctionWithMaxCardinalityFromIndex ( int64  index,
int64  max_cardinality,
f 
) const
inline

Calls f for each variable index of indices in the same disjunctions as the node corresponding to the variable index 'index'; only disjunctions of cardinality 'cardinality' are considered.

Definition at line 639 of file routing.h.

◆ GetAllDimensionNames()

std::vector< std::string > GetAllDimensionNames ( ) const

Outputs the names of all dimensions added to the routing engine.

Definition at line 1121 of file routing.cc.

◆ GetAmortizedLinearCostFactorOfVehicles()

const std::vector< int64 > & GetAmortizedLinearCostFactorOfVehicles ( ) const
inline

Definition at line 943 of file routing.h.

◆ GetAmortizedQuadraticCostFactorOfVehicles()

const std::vector< int64 > & GetAmortizedQuadraticCostFactorOfVehicles ( ) const
inline

Definition at line 946 of file routing.h.

◆ GetArcCostForClass()

int64 GetArcCostForClass ( int64  from_index,
int64  to_index,
int64  cost_class_index 
) const

Returns the cost of the segment between two nodes for a given cost class.

Input are variable indices of nodes and the cost class. Unlike GetArcCostForVehicle(), if cost_class is kNoCost, then the returned cost won't necessarily be zero: only some of the components of the cost that depend on the cost class will be omited. See the code for details.

Definition at line 3928 of file routing.cc.

◆ GetArcCostForFirstSolution()

int64 GetArcCostForFirstSolution ( int64  from_index,
int64  to_index 
) const

Returns the cost of the arc in the context of the first solution strategy.

This is typically a simplification of the actual cost; see the .cc.

Definition at line 3939 of file routing.cc.

◆ GetArcCostForVehicle()

int64 GetArcCostForVehicle ( int64  from_index,
int64  to_index,
int64  vehicle 
) const

Returns the cost of the transit arc between two nodes for a given vehicle.

Input are variable indices of node. This returns 0 if vehicle < 0.

Definition at line 3918 of file routing.cc.

◆ GetAutomaticFirstSolutionStrategy()

operations_research::FirstSolutionStrategy::Value GetAutomaticFirstSolutionStrategy ( ) const
inline

Returns the automatic first solution strategy selected.

Definition at line 1357 of file routing.h.

◆ GetCostClassesCount()

int GetCostClassesCount ( ) const
inline

Returns the number of different cost classes in the model.

Definition at line 1268 of file routing.h.

◆ GetCostClassIndexOfVehicle()

CostClassIndex GetCostClassIndexOfVehicle ( int64  vehicle) const
inline

Get the cost class index of the given vehicle.

Definition at line 1251 of file routing.h.

◆ GetCumulBounds()

std::vector< std::vector< std::pair< int64, int64 > > > GetCumulBounds ( const Assignment solution_assignment,
const RoutingDimension dimension 
)

Returns a vector cumul_bounds, for which cumul_bounds[i][j] is a pair containing the minimum and maximum of the CumulVar of the jth node on route i.

  • cumul_bounds[i][j].first is the minimum.
  • cumul_bounds[i][j].second is the maximum.

Definition at line 4314 of file routing.cc.

◆ GetDeliveryIndexPairs()

const std::vector< std::pair< int, int > > & GetDeliveryIndexPairs ( int64  node_index) const

Same as above for deliveries.

Definition at line 1713 of file routing.cc.

◆ GetDepot()

int64 GetDepot ( ) const

Returns the variable index of the first starting or ending node of all routes.

If all routes start and end at the same node (single depot), this is the node returned.

Definition at line 1785 of file routing.cc.

◆ GetDimensionOrDie()

const RoutingDimension & GetDimensionOrDie ( const std::string &  dimension_name) const

Returns a dimension from its name. Dies if the dimension does not exist.

Definition at line 1176 of file routing.cc.

◆ GetDimensions()

const std::vector< RoutingDimension * > & GetDimensions ( ) const
inline

Returns all dimensions of the model.

Definition at line 559 of file routing.h.

◆ GetDimensionsWithSoftOrSpanCosts()

std::vector< RoutingDimension * > GetDimensionsWithSoftOrSpanCosts ( ) const

Returns dimensions with soft or vehicle span costs.

Definition at line 4996 of file routing.cc.

◆ GetDisjunctionIndices() [1/2]

const std::vector< int64 > & GetDisjunctionIndices ( DisjunctionIndex  index) const
inline

Returns the variable indices of the nodes in the disjunction of index 'index'.

Definition at line 652 of file routing.h.

◆ GetDisjunctionIndices() [2/2]

const std::vector< DisjunctionIndex > & GetDisjunctionIndices ( int64  index) const
inline

Returns the indices of the disjunctions to which an index belongs.

Definition at line 631 of file routing.h.

◆ GetDisjunctionMaxCardinality()

int64 GetDisjunctionMaxCardinality ( DisjunctionIndex  index) const
inline

Returns the maximum number of possible active nodes of the node disjunction of index 'index'.

Definition at line 663 of file routing.h.

◆ GetDisjunctionPenalty()

int64 GetDisjunctionPenalty ( DisjunctionIndex  index) const
inline

Returns the penalty of the node disjunction of index 'index'.

Definition at line 658 of file routing.h.

◆ GetFixedCostOfVehicle()

int64 GetFixedCostOfVehicle ( 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 1210 of file routing.cc.

◆ GetGlobalDimensionCumulOptimizers()

const std::vector< std::unique_ptr< GlobalDimensionCumulOptimizer > > & GetGlobalDimensionCumulOptimizers ( ) const
inline

Returns [global|local]_dimension_optimizers_, which are empty if the model has not been closed.

Definition at line 568 of file routing.h.

◆ GetHardTypeIncompatibilitiesOfType()

const absl::flat_hash_set< int > & GetHardTypeIncompatibilitiesOfType ( int  type) const

Returns visit types incompatible with a given type.

Definition at line 4122 of file routing.cc.

◆ GetHomogeneousCost()

int64 GetHomogeneousCost ( int64  from_index,
int64  to_index 
) const
inline

Returns the cost of the segment between two nodes supposing all vehicle costs are the same (returns the cost for the first vehicle otherwise).

Definition at line 1236 of file routing.h.

◆ GetImplicitUniquePickupAndDeliveryPairs()

const IndexPairs & GetImplicitUniquePickupAndDeliveryPairs ( ) const
inline

Returns implicit pickup and delivery pairs currently in the model.

Pairs are implicit if they are not linked by a pickup and delivery constraint but that for a given unary dimension, the first element of the pair has a positive demand d, and the second element has a demand of -d.

Definition at line 757 of file routing.h.

◆ GetLocalDimensionCumulMPOptimizers()

const std::vector< std::unique_ptr< LocalDimensionCumulOptimizer > > & GetLocalDimensionCumulMPOptimizers ( ) const
inline

Definition at line 576 of file routing.h.

◆ GetLocalDimensionCumulOptimizers()

const std::vector< std::unique_ptr< LocalDimensionCumulOptimizer > > & GetLocalDimensionCumulOptimizers ( ) const
inline

Definition at line 572 of file routing.h.

◆ GetMaximumNumberOfActiveVehicles()

int GetMaximumNumberOfActiveVehicles ( ) const
inline

Returns the maximum number of active vehicles.

Definition at line 904 of file routing.h.

◆ GetMutableDimension()

RoutingDimension * GetMutableDimension ( const std::string &  dimension_name) const

Returns a dimension from its name.

Returns nullptr if the dimension does not exist.

Definition at line 1181 of file routing.cc.

◆ GetMutableGlobalCumulOptimizer()

GlobalDimensionCumulOptimizer * GetMutableGlobalCumulOptimizer ( const RoutingDimension dimension) const

Returns the global/local dimension cumul optimizer for a given dimension, or nullptr if there is none.

Definition at line 1130 of file routing.cc.

◆ GetMutableLocalCumulMPOptimizer()

LocalDimensionCumulOptimizer * GetMutableLocalCumulMPOptimizer ( const RoutingDimension dimension) const

Definition at line 1154 of file routing.cc.

◆ GetMutableLocalCumulOptimizer()

LocalDimensionCumulOptimizer * GetMutableLocalCumulOptimizer ( const RoutingDimension dimension) const

Definition at line 1142 of file routing.cc.

◆ GetNonZeroCostClassesCount()

int GetNonZeroCostClassesCount ( ) const
inline

Ditto, minus the 'always zero', built-in cost class.

Definition at line 1270 of file routing.h.

◆ GetNumberOfDecisionsInFirstSolution()

int64 GetNumberOfDecisionsInFirstSolution ( const RoutingSearchParameters &  search_parameters) const

Returns statistics on first solution search, number of decisions sent to filters, number of decisions rejected by filters.

Definition at line 3621 of file routing.cc.

◆ GetNumberOfDisjunctions()

int GetNumberOfDisjunctions ( ) const
inline

Returns the number of node disjunctions in the model.

Definition at line 667 of file routing.h.

◆ GetNumberOfRejectsInFirstSolution()

int64 GetNumberOfRejectsInFirstSolution ( const RoutingSearchParameters &  search_parameters) const

Definition at line 3629 of file routing.cc.

◆ GetNumberOfVisitTypes()

int GetNumberOfVisitTypes ( ) const
inline

Definition at line 801 of file routing.h.

◆ GetNumOfSingletonNodes()

int GetNumOfSingletonNodes ( ) const

Returns the number of non-start/end nodes which do not appear in a pickup/delivery pair.

Definition at line 1739 of file routing.cc.

◆ GetPairIndicesOfType()

const std::vector< int > & GetPairIndicesOfType ( int  type) const

Definition at line 4083 of file routing.cc.

◆ GetPerfectBinaryDisjunctions()

std::vector< std::pair< int64, int64 > > GetPerfectBinaryDisjunctions ( ) const

Returns the list of all perfect binary disjunctions, as pairs of variable indices: a disjunction is "perfect" when its variables do not appear in any other disjunction.

Each pair is sorted (lowest variable index first), and the output vector is also sorted (lowest pairs first).

Definition at line 1591 of file routing.cc.

◆ GetPickupAndDeliveryDisjunctions()

const std::vector< std::pair< DisjunctionIndex, DisjunctionIndex > > & GetPickupAndDeliveryDisjunctions ( ) const
inline

Definition at line 750 of file routing.h.

◆ GetPickupAndDeliveryPairs()

const IndexPairs & GetPickupAndDeliveryPairs ( ) const
inline

Returns pickup and delivery pairs currently in the model.

Definition at line 746 of file routing.h.

◆ GetPickupAndDeliveryPolicyOfVehicle()

RoutingModel::PickupAndDeliveryPolicy GetPickupAndDeliveryPolicyOfVehicle ( int  vehicle) const

Definition at line 1734 of file routing.cc.

◆ GetPickupIndexPairs()

const std::vector< std::pair< int, int > > & GetPickupIndexPairs ( int64  node_index) const

Returns pairs for which the node is a pickup; the first element of each pair is the index in the pickup and delivery pairs list in which the pickup appears, the second element is its index in the pickups list.

Definition at line 1707 of file routing.cc.

◆ GetPrimaryConstrainedDimension()

const std::string & GetPrimaryConstrainedDimension ( ) const
inline

Get the primary constrained dimension, or an empty string if it is unset.

Definition at line 608 of file routing.h.

◆ GetRequiredTypeAlternativesWhenAddingType()

const std::vector< absl::flat_hash_set< int > > & GetRequiredTypeAlternativesWhenAddingType ( int  type) const

Returns the set of requirement alternatives when adding the given type.

Definition at line 4211 of file routing.cc.

◆ GetRequiredTypeAlternativesWhenRemovingType()

const std::vector< absl::flat_hash_set< int > > & GetRequiredTypeAlternativesWhenRemovingType ( int  type) const

Returns the set of requirement alternatives when removing the given type.

Definition at line 4218 of file routing.cc.

◆ GetRoutesFromAssignment()

std::vector< std::vector< int64 > > GetRoutesFromAssignment ( const Assignment assignment)

Converts the solution in the given assignment to routes for all vehicles.

If the returned vector is route_indices, route_indices[i][j] is the index for jth location visited on route i. Note that contrary to AssignmentToRoutes, the vectors do include start and end locations.

Definition at line 3836 of file routing.cc.

◆ GetSameVehicleIndicesOfIndex()

const std::vector< int > & GetSameVehicleIndicesOfIndex ( int  node) const
inline

Returns variable indices of nodes constrained to be on the same route.

Definition at line 1280 of file routing.h.

◆ GetSameVehicleRequiredTypeAlternativesOfType()

const std::vector< absl::flat_hash_set< int > > & GetSameVehicleRequiredTypeAlternativesOfType ( int  type) const

Returns the set of same-vehicle requirement alternatives for the given type.

Definition at line 4203 of file routing.cc.

◆ GetSingleNodesOfType()

const std::vector< int > & GetSingleNodesOfType ( int  type) const

Definition at line 4078 of file routing.cc.

◆ GetTemporalTypeIncompatibilitiesOfType()

const absl::flat_hash_set< int > & GetTemporalTypeIncompatibilitiesOfType ( int  type) const

Definition at line 4129 of file routing.cc.

◆ GetTopologicallySortedVisitTypes()

const std::vector< std::vector< int > > & GetTopologicallySortedVisitTypes ( ) const
inline

Definition at line 803 of file routing.h.

◆ GetVehicleClassesCount()

int GetVehicleClassesCount ( ) const
inline

Returns the number of different vehicle classes in the model.

Definition at line 1278 of file routing.h.

◆ GetVehicleClassIndexOfVehicle()

VehicleClassIndex GetVehicleClassIndexOfVehicle ( int64  vehicle) const
inline

Definition at line 1273 of file routing.h.

◆ GetVehicleTypeContainer()

const VehicleTypeContainer & GetVehicleTypeContainer ( ) const
inline

Definition at line 1285 of file routing.h.

◆ GetVisitType()

int GetVisitType ( int64  index) const

Definition at line 4073 of file routing.cc.

◆ GetVisitTypePolicy()

RoutingModel::VisitTypePolicy GetVisitTypePolicy ( int64  index) const

Definition at line 4088 of file routing.cc.

◆ HasDimension()

bool HasDimension ( const std::string &  dimension_name) const

Returns true if a dimension exists for a given dimension name.

Definition at line 1166 of file routing.cc.

◆ HasHardTypeIncompatibilities()

bool HasHardTypeIncompatibilities ( ) const
inline

Returns true iff any hard (resp.

temporal) type incompatibilities have been added to the model.

Definition at line 822 of file routing.h.

◆ HasSameVehicleTypeRequirements()

bool HasSameVehicleTypeRequirements ( ) const
inline

Returns true iff any same-route (resp.

temporal) type requirements have been added to the model.

Definition at line 867 of file routing.h.

◆ HasTemporalTypeIncompatibilities()

bool HasTemporalTypeIncompatibilities ( ) const
inline

Definition at line 825 of file routing.h.

◆ HasTemporalTypeRequirements()

bool HasTemporalTypeRequirements ( ) const
inline

Definition at line 870 of file routing.h.

◆ HasTypeRegulations()

bool HasTypeRegulations ( ) const
inline

Returns true iff the model has any incompatibilities or requirements set on node types.

Definition at line 876 of file routing.h.

◆ HasVehicleWithCostClassIndex()

bool HasVehicleWithCostClassIndex ( CostClassIndex  cost_class_index) const
inline

Returns true iff the model contains a vehicle with the given cost_class_index.

Definition at line 1260 of file routing.h.

◆ IgnoreDisjunctionsAlreadyForcedToZero()

void IgnoreDisjunctionsAlreadyForcedToZero ( )

SPECIAL: Makes the solver ignore all the disjunctions whose active variables are all trivially zero (i.e.

Max() == 0), by setting their max_cardinality to 0. This can be useful when using the BaseBinaryDisjunctionNeighborhood operators, in the context of arc-based routing.

Definition at line 1608 of file routing.cc.

◆ IsEnd()

bool IsEnd ( int64  index) const
inline

Returns true if 'index' represents the last node of a route.

Definition at line 1186 of file routing.h.

◆ IsMatchingModel()

bool IsMatchingModel ( ) const

Returns true if a vehicle/node matching problem is detected.

Definition at line 34 of file routing_flow.cc.

◆ IsStart()

bool IsStart ( int64  index) const

Returns true if 'index' represents the first node of a route.

Definition at line 3896 of file routing.cc.

◆ IsVehicleAllowedForIndex()

bool IsVehicleAllowedForIndex ( int  vehicle,
int64  index 
)
inline

Returns true if a vehicle is allowed to visit a given node.

Definition at line 694 of file routing.h.

◆ IsVehicleUsed()

bool IsVehicleUsed ( const Assignment assignment,
int  vehicle 
) const

Returns true if the route of 'vehicle' is non empty in 'assignment'.

Definition at line 3900 of file routing.cc.

◆ MakeGreedyDescentLSOperator()

std::unique_ptr< LocalSearchOperator > MakeGreedyDescentLSOperator ( std::vector< IntVar * >  variables)
static

Perhaps move it to constraint_solver.h.

MakeGreedyDescentLSOperator creates a local search operator that tries to improve the initial assignment by moving a logarithmically decreasing step away in each possible dimension.

Definition at line 6289 of file routing_search.cc.

◆ MakeGuidedSlackFinalizer()

DecisionBuilder * MakeGuidedSlackFinalizer ( const RoutingDimension dimension,
std::function< int64(int64)>  initializer 
)

The next few members are in the public section only for testing purposes.

MakeGuidedSlackFinalizer creates a DecisionBuilder for the slacks of a dimension using a callback to choose which values to start with. The finalizer works only when all next variables in the model have been fixed. It has the following two characteristics:

  1. It follows the routes defined by the nexts variables when choosing a variable to make a decision on.
  2. When it comes to choose a value for the slack of node i, the decision builder first calls the callback with argument i, and supposingly the returned value is x it creates decisions slack[i] = x, slack[i] = x + 1, slack[i] = x - 1, slack[i] = x + 2, etc.

Definition at line 6162 of file routing_search.cc.

◆ MakePathSpansAndTotalSlacks()

Constraint * MakePathSpansAndTotalSlacks ( const RoutingDimension dimension,
std::vector< IntVar * >  spans,
std::vector< IntVar * >  total_slacks 
)

For every vehicle of the routing model:

  • if total_slacks[vehicle] is not nullptr, constrains it to be the sum of slacks on that vehicle, that is, dimension->CumulVar(end) - dimension->CumulVar(start) - sum_{node in path of vehicle} dimension->FixedTransitVar(node).
  • if spans[vehicle] is not nullptr, constrains it to be dimension->CumulVar(end) - dimension->CumulVar(start) This does stronger propagation than a decomposition, and takes breaks into account.

Definition at line 5927 of file routing.cc.

◆ MakeSelfDependentDimensionFinalizer()

DecisionBuilder * MakeSelfDependentDimensionFinalizer ( const RoutingDimension dimension)

SWIG

MakeSelfDependentDimensionFinalizer is a finalizer for the slacks of a self-dependent dimension. It makes an extensive use of the caches of the state dependent transits. In detail, MakeSelfDependentDimensionFinalizer returns a composition of a local search decision builder with a greedy descent operator for the cumul of the start of each route and a guided slack finalizer. Provided there are no time windows and the maximum slacks are large enough, once the cumul of the start of route is fixed, the guided finalizer can find optimal values of the slacks for the rest of the route in time proportional to the length of the route. Therefore the composed finalizer generally works in time O(log(t)*n*m), where t is the latest possible departute time, n is the number of nodes in the network and m is the number of vehicles.

Definition at line 6295 of file routing_search.cc.

◆ MakeStateDependentTransit()

RoutingModel::StateDependentTransit MakeStateDependentTransit ( const std::function< int64(int64)> &  f,
int64  domain_start,
int64  domain_end 
)
static

Creates a cached StateDependentTransit from an std::function.

Definition at line 1111 of file routing.cc.

◆ MutablePreAssignment()

Assignment * MutablePreAssignment ( )
inline

Definition at line 1067 of file routing.h.

◆ Next()

int64 Next ( const Assignment assignment,
int64  index 
) const

Assignment inspection Returns the variable index of the node directly after the node corresponding to 'index' in 'assignment'.

Definition at line 3910 of file routing.cc.

◆ Nexts()

const std::vector< IntVar * > & Nexts ( ) const
inline

Returns all next variables of the model, such that Nexts(i) is the next variable of the node corresponding to i.

Definition at line 1200 of file routing.h.

◆ NextVar()

IntVar * NextVar ( int64  index) const
inline

!defined(SWIGPYTHON)

Returns the next variable of the node corresponding to index. Note that NextVar(index) == index is equivalent to ActiveVar(index) == 0.

Definition at line 1207 of file routing.h.

◆ nodes()

int nodes ( ) const
inline

Sizes and indices Returns the number of nodes in the model.

Definition at line 1343 of file routing.h.

◆ PackCumulsOfOptimizerDimensionsFromAssignment()

const Assignment * PackCumulsOfOptimizerDimensionsFromAssignment ( const Assignment original_assignment,
absl::Duration  duration_limit 
)

For every dimension in the model with an optimizer in local/global_dimension_optimizers_, this method tries to pack the cumul values of the dimension, such that:

  • The cumul costs (span costs, soft lower and upper bound costs, etc) are minimized.
  • The cumuls of the ends of the routes are minimized for this given minimal cumul cost.
  • Given these minimal end cumuls, the route start cumuls are maximized. Returns the assignment resulting from allocating these packed cumuls with the solver, and nullptr if these cumuls could not be set by the solver.

Definition at line 390 of file routing.cc.

◆ PreAssignment()

const Assignment *const 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.

Definition at line 1066 of file routing.h.

◆ ReadAssignment()

Assignment * ReadAssignment ( const std::string &  file_name)

Reads an assignment from a file and returns the current solution.

Returns nullptr if the file cannot be opened or if the assignment is not valid.

Definition at line 3646 of file routing.cc.

◆ ReadAssignmentFromRoutes()

Assignment * ReadAssignmentFromRoutes ( const std::vector< std::vector< int64 > > &  routes,
bool  ignore_inactive_indices 
)

Restores the routes as the current solution.

Returns nullptr 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 3789 of file routing.cc.

◆ RegisterPositiveTransitCallback()

int RegisterPositiveTransitCallback ( TransitCallback2  callback)

Definition at line 844 of file routing.cc.

◆ RegisterPositiveUnaryTransitCallback()

int RegisterPositiveUnaryTransitCallback ( TransitCallback1  callback)

Definition at line 810 of file routing.cc.

◆ RegisterStateDependentTransitCallback()

int RegisterStateDependentTransitCallback ( VariableIndexEvaluator2  callback)

Definition at line 851 of file routing.cc.

◆ RegisterTransitCallback()

int RegisterTransitCallback ( TransitCallback2  callback)

Definition at line 818 of file routing.cc.

◆ RegisterTransitMatrix()

int RegisterTransitMatrix ( std::vector< std::vector< int64 > >  values)

Definition at line 791 of file routing.cc.

◆ RegisterUnaryTransitCallback()

int RegisterUnaryTransitCallback ( TransitCallback1  callback)

Definition at line 783 of file routing.cc.

◆ RegisterUnaryTransitVector()

int RegisterUnaryTransitVector ( std::vector< int64 values)

Registers 'callback' and returns its index.

Definition at line 772 of file routing.cc.

◆ RemainingTime()

absl::Duration RemainingTime ( ) const
inline

Returns the time left in the search limit.

Definition at line 1336 of file routing.h.

◆ RestoreAssignment()

Assignment * RestoreAssignment ( const Assignment solution)

Restores an assignment as a solution in the routing model and returns the new solution.

Returns nullptr if the assignment is not valid.

Definition at line 3655 of file routing.cc.

◆ RoutesToAssignment()

bool RoutesToAssignment ( const std::vector< std::vector< int64 > > &  routes,
bool  ignore_inactive_indices,
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 variable indices that appear on the routes of the vehicles. The indices of the outer vector in 'routes' correspond to vehicles IDs, the inner vector contains the variable indices on the routes for the given vehicle. The inner vectors must not contain the start and end indices, 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_indices set to false, this method will fail (return nullptr) in case some of the route contain indices that are deactivated in the model; when set to true, these indices will be skipped. Returns true if routes were 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 3677 of file routing.cc.

◆ SetAllowedVehiclesForIndex()

void SetAllowedVehiclesForIndex ( const std::vector< int > &  vehicles,
int64  index 
)

Sets the vehicles which can visit a given node.

If the node is in a disjunction, this will not prevent it from being unperformed. Specifying an empty vector of vehicles has no effect (all vehicles will be allowed to visit the node).

Definition at line 1662 of file routing.cc.

◆ SetAmortizedCostFactorsOfAllVehicles()

void SetAmortizedCostFactorsOfAllVehicles ( int64  linear_cost_factor,
int64  quadratic_cost_factor 
)

The following methods set the linear and quadratic cost factors of vehicles (must be positive values).

The default value of these parameters is zero for all vehicles.

When set, the cost_ of the model will contain terms aiming at reducing the number of vehicles used in the model, by adding the following to the objective for every vehicle v: INDICATOR(v used in the model) * [linear_cost_factor_of_vehicle_[v]

  • quadratic_cost_factor_of_vehicle_[v]*(square of length of route v)] i.e. for every used vehicle, we add the linear factor as fixed cost, and subtract the square of the route length multiplied by the quadratic factor. This second term aims at making the routes as dense as possible.

Sets the linear and quadratic cost factor of all vehicles.

Definition at line 1221 of file routing.cc.

◆ SetAmortizedCostFactorsOfVehicle()

void SetAmortizedCostFactorsOfVehicle ( int64  linear_cost_factor,
int64  quadratic_cost_factor,
int  vehicle 
)

Sets the linear and quadratic cost factor of the given vehicle.

Definition at line 1229 of file routing.cc.

◆ SetArcCostEvaluatorOfAllVehicles()

void SetArcCostEvaluatorOfAllVehicles ( int  evaluator_index)

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 1190 of file routing.cc.

◆ SetArcCostEvaluatorOfVehicle()

void SetArcCostEvaluatorOfVehicle ( int  evaluator_index,
int  vehicle 
)

Sets the cost function for a given vehicle route.

Definition at line 1197 of file routing.cc.

◆ SetAssignmentFromOtherModelAssignment()

void SetAssignmentFromOtherModelAssignment ( Assignment target_assignment,
const RoutingModel source_model,
const Assignment source_assignment 
)

Given a "source_model" and its "source_assignment", resets "target_assignment" with the IntVar variables (nexts_, and vehicle_vars_ if costs aren't homogeneous across vehicles) of "this" model, with the values set according to those in "other_assignment".

The objective_element of target_assignment is set to this->cost_.

Definition at line 3321 of file routing.cc.

◆ SetFirstSolutionEvaluator()

void SetFirstSolutionEvaluator ( Solver::IndexEvaluator2  evaluator)
inline

Takes ownership of evaluator.

Definition at line 968 of file routing.h.

◆ SetFixedCostOfAllVehicles()

void SetFixedCostOfAllVehicles ( int64  cost)

Sets the fixed cost of all vehicle routes.

It is equivalent to calling SetFixedCostOfVehicle on all vehicle routes.

Definition at line 1204 of file routing.cc.

◆ SetFixedCostOfVehicle()

void SetFixedCostOfVehicle ( int64  cost,
int  vehicle 
)

Sets the fixed cost of one vehicle route.

Definition at line 1215 of file routing.cc.

◆ SetMaximumNumberOfActiveVehicles()

void SetMaximumNumberOfActiveVehicles ( int  max_active_vehicles)
inline

Constrains the maximum number of active vehicles, aka the number of vehicles which do not have an empty route.

For instance, this can be used to limit the number of routes in the case where there are fewer drivers than vehicles and that the fleet of vehicle is heterogeneous.

Definition at line 900 of file routing.h.

◆ SetPickupAndDeliveryPolicyOfAllVehicles()

void SetPickupAndDeliveryPolicyOfAllVehicles ( PickupAndDeliveryPolicy  policy)

Sets the Pickup and delivery policy of all vehicles.

It is equivalent to calling SetPickupAndDeliveryPolicyOfVehicle on all vehicles.

Definition at line 1725 of file routing.cc.

◆ SetPickupAndDeliveryPolicyOfVehicle()

void SetPickupAndDeliveryPolicyOfVehicle ( PickupAndDeliveryPolicy  policy,
int  vehicle 
)

Definition at line 1719 of file routing.cc.

◆ SetPrimaryConstrainedDimension()

void SetPrimaryConstrainedDimension ( const std::string &  dimension_name)
inline

Set the given dimension as "primary constrained".

As of August 2013, this is only used by ArcIsMoreConstrainedThanArc(). "dimension" must be the name of an existing dimension, or be empty, in which case there will not be a primary dimension after this call.

Definition at line 603 of file routing.h.

◆ SetSweepArranger()

void SetSweepArranger ( SweepArranger sweep_arranger)
inline

Definition at line 1158 of file routing.h.

◆ SetTabuVarsCallback()

void SetTabuVarsCallback ( GetTabuVarsCallback  tabu_var_callback)

Definition at line 5476 of file routing.cc.

◆ SetVisitType()

void SetVisitType ( int64  index,
int  type,
VisitTypePolicy  type_policy 
)

Definition at line 4065 of file routing.cc.

◆ Size()

int64 Size ( ) const
inline

Returns the number of next variables in the model.

Definition at line 1347 of file routing.h.

◆ Solve()

const Assignment * Solve ( const Assignment assignment = nullptr)

Solves the current routing model; closes the current model.

This is equivalent to calling SolveWithParameters(DefaultRoutingSearchParameters()) or SolveFromAssignmentWithParameters(assignment, DefaultRoutingSearchParameters()).

Definition at line 3131 of file routing.cc.

◆ SolveFromAssignmentWithParameters()

const Assignment * SolveFromAssignmentWithParameters ( const Assignment assignment,
const RoutingSearchParameters &  search_parameters,
std::vector< const Assignment * > *  solutions = nullptr 
)

Definition at line 3201 of file routing.cc.

◆ solver()

Solver * solver ( ) const
inline

Returns the underlying constraint solver.

Can be used to add extra constraints and/or modify search algoithms.

Definition at line 1327 of file routing.h.

◆ SolveWithParameters()

const Assignment * SolveWithParameters ( const RoutingSearchParameters &  search_parameters,
std::vector< const Assignment * > *  solutions = nullptr 
)

Solves the current routing model with the given parameters.

If 'solutions' is specified, it will contain the k best solutions found during the search (from worst to best, including the one returned by this method), where k corresponds to the 'number_of_solutions_to_collect' in 'search_parameters'. Note that the Assignment returned by the method and the ones in solutions are owned by the underlying solver and should not be deleted.

Definition at line 3136 of file routing.cc.

◆ Start()

int64 Start ( int  vehicle) const
inline

Model inspection.

Returns the variable index of the starting node of a vehicle route.

Definition at line 1180 of file routing.h.

◆ StateDependentTransitCallback()

const VariableIndexEvaluator2 & StateDependentTransitCallback ( int  callback_index) const
inline

Definition at line 421 of file routing.h.

◆ status()

Status status ( ) const
inline

Returns the current status of the routing model.

Definition at line 1042 of file routing.h.

◆ sweep_arranger()

SweepArranger * sweep_arranger ( ) const
inline

Returns the sweep arranger to be used by routing heuristics.

Definition at line 1162 of file routing.h.

◆ TransitCallback()

const TransitCallback2 & TransitCallback ( int  callback_index) const
inline

Definition at line 413 of file routing.h.

◆ UnaryTransitCallbackOrNull()

const TransitCallback1 & UnaryTransitCallbackOrNull ( int  callback_index) const
inline

Definition at line 417 of file routing.h.

◆ UnperformedPenalty()

int64 UnperformedPenalty ( int64  var_index) const

Get the "unperformed" penalty of a node.

This is only well defined if the node is only part of a single Disjunction involving only itself, and that disjunction has a penalty. In all other cases, including forced active nodes, this returns 0.

Definition at line 4224 of file routing.cc.

◆ UnperformedPenaltyOrValue()

int64 UnperformedPenaltyOrValue ( int64  default_value,
int64  var_index 
) const

Same as above except that it returns default_value instead of 0 when penalty is not well defined (default value is passed as first argument to simplify the usage of the method in a callback).

Definition at line 4228 of file routing.cc.

◆ VehicleCostsConsideredVar()

IntVar * VehicleCostsConsideredVar ( int  vehicle) const
inline

Returns the variable specifying whether or not costs are considered for vehicle.

Definition at line 1217 of file routing.h.

◆ VehicleIndex()

int VehicleIndex ( int64  index) const
inline

Returns the vehicle of the given start/end index, and -1 if the given index is not a vehicle start/end.

Definition at line 1189 of file routing.h.

◆ vehicles()

int vehicles ( ) const
inline

Returns the number of vehicle routes in the model.

Definition at line 1345 of file routing.h.

◆ VehicleVar()

IntVar * VehicleVar ( int64  index) const
inline

Returns the vehicle variable of the node corresponding to index.

Note that VehicleVar(index) == -1 is equivalent to ActiveVar(index) == 0.

Definition at line 1222 of file routing.h.

◆ VehicleVars()

const std::vector< IntVar * > & VehicleVars ( ) const
inline

Returns all vehicle variables of the model, such that VehicleVars(i) is the vehicle variable of the node corresponding to i.

Definition at line 1203 of file routing.h.

◆ WriteAssignment()

bool WriteAssignment ( const std::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 3637 of file routing.cc.

Member Data Documentation

◆ kNoDimension

const RoutingModel::DimensionIndex kNoDimension
static

Constant used to express the "no dimension" index, returned when a dimension name does not correspond to an actual dimension.

Definition at line 392 of file routing.h.

◆ kNoDisjunction

const RoutingModel::DisjunctionIndex kNoDisjunction
static

Constant used to express the "no disjunction" index, returned when a node does not appear in any disjunction.

Definition at line 388 of file routing.h.

◆ kNoPenalty

const int64 kNoPenalty = -1
static

Constant used to express a hard constraint instead of a soft penalty.

Definition at line 384 of file routing.h.


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