operations_research::RoutingModel Class Reference

Detailed Description

Definition at line 258 of file routing.h.

#include <routing.h>

Classes
struct	StateDependentTransit
struct	CostClass
struct	VehicleTypeContainer
class	ResourceGroup
struct	VariableValuePair
	Struct used to store a variable value. More...
class	SecondaryOptimizer
	Class used to solve a secondary model within a first solution strategy. More...
struct	PickupDeliveryPosition
	The position of a node in the set of pickup and delivery pairs. More...
struct	RouteDimensionTravelInfo
struct	NodeNeighborsParameters
class	NodeNeighborsByCostClass

Public Types
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	TransitEvaluatorSign { kTransitEvaluatorSignUnknown = 0 , kTransitEvaluatorSignPositiveOrZero = 1 , kTransitEvaluatorSignNegativeOrZero = 2 }
	Represents the sign of values returned by a transit evaluator. More...
enum	PenaltyCostBehavior { PENALIZE_ONCE , PENALIZE_PER_INACTIVE }
enum	VisitTypePolicy { TYPE_ADDED_TO_VEHICLE , ADDED_TYPE_REMOVED_FROM_VEHICLE , TYPE_ON_VEHICLE_UP_TO_VISIT , TYPE_SIMULTANEOUSLY_ADDED_AND_REMOVED }
typedef RoutingCostClassIndex	CostClassIndex
typedef RoutingDimensionIndex	DimensionIndex
typedef RoutingDisjunctionIndex	DisjunctionIndex
typedef RoutingVehicleClassIndex	VehicleClassIndex
typedef RoutingResourceClassIndex	ResourceClassIndex
typedef RoutingTransitCallback1	TransitCallback1
typedef RoutingTransitCallback2	TransitCallback2
typedef RoutingCumulDependentTransitCallback2	CumulDependentTransitCallback2
typedef std::function< StateDependentTransit(int64_t, int64_t)>	VariableIndexEvaluator2
using	GetTabuVarsCallback

Public Member Functions
	RoutingModel (const RoutingIndexManager &index_manager)
	RoutingModel (const RoutingIndexManager &index_manager, const RoutingModelParameters &parameters)
	RoutingModel (const RoutingModel &)=delete
RoutingModel &	operator= (const RoutingModel &)=delete
	~RoutingModel ()
int	RegisterUnaryTransitVector (std::vector< int64_t > values)
int	RegisterUnaryTransitCallback (TransitCallback1 callback, TransitEvaluatorSign sign=kTransitEvaluatorSignUnknown)
int	RegisterTransitMatrix (std::vector< std::vector< int64_t > > values)
int	RegisterTransitCallback (TransitCallback2 callback, TransitEvaluatorSign sign=kTransitEvaluatorSignUnknown)
int	RegisterCumulDependentTransitCallback (CumulDependentTransitCallback2 callback)
int	RegisterStateDependentTransitCallback (VariableIndexEvaluator2 callback)
const TransitCallback2 &	TransitCallback (int callback_index) const
const TransitCallback1 &	UnaryTransitCallbackOrNull (int callback_index) const
const CumulDependentTransitCallback2 &	CumulDependentTransitCallback (int callback_index) const
const VariableIndexEvaluator2 &	StateDependentTransitCallback (int callback_index) const
bool	AddDimension (int evaluator_index, int64_t slack_max, int64_t capacity, bool fix_start_cumul_to_zero, const std::string &name)
	Model creation.
bool	AddDimensionWithVehicleTransits (const std::vector< int > &evaluator_indices, int64_t slack_max, int64_t capacity, bool fix_start_cumul_to_zero, const std::string &name)
bool	AddDimensionWithVehicleCapacity (int evaluator_index, int64_t slack_max, std::vector< int64_t > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
bool	AddDimensionWithVehicleTransitAndCapacity (const std::vector< int > &evaluator_indices, int64_t slack_max, std::vector< int64_t > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
bool	AddDimensionWithCumulDependentVehicleTransitAndCapacity (const std::vector< int > &fixed_evaluator_indices, const std::vector< int > &cumul_dependent_evaluator_indices, int64_t slack_max, std::vector< int64_t > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
std::pair< int, bool >	AddConstantDimensionWithSlack (int64_t value, int64_t capacity, int64_t slack_max, bool fix_start_cumul_to_zero, const std::string &name)
std::pair< int, bool >	AddConstantDimension (int64_t value, int64_t capacity, bool fix_start_cumul_to_zero, const std::string &name)
std::pair< int, bool >	AddVectorDimension (std::vector< int64_t > values, int64_t capacity, bool fix_start_cumul_to_zero, const std::string &name)
std::pair< int, bool >	AddMatrixDimension (std::vector< std::vector< int64_t > > values, int64_t capacity, bool fix_start_cumul_to_zero, const std::string &name)
bool	AddDimensionDependentDimensionWithVehicleCapacity (const std::vector< int > &pure_transits, const std::vector< int > &dependent_transits, const RoutingDimension *base_dimension, int64_t slack_max, std::vector< int64_t > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
bool	AddDimensionDependentDimensionWithVehicleCapacity (const std::vector< int > &transits, const RoutingDimension *base_dimension, int64_t slack_max, std::vector< int64_t > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
	As above, but pure_transits are taken to be zero evaluators.
bool	AddDimensionDependentDimensionWithVehicleCapacity (int transit, const RoutingDimension *base_dimension, int64_t slack_max, int64_t vehicle_capacity, bool fix_start_cumul_to_zero, const std::string &name)
	Homogeneous versions of the functions above.
bool	AddDimensionDependentDimensionWithVehicleCapacity (int pure_transit, int dependent_transit, const RoutingDimension *base_dimension, int64_t slack_max, int64_t vehicle_capacity, bool fix_start_cumul_to_zero, const std::string &name)
std::vector< std::string >	GetAllDimensionNames () const
	Outputs the names of all dimensions added to the routing engine.
const std::vector< RoutingDimension * > &	GetDimensions () const
	Returns all dimensions of the model.
std::vector< RoutingDimension * >	GetDimensionsWithSoftOrSpanCosts () const
	Returns dimensions with soft or vehicle span costs.
std::vector< RoutingDimension * >	GetUnaryDimensions () const
	Returns dimensions for which all transit evaluators are unary.
std::vector< const RoutingDimension * >	GetDimensionsWithGlobalCumulOptimizers () const
	Returns the dimensions which have [global|local]_dimension_optimizers_.
std::vector< const RoutingDimension * >	GetDimensionsWithLocalCumulOptimizers () const
bool	HasGlobalCumulOptimizer (const RoutingDimension &dimension) const
	Returns whether the given dimension has global/local cumul optimizers.
bool	HasLocalCumulOptimizer (const RoutingDimension &dimension) const
GlobalDimensionCumulOptimizer *	GetMutableGlobalCumulLPOptimizer (const RoutingDimension &dimension) const
GlobalDimensionCumulOptimizer *	GetMutableGlobalCumulMPOptimizer (const RoutingDimension &dimension) const
LocalDimensionCumulOptimizer *	GetMutableLocalCumulLPOptimizer (const RoutingDimension &dimension) const
LocalDimensionCumulOptimizer *	GetMutableLocalCumulMPOptimizer (const RoutingDimension &dimension) const
bool	HasDimension (absl::string_view dimension_name) const
	Returns true if a dimension exists for a given dimension name.
const RoutingDimension &	GetDimensionOrDie (const std::string &dimension_name) const
	Returns a dimension from its name. Dies if the dimension does not exist.
RoutingDimension *	GetMutableDimension (const std::string &dimension_name) const
void	SetPrimaryConstrainedDimension (absl::string_view dimension_name)
const std::string &	GetPrimaryConstrainedDimension () const
	Get the primary constrained dimension, or an empty string if it is unset.
ResourceGroup *	AddResourceGroup ()
	Adds a resource group to the routing model and returns a pointer to it.
const std::vector< std::unique_ptr< ResourceGroup > > &	GetResourceGroups () const
ResourceGroup *	GetResourceGroup (int rg_index) const
const std::vector< int > &	GetDimensionResourceGroupIndices (const RoutingDimension *dimension) const
int	GetDimensionResourceGroupIndex (const RoutingDimension *dimension) const
DisjunctionIndex	AddDisjunction (const std::vector< int64_t > &indices, int64_t penalty=kNoPenalty, int64_t max_cardinality=1, PenaltyCostBehavior penalty_cost_behavior=PenaltyCostBehavior::PENALIZE_ONCE)
	Adds a disjunction constraint on the indices.
const std::vector< DisjunctionIndex > &	GetDisjunctionIndices (int64_t index) const
	Returns the indices of the disjunctions to which an index belongs.
template<typename F>
void	ForEachNodeInDisjunctionWithMaxCardinalityFromIndex (int64_t index, int64_t max_cardinality, F f) const
const std::vector< int64_t > &	GetDisjunctionNodeIndices (DisjunctionIndex index) const
int64_t	GetDisjunctionPenalty (DisjunctionIndex index) const
	Returns the penalty of the node disjunction of index 'index'.
int64_t	GetDisjunctionMaxCardinality (DisjunctionIndex index) const
PenaltyCostBehavior	GetDisjunctionPenaltyCostBehavior (DisjunctionIndex index) const
int	GetNumberOfDisjunctions () const
	Returns the number of node disjunctions in the model.
bool	HasMandatoryDisjunctions () const
bool	HasMaxCardinalityConstrainedDisjunctions () const
std::vector< std::pair< int64_t, int64_t > >	GetPerfectBinaryDisjunctions () const
void	IgnoreDisjunctionsAlreadyForcedToZero ()
void	AddSoftSameVehicleConstraint (std::vector< int64_t > indices, int64_t cost)
int	GetNumberOfSoftSameVehicleConstraints () const
	Returns the number of soft same vehicle constraints in the model.
const std::vector< int64_t > &	GetSoftSameVehicleIndices (int index) const
int64_t	GetSoftSameVehicleCost (int index) const
	Returns the cost of the soft same vehicle constraint of index 'index'.
void	SetAllowedVehiclesForIndex (absl::Span< const int > vehicles, int64_t index)
bool	IsVehicleAllowedForIndex (int vehicle, int64_t index) const
	Returns true if a vehicle is allowed to visit a given node.
void	AddPickupAndDelivery (int64_t pickup, int64_t delivery)
void	AddPickupAndDeliverySets (DisjunctionIndex pickup_disjunction, DisjunctionIndex delivery_disjunction)
std::optional< PickupDeliveryPosition >	GetPickupPosition (int64_t node_index) const
	Returns the pickup and delivery positions where the node is a pickup.
std::optional< PickupDeliveryPosition >	GetDeliveryPosition (int64_t node_index) const
	Returns the pickup and delivery positions where the node is a delivery.
bool	IsPickup (int64_t node_index) const
	Returns whether the node is a pickup (resp. delivery).
bool	IsDelivery (int64_t node_index) const
void	SetPickupAndDeliveryPolicyOfAllVehicles (PickupAndDeliveryPolicy policy)
void	SetPickupAndDeliveryPolicyOfVehicle (PickupAndDeliveryPolicy policy, int vehicle)
PickupAndDeliveryPolicy	GetPickupAndDeliveryPolicyOfVehicle (int vehicle) const
int	GetNumOfSingletonNodes () const
const std::vector< PickupDeliveryPair > &	GetPickupAndDeliveryPairs () const
	Returns pickup and delivery pairs currently in the model.
const std::vector< std::pair< DisjunctionIndex, DisjunctionIndex > > &	GetPickupAndDeliveryDisjunctions () const
const std::vector< PickupDeliveryPair > &	GetImplicitUniquePickupAndDeliveryPairs () const
std::optional< int64_t >	GetFirstMatchingPickupDeliverySibling (int64_t node, const std::function< bool(int64_t)> &is_match) const
void	SetVisitType (int64_t index, int type, VisitTypePolicy type_policy)
int	GetVisitType (int64_t index) const
const std::vector< int > &	GetSingleNodesOfType (int type) const
const std::vector< int > &	GetPairIndicesOfType (int type) const
VisitTypePolicy	GetVisitTypePolicy (int64_t index) const
const std::vector< std::vector< int > > &	GetVisitTypeComponents () const
int	GetNumberOfVisitTypes () const
const std::vector< std::vector< int > > &	GetTopologicallySortedVisitTypes () const
const std::vector< std::vector< std::vector< int > > > &	GetTopologicallySortedNodePrecedences () const
void	AddHardTypeIncompatibility (int type1, int type2)
void	AddTemporalTypeIncompatibility (int type1, int type2)
const absl::flat_hash_set< int > &	GetHardTypeIncompatibilitiesOfType (int type) const
	Returns visit types incompatible with a given type.
const absl::flat_hash_set< int > &	GetTemporalTypeIncompatibilitiesOfType (int type) const
bool	HasHardTypeIncompatibilities () const
bool	HasTemporalTypeIncompatibilities () const
void	AddSameVehicleRequiredTypeAlternatives (int dependent_type, absl::flat_hash_set< int > required_type_alternatives)
void	AddRequiredTypeAlternativesWhenAddingType (int dependent_type, absl::flat_hash_set< int > required_type_alternatives)
void	AddRequiredTypeAlternativesWhenRemovingType (int dependent_type, absl::flat_hash_set< int > required_type_alternatives)
const std::vector< absl::flat_hash_set< int > > &	GetSameVehicleRequiredTypeAlternativesOfType (int type) const
const std::vector< absl::flat_hash_set< int > > &	GetRequiredTypeAlternativesWhenAddingType (int type) const
	Returns the set of requirement alternatives when adding the given type.
const std::vector< absl::flat_hash_set< int > > &	GetRequiredTypeAlternativesWhenRemovingType (int type) const
	Returns the set of requirement alternatives when removing the given type.
bool	HasSameVehicleTypeRequirements () const
bool	HasTemporalTypeRequirements () const
bool	HasTypeRegulations () const
int64_t	UnperformedPenalty (int64_t var_index) const
int64_t	UnperformedPenaltyOrValue (int64_t default_value, int64_t var_index) const
int64_t	GetDepot () const
void	SetMaximumNumberOfActiveVehicles (int max_active_vehicles)
int	GetMaximumNumberOfActiveVehicles () const
	Returns the maximum number of active vehicles.
void	SetArcCostEvaluatorOfAllVehicles (int evaluator_index)
void	SetArcCostEvaluatorOfVehicle (int evaluator_index, int vehicle)
	Sets the cost function for a given vehicle route.
void	SetFixedCostOfAllVehicles (int64_t cost)
void	SetFixedCostOfVehicle (int64_t cost, int vehicle)
	Sets the fixed cost of one vehicle route.
int64_t	GetFixedCostOfVehicle (int vehicle) const
void	SetPathEnergyCostOfVehicle (const std::string &force, const std::string &distance, int64_t cost_per_unit, int vehicle)
void	SetPathEnergyCostsOfVehicle (const std::string &force, const std::string &distance, int64_t threshold, int64_t cost_per_unit_below_threshold, int64_t cost_per_unit_above_threshold, int vehicle)
void	SetAmortizedCostFactorsOfAllVehicles (int64_t linear_cost_factor, int64_t quadratic_cost_factor)
	Sets the linear and quadratic cost factor of all vehicles.
void	SetAmortizedCostFactorsOfVehicle (int64_t linear_cost_factor, int64_t quadratic_cost_factor, int vehicle)
	Sets the linear and quadratic cost factor of the given vehicle.
const std::vector< int64_t > &	GetAmortizedLinearCostFactorOfVehicles () const
const std::vector< int64_t > &	GetAmortizedQuadraticCostFactorOfVehicles () const
void	AddRouteConstraint (absl::AnyInvocable< std::optional< int64_t >(const std::vector< int64_t > &)> route_evaluator, bool costs_are_homogeneous_across_vehicles=false)
std::optional< int64_t >	GetRouteCost (const std::vector< int64_t > &route) const
void	SetVehicleUsedWhenEmpty (bool is_used, int vehicle)
bool	IsVehicleUsedWhenEmpty (int vehicle) const
const Solver::IndexEvaluator2 &	first_solution_evaluator () const
void	SetFirstSolutionEvaluator (Solver::IndexEvaluator2 evaluator)
	Takes ownership of evaluator.
void	SetFirstSolutionHint (const operations_research::Assignment *hint)
const operations_research::Assignment *	GetFirstSolutionHint () const
	Returns the current hint assignment.
void	AddLocalSearchOperator (LocalSearchOperator *ls_operator)
void	AddSearchMonitor (SearchMonitor *monitor)
	Adds a search monitor to the search used to solve the routing model.
void	AddEnterSearchCallback (std::function< void()> callback)
void	AddAtSolutionCallback (std::function< void()> callback, bool track_unchecked_neighbors=false)
void	AddRestoreDimensionValuesResetCallback (std::function< void()> callback)
void	AddVariableMinimizedByFinalizer (operations_research::IntVar *var)
void	AddVariableMaximizedByFinalizer (operations_research::IntVar *var)
void	AddWeightedVariableMinimizedByFinalizer (operations_research::IntVar *var, int64_t cost)
void	AddWeightedVariableMaximizedByFinalizer (operations_research::IntVar *var, int64_t cost)
void	AddVariableTargetToFinalizer (operations_research::IntVar *var, int64_t target)
void	AddWeightedVariableTargetToFinalizer (operations_research::IntVar *var, int64_t target, int64_t cost)
void	CloseModel ()
void	CloseModelWithParameters (const RoutingSearchParameters &search_parameters)
const operations_research::Assignment *	Solve (const operations_research::Assignment *assignment=nullptr)
const operations_research::Assignment *	SolveWithParameters (const RoutingSearchParameters &search_parameters, std::vector< const operations_research::Assignment * > *solutions=nullptr)
const operations_research::Assignment *	SolveFromAssignmentWithParameters (const operations_research::Assignment *assignment, const RoutingSearchParameters &search_parameters, std::vector< const operations_research::Assignment * > *solutions=nullptr)
const operations_research::Assignment *	FastSolveFromAssignmentWithParameters (const operations_research::Assignment *assignment, const RoutingSearchParameters &search_parameters, bool check_solution_in_cp, absl::flat_hash_set< operations_research::IntVar * > *touched=nullptr)
const operations_research::Assignment *	SolveFromAssignmentsWithParameters (const std::vector< const operations_research::Assignment * > &assignments, const RoutingSearchParameters &search_parameters, std::vector< const operations_research::Assignment * > *solutions=nullptr)
const operations_research::Assignment *	SolveWithIteratedLocalSearch (const RoutingSearchParameters &search_parameters)
void	SetAssignmentFromOtherModelAssignment (operations_research::Assignment *target_assignment, const RoutingModel *source_model, const operations_research::Assignment *source_assignment)
operations_research::SubSolverStatistics	GetSubSolverStatistics () const
	Returns detailed search statistics.
int64_t	ComputeLowerBound ()
int64_t	objective_lower_bound () const
RoutingSearchStatus::Value	status () const
	Returns the current status of the routing model.
const RoutingSearchStats &	search_stats () const
	Returns search statistics.
bool	enable_deep_serialization () const
	Returns the value of the internal enable_deep_serialization_ parameter.
operations_research::IntVar *	ApplyLocks (absl::Span< const int64_t > locks)
bool	ApplyLocksToAllVehicles (const std::vector< std::vector< int64_t > > &locks, bool close_routes)
const operations_research::Assignment *	PreAssignment () const
operations_research::Assignment *	MutablePreAssignment ()
bool	WriteAssignment (const std::string &file_name) const
operations_research::Assignment *	ReadAssignment (const std::string &file_name)
operations_research::Assignment *	RestoreAssignment (const operations_research::Assignment &solution)
operations_research::Assignment *	ReadAssignmentFromRoutes (const std::vector< std::vector< int64_t > > &routes, bool ignore_inactive_indices)
bool	RoutesToAssignment (const std::vector< std::vector< int64_t > > &routes, bool ignore_inactive_indices, bool close_routes, operations_research::Assignment *assignment) const
void	AssignmentToRoutes (const operations_research::Assignment &assignment, std::vector< std::vector< int64_t > > *routes) const
std::vector< std::vector< int64_t > >	GetRoutesFromAssignment (const operations_research::Assignment &assignment)
operations_research::Assignment *	CompactAssignment (const operations_research::Assignment &assignment) const
operations_research::Assignment *	CompactAndCheckAssignment (const operations_research::Assignment &assignment) const
void	AddToAssignment (operations_research::IntVar *var)
	Adds an extra variable to the vehicle routing assignment.
void	AddIntervalToAssignment (IntervalVar *interval)
const operations_research::Assignment *	PackCumulsOfOptimizerDimensionsFromAssignment (const operations_research::Assignment *original_assignment, absl::Duration duration_limit, bool *time_limit_was_reached=nullptr)
void	SetSweepArranger (SweepArranger *sweep_arranger)
SweepArranger *	sweep_arranger () const
	Returns the sweep arranger to be used by routing heuristics.
const NodeNeighborsByCostClass *	GetOrCreateNodeNeighborsByCostClass (double neighbors_ratio, int64_t min_neighbors, double &neighbors_ratio_used, bool add_vehicle_starts_to_neighbors=true, bool add_vehicle_ends_to_neighbors=false, bool only_sort_neighbors_for_partial_neighborhoods=true)
const NodeNeighborsByCostClass *	GetOrCreateNodeNeighborsByCostClass (const NodeNeighborsParameters &params)
void	AddLocalSearchFilter (LocalSearchFilter *filter)
int64_t	Start (int vehicle) const
int64_t	End (int vehicle) const
	Returns the variable index of the ending node of a vehicle route.
bool	IsStart (int64_t index) const
	Returns true if 'index' represents the first node of a route.
bool	IsEnd (int64_t index) const
	Returns true if 'index' represents the last node of a route.
int	VehicleIndex (int64_t index) const
int64_t	Next (const operations_research::Assignment &assignment, int64_t index) const
bool	IsVehicleUsed (const operations_research::Assignment &assignment, int vehicle) const
	Returns true if the route of 'vehicle' is non empty in 'assignment'.
const std::vector< operations_research::IntVar * > &	Nexts () const
const std::vector< operations_research::IntVar * > &	VehicleVars () const
const std::vector< operations_research::IntVar * > &	ResourceVars (int resource_group) const
operations_research::IntVar *	NextVar (int64_t index) const
operations_research::IntVar *	ActiveVar (int64_t index) const
	Returns the active variable of the node corresponding to index.
operations_research::IntVar *	ActiveVehicleVar (int vehicle) const
operations_research::IntVar *	VehicleRouteConsideredVar (int vehicle) const
operations_research::IntVar *	VehicleVar (int64_t index) const
operations_research::IntVar *	ResourceVar (int vehicle, int resource_group) const
operations_research::IntVar *	CostVar () const
	Returns the global cost variable which is being minimized.
int64_t	GetArcCostForVehicle (int64_t from_index, int64_t to_index, int64_t vehicle) const
bool	CostsAreHomogeneousAcrossVehicles () const
	Whether costs are homogeneous across all vehicles.
int64_t	GetHomogeneousCost (int64_t from_index, int64_t to_index) const
int64_t	GetArcCostForFirstSolution (int64_t from_index, int64_t to_index) const
int64_t	GetArcCostForClass (int64_t from_index, int64_t to_index, int64_t cost_class_index) const
CostClassIndex	GetCostClassIndexOfVehicle (int64_t vehicle) const
	Get the cost class index of the given vehicle.
bool	HasVehicleWithCostClassIndex (CostClassIndex cost_class_index) const
int	GetCostClassesCount () const
	Returns the number of different cost classes in the model.
int	GetNonZeroCostClassesCount () const
	Ditto, minus the 'always zero', built-in cost class.
VehicleClassIndex	GetVehicleClassIndexOfVehicle (int64_t vehicle) const
int	GetVehicleOfClass (VehicleClassIndex vehicle_class) const
int	GetVehicleClassesCount () const
	Returns the number of different vehicle classes in the model.
const std::vector< int > &	GetSameVehicleIndicesOfIndex (int node) const
	Returns variable indices of nodes constrained to be on the same route.
void	AddSameActivityGroup (absl::Span< const int > nodes)
const std::vector< int > &	GetSameActivityIndicesOfIndex (int node) const
	Returns variable indices of nodes constrained to have the same activity.
int	GetSameActivityGroupOfIndex (int node) const
	Returns the same activity group of the node.
const std::vector< int > &	GetSameActivityGroups () const
	Returns same activity groups of all nodes.
int	GetSameActivityGroupsCount () const
	Returns the number of same activity groups.
const std::vector< int > &	GetSameActivityIndicesOfGroup (int group) const
	Returns variable indices of nodes in the same activity group.
void	AddOrderedActivityGroup (std::vector< DisjunctionIndex > disjunctions)
const std::vector< std::vector< DisjunctionIndex > > &	GetOrderedActivityGroups () const
	Returns all ordered activity groups.
const VehicleTypeContainer &	GetVehicleTypeContainer () const
bool	ArcIsMoreConstrainedThanArc (int64_t from, int64_t to1, int64_t to2)
std::string	DebugOutputAssignment (const operations_research::Assignment &solution_assignment, const std::string &dimension_to_print) const
std::vector< std::vector< std::pair< int64_t, int64_t > > >	GetCumulBounds (const operations_research::Assignment &solution_assignment, const RoutingDimension &dimension)
bool	CheckIfAssignmentIsFeasible (const operations_research::Assignment &assignment, bool call_at_solution_monitors)
	Checks if an assignment is feasible.
Solver *	solver () const
bool	CheckLimit (absl::Duration offset=absl::ZeroDuration())
absl::Duration	RemainingTime () const
	Returns the time left in the search limit.
void	UpdateTimeLimit (absl::Duration time_limit)
	Updates the time limit of the search limit.
absl::Duration	TimeBuffer () const
	Returns the time buffer to safely return a solution.
std::atomic< bool > *	GetMutableCPSatInterrupt ()
	Returns the atomic<bool> to stop the CP-SAT solver.
std::atomic< bool > *	GetMutableCPInterrupt ()
	Returns the atomic<bool> to stop the CP solver.
void	CancelSearch ()
	Cancels the current search.
int	nodes () const
int	vehicles () const
	Returns the number of vehicle routes in the model.
int64_t	Size () const
	Returns the number of next variables in the model.
int64_t	GetNumberOfDecisionsInFirstSolution (const RoutingSearchParameters &search_parameters) const
int64_t	GetNumberOfRejectsInFirstSolution (const RoutingSearchParameters &search_parameters) const
operations_research::FirstSolutionStrategy::Value	GetAutomaticFirstSolutionStrategy () const
	Returns the automatic first solution strategy selected.
bool	IsMatchingModel () const
	Returns true if a vehicle/node matching problem is detected.
bool	AreRoutesInterdependent (const RoutingSearchParameters &parameters) const
void	SetTabuVarsCallback (GetTabuVarsCallback tabu_var_callback)
DecisionBuilder *	MakeGuidedSlackFinalizer (const RoutingDimension *dimension, std::function< int64_t(int64_t)> initializer)
	The next few members are in the public section only for testing purposes.
const std::vector< SearchMonitor * > &	GetSearchMonitors () const
DecisionBuilder *	MakeSelfDependentDimensionFinalizer (const RoutingDimension *dimension)
const PathsMetadata &	GetPathsMetadata () const
BinCapacities *	GetBinCapacities ()
void	SetSecondaryModel (RoutingModel *secondary_model, RoutingSearchParameters secondary_parameters)
const std::deque< int > &	GetVehiclesOfSameClass (int64_t start_end_index) const
std::vector< std::pair< int64_t, int64_t > >	GetSameVehicleClassArcs (int64_t from_index, int64_t to_index) const

Static Public Member Functions
static RoutingModel::StateDependentTransit	MakeStateDependentTransit (const std::function< int64_t(int64_t)> &f, int64_t domain_start, int64_t domain_end)
	Creates a cached StateDependentTransit from an std::function.
static std::unique_ptr< LocalSearchOperator >	MakeGreedyDescentLSOperator (std::vector< operations_research::IntVar * > variables)

Static Public Attributes
static const int64_t	kNoPenalty = -1
	Constant used to express a hard constraint instead of a soft penalty.
static const DisjunctionIndex	kNoDisjunction
static const DimensionIndex	kNoDimension

Friends
class	RoutingDimension
class	RoutingModelInspector
class	ResourceGroup::Resource

Member Typedef Documentation

CostClassIndex

typedef RoutingCostClassIndex operations_research::RoutingModel::CostClassIndex

Definition at line 269 of file routing.h.

CumulDependentTransitCallback2

typedef RoutingCumulDependentTransitCallback2 operations_research::RoutingModel::CumulDependentTransitCallback2

Definition at line 276 of file routing.h.

DimensionIndex

typedef RoutingDimensionIndex operations_research::RoutingModel::DimensionIndex

Definition at line 270 of file routing.h.

DisjunctionIndex

typedef RoutingDisjunctionIndex operations_research::RoutingModel::DisjunctionIndex

Definition at line 271 of file routing.h.

GetTabuVarsCallback

using operations_research::RoutingModel::GetTabuVarsCallback

Initial value:

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

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

Definition at line 2128 of file routing.h.

ResourceClassIndex

typedef RoutingResourceClassIndex operations_research::RoutingModel::ResourceClassIndex

Definition at line 273 of file routing.h.

TransitCallback1

typedef RoutingTransitCallback1 operations_research::RoutingModel::TransitCallback1

Definition at line 274 of file routing.h.

TransitCallback2

typedef RoutingTransitCallback2 operations_research::RoutingModel::TransitCallback2

Definition at line 275 of file routing.h.

VariableIndexEvaluator2

typedef std::function<StateDependentTransit(int64_t, int64_t)> operations_research::RoutingModel::VariableIndexEvaluator2

Definition at line 296 of file routing.h.

VehicleClassIndex

typedef RoutingVehicleClassIndex operations_research::RoutingModel::VehicleClassIndex

Definition at line 272 of file routing.h.

Member Enumeration Documentation

PenaltyCostBehavior

enum operations_research::RoutingModel::PenaltyCostBehavior

The following enum is used to describe how the penalty cost is computed when using AddDisjunction.

Enumerator
PENALIZE_ONCE
PENALIZE_PER_INACTIVE

Definition at line 892 of file routing.h.

PickupAndDeliveryPolicy

enum operations_research::RoutingModel::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 261 of file routing.h.

TransitEvaluatorSign

enum operations_research::RoutingModel::TransitEvaluatorSign

Represents the sign of values returned by a transit evaluator.

Enumerator
kTransitEvaluatorSignUnknown
kTransitEvaluatorSignPositiveOrZero
kTransitEvaluatorSignNegativeOrZero

Definition at line 637 of file routing.h.

VisitTypePolicy

enum operations_research::RoutingModel::VisitTypePolicy

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

Note

Before adding any incompatibilities and/or requirements on types, all corresponding node types must have been set. 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 1110 of file routing.h.

Constructor & Destructor Documentation

RoutingModel() [1/3]

operations_research::RoutingModel::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 514 of file routing.cc.

RoutingModel() [2/3]

operations_research::RoutingModel::RoutingModel	(	const RoutingIndexManager &	index_manager,
		const RoutingModelParameters &	parameters )

Definition at line 528 of file routing.cc.

RoutingModel() [3/3]

operations_research::RoutingModel::RoutingModel ( const RoutingModel & )

delete

~RoutingModel()

operations_research::RoutingModel::~RoutingModel

(

)

Definition at line 607 of file routing.cc.

Member Function Documentation

ActiveVar()

operations_research::IntVar * operations_research::RoutingModel::ActiveVar ( int64_t index ) const

inline

Returns the active variable of the node corresponding to index.

Definition at line 1863 of file routing.h.

ActiveVehicleVar()

operations_research::IntVar * operations_research::RoutingModel::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 1868 of file routing.h.

AddAtSolutionCallback()

void operations_research::RoutingModel::AddAtSolutionCallback	(	std::function< void()>	callback,
		bool	track_unchecked_neighbors = false )

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. If track_unchecked_neighbors is true, the callback will also be called on AcceptUncheckedNeighbor() events, which is useful to grab solutions obtained when solver_parameters.check_solution_period > 1 (aka fastLS).

Definition at line 3160 of file routing.cc.

AddConstantDimension()

std::pair< int, bool > operations_research::RoutingModel::AddConstantDimension ( int64_t value, int64_t capacity, bool fix_start_cumul_to_zero, const std::string & name )

inline

Definition at line 738 of file routing.h.

AddConstantDimensionWithSlack()

std::pair< int, bool > operations_research::RoutingModel::AddConstantDimensionWithSlack	(	int64_t	value,
		int64_t	capacity,
		int64_t	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 836 of file routing.cc.

AddDimension()

bool operations_research::RoutingModel::AddDimension	(	int	evaluator_index,
		int64_t	slack_max,
		int64_t	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, j) + 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 743 of file routing.cc.

AddDimensionDependentDimensionWithVehicleCapacity() [1/4]

bool operations_research::RoutingModel::AddDimensionDependentDimensionWithVehicleCapacity ( const std::vector< int > & pure_transits, const std::vector< int > & dependent_transits, const RoutingDimension * base_dimension, int64_t slack_max, std::vector< int64_t > 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 775 of file routing.h.

AddDimensionDependentDimensionWithVehicleCapacity() [2/4]

bool operations_research::RoutingModel::AddDimensionDependentDimensionWithVehicleCapacity	(	const std::vector< int > &	transits,
		const RoutingDimension *	base_dimension,
		int64_t	slack_max,
		std::vector< int64_t >	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 944 of file routing.cc.

AddDimensionDependentDimensionWithVehicleCapacity() [3/4]

bool operations_research::RoutingModel::AddDimensionDependentDimensionWithVehicleCapacity	(	int	pure_transit,
		int	dependent_transit,
		const RoutingDimension *	base_dimension,
		int64_t	slack_max,
		int64_t	vehicle_capacity,
		bool	fix_start_cumul_to_zero,
		const std::string &	name )

Definition at line 985 of file routing.cc.

AddDimensionDependentDimensionWithVehicleCapacity() [4/4]

bool operations_research::RoutingModel::AddDimensionDependentDimensionWithVehicleCapacity	(	int	transit,
		const RoutingDimension *	base_dimension,
		int64_t	slack_max,
		int64_t	vehicle_capacity,
		bool	fix_start_cumul_to_zero,
		const std::string &	name )

Homogeneous versions of the functions above.

Definition at line 955 of file routing.cc.

AddDimensionWithCumulDependentVehicleTransitAndCapacity()

bool operations_research::RoutingModel::AddDimensionWithCumulDependentVehicleTransitAndCapacity	(	const std::vector< int > &	fixed_evaluator_indices,
		const std::vector< int > &	cumul_dependent_evaluator_indices,
		int64_t	slack_max,
		std::vector< int64_t >	vehicle_capacities,
		bool	fix_start_cumul_to_zero,
		const std::string &	name )

Creates a dimension where the transit variable on arc i->j is the sum of:

• A "fixed" transit value, obtained from the fixed_evaluator_index for this vehicle, referencing evaluators in transit_evaluators_, and
• A FloatSlopePiecewiseLinearFunction of the cumul of node i, obtained from the cumul_dependent_evaluator_index of this vehicle, pointing to an evaluator in cumul_dependent_transit_evaluators_.

Definition at line 781 of file routing.cc.

AddDimensionWithVehicleCapacity()

bool operations_research::RoutingModel::AddDimensionWithVehicleCapacity	(	int	evaluator_index,
		int64_t	slack_max,
		std::vector< int64_t >	vehicle_capacities,
		bool	fix_start_cumul_to_zero,
		const std::string &	name )

Definition at line 762 of file routing.cc.

AddDimensionWithVehicleTransitAndCapacity()

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

Definition at line 772 of file routing.cc.

AddDimensionWithVehicleTransits()

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

Definition at line 753 of file routing.cc.

AddDisjunction()

RoutingModel::DisjunctionIndex operations_research::RoutingModel::AddDisjunction	(	const std::vector< int64_t > &	indices,
		int64_t	penalty = kNoPenalty,
		int64_t	max_cardinality = 1,
		PenaltyCostBehavior	penalty_cost_behavior = PenaltyCostBehavior::PENALIZE_ONCE )

Adds a disjunction constraint on the indices.

Exactly 'max_cardinality' of the indices are active. 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 if the penalty cost is set to PENALIZE_PER_INACTIVE. This is equivalent to adding the constraint: p + Sum(i)active[i] == max_cardinality where p is an integer variable. If the penalty cost is set to PENALIZE_ONCE, then 'penalty' is payed once if there are less than max_cardinality of the indices active. This is equivalent to adding the constraint: p == (Sum(i)active[i] != max_cardinality) where p is a boolean variable. The following cost is added to the cost function: p * penalty.

Parameters

[in]

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.

Warning

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

Definition at line 1930 of file routing.cc.

AddEnterSearchCallback()

void operations_research::RoutingModel::AddEnterSearchCallback

(

std::function< void()>

callback

)

Definition at line 3154 of file routing.cc.

AddHardTypeIncompatibility()

void operations_research::RoutingModel::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.

Note

To avoid unnecessary memory reallocations, it is recommended to only add incompatibilities once all the existing types have been set with SetVisitType().

Definition at line 4479 of file routing.cc.

AddIntervalToAssignment()

void operations_research::RoutingModel::AddIntervalToAssignment

(

IntervalVar *

interval

)

Definition at line 6654 of file routing.cc.

AddLocalSearchFilter()

void operations_research::RoutingModel::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 1806 of file routing.h.

AddLocalSearchOperator()

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

AddMatrixDimension()

std::pair< int, bool > operations_research::RoutingModel::AddMatrixDimension	(	std::vector< std::vector< int64_t > >	values,
		int64_t	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 858 of file routing.cc.

AddOrderedActivityGroup()

void operations_research::RoutingModel::AddOrderedActivityGroup ( std::vector< DisjunctionIndex > disjunctions )

inline

Adds an ordered activity group. This enforces that if disjunctions[i] is active, then disjunctions[i-1] must be active.

Definition at line 2004 of file routing.h.

AddPickupAndDelivery()

void operations_research::RoutingModel::AddPickupAndDelivery	(	int64_t	pickup,
		int64_t	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_t index1 = manager.NodeToIndex(node1); int64_t index2 = manager.NodeToIndex(node2); solver->AddConstraint(solver->MakeEquality( routing.VehicleVar(index1), routing.VehicleVar(index2))); routing.AddPickupAndDelivery(index1, index2);

Definition at line 2055 of file routing.cc.

AddPickupAndDeliverySets()

void operations_research::RoutingModel::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 2060 of file routing.cc.

AddRequiredTypeAlternativesWhenAddingType()

void operations_research::RoutingModel::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 4546 of file routing.cc.

AddRequiredTypeAlternativesWhenRemovingType()

void operations_research::RoutingModel::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 4569 of file routing.cc.

AddResourceGroup()

ResourceGroup * operations_research::RoutingModel::AddResourceGroup

(

)

Adds a resource group to the routing model and returns a pointer to it.

Definition at line 1137 of file routing.cc.

AddRestoreDimensionValuesResetCallback()

void operations_research::RoutingModel::AddRestoreDimensionValuesResetCallback

(

std::function< void()>

callback

)

Definition at line 3103 of file routing.cc.

AddRouteConstraint()

void operations_research::RoutingModel::AddRouteConstraint	(	absl::AnyInvocable< std::optional< int64_t >(const std::vector< int64_t > &)>	route_evaluator,
		bool	costs_are_homogeneous_across_vehicles = false )

Definition at line 1375 of file routing.cc.

AddSameActivityGroup()

void operations_research::RoutingModel::AddSameActivityGroup ( absl::Span< const int > nodes )

inline

Definition at line 1968 of file routing.h.

AddSameVehicleRequiredTypeAlternatives()

void operations_research::RoutingModel::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.

To avoid unnecessary memory reallocations, it is recommended to only add requirements once all the existing types have been set with SetVisitType().

Definition at line 4521 of file routing.cc.

AddSearchMonitor()

void operations_research::RoutingModel::AddSearchMonitor

(

SearchMonitor *

monitor

)

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

Definition at line 3098 of file routing.cc.

AddSoftSameVehicleConstraint()

void operations_research::RoutingModel::AddSoftSameVehicleConstraint	(	std::vector< int64_t >	indices,
		int64_t	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.

Todo

(user): Extend this to allow nodes/indices to be on the same given set of vehicle.

Definition at line 2037 of file routing.cc.

AddTemporalTypeIncompatibility()

void operations_research::RoutingModel::AddTemporalTypeIncompatibility	(	int	type1,
		int	type2 )

Definition at line 4489 of file routing.cc.

AddToAssignment()

void operations_research::RoutingModel::AddToAssignment

(

operations_research::IntVar *

var

)

Adds an extra variable to the vehicle routing assignment.

Definition at line 6650 of file routing.cc.

AddVariableMaximizedByFinalizer()

void operations_research::RoutingModel::AddVariableMaximizedByFinalizer

(

operations_research::IntVar *

var

)

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

Definition at line 6610 of file routing.cc.

AddVariableMinimizedByFinalizer()

void operations_research::RoutingModel::AddVariableMinimizedByFinalizer

(

operations_research::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 6614 of file routing.cc.

AddVariableTargetToFinalizer()

void operations_research::RoutingModel::AddVariableTargetToFinalizer	(	operations_research::IntVar *	var,
		int64_t	target )

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

Definition at line 6606 of file routing.cc.

AddVectorDimension()

std::pair< int, bool > operations_research::RoutingModel::AddVectorDimension	(	std::vector< int64_t >	values,
		int64_t	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 849 of file routing.cc.

AddWeightedVariableMaximizedByFinalizer()

void operations_research::RoutingModel::AddWeightedVariableMaximizedByFinalizer	(	operations_research::IntVar *	var,
		int64_t	cost )

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

Definition at line 6601 of file routing.cc.

AddWeightedVariableMinimizedByFinalizer()

void operations_research::RoutingModel::AddWeightedVariableMinimizedByFinalizer	(	operations_research::IntVar *	var,
		int64_t	cost )

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

Definition at line 6596 of file routing.cc.

AddWeightedVariableTargetToFinalizer()

void operations_research::RoutingModel::AddWeightedVariableTargetToFinalizer	(	operations_research::IntVar *	var,
		int64_t	target,
		int64_t	cost )

Same as above with a weighted priority: the higher the cost, the more priority it has to be set close to the target value.

Definition at line 6590 of file routing.cc.

ApplyLocks()

IntVar * operations_research::RoutingModel::ApplyLocks

(

absl::Span< const int64_t >

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

ApplyLocksToAllVehicles()

bool operations_research::RoutingModel::ApplyLocksToAllVehicles	(	const std::vector< std::vector< int64_t > > &	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 3974 of file routing.cc.

ArcIsMoreConstrainedThanArc()

bool operations_research::RoutingModel::ArcIsMoreConstrainedThanArc	(	int64_t	from,
		int64_t	to1,
		int64_t	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 4354 of file routing.cc.

AreRoutesInterdependent()

bool operations_research::RoutingModel::AreRoutesInterdependent

(

const RoutingSearchParameters &

parameters

)

const

Returns true if routes are interdependent. This means that any modification to a route might impact another.

Definition at line 5817 of file routing.cc.

AssignmentToRoutes()

void operations_research::RoutingModel::AssignmentToRoutes	(	const operations_research::Assignment &	assignment,
		std::vector< std::vector< int64_t > > *	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 4162 of file routing.cc.

CancelSearch()

void operations_research::RoutingModel::CancelSearch ( )

inline

Cancels the current search.

Definition at line 2093 of file routing.h.

CheckIfAssignmentIsFeasible()

bool operations_research::RoutingModel::CheckIfAssignmentIsFeasible	(	const operations_research::Assignment &	assignment,
		bool	call_at_solution_monitors )

Checks if an assignment is feasible.

Definition at line 3203 of file routing.cc.

CheckLimit()

bool operations_research::RoutingModel::CheckLimit ( absl::Duration offset = absl::ZeroDuration() )

inline

Returns true if the search limit has been crossed with the given time offset.

Definition at line 2066 of file routing.h.

CloseModel()

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

Definition at line 2345 of file routing.cc.

CloseModelWithParameters()

void operations_research::RoutingModel::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 2550 of file routing.cc.

CompactAndCheckAssignment()

Assignment * operations_research::RoutingModel::CompactAndCheckAssignment

(

const operations_research::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 3867 of file routing.cc.

CompactAssignment()

Assignment * operations_research::RoutingModel::CompactAssignment

(

const operations_research::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 3862 of file routing.cc.

ComputeLowerBound()

int64_t operations_research::RoutingModel::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

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

CostsAreHomogeneousAcrossVehicles()

bool operations_research::RoutingModel::CostsAreHomogeneousAcrossVehicles ( ) const

inline

Whether costs are homogeneous across all vehicles.

Definition at line 1899 of file routing.h.

CostVar()

operations_research::IntVar * operations_research::RoutingModel::CostVar ( ) const

inline

Returns the global cost variable which is being minimized.

Definition at line 1892 of file routing.h.

CumulDependentTransitCallback()

const CumulDependentTransitCallback2 & operations_research::RoutingModel::CumulDependentTransitCallback ( int callback_index ) const

inline

Definition at line 669 of file routing.h.

DebugOutputAssignment()

std::string operations_research::RoutingModel::DebugOutputAssignment	(	const operations_research::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 4642 of file routing.cc.

enable_deep_serialization()

bool operations_research::RoutingModel::enable_deep_serialization ( ) const

inline

Returns the value of the internal enable_deep_serialization_ parameter.

Definition at line 1500 of file routing.h.

End()

int64_t operations_research::RoutingModel::End ( int vehicle ) const

inline

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

Definition at line 1819 of file routing.h.

FastSolveFromAssignmentWithParameters()

const Assignment * operations_research::RoutingModel::FastSolveFromAssignmentWithParameters	(	const operations_research::Assignment *	assignment,
		const RoutingSearchParameters &	search_parameters,
		bool	check_solution_in_cp,
		absl::flat_hash_set< operations_research::IntVar * > *	touched = nullptr )

Improves a given assignment using unchecked local search. If check_solution_in_cp is true the final solution will be checked with the CP solver. As of 11/2023, only works with greedy descent.

Definition at line 3251 of file routing.cc.

first_solution_evaluator()

const Solver::IndexEvaluator2 & operations_research::RoutingModel::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 1359 of file routing.h.

ForEachNodeInDisjunctionWithMaxCardinalityFromIndex()

template<typename F>

void operations_research::RoutingModel::ForEachNodeInDisjunctionWithMaxCardinalityFromIndex ( int64_t index, int64_t max_cardinality, F 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 931 of file routing.h.

GetAllDimensionNames()

std::vector< std::string > operations_research::RoutingModel::GetAllDimensionNames

(

)

const

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

Definition at line 1010 of file routing.cc.

GetAmortizedLinearCostFactorOfVehicles()

const std::vector< int64_t > & operations_research::RoutingModel::GetAmortizedLinearCostFactorOfVehicles ( ) const

inline

Definition at line 1318 of file routing.h.

GetAmortizedQuadraticCostFactorOfVehicles()

const std::vector< int64_t > & operations_research::RoutingModel::GetAmortizedQuadraticCostFactorOfVehicles ( ) const

inline

Definition at line 1321 of file routing.h.

GetArcCostForClass()

int64_t operations_research::RoutingModel::GetArcCostForClass	(	int64_t	from_index,
		int64_t	to_index,
		int64_t	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 4308 of file routing.cc.

GetArcCostForFirstSolution()

int64_t operations_research::RoutingModel::GetArcCostForFirstSolution	(	int64_t	from_index,
		int64_t	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 4319 of file routing.cc.

GetArcCostForVehicle()

int64_t operations_research::RoutingModel::GetArcCostForVehicle	(	int64_t	from_index,
		int64_t	to_index,
		int64_t	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 4298 of file routing.cc.

GetAutomaticFirstSolutionStrategy()

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

inline

Returns the automatic first solution strategy selected.

Definition at line 2114 of file routing.h.

GetBinCapacities()

BinCapacities * operations_research::RoutingModel::GetBinCapacities ( )

inline

Definition at line 2182 of file routing.h.

GetCostClassesCount()

int operations_research::RoutingModel::GetCostClassesCount ( ) const

inline

Returns the number of different cost classes in the model.

Definition at line 1937 of file routing.h.

GetCostClassIndexOfVehicle()

CostClassIndex operations_research::RoutingModel::GetCostClassIndexOfVehicle ( int64_t vehicle ) const

inline

Get the cost class index of the given vehicle.

Definition at line 1920 of file routing.h.

GetCumulBounds()

std::vector< std::vector< std::pair< int64_t, int64_t > > > operations_research::RoutingModel::GetCumulBounds	(	const operations_research::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 4716 of file routing.cc.

GetDeliveryPosition()

std::optional< RoutingModel::PickupDeliveryPosition > operations_research::RoutingModel::GetDeliveryPosition

(

int64_t

node_index

)

const

Returns the pickup and delivery positions where the node is a delivery.

Definition at line 2106 of file routing.cc.

GetDepot()

int64_t operations_research::RoutingModel::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 2213 of file routing.cc.

GetDimensionOrDie()

const RoutingDimension & operations_research::RoutingModel::GetDimensionOrDie

(

const std::string &

dimension_name

)

const

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

Definition at line 1087 of file routing.cc.

GetDimensionResourceGroupIndex()

int operations_research::RoutingModel::GetDimensionResourceGroupIndex ( const RoutingDimension * dimension ) const

inline

Returns the index of the resource group attached to the dimension. DCHECKS that there's exactly one resource group for this dimension.

Definition at line 885 of file routing.h.

GetDimensionResourceGroupIndices()

const std::vector< int > & operations_research::RoutingModel::GetDimensionResourceGroupIndices

(

const RoutingDimension *

dimension

)

const

Returns the indices of resource groups for this dimension. This method can only be called after the model has been closed.

Definition at line 1233 of file routing.cc.

GetDimensions()

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

inline

Returns all dimensions of the model.

Definition at line 811 of file routing.h.

GetDimensionsWithGlobalCumulOptimizers()

std::vector< const RoutingDimension * > operations_research::RoutingModel::GetDimensionsWithGlobalCumulOptimizers

(

)

const

Returns the dimensions which have [global|local]_dimension_optimizers_.

Definition at line 5794 of file routing.cc.

GetDimensionsWithLocalCumulOptimizers()

std::vector< const RoutingDimension * > operations_research::RoutingModel::GetDimensionsWithLocalCumulOptimizers

(

)

const

Definition at line 5806 of file routing.cc.

GetDimensionsWithSoftOrSpanCosts()

std::vector< RoutingDimension * > operations_research::RoutingModel::GetDimensionsWithSoftOrSpanCosts

(

)

const

Returns dimensions with soft or vehicle span costs.

Definition at line 5758 of file routing.cc.

GetDisjunctionIndices()

const std::vector< DisjunctionIndex > & operations_research::RoutingModel::GetDisjunctionIndices ( int64_t index ) const

inline

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

Definition at line 923 of file routing.h.

GetDisjunctionMaxCardinality()

int64_t operations_research::RoutingModel::GetDisjunctionMaxCardinality ( DisjunctionIndex index ) const

inline

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

Definition at line 955 of file routing.h.

GetDisjunctionNodeIndices()

const std::vector< int64_t > & operations_research::RoutingModel::GetDisjunctionNodeIndices ( DisjunctionIndex index ) const

inline

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

Definition at line 944 of file routing.h.

GetDisjunctionPenalty()

int64_t operations_research::RoutingModel::GetDisjunctionPenalty ( DisjunctionIndex index ) const

inline

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

Definition at line 950 of file routing.h.

GetDisjunctionPenaltyCostBehavior()

PenaltyCostBehavior operations_research::RoutingModel::GetDisjunctionPenaltyCostBehavior ( DisjunctionIndex index ) const

inline

Returns the PenaltyCostBehavior used by the disjunction of index 'index'.

Definition at line 960 of file routing.h.

GetFirstMatchingPickupDeliverySibling()

std::optional< int64_t > operations_research::RoutingModel::GetFirstMatchingPickupDeliverySibling	(	int64_t	node,
		const std::function< bool(int64_t)> &	is_match ) const

Definition at line 2132 of file routing.cc.

GetFirstSolutionHint()

const operations_research::Assignment * operations_research::RoutingModel::GetFirstSolutionHint ( ) const

inline

Returns the current hint assignment.

Definition at line 1375 of file routing.h.

GetFixedCostOfVehicle()

int64_t operations_research::RoutingModel::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 1310 of file routing.cc.

GetHardTypeIncompatibilitiesOfType()

const absl::flat_hash_set< int > & operations_research::RoutingModel::GetHardTypeIncompatibilitiesOfType

(

int

type

)

const

Returns visit types incompatible with a given type.

Definition at line 4500 of file routing.cc.

GetHomogeneousCost()

int64_t operations_research::RoutingModel::GetHomogeneousCost ( int64_t from_index, int64_t 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 1904 of file routing.h.

GetImplicitUniquePickupAndDeliveryPairs()

const std::vector< PickupDeliveryPair > & operations_research::RoutingModel::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 1088 of file routing.h.

GetMaximumNumberOfActiveVehicles()

int operations_research::RoutingModel::GetMaximumNumberOfActiveVehicles ( ) const

inline

Returns the maximum number of active vehicles.

Definition at line 1255 of file routing.h.

GetMutableCPInterrupt()

std::atomic< bool > * operations_research::RoutingModel::GetMutableCPInterrupt ( )

inline

Returns the atomic<bool> to stop the CP solver.

Definition at line 2091 of file routing.h.

GetMutableCPSatInterrupt()

std::atomic< bool > * operations_research::RoutingModel::GetMutableCPSatInterrupt ( )

inline

Returns the atomic<bool> to stop the CP-SAT solver.

Definition at line 2089 of file routing.h.

GetMutableDimension()

RoutingDimension * operations_research::RoutingModel::GetMutableDimension

(

const std::string &

dimension_name

)

const

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

Definition at line 1092 of file routing.cc.

GetMutableGlobalCumulLPOptimizer()

GlobalDimensionCumulOptimizer * operations_research::RoutingModel::GetMutableGlobalCumulLPOptimizer

(

const RoutingDimension &

dimension

)

const

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

Definition at line 1019 of file routing.cc.

GetMutableGlobalCumulMPOptimizer()

GlobalDimensionCumulOptimizer * operations_research::RoutingModel::GetMutableGlobalCumulMPOptimizer

(

const RoutingDimension &

dimension

)

const

Definition at line 1027 of file routing.cc.

GetMutableLocalCumulLPOptimizer()

LocalDimensionCumulOptimizer * operations_research::RoutingModel::GetMutableLocalCumulLPOptimizer

(

const RoutingDimension &

dimension

)

const

Definition at line 1048 of file routing.cc.

GetMutableLocalCumulMPOptimizer()

LocalDimensionCumulOptimizer * operations_research::RoutingModel::GetMutableLocalCumulMPOptimizer

(

const RoutingDimension &

dimension

)

const

Definition at line 1056 of file routing.cc.

GetNonZeroCostClassesCount()

int operations_research::RoutingModel::GetNonZeroCostClassesCount ( ) const

inline

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

Definition at line 1939 of file routing.h.

GetNumberOfDecisionsInFirstSolution()

int64_t operations_research::RoutingModel::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 3980 of file routing.cc.

GetNumberOfDisjunctions()

int operations_research::RoutingModel::GetNumberOfDisjunctions ( ) const

inline

Returns the number of node disjunctions in the model.

Definition at line 965 of file routing.h.

GetNumberOfRejectsInFirstSolution()

int64_t operations_research::RoutingModel::GetNumberOfRejectsInFirstSolution

(

const RoutingSearchParameters &

search_parameters

)

const

Definition at line 3988 of file routing.cc.

GetNumberOfSoftSameVehicleConstraints()

int operations_research::RoutingModel::GetNumberOfSoftSameVehicleConstraints ( ) const

inline

Returns the number of soft same vehicle constraints in the model.

Definition at line 991 of file routing.h.

GetNumberOfVisitTypes()

int operations_research::RoutingModel::GetNumberOfVisitTypes ( ) const

inline

Definition at line 1138 of file routing.h.

GetNumOfSingletonNodes()

int operations_research::RoutingModel::GetNumOfSingletonNodes

(

)

const

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

Definition at line 2168 of file routing.cc.

GetOrCreateNodeNeighborsByCostClass() [1/2]

const RoutingModel::NodeNeighborsByCostClass * operations_research::RoutingModel::GetOrCreateNodeNeighborsByCostClass

(

const NodeNeighborsParameters &

params

)

Returns parameters.num_neighbors neighbors of all nodes for every cost class. The result is cached and is computed once.

Definition at line 482 of file routing.cc.

GetOrCreateNodeNeighborsByCostClass() [2/2]

const RoutingModel::NodeNeighborsByCostClass * operations_research::RoutingModel::GetOrCreateNodeNeighborsByCostClass	(	double	neighbors_ratio,
		int64_t	min_neighbors,
		double &	neighbors_ratio_used,
		bool	add_vehicle_starts_to_neighbors = true,
		bool	add_vehicle_ends_to_neighbors = false,
		bool	only_sort_neighbors_for_partial_neighborhoods = true )

Returns neighbors of all nodes for every cost class. The result is cached and is computed once. The number of neighbors considered is based on a ratio of non-vehicle nodes, specified by neighbors_ratio, with a minimum of min-neighbors node considered.

Definition at line 462 of file routing.cc.

GetOrderedActivityGroups()

const std::vector< std::vector< DisjunctionIndex > > & operations_research::RoutingModel::GetOrderedActivityGroups ( ) const

inline

Returns all ordered activity groups.

Definition at line 2010 of file routing.h.

GetPairIndicesOfType()

const std::vector< int > & operations_research::RoutingModel::GetPairIndicesOfType

(

int

type

)

const

Definition at line 4468 of file routing.cc.

GetPathsMetadata()

const PathsMetadata & operations_research::RoutingModel::GetPathsMetadata ( ) const

inline

Definition at line 2180 of file routing.h.

GetPerfectBinaryDisjunctions()

std::vector< std::pair< int64_t, int64_t > > operations_research::RoutingModel::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 1962 of file routing.cc.

GetPickupAndDeliveryDisjunctions()

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

inline

Definition at line 1080 of file routing.h.

GetPickupAndDeliveryPairs()

const std::vector< PickupDeliveryPair > & operations_research::RoutingModel::GetPickupAndDeliveryPairs ( ) const

inline

Returns pickup and delivery pairs currently in the model.

Definition at line 1076 of file routing.h.

GetPickupAndDeliveryPolicyOfVehicle()

RoutingModel::PickupAndDeliveryPolicy operations_research::RoutingModel::GetPickupAndDeliveryPolicyOfVehicle

(

int

vehicle

)

const

Definition at line 2127 of file routing.cc.

GetPickupPosition()

std::optional< RoutingModel::PickupDeliveryPosition > operations_research::RoutingModel::GetPickupPosition

(

int64_t

node_index

)

const

Returns the pickup and delivery positions where the node is a pickup.

Definition at line 2099 of file routing.cc.

GetPrimaryConstrainedDimension()

const std::string & operations_research::RoutingModel::GetPrimaryConstrainedDimension ( ) const

inline

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

Definition at line 861 of file routing.h.

GetRequiredTypeAlternativesWhenAddingType()

const std::vector< absl::flat_hash_set< int > > & operations_research::RoutingModel::GetRequiredTypeAlternativesWhenAddingType

(

int

type

)

const

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

Definition at line 4605 of file routing.cc.

GetRequiredTypeAlternativesWhenRemovingType()

const std::vector< absl::flat_hash_set< int > > & operations_research::RoutingModel::GetRequiredTypeAlternativesWhenRemovingType

(

int

type

)

const

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

Definition at line 4615 of file routing.cc.

GetResourceGroup()

ResourceGroup * operations_research::RoutingModel::GetResourceGroup ( int rg_index ) const

inline

Definition at line 873 of file routing.h.

GetResourceGroups()

const std::vector< std::unique_ptr< ResourceGroup > > & operations_research::RoutingModel::GetResourceGroups ( ) const

inline

Definition at line 868 of file routing.h.

GetRouteCost()

std::optional< int64_t > operations_research::RoutingModel::GetRouteCost ( const std::vector< int64_t > & route ) const

inline

Definition at line 1336 of file routing.h.

GetRoutesFromAssignment()

std::vector< std::vector< int64_t > > operations_research::RoutingModel::GetRoutesFromAssignment

(

const operations_research::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 4196 of file routing.cc.

GetSameActivityGroupOfIndex()

int operations_research::RoutingModel::GetSameActivityGroupOfIndex ( int node ) const

inline

Returns the same activity group of the node.

Definition at line 1982 of file routing.h.

GetSameActivityGroups()

const std::vector< int > & operations_research::RoutingModel::GetSameActivityGroups ( ) const

inline

Returns same activity groups of all nodes.

Definition at line 1987 of file routing.h.

GetSameActivityGroupsCount()

int operations_research::RoutingModel::GetSameActivityGroupsCount ( ) const

inline

Returns the number of same activity groups.

Definition at line 1992 of file routing.h.

GetSameActivityIndicesOfGroup()

const std::vector< int > & operations_research::RoutingModel::GetSameActivityIndicesOfGroup ( int group ) const

inline

Returns variable indices of nodes in the same activity group.

Definition at line 1997 of file routing.h.

GetSameActivityIndicesOfIndex()

const std::vector< int > & operations_research::RoutingModel::GetSameActivityIndicesOfIndex ( int node ) const

inline

Returns variable indices of nodes constrained to have the same activity.

Definition at line 1977 of file routing.h.

GetSameVehicleClassArcs()

std::vector< std::pair< int64_t, int64_t > > operations_research::RoutingModel::GetSameVehicleClassArcs	(	int64_t	from_index,
		int64_t	to_index ) const

Returns all arcs which are equivalent to the {from_index, to_index} arc wrt vehicle classes. Arcs will be returned only if from_index is the start of a vehicle or if to_index is the end of a vehicle. The returned arcs will then be starting or ending at start or end nodes of vehicles in the same vehicle class. The input arc is included in the returned vector.

Definition at line 2301 of file routing.cc.

GetSameVehicleIndicesOfIndex()

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

inline

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

Definition at line 1964 of file routing.h.

GetSameVehicleRequiredTypeAlternativesOfType()

const std::vector< absl::flat_hash_set< int > > & operations_research::RoutingModel::GetSameVehicleRequiredTypeAlternativesOfType

(

int

type

)

const

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

Definition at line 4595 of file routing.cc.

GetSearchMonitors()

const std::vector< SearchMonitor * > & operations_research::RoutingModel::GetSearchMonitors ( ) const

inline

Definition at line 2160 of file routing.h.

GetSingleNodesOfType()

const std::vector< int > & operations_research::RoutingModel::GetSingleNodesOfType

(

int

type

)

const

Definition at line 4463 of file routing.cc.

GetSoftSameVehicleCost()

int64_t operations_research::RoutingModel::GetSoftSameVehicleCost ( int index ) const

inline

Returns the cost of the soft same vehicle constraint of index 'index'.

Definition at line 1000 of file routing.h.

GetSoftSameVehicleIndices()

const std::vector< int64_t > & operations_research::RoutingModel::GetSoftSameVehicleIndices ( int index ) const

inline

Returns the indices of the nodes in the soft same vehicle constraint of index 'index'.

Definition at line 996 of file routing.h.

GetSubSolverStatistics()

SubSolverStatistics operations_research::RoutingModel::GetSubSolverStatistics

(

)

const

Returns detailed search statistics.

Definition at line 3697 of file routing.cc.

GetTemporalTypeIncompatibilitiesOfType()

const absl::flat_hash_set< int > & operations_research::RoutingModel::GetTemporalTypeIncompatibilitiesOfType

(

int

type

)

const

Definition at line 4510 of file routing.cc.

GetTopologicallySortedNodePrecedences()

const std::vector< std::vector< std::vector< int > > > & operations_research::RoutingModel::GetTopologicallySortedNodePrecedences ( ) const

inline

Definition at line 1146 of file routing.h.

GetTopologicallySortedVisitTypes()

const std::vector< std::vector< int > > & operations_research::RoutingModel::GetTopologicallySortedVisitTypes ( ) const

inline

Definition at line 1140 of file routing.h.

GetUnaryDimensions()

std::vector< RoutingDimension * > operations_research::RoutingModel::GetUnaryDimensions

(

)

const

Returns dimensions for which all transit evaluators are unary.

Definition at line 5783 of file routing.cc.

GetVehicleClassesCount()

int operations_research::RoutingModel::GetVehicleClassesCount ( ) const

inline

Returns the number of different vehicle classes in the model.

Definition at line 1962 of file routing.h.

GetVehicleClassIndexOfVehicle()

VehicleClassIndex operations_research::RoutingModel::GetVehicleClassIndexOfVehicle ( int64_t vehicle ) const

inline

Definition at line 1942 of file routing.h.

GetVehicleOfClass()

int operations_research::RoutingModel::GetVehicleOfClass ( VehicleClassIndex vehicle_class ) const

inline

Returns a vehicle of the given vehicle class, and -1 if there are no vehicles for this class.

Definition at line 1948 of file routing.h.

GetVehiclesOfSameClass()

const std::deque< int > & operations_research::RoutingModel::GetVehiclesOfSameClass

(

int64_t

start_end_index

)

const

Returns indices of the vehicles which are in the same vehicle class as the vehicle starting or ending at start_end_index.

Definition at line 2293 of file routing.cc.

GetVehicleTypeContainer()

const VehicleTypeContainer & operations_research::RoutingModel::GetVehicleTypeContainer ( ) const

inline

Definition at line 2015 of file routing.h.

GetVisitType()

int operations_research::RoutingModel::GetVisitType

(

int64_t

index

)

const

Definition at line 4458 of file routing.cc.

GetVisitTypeComponents()

const std::vector< std::vector< int > > & operations_research::RoutingModel::GetVisitTypeComponents ( ) const

inline

Definition at line 1134 of file routing.h.

GetVisitTypePolicy()

RoutingModel::VisitTypePolicy operations_research::RoutingModel::GetVisitTypePolicy

(

int64_t

index

)

const

Definition at line 4473 of file routing.cc.

HasDimension()

bool operations_research::RoutingModel::HasDimension

(

absl::string_view

dimension_name

)

const

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

Definition at line 1077 of file routing.cc.

HasGlobalCumulOptimizer()

bool operations_research::RoutingModel::HasGlobalCumulOptimizer ( const RoutingDimension & dimension ) const

inline

Returns whether the given dimension has global/local cumul optimizers.

Definition at line 826 of file routing.h.

HasHardTypeIncompatibilities()

bool operations_research::RoutingModel::HasHardTypeIncompatibilities ( ) const

inline

Returns true iff any hard (resp. temporal) type incompatibilities have been added to the model.

Definition at line 1167 of file routing.h.

HasLocalCumulOptimizer()

bool operations_research::RoutingModel::HasLocalCumulOptimizer ( const RoutingDimension & dimension ) const

inline

Definition at line 829 of file routing.h.

HasMandatoryDisjunctions()

bool operations_research::RoutingModel::HasMandatoryDisjunctions

(

)

const

Returns true if the model contains mandatory disjunctions (ones with kNoPenalty as penalty).

Definition at line 1947 of file routing.cc.

HasMaxCardinalityConstrainedDisjunctions()

bool operations_research::RoutingModel::HasMaxCardinalityConstrainedDisjunctions

(

)

const

Returns true if the model contains at least one disjunction which is constrained by its max_cardinality.

Definition at line 1954 of file routing.cc.

HasSameVehicleTypeRequirements()

bool operations_research::RoutingModel::HasSameVehicleTypeRequirements ( ) const

inline

Returns true iff any same-route (resp. temporal) type requirements have been added to the model.

Definition at line 1216 of file routing.h.

HasTemporalTypeIncompatibilities()

bool operations_research::RoutingModel::HasTemporalTypeIncompatibilities ( ) const

inline

Definition at line 1170 of file routing.h.

HasTemporalTypeRequirements()

bool operations_research::RoutingModel::HasTemporalTypeRequirements ( ) const

inline

Definition at line 1219 of file routing.h.

HasTypeRegulations()

bool operations_research::RoutingModel::HasTypeRegulations ( ) const

inline

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

Definition at line 1226 of file routing.h.

HasVehicleWithCostClassIndex()

bool operations_research::RoutingModel::HasVehicleWithCostClassIndex ( CostClassIndex cost_class_index ) const

inline

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

Definition at line 1929 of file routing.h.

IgnoreDisjunctionsAlreadyForcedToZero()

void operations_research::RoutingModel::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 1979 of file routing.cc.

IsDelivery()

bool operations_research::RoutingModel::IsDelivery ( int64_t node_index ) const

inline

Definition at line 1058 of file routing.h.

IsEnd()

bool operations_research::RoutingModel::IsEnd ( int64_t index ) const

inline

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

Definition at line 1823 of file routing.h.

IsMatchingModel()

bool operations_research::RoutingModel::IsMatchingModel

(

)

const

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

Definition at line 52 of file routing_flow.cc.

IsPickup()

bool operations_research::RoutingModel::IsPickup ( int64_t node_index ) const

inline

Returns whether the node is a pickup (resp. delivery).

Definition at line 1055 of file routing.h.

IsStart()

bool operations_research::RoutingModel::IsStart ( int64_t index ) const

inline

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

Definition at line 1821 of file routing.h.

IsVehicleAllowedForIndex()

bool operations_research::RoutingModel::IsVehicleAllowedForIndex ( int vehicle, int64_t index ) const

inline

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

Definition at line 1012 of file routing.h.

IsVehicleUsed()

bool operations_research::RoutingModel::IsVehicleUsed	(	const operations_research::Assignment &	assignment,
		int	vehicle ) const

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

Definition at line 4280 of file routing.cc.

IsVehicleUsedWhenEmpty()

bool operations_research::RoutingModel::IsVehicleUsedWhenEmpty ( int vehicle ) const

inline

Definition at line 1351 of file routing.h.

MakeGreedyDescentLSOperator()

std::unique_ptr< LocalSearchOperator > operations_research::RoutingModel::MakeGreedyDescentLSOperator ( std::vector< operations_research::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 5754 of file routing_search.cc.

MakeGuidedSlackFinalizer()

DecisionBuilder * operations_research::RoutingModel::MakeGuidedSlackFinalizer	(	const RoutingDimension *	dimension,
		std::function< int64_t(int64_t)>	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 5625 of file routing_search.cc.

MakeSelfDependentDimensionFinalizer()

DecisionBuilder * operations_research::RoutingModel::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 5760 of file routing_search.cc.

MakeStateDependentTransit()

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

static

Creates a cached StateDependentTransit from an std::function.

Definition at line 998 of file routing.cc.

MutablePreAssignment()

operations_research::Assignment * operations_research::RoutingModel::MutablePreAssignment ( )

inline

Definition at line 1528 of file routing.h.

Next()

int64_t operations_research::RoutingModel::Next	(	const operations_research::Assignment &	assignment,
		int64_t	index ) const

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

Definition at line 4290 of file routing.cc.

Nexts()

const std::vector< operations_research::IntVar * > & operations_research::RoutingModel::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 1841 of file routing.h.

NextVar()

operations_research::IntVar * operations_research::RoutingModel::NextVar ( int64_t 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 1859 of file routing.h.

nodes()

int operations_research::RoutingModel::nodes ( ) const

inline

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

Definition at line 2100 of file routing.h.

objective_lower_bound()

int64_t operations_research::RoutingModel::objective_lower_bound ( ) const

inline

Returns the current lower bound found by internal solvers during the search.

Definition at line 1494 of file routing.h.

operator=()

RoutingModel & operations_research::RoutingModel::operator= ( const RoutingModel & )

delete

PackCumulsOfOptimizerDimensionsFromAssignment()

const Assignment * operations_research::RoutingModel::PackCumulsOfOptimizerDimensionsFromAssignment	(	const operations_research::Assignment *	original_assignment,
		absl::Duration	duration_limit,
		bool *	time_limit_was_reached = nullptr )

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

PreAssignment()

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

Definition at line 1525 of file routing.h.

ReadAssignment()

Assignment * operations_research::RoutingModel::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 4005 of file routing.cc.

ReadAssignmentFromRoutes()

Assignment * operations_research::RoutingModel::ReadAssignmentFromRoutes	(	const std::vector< std::vector< int64_t > > &	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 4149 of file routing.cc.

RegisterCumulDependentTransitCallback()

int operations_research::RoutingModel::RegisterCumulDependentTransitCallback

(

CumulDependentTransitCallback2

callback

)

Definition at line 730 of file routing.cc.

RegisterStateDependentTransitCallback()

int operations_research::RoutingModel::RegisterStateDependentTransitCallback

(

VariableIndexEvaluator2

callback

)

Definition at line 713 of file routing.cc.

RegisterTransitCallback()

int operations_research::RoutingModel::RegisterTransitCallback	(	TransitCallback2	callback,
		TransitEvaluatorSign	sign = kTransitEvaluatorSignUnknown )

Definition at line 676 of file routing.cc.

RegisterTransitMatrix()

int operations_research::RoutingModel::RegisterTransitMatrix

(

std::vector< std::vector< int64_t > >

values

)

Definition at line 650 of file routing.cc.

RegisterUnaryTransitCallback()

int operations_research::RoutingModel::RegisterUnaryTransitCallback	(	TransitCallback1	callback,
		TransitEvaluatorSign	sign = kTransitEvaluatorSignUnknown )

Definition at line 639 of file routing.cc.

RegisterUnaryTransitVector()

int operations_research::RoutingModel::RegisterUnaryTransitVector

(

std::vector< int64_t >

values

)

Registers 'callback' and returns its index. The sign parameter allows to notify the solver that the callback only return values of the given sign. This can help the solver, but passing an incorrect sign may crash in non-opt compilation mode, and yield incorrect results in opt.

Definition at line 623 of file routing.cc.

RemainingTime()

absl::Duration operations_research::RoutingModel::RemainingTime ( ) const

inline

Returns the time left in the search limit.

Definition at line 2072 of file routing.h.

ResourceVar()

operations_research::IntVar * operations_research::RoutingModel::ResourceVar ( int vehicle, int resource_group ) const

inline

Returns the resource variable for the given vehicle index in the given resource group. If a vehicle doesn't require a resource from the corresponding resource group, then ResourceVar(v, r_g) == -1.

Definition at line 1885 of file routing.h.

ResourceVars()

const std::vector< operations_research::IntVar * > & operations_research::RoutingModel::ResourceVars ( int resource_group ) const

inline

Returns vehicle resource variables for a given resource group, such that ResourceVars(r_g)[v] is the resource variable for vehicle 'v' in resource group 'r_g'.

Definition at line 1852 of file routing.h.

RestoreAssignment()

Assignment * operations_research::RoutingModel::RestoreAssignment

(

const operations_research::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 4014 of file routing.cc.

RoutesToAssignment()

bool operations_research::RoutingModel::RoutesToAssignment	(	const std::vector< std::vector< int64_t > > &	routes,
		bool	ignore_inactive_indices,
		bool	close_routes,
		operations_research::Assignment *	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 4036 of file routing.cc.

search_stats()

const RoutingSearchStats & operations_research::RoutingModel::search_stats ( ) const

inline

Returns search statistics.

Definition at line 1498 of file routing.h.

SetAllowedVehiclesForIndex()

void operations_research::RoutingModel::SetAllowedVehiclesForIndex	(	absl::Span< const int >	vehicles,
		int64_t	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 2045 of file routing.cc.

SetAmortizedCostFactorsOfAllVehicles()

void operations_research::RoutingModel::SetAmortizedCostFactorsOfAllVehicles	(	int64_t	linear_cost_factor,
		int64_t	quadratic_cost_factor )

Sets the linear and quadratic cost factor of all vehicles.

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.

Definition at line 1355 of file routing.cc.

SetAmortizedCostFactorsOfVehicle()

void operations_research::RoutingModel::SetAmortizedCostFactorsOfVehicle	(	int64_t	linear_cost_factor,
		int64_t	quadratic_cost_factor,
		int	vehicle )

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

Definition at line 1363 of file routing.cc.

SetArcCostEvaluatorOfAllVehicles()

void operations_research::RoutingModel::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 1290 of file routing.cc.

SetArcCostEvaluatorOfVehicle()

void operations_research::RoutingModel::SetArcCostEvaluatorOfVehicle	(	int	evaluator_index,
		int	vehicle )

Sets the cost function for a given vehicle route.

Definition at line 1297 of file routing.cc.

SetAssignmentFromOtherModelAssignment()

void operations_research::RoutingModel::SetAssignmentFromOtherModelAssignment	(	operations_research::Assignment *	target_assignment,
		const RoutingModel *	source_model,
		const operations_research::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 3669 of file routing.cc.

SetFirstSolutionEvaluator()

void operations_research::RoutingModel::SetFirstSolutionEvaluator ( Solver::IndexEvaluator2 evaluator )

inline

Takes ownership of evaluator.

Definition at line 1364 of file routing.h.

SetFirstSolutionHint()

void operations_research::RoutingModel::SetFirstSolutionHint ( const operations_research::Assignment * hint )

inline

Adds a hint to be used by first solution strategies. The hint assignment must outlive the search. As of 2024-12, only used by LOCAL_CHEAPEST_INSERTION and LOCAL_CHEAPEST_COST_INSERTION.

Definition at line 1371 of file routing.h.

SetFixedCostOfAllVehicles()

void operations_research::RoutingModel::SetFixedCostOfAllVehicles

(

int64_t

cost

)

Sets the fixed cost of all vehicle routes. It is equivalent to calling SetFixedCostOfVehicle on all vehicle routes.

Definition at line 1304 of file routing.cc.

SetFixedCostOfVehicle()

void operations_research::RoutingModel::SetFixedCostOfVehicle	(	int64_t	cost,
		int	vehicle )

Sets the fixed cost of one vehicle route.

Definition at line 1315 of file routing.cc.

SetMaximumNumberOfActiveVehicles()

void operations_research::RoutingModel::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 1251 of file routing.h.

SetPathEnergyCostOfVehicle()

void operations_research::RoutingModel::SetPathEnergyCostOfVehicle	(	const std::string &	force,
		const std::string &	distance,
		int64_t	cost_per_unit,
		int	vehicle )

Definition at line 1321 of file routing.cc.

SetPathEnergyCostsOfVehicle()

void operations_research::RoutingModel::SetPathEnergyCostsOfVehicle	(	const std::string &	force,
		const std::string &	distance,
		int64_t	threshold,
		int64_t	cost_per_unit_below_threshold,
		int64_t	cost_per_unit_above_threshold,
		int	vehicle )

Definition at line 1331 of file routing.cc.

SetPickupAndDeliveryPolicyOfAllVehicles()

void operations_research::RoutingModel::SetPickupAndDeliveryPolicyOfAllVehicles

(

PickupAndDeliveryPolicy

policy

)

Sets the Pickup and delivery policy of all vehicles. It is equivalent to calling SetPickupAndDeliveryPolicyOfVehicle on all vehicles.

Definition at line 2118 of file routing.cc.

SetPickupAndDeliveryPolicyOfVehicle()

void operations_research::RoutingModel::SetPickupAndDeliveryPolicyOfVehicle	(	PickupAndDeliveryPolicy	policy,
		int	vehicle )

Definition at line 2112 of file routing.cc.

SetPrimaryConstrainedDimension()

void operations_research::RoutingModel::SetPrimaryConstrainedDimension ( absl::string_view 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 856 of file routing.h.

SetSecondaryModel()

void operations_research::RoutingModel::SetSecondaryModel ( RoutingModel * secondary_model, RoutingSearchParameters secondary_parameters )

inline

Sets a secondary solver (routing model + parameters) which can be used to run sub-solves while building a first solution.

Definition at line 2186 of file routing.h.

SetSweepArranger()

void operations_research::RoutingModel::SetSweepArranger

(

SweepArranger *

sweep_arranger

)

Definition at line 207 of file routing.cc.

SetTabuVarsCallback()

void operations_research::RoutingModel::SetTabuVarsCallback

(

GetTabuVarsCallback

tabu_var_callback

)

Definition at line 6438 of file routing.cc.

SetVehicleUsedWhenEmpty()

void operations_research::RoutingModel::SetVehicleUsedWhenEmpty ( bool is_used, int vehicle )

inline

Definition at line 1346 of file routing.h.

SetVisitType()

void operations_research::RoutingModel::SetVisitType	(	int64_t	index,
		int	type,
		VisitTypePolicy	type_policy )

Definition at line 4449 of file routing.cc.

Size()

int64_t operations_research::RoutingModel::Size ( ) const

inline

Returns the number of next variables in the model.

Definition at line 2104 of file routing.h.

Solve()

const Assignment * operations_research::RoutingModel::Solve

(

const operations_research::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 3169 of file routing.cc.

SolveFromAssignmentsWithParameters()

const Assignment * operations_research::RoutingModel::SolveFromAssignmentsWithParameters	(	const std::vector< const operations_research::Assignment * > &	assignments,
		const RoutingSearchParameters &	search_parameters,
		std::vector< const operations_research::Assignment * > *	solutions = nullptr )

Same as above but will try all assignments in order as first solutions until one succeeds.

Definition at line 3300 of file routing.cc.

SolveFromAssignmentWithParameters()

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

Same as above, except that if assignment is not null, it will be used as the initial solution.

Definition at line 3244 of file routing.cc.

solver()

Solver * operations_research::RoutingModel::solver ( ) const

inline

Returns the underlying constraint solver. Can be used to add extra constraints and/or modify search algorithms.

Definition at line 2062 of file routing.h.

SolveWithIteratedLocalSearch()

const Assignment * operations_research::RoutingModel::SolveWithIteratedLocalSearch

(

const RoutingSearchParameters &

search_parameters

)

Solves the current routing model by using an Iterated Local Search approach.

Definition at line 3542 of file routing.cc.

SolveWithParameters()

const Assignment * operations_research::RoutingModel::SolveWithParameters	(	const RoutingSearchParameters &	search_parameters,
		std::vector< const operations_research::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 3174 of file routing.cc.

Start()

int64_t operations_research::RoutingModel::Start ( int vehicle ) const

inline

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

Definition at line 1817 of file routing.h.

StateDependentTransitCallback()

const VariableIndexEvaluator2 & operations_research::RoutingModel::StateDependentTransitCallback ( int callback_index ) const

inline

Definition at line 674 of file routing.h.

status()

RoutingSearchStatus::Value operations_research::RoutingModel::status ( ) const

inline

Returns the current status of the routing model.

Definition at line 1496 of file routing.h.

sweep_arranger()

SweepArranger * operations_research::RoutingModel::sweep_arranger

(

)

const

Returns the sweep arranger to be used by routing heuristics.

Definition at line 211 of file routing.cc.

TimeBuffer()

absl::Duration operations_research::RoutingModel::TimeBuffer ( ) const

inline

Returns the time buffer to safely return a solution.

Definition at line 2086 of file routing.h.

TransitCallback()

const TransitCallback2 & operations_research::RoutingModel::TransitCallback ( int callback_index ) const

inline

Definition at line 661 of file routing.h.

UnaryTransitCallbackOrNull()

const TransitCallback1 & operations_research::RoutingModel::UnaryTransitCallbackOrNull ( int callback_index ) const

inline

Definition at line 665 of file routing.h.

UnperformedPenalty()

int64_t operations_research::RoutingModel::UnperformedPenalty

(

int64_t

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, and that disjunction has a penalty. For forced active nodes returns max int64_t. In all other cases, this returns 0.

Definition at line 4624 of file routing.cc.

UnperformedPenaltyOrValue()

int64_t operations_research::RoutingModel::UnperformedPenaltyOrValue	(	int64_t	default_value,
		int64_t	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 4628 of file routing.cc.

UpdateTimeLimit()

void operations_research::RoutingModel::UpdateTimeLimit ( absl::Duration time_limit )

inline

Updates the time limit of the search limit.

Definition at line 2078 of file routing.h.

VehicleIndex()

int operations_research::RoutingModel::VehicleIndex ( int64_t 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 1826 of file routing.h.

VehicleRouteConsideredVar()

operations_research::IntVar * operations_research::RoutingModel::VehicleRouteConsideredVar ( int vehicle ) const

inline

Returns the variable specifying whether or not the given vehicle route is considered for costs and constraints. It will be equal to 1 iff the route of the vehicle is not empty OR vehicle_used_when_empty_[vehicle] is true.

Definition at line 1874 of file routing.h.

vehicles()

int operations_research::RoutingModel::vehicles ( ) const

inline

Returns the number of vehicle routes in the model.

Definition at line 2102 of file routing.h.

VehicleVar()

operations_research::IntVar * operations_research::RoutingModel::VehicleVar ( int64_t 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 1879 of file routing.h.

VehicleVars()

const std::vector< operations_research::IntVar * > & operations_research::RoutingModel::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 1846 of file routing.h.

WriteAssignment()

bool operations_research::RoutingModel::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 3996 of file routing.cc.

Friends And Related Symbol Documentation

ResourceGroup::Resource

friend class ResourceGroup::Resource

friend

Definition at line 2858 of file routing.h.

RoutingDimension

friend class RoutingDimension

friend

Definition at line 2856 of file routing.h.

RoutingModelInspector

friend class RoutingModelInspector

friend

Definition at line 2857 of file routing.h.

Member Data Documentation

kNoDimension

const RoutingModel::DimensionIndex operations_research::RoutingModel::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 621 of file routing.h.

kNoDisjunction

const RoutingModel::DisjunctionIndex operations_research::RoutingModel::kNoDisjunction

static

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

Definition at line 617 of file routing.h.

kNoPenalty

const int64_t operations_research::RoutingModel::kNoPenalty = -1

static

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

Definition at line 613 of file routing.h.

---

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

• ortools/constraint_solver/routing.h
• ortools/constraint_solver/routing.cc
• ortools/constraint_solver/routing_flow.cc
• ortools/constraint_solver/routing_search.cc