The vehicle routing library lets one model and solve generic vehicle routing problems ranging from the Traveling Salesman Problem to more complex problems such as the Capacitated Vehicle Routing Problem with Time Windows. More...

Classes
class	ArgumentHolder
	Argument Holder: useful when visiting a model. More...

class	ArrayWithOffset

class	BaseIntExpr
	This is the base class for all expressions that are not variables. More...

class	BaseLns
	This is the base class for building an Lns operator. More...

class	BasePathFilter
	Generic path-based filter class. More...

class	BooleanVar

class	CallMethod0
	Demon proxy to a method on the constraint with no arguments. More...

class	CallMethod1
	Demon proxy to a method on the constraint with one argument. More...

class	CallMethod2
	Demon proxy to a method on the constraint with two arguments. More...

class	CallMethod3
	Demon proxy to a method on the constraint with three arguments. More...

class	ChangeValue
	Defines operators which change the value of variables; each neighbor corresponds to one modified variable. More...

class	CheapestAdditionFilteredHeuristic
	Filtered-base decision builder based on the addition heuristic, extending a path from its start node with the cheapest arc. More...

class	CheapestInsertionFilteredHeuristic

class	ChristofidesFilteredHeuristic
	Christofides addition heuristic. More...

class	ComparatorCheapestAdditionFilteredHeuristic
	A CheapestAdditionFilteredHeuristic where the notion of 'cheapest arc' comes from an arc comparator. More...

class	CPFeasibilityFilter
	This filter accepts deltas for which the assignment satisfies the constraints of the Solver. More...

class	CumulBoundsPropagator

class	DelayedCallMethod0
	Low-priority demon proxy to a method on the constraint with no arguments. More...

class	DelayedCallMethod1
	Low-priority demon proxy to a method on the constraint with one argument. More...

class	DelayedCallMethod2
	Low-priority demon proxy to a method on the constraint with two arguments. More...

class	DimensionCumulOptimizerCore

class	DisjunctivePropagator
	This class acts like a CP propagator: it takes a set of tasks given by their start/duration/end features, and reduces the range of possible values. More...

class	EvaluatorCheapestAdditionFilteredHeuristic
	A CheapestAdditionFilteredHeuristic where the notion of 'cheapest arc' comes from an arc evaluator. More...

class	ExchangeSubtrip

class	FilteredHeuristicExpensiveChainLNSOperator
	Similar to the move above, but instead of removing one route entirely, the destruction phase consists of removing all nodes on an "expensive" chain from a route. More...

class	FilteredHeuristicPathLNSOperator
	LNS-like operator based on a filtered first solution heuristic to rebuild the solution, after the destruction phase consisting of removing one route. More...

class	GlobalCheapestInsertionFilteredHeuristic
	Filter-based decision builder which builds a solution by inserting nodes at their cheapest position on any route; potentially several routes can be built in parallel. More...

class	GlobalDimensionCumulOptimizer

class	GlobalVehicleBreaksConstraint
	GlobalVehicleBreaksConstraint ensures breaks constraints are enforced on all vehicles in the dimension passed to its constructor. More...

class	IndexPairSwapActiveOperator
	Operator which inserts inactive nodes into a path and makes a pair of active nodes inactive. More...

class	IntVarFilteredDecisionBuilder
	Decision builder building a solution using heuristics with local search filters to evaluate its feasibility. More...

class	IntVarFilteredHeuristic
	Generic filter-based heuristic applied to IntVars. More...

class	IntVarLocalSearchFilter

class	IntVarLocalSearchHandler

class	IntVarLocalSearchOperator
	Specialization of LocalSearchOperator built from an array of IntVars which specifies the scope of the operator. More...

class	LightPairRelocateOperator

class	LocalCheapestInsertionFilteredHeuristic
	Filter-base decision builder which builds a solution by inserting nodes at their cheapest position. More...

class	LocalDimensionCumulOptimizer

class	LocalSearchFilter
	Local Search Filters are used for fast neighbor pruning. More...

class	LocalSearchFilterManager
	Filter manager: when a move is made, filters are executed to decide whether the solution is feasible and compute parts of the new cost. More...

class	LocalSearchMonitor

class	LocalSearchOperator
	The base class for all local search operators. More...

class	LocalSearchState

class	LocalSearchVariable

class	MakePairActiveOperator
	Pair-based neighborhood operators, designed to move nodes by pairs (pairs are static and given). More...

class	MakePairInactiveOperator
	Operator which makes pairs of active nodes inactive. More...

class	MakeRelocateNeighborsOperator
	Relocate neighborhood which moves chains of neighbors. More...

class	ModelCache
	Implements a complete cache for model elements: expressions and constraints. More...

class	ModelParser
	Model Parser. More...

class	PairExchangeOperator
	Operator which exchanges the position of two pairs; for both pairs the first node of the pair must be before the second node on the same path. More...

class	PairExchangeRelocateOperator
	Operator which exchanges the paths of two pairs (path have to be different). More...

class	PairNodeSwapActiveOperator
	Operator which inserts pairs of inactive nodes into a path and makes an active node inactive. More...

class	PairRelocateOperator
	Operator which moves a pair of nodes to another position where the first node of the pair must be before the second node on the same path. More...

class	ParallelSavingsFilteredHeuristic

class	PathOperator
	Base class of the local search operators dedicated to path modifications (a path is a set of nodes linked together by arcs). More...

class	PathState

class	PropagationMonitor

class	PROTOBUF_FINAL

class	RelocateExpensiveChain
	RelocateExpensiveChain. More...

class	RelocateSubtrip
	Tries to move subtrips after an insertion node. More...

class	RevBitMatrix
	Matrix version of the RevBitSet class. More...

class	RevBitSet
	This class represents a reversible bitset. More...

class	RevGrowingArray
	This class is a reversible growing array. More...

class	RevImmutableMultiMap
	Reversible Immutable MultiMap class. More...

class	RevIntSet
	This is a special class to represent a 'residual' set of T. More...

class	RevPartialSequence
	--— RevPartialSequence --— More...

class	RevSwitch
	A reversible switch that can switch once from false to true. More...

class	RoutingCPSatWrapper

class	RoutingDimension
	Dimensions represent quantities accumulated at nodes along the routes. More...

class	RoutingFilteredHeuristic
	Filter-based heuristic dedicated to routing. More...

class	RoutingGlopWrapper

class	RoutingIndexManager
	Manager for any NodeIndex <-> variable index conversion. More...

class	RoutingLinearSolverWrapper

class	RoutingModel

class	RoutingModelVisitor
	Routing model visitor. More...

class	SavingsFilteredHeuristic
	Filter-based decision builder which builds a solution by using Clarke & Wright's Savings heuristic. More...

class	SearchLog
	The base class of all search logs that periodically outputs information when the search is running. More...

class	SequenceVarLocalSearchHandler

class	SequenceVarLocalSearchOperator

class	SequentialSavingsFilteredHeuristic

class	SimpleBoundCosts
	A structure meant to store soft bounds and associated violation constants. More...

class	SimpleRevFIFO
	This class represent a reversible FIFO structure. More...

class	SmallRevBitSet
	This class represents a small reversible bitset (size <= 64). More...

class	SwapIndexPairOperator
	Operator which iterates through each alternative of a set of pairs. More...

class	SweepArranger
	Class to arrange indices by by their distance and their angles from the depot. More...

class	SymmetryBreaker
	A symmetry breaker is an object that will visit a decision and create the 'symmetrical' decision in return. More...

class	TypeIncompatibilityChecker
	Checker for type incompatibilities. More...

class	TypeRegulationsChecker

class	TypeRegulationsConstraint
	The following constraint ensures that incompatibilities and requirements between types are respected. More...

class	TypeRequirementChecker
	Checker for type requirements. More...

class	UnaryDimensionChecker

class	UnsortedNullableRevBitset
	This class represents a reversible bitset. More...

class	VarLocalSearchOperator
	Base operator class for operators manipulating variables. More...

Typedefs
typedef VarLocalSearchOperator< SequenceVar, std::vector< int >, SequenceVarLocalSearchHandler >	SequenceVarLocalSearchOperatorTemplate

typedef std::function< int64(int64)>	RoutingTransitCallback1

typedef std::function< int64(int64, int64)>	RoutingTransitCallback2

typedef std::pair< std::vector< int64 >, std::vector< int64 > >	RoutingIndexPair

typedef std::vector< RoutingIndexPair >	RoutingIndexPairs

Enumerations
enum	VarTypes { UNSPECIFIED, DOMAIN_INT_VAR, BOOLEAN_VAR, CONST_VAR, VAR_ADD_CST, VAR_TIMES_CST, CST_SUB_VAR, OPP_VAR, TRACE_VAR }
	This enum is used internally to do dynamic typing on subclasses of integer variables. More...

enum	DimensionSchedulingStatus { OPTIMAL, RELAXED_OPTIMAL_ONLY, INFEASIBLE }

enum	FirstSolutionStrategy_Value : int { FirstSolutionStrategy_Value_UNSET = 0, FirstSolutionStrategy_Value_AUTOMATIC = 15, FirstSolutionStrategy_Value_PATH_CHEAPEST_ARC = 3, FirstSolutionStrategy_Value_PATH_MOST_CONSTRAINED_ARC = 4, FirstSolutionStrategy_Value_EVALUATOR_STRATEGY = 5, FirstSolutionStrategy_Value_SAVINGS = 10, FirstSolutionStrategy_Value_SWEEP = 11, FirstSolutionStrategy_Value_CHRISTOFIDES = 13, FirstSolutionStrategy_Value_ALL_UNPERFORMED = 6, FirstSolutionStrategy_Value_BEST_INSERTION = 7, FirstSolutionStrategy_Value_PARALLEL_CHEAPEST_INSERTION = 8, FirstSolutionStrategy_Value_SEQUENTIAL_CHEAPEST_INSERTION = 14, FirstSolutionStrategy_Value_LOCAL_CHEAPEST_INSERTION = 9, FirstSolutionStrategy_Value_GLOBAL_CHEAPEST_ARC = 1, FirstSolutionStrategy_Value_LOCAL_CHEAPEST_ARC = 2, FirstSolutionStrategy_Value_FIRST_UNBOUND_MIN_VALUE = 12, FirstSolutionStrategy_Value_FirstSolutionStrategy_Value_INT_MIN_SENTINEL_DO_NOT_USE_ = std::numeric_limits<::PROTOBUF_NAMESPACE_ID::int32>::min(), FirstSolutionStrategy_Value_FirstSolutionStrategy_Value_INT_MAX_SENTINEL_DO_NOT_USE_ = std::numeric_limits<::PROTOBUF_NAMESPACE_ID::int32>::max() }

enum	LocalSearchMetaheuristic_Value : int { LocalSearchMetaheuristic_Value_UNSET = 0, LocalSearchMetaheuristic_Value_AUTOMATIC = 6, LocalSearchMetaheuristic_Value_GREEDY_DESCENT = 1, LocalSearchMetaheuristic_Value_GUIDED_LOCAL_SEARCH = 2, LocalSearchMetaheuristic_Value_SIMULATED_ANNEALING = 3, LocalSearchMetaheuristic_Value_TABU_SEARCH = 4, LocalSearchMetaheuristic_Value_GENERIC_TABU_SEARCH = 5, LocalSearchMetaheuristic_Value_LocalSearchMetaheuristic_Value_INT_MIN_SENTINEL_DO_NOT_USE_ = std::numeric_limits<::PROTOBUF_NAMESPACE_ID::int32>::min(), LocalSearchMetaheuristic_Value_LocalSearchMetaheuristic_Value_INT_MAX_SENTINEL_DO_NOT_USE_ = std::numeric_limits<::PROTOBUF_NAMESPACE_ID::int32>::max() }

enum	RoutingSearchParameters_SchedulingSolver : int { RoutingSearchParameters_SchedulingSolver_UNSET = 0, RoutingSearchParameters_SchedulingSolver_GLOP = 1, RoutingSearchParameters_SchedulingSolver_CP_SAT = 2, RoutingSearchParameters_SchedulingSolver_RoutingSearchParameters_SchedulingSolver_INT_MIN_SENTINEL_DO_NOT_USE_ = std::numeric_limits<::PROTOBUF_NAMESPACE_ID::int32>::min(), RoutingSearchParameters_SchedulingSolver_RoutingSearchParameters_SchedulingSolver_INT_MAX_SENTINEL_DO_NOT_USE_ = std::numeric_limits<::PROTOBUF_NAMESPACE_ID::int32>::max() }

enum	ConstraintSolverParameters_TrailCompression : int { ConstraintSolverParameters_TrailCompression_NO_COMPRESSION = 0, ConstraintSolverParameters_TrailCompression_COMPRESS_WITH_ZLIB = 1, ConstraintSolverParameters_TrailCompression_ConstraintSolverParameters_TrailCompression_INT_MIN_SENTINEL_DO_NOT_USE_ = std::numeric_limits<::PROTOBUF_NAMESPACE_ID::int32>::min(), ConstraintSolverParameters_TrailCompression_ConstraintSolverParameters_TrailCompression_INT_MAX_SENTINEL_DO_NOT_USE_ = std::numeric_limits<::PROTOBUF_NAMESPACE_ID::int32>::max() }

Functions
uint64	Hash1 (uint64 value)
	Hash functions. More...

uint64	Hash1 (uint32 value)

uint64	Hash1 (int64 value)

uint64	Hash1 (int value)

uint64	Hash1 (void *const ptr)

template<class T >
uint64	Hash1 (const std::vector< T * > &ptrs)

uint64	Hash1 (const std::vector< int64 > &ptrs)

template<class T >
LocalSearchOperator *	MakeLocalSearchOperator (Solver solver, const std::vector< IntVar > &vars, const std::vector< IntVar * > &secondary_vars, std::function< int(int64)> start_empty_path_class)
	Operator Factories. More...

template<class T >
bool	IsArrayConstant (const std::vector< T > &values, const T &value)

template<class T >
bool	IsArrayBoolean (const std::vector< T > &values)

template<class T >
bool	AreAllOnes (const std::vector< T > &values)

template<class T >
bool	AreAllNull (const std::vector< T > &values)

template<class T >
bool	AreAllGreaterOrEqual (const std::vector< T > &values, const T &value)

template<class T >
bool	AreAllLessOrEqual (const std::vector< T > &values, const T &value)

template<class T >
bool	AreAllPositive (const std::vector< T > &values)

template<class T >
bool	AreAllNegative (const std::vector< T > &values)

template<class T >
bool	AreAllStrictlyPositive (const std::vector< T > &values)

template<class T >
bool	AreAllStrictlyNegative (const std::vector< T > &values)

template<class T >
bool	IsIncreasingContiguous (const std::vector< T > &values)

template<class T >
bool	IsIncreasing (const std::vector< T > &values)

template<class T >
bool	IsArrayInRange (const std::vector< IntVar * > &vars, T range_min, T range_max)

bool	AreAllBound (const std::vector< IntVar * > &vars)

bool	AreAllBooleans (const std::vector< IntVar * > &vars)

template<class T >
bool	AreAllBoundOrNull (const std::vector< IntVar * > &vars, const std::vector< T > &values)
	Returns true if all the variables are assigned to a single value, or if their corresponding value is null. More...

bool	AreAllBoundTo (const std::vector< IntVar * > &vars, int64 value)
	Returns true if all variables are assigned to 'value'. More...

int64	MaxVarArray (const std::vector< IntVar * > &vars)

int64	MinVarArray (const std::vector< IntVar * > &vars)

void	FillValues (const std::vector< IntVar * > &vars, std::vector< int64 > *const values)

int64	PosIntDivUp (int64 e, int64 v)

int64	PosIntDivDown (int64 e, int64 v)

std::vector< int64 >	ToInt64Vector (const std::vector< int > &input)

LocalSearchFilter *	MakePathStateFilter (Solver solver, std::unique_ptr< PathState > path_state, const std::vector< IntVar > &nexts)

LocalSearchFilter *	MakeUnaryDimensionFilter (Solver *solver, std::unique_ptr< UnaryDimensionChecker > checker)

void	AppendTasksFromPath (const std::vector< int64 > &path, const std::vector< int64 > &min_travels, const std::vector< int64 > &max_travels, const std::vector< int64 > &pre_travels, const std::vector< int64 > &post_travels, const RoutingDimension &dimension, DisjunctivePropagator::Tasks *tasks)

void	AppendTasksFromIntervals (const std::vector< IntervalVar * > &intervals, DisjunctivePropagator::Tasks *tasks)

void	FillPathEvaluation (const std::vector< int64 > &path, const RoutingModel::TransitCallback2 &evaluator, std::vector< int64 > *values)

DecisionBuilder *	MakeSetValuesFromTargets (Solver solver, std::vector< IntVar > variables, std::vector< int64 > targets)
	A decision builder which tries to assign values to variables as close as possible to target values first. More...

bool	SolveModelWithSat (const RoutingModel &model, const RoutingSearchParameters &search_parameters, const Assignment initial_solution, Assignment solution)
	Attempts to solve the model using the cp-sat solver. More...

IntVarLocalSearchFilter *	MakeNodeDisjunctionFilter (const RoutingModel &routing_model)

IntVarLocalSearchFilter *	MakeVehicleAmortizedCostFilter (const RoutingModel &routing_model)

IntVarLocalSearchFilter *	MakeTypeRegulationsFilter (const RoutingModel &routing_model)

void	AppendDimensionCumulFilters (const std::vector< RoutingDimension * > &dimensions, const RoutingSearchParameters &parameters, bool filter_objective_cost, std::vector< LocalSearchFilter * > *filters)

IntVarLocalSearchFilter *	MakePathCumulFilter (const RoutingDimension &dimension, const RoutingSearchParameters &parameters, bool propagate_own_objective_value, bool filter_objective_cost)

IntVarLocalSearchFilter *	MakeCumulBoundsPropagatorFilter (const RoutingDimension &dimension)

IntVarLocalSearchFilter *	MakeGlobalLPCumulFilter (GlobalDimensionCumulOptimizer *optimizer, bool filter_objective_cost)

IntVarLocalSearchFilter *	MakePickupDeliveryFilter (const RoutingModel &routing_model, const RoutingModel::IndexPairs &pairs, const std::vector< RoutingModel::PickupAndDeliveryPolicy > &vehicle_policies)

IntVarLocalSearchFilter *	MakeVehicleVarFilter (const RoutingModel &routing_model)

IntVarLocalSearchFilter *	MakeVehicleBreaksFilter (const RoutingModel &routing_model, const RoutingDimension &dimension)

IntVarLocalSearchFilter *	MakeCPFeasibilityFilter (const RoutingModel *routing_model)

RoutingModelParameters	BuildModelParametersFromFlags ()
	Builds routing search parameters from flags. More...

RoutingSearchParameters	BuildSearchParametersFromFlags ()
	Builds routing search parameters from flags. More...

RoutingModelParameters	DefaultRoutingModelParameters ()

RoutingSearchParameters	DefaultRoutingSearchParameters ()

std::string	FindErrorInRoutingSearchParameters (const RoutingSearchParameters &search_parameters)
	Returns an empty std::string if the routing search parameters are valid, and a non-empty, human readable error description if they're not. More...

	DEFINE_INT_TYPE (RoutingNodeIndex, int)
	Defining common types used in the routing library outside the main RoutingModel class has several purposes: 1) It allows some small libraries to avoid a dependency on routing. More...

	DEFINE_INT_TYPE (RoutingCostClassIndex, int)

	DEFINE_INT_TYPE (RoutingDimensionIndex, int)

	DEFINE_INT_TYPE (RoutingDisjunctionIndex, int)

	DEFINE_INT_TYPE (RoutingVehicleClassIndex, int)

bool	FirstSolutionStrategy_Value_IsValid (int value)

const ::PROTOBUF_NAMESPACE_ID::EnumDescriptor *	FirstSolutionStrategy_Value_descriptor ()

template<typename T >
const std::string &	FirstSolutionStrategy_Value_Name (T enum_t_value)

bool	FirstSolutionStrategy_Value_Parse (const std::string &name, FirstSolutionStrategy_Value *value)

bool	LocalSearchMetaheuristic_Value_IsValid (int value)

const ::PROTOBUF_NAMESPACE_ID::EnumDescriptor *	LocalSearchMetaheuristic_Value_descriptor ()

template<typename T >
const std::string &	LocalSearchMetaheuristic_Value_Name (T enum_t_value)

bool	LocalSearchMetaheuristic_Value_Parse (const std::string &name, LocalSearchMetaheuristic_Value *value)

bool	RoutingSearchParameters_SchedulingSolver_IsValid (int value)

const ::PROTOBUF_NAMESPACE_ID::EnumDescriptor *	RoutingSearchParameters_SchedulingSolver_descriptor ()

template<typename T >
const std::string &	RoutingSearchParameters_SchedulingSolver_Name (T enum_t_value)

bool	RoutingSearchParameters_SchedulingSolver_Parse (const std::string &name, RoutingSearchParameters_SchedulingSolver *value)

bool	ConstraintSolverParameters_TrailCompression_IsValid (int value)

const ::PROTOBUF_NAMESPACE_ID::EnumDescriptor *	ConstraintSolverParameters_TrailCompression_descriptor ()

template<typename T >
const std::string &	ConstraintSolverParameters_TrailCompression_Name (T enum_t_value)

bool	ConstraintSolverParameters_TrailCompression_Parse (const std::string &name, ConstraintSolverParameters_TrailCompression *value)

Variables
AssignmentProtoDefaultTypeInternal	_AssignmentProto_default_instance_

IntVarAssignmentDefaultTypeInternal	_IntVarAssignment_default_instance_

IntervalVarAssignmentDefaultTypeInternal	_IntervalVarAssignment_default_instance_

SequenceVarAssignmentDefaultTypeInternal	_SequenceVarAssignment_default_instance_

WorkerInfoDefaultTypeInternal	_WorkerInfo_default_instance_

ConstraintRunsDefaultTypeInternal	_ConstraintRuns_default_instance_

DemonRunsDefaultTypeInternal	_DemonRuns_default_instance_

FirstSolutionStrategyDefaultTypeInternal	_FirstSolutionStrategy_default_instance_

LocalSearchMetaheuristicDefaultTypeInternal	_LocalSearchMetaheuristic_default_instance_

constexpr FirstSolutionStrategy_Value	FirstSolutionStrategy_Value_Value_MIN = FirstSolutionStrategy_Value_UNSET

constexpr FirstSolutionStrategy_Value	FirstSolutionStrategy_Value_Value_MAX = FirstSolutionStrategy_Value_AUTOMATIC

constexpr int	FirstSolutionStrategy_Value_Value_ARRAYSIZE = FirstSolutionStrategy_Value_Value_MAX + 1

constexpr LocalSearchMetaheuristic_Value	LocalSearchMetaheuristic_Value_Value_MIN = LocalSearchMetaheuristic_Value_UNSET

constexpr LocalSearchMetaheuristic_Value	LocalSearchMetaheuristic_Value_Value_MAX = LocalSearchMetaheuristic_Value_AUTOMATIC

constexpr int	LocalSearchMetaheuristic_Value_Value_ARRAYSIZE = LocalSearchMetaheuristic_Value_Value_MAX + 1

RoutingModelParametersDefaultTypeInternal	_RoutingModelParameters_default_instance_

RoutingSearchParametersDefaultTypeInternal	_RoutingSearchParameters_default_instance_

RoutingSearchParameters_LocalSearchNeighborhoodOperatorsDefaultTypeInternal	_RoutingSearchParameters_LocalSearchNeighborhoodOperators_default_instance_

constexpr RoutingSearchParameters_SchedulingSolver	RoutingSearchParameters_SchedulingSolver_SchedulingSolver_MIN = RoutingSearchParameters_SchedulingSolver_UNSET

constexpr RoutingSearchParameters_SchedulingSolver	RoutingSearchParameters_SchedulingSolver_SchedulingSolver_MAX = RoutingSearchParameters_SchedulingSolver_CP_SAT

constexpr int	RoutingSearchParameters_SchedulingSolver_SchedulingSolver_ARRAYSIZE = RoutingSearchParameters_SchedulingSolver_SchedulingSolver_MAX + 1

RegularLimitParametersDefaultTypeInternal	_RegularLimitParameters_default_instance_

ConstraintSolverParametersDefaultTypeInternal	_ConstraintSolverParameters_default_instance_

constexpr ConstraintSolverParameters_TrailCompression	ConstraintSolverParameters_TrailCompression_TrailCompression_MIN = ConstraintSolverParameters_TrailCompression_NO_COMPRESSION

constexpr ConstraintSolverParameters_TrailCompression	ConstraintSolverParameters_TrailCompression_TrailCompression_MAX = ConstraintSolverParameters_TrailCompression_COMPRESS_WITH_ZLIB

constexpr int	ConstraintSolverParameters_TrailCompression_TrailCompression_ARRAYSIZE = ConstraintSolverParameters_TrailCompression_TrailCompression_MAX + 1

Detailed Description

The vehicle routing library lets one model and solve generic vehicle routing problems ranging from the Traveling Salesman Problem to more complex problems such as the Capacitated Vehicle Routing Problem with Time Windows.

The objective of a vehicle routing problem is to build routes covering a set of nodes minimizing the overall cost of the routes (usually proportional to the sum of the lengths of each segment of the routes) while respecting some problem-specific constraints (such as the length of a route). A route is equivalent to a path connecting nodes, starting/ending at specific starting/ending nodes.

The term "vehicle routing" is historical and the category of problems solved is not limited to the routing of vehicles: any problem involving finding routes visiting a given number of nodes optimally falls under this category of problems, such as finding the optimal sequence in a playlist. The literature around vehicle routing problems is extremely dense but one can find some basic introductions in the following links:

The vehicle routing library is a vertical layer above the constraint programming library (ortools/constraint_programming:cp). One has access to all underlying constrained variables of the vehicle routing model which can therefore be enriched by adding any constraint available in the constraint programming library.

There are two sets of variables available:

path variables:
- "next(i)" variables representing the immediate successor of the node corresponding to i; use IndexToNode() to get the node corresponding to a "next" variable value; note that node indices are strongly typed integers (cf. ortools/base/int_type.h);
- "vehicle(i)" variables representing the vehicle route to which the node corresponding to i belongs;
- "active(i)" boolean variables, true if the node corresponding to i is visited and false if not; this can be false when nodes are either optional or part of a disjunction;
- The following relationships hold for all i: active(i) == 0 <=> next(i) == i <=> vehicle(i) == -1, next(i) == j => vehicle(j) == vehicle(i).
dimension variables, used when one is accumulating quantities along routes, such as weight or volume carried, distance or time:
- "cumul(i,d)" variables representing the quantity of dimension d when arriving at the node corresponding to i;
- "transit(i,d)" variables representing the quantity of dimension d added after visiting the node corresponding to i.
- The following relationship holds for all (i,d): next(i) == j => cumul(j,d) == cumul(i,d) + transit(i,d). Solving the vehicle routing problems is mainly done using approximate methods (namely local search, cf. http://en.wikipedia.org/wiki/Local_search_(optimization) ), potentially combined with exact techniques based on dynamic programming and exhaustive tree search. Advanced tips: Flags are available to tune the search used to solve routing problems. Here is a quick overview of the ones one might want to modify:
Limiting the search for solutions:
- routing_solution_limit (default: kint64max): stop the search after finding 'routing_solution_limit' improving solutions;
- routing_time_limit (default: kint64max): stop the search after 'routing_time_limit' milliseconds;
Customizing search:
- routing_first_solution (default: select the first node with an unbound successor and connect it to the first available node): selects the heuristic to build a first solution which will then be improved by local search; possible values are GlobalCheapestArc (iteratively connect two nodes which produce the cheapest route segment), LocalCheapestArc (select the first node with an unbound successor and connect it to the node which produces the cheapest route segment), PathCheapestArc (starting from a route "start" node, connect it to the node which produces the cheapest route segment, then extend the route by iterating on the last node added to the route).
- Local search neighborhoods:
  - routing_no_lns (default: false): forbids the use of Large Neighborhood Search (LNS); LNS can find good solutions but is usually very slow. Refer to the description of PATHLNS in the LocalSearchOperators enum in constraint_solver.h for more information.
  - routing_no_tsp (default: true): forbids the use of exact methods to solve "sub"-traveling salesman problems (TSPs) of the current model (such as sub-parts of a route, or one route in a multiple route problem). Uses dynamic programming to solve such TSPs with a maximum size (in number of nodes) up to cp_local_search_tsp_opt_size (flag with a default value of 13 nodes). It is not activated by default because it can slow down the search.
- Meta-heuristics: used to guide the search out of local minima found by local search. Note that, in general, a search with metaheuristics activated never stops, therefore one must specify a search limit. Several types of metaheuristics are provided:
  - routing_guided_local_search (default: false): activates guided local search (cf. http://en.wikipedia.org/wiki/Guided_Local_Search); this is generally the most efficient metaheuristic for vehicle routing;
  - routing_simulated_annealing (default: false): activates simulated annealing (cf. http://en.wikipedia.org/wiki/Simulated_annealing);
  - routing_tabu_search (default: false): activates tabu search (cf. http://en.wikipedia.org/wiki/Tabu_search).

Code sample: Here is a simple example solving a traveling salesman problem given a cost function callback (returns the cost of a route segment):

Define a custom distance/cost function from an index to another; in this example just returns the sum of the indices:

int64 MyDistance(int64 from, int64 to) { return from + to; }
Create a routing model for a given problem size (int number of nodes) and number of routes (here, 1):

RoutingIndexManager manager(...number of nodes..., 1); RoutingModel routing(manager);
Set the cost function by registering an std::function<int64(int64, int64)> in the model and passing its index as the vehicle cost.

const int cost = routing.RegisterTransitCallback(MyDistance); routing.SetArcCostEvaluatorOfAllVehicles(cost);
Find a solution using Solve(), returns a solution if any (owned by routing):

const Assignment* solution = routing.Solve(); CHECK(solution != nullptr);
Inspect the solution cost and route (only one route here):

LOG(INFO) << "Cost " << solution->ObjectiveValue(); const int route_number = 0; for (int64 node = routing.Start(route_number); !routing.IsEnd(node); node = solution->Value(routing.NextVar(node))) { LOG(INFO) << manager.IndexToNode(node); }

Keywords: Vehicle Routing, Traveling Salesman Problem, TSP, VRP, CVRPTW, PDP.

Typedef Documentation

◆ RoutingIndexPair

typedef std::pair<std::vector<int64>, std::vector<int64> > RoutingIndexPair

Definition at line 44 of file routing_types.h.

◆ RoutingIndexPairs

typedef std::vector<RoutingIndexPair> RoutingIndexPairs

Definition at line 45 of file routing_types.h.

◆ RoutingTransitCallback1

typedef std::function<int64(int64)> RoutingTransitCallback1

Definition at line 41 of file routing_types.h.

◆ RoutingTransitCallback2

typedef std::function<int64(int64, int64)> RoutingTransitCallback2

Definition at line 42 of file routing_types.h.

◆ SequenceVarLocalSearchOperatorTemplate

typedef VarLocalSearchOperator<SequenceVar, std::vector<int>, SequenceVarLocalSearchHandler> SequenceVarLocalSearchOperatorTemplate

Definition at line 1159 of file constraint_solveri.h.

Enumeration Type Documentation

◆ ConstraintSolverParameters_TrailCompression

enum ConstraintSolverParameters_TrailCompression : int

Enumerator
ConstraintSolverParameters_TrailCompression_NO_COMPRESSION
ConstraintSolverParameters_TrailCompression_COMPRESS_WITH_ZLIB
ConstraintSolverParameters_TrailCompression_ConstraintSolverParameters_TrailCompression_INT_MIN_SENTINEL_DO_NOT_USE_
ConstraintSolverParameters_TrailCompression_ConstraintSolverParameters_TrailCompression_INT_MAX_SENTINEL_DO_NOT_USE_

Definition at line 68 of file solver_parameters.pb.h.

◆ DimensionSchedulingStatus

enum DimensionSchedulingStatus

strong

Enumerator
OPTIMAL
RELAXED_OPTIMAL_ONLY
INFEASIBLE

Definition at line 124 of file routing_lp_scheduling.h.

◆ FirstSolutionStrategy_Value

enum FirstSolutionStrategy_Value : int

Enumerator
FirstSolutionStrategy_Value_UNSET
FirstSolutionStrategy_Value_AUTOMATIC
FirstSolutionStrategy_Value_PATH_CHEAPEST_ARC
FirstSolutionStrategy_Value_PATH_MOST_CONSTRAINED_ARC
FirstSolutionStrategy_Value_EVALUATOR_STRATEGY
FirstSolutionStrategy_Value_SAVINGS
FirstSolutionStrategy_Value_SWEEP
FirstSolutionStrategy_Value_CHRISTOFIDES
FirstSolutionStrategy_Value_ALL_UNPERFORMED
FirstSolutionStrategy_Value_BEST_INSERTION
FirstSolutionStrategy_Value_PARALLEL_CHEAPEST_INSERTION
FirstSolutionStrategy_Value_SEQUENTIAL_CHEAPEST_INSERTION
FirstSolutionStrategy_Value_LOCAL_CHEAPEST_INSERTION
FirstSolutionStrategy_Value_GLOBAL_CHEAPEST_ARC
FirstSolutionStrategy_Value_LOCAL_CHEAPEST_ARC
FirstSolutionStrategy_Value_FIRST_UNBOUND_MIN_VALUE
FirstSolutionStrategy_Value_FirstSolutionStrategy_Value_INT_MIN_SENTINEL_DO_NOT_USE_
FirstSolutionStrategy_Value_FirstSolutionStrategy_Value_INT_MAX_SENTINEL_DO_NOT_USE_

Definition at line 72 of file routing_enums.pb.h.

◆ LocalSearchMetaheuristic_Value

enum LocalSearchMetaheuristic_Value : int

Enumerator
LocalSearchMetaheuristic_Value_UNSET
LocalSearchMetaheuristic_Value_AUTOMATIC
LocalSearchMetaheuristic_Value_GREEDY_DESCENT
LocalSearchMetaheuristic_Value_GUIDED_LOCAL_SEARCH
LocalSearchMetaheuristic_Value_SIMULATED_ANNEALING
LocalSearchMetaheuristic_Value_TABU_SEARCH
LocalSearchMetaheuristic_Value_GENERIC_TABU_SEARCH
LocalSearchMetaheuristic_Value_LocalSearchMetaheuristic_Value_INT_MIN_SENTINEL_DO_NOT_USE_
LocalSearchMetaheuristic_Value_LocalSearchMetaheuristic_Value_INT_MAX_SENTINEL_DO_NOT_USE_

Definition at line 111 of file routing_enums.pb.h.

◆ RoutingSearchParameters_SchedulingSolver

enum RoutingSearchParameters_SchedulingSolver : int

Enumerator
RoutingSearchParameters_SchedulingSolver_UNSET
RoutingSearchParameters_SchedulingSolver_GLOP
RoutingSearchParameters_SchedulingSolver_CP_SAT
RoutingSearchParameters_SchedulingSolver_RoutingSearchParameters_SchedulingSolver_INT_MIN_SENTINEL_DO_NOT_USE_
RoutingSearchParameters_SchedulingSolver_RoutingSearchParameters_SchedulingSolver_INT_MAX_SENTINEL_DO_NOT_USE_

Definition at line 80 of file routing_parameters.pb.h.

◆ VarTypes

enum VarTypes

This enum is used internally to do dynamic typing on subclasses of integer variables.

Enumerator
UNSPECIFIED
DOMAIN_INT_VAR
BOOLEAN_VAR
CONST_VAR
VAR_ADD_CST
VAR_TIMES_CST
CST_SUB_VAR
OPP_VAR
TRACE_VAR

Definition at line 123 of file constraint_solveri.h.

Function Documentation

◆ AppendDimensionCumulFilters()

void operations_research::AppendDimensionCumulFilters	(	const std::vector< RoutingDimension * > &	dimensions,
		const RoutingSearchParameters &	parameters,
		bool	filter_objective_cost,
		std::vector< LocalSearchFilter * > *	filters
	)

◆ AppendTasksFromIntervals()

void operations_research::AppendTasksFromIntervals	(	const std::vector< IntervalVar * > &	intervals,
		DisjunctivePropagator::Tasks *	tasks
	)

◆ AppendTasksFromPath()

void operations_research::AppendTasksFromPath	(	const std::vector< int64 > &	path,
		const std::vector< int64 > &	min_travels,
		const std::vector< int64 > &	max_travels,
		const std::vector< int64 > &	pre_travels,
		const std::vector< int64 > &	post_travels,
		const RoutingDimension &	dimension,
		DisjunctivePropagator::Tasks *	tasks
	)

◆ AreAllBooleans()

bool operations_research::AreAllBooleans ( const std::vector< IntVar * > & vars )

inline

Definition at line 2919 of file constraint_solveri.h.

◆ AreAllBound()

bool operations_research::AreAllBound ( const std::vector< IntVar * > & vars )

inline

Definition at line 2910 of file constraint_solveri.h.

◆ AreAllBoundOrNull()

bool operations_research::AreAllBoundOrNull	(	const std::vector< IntVar * > &	vars,
		const std::vector< T > &	values
	)

Returns true if all the variables are assigned to a single value, or if their corresponding value is null.

Definition at line 2926 of file constraint_solveri.h.

◆ AreAllBoundTo()

bool operations_research::AreAllBoundTo	(	const std::vector< IntVar * > &	vars,
		int64	value
	)

inline

Returns true if all variables are assigned to 'value'.

Definition at line 2937 of file constraint_solveri.h.

◆ AreAllGreaterOrEqual()

bool operations_research::AreAllGreaterOrEqual	(	const std::vector< T > &	values,
		const T &	value
	)

Definition at line 2840 of file constraint_solveri.h.

◆ AreAllLessOrEqual()

bool operations_research::AreAllLessOrEqual	(	const std::vector< T > &	values,
		const T &	value
	)

Definition at line 2850 of file constraint_solveri.h.

◆ AreAllNegative()

bool operations_research::AreAllNegative ( const std::vector< T > & values )

Definition at line 2865 of file constraint_solveri.h.

◆ AreAllNull()

bool operations_research::AreAllNull ( const std::vector< T > & values )

Definition at line 2835 of file constraint_solveri.h.

◆ AreAllOnes()

bool operations_research::AreAllOnes ( const std::vector< T > & values )

Definition at line 2830 of file constraint_solveri.h.

◆ AreAllPositive()

bool operations_research::AreAllPositive ( const std::vector< T > & values )

Definition at line 2860 of file constraint_solveri.h.

◆ AreAllStrictlyNegative()

bool operations_research::AreAllStrictlyNegative ( const std::vector< T > & values )

Definition at line 2875 of file constraint_solveri.h.

◆ AreAllStrictlyPositive()

bool operations_research::AreAllStrictlyPositive ( const std::vector< T > & values )

Definition at line 2870 of file constraint_solveri.h.

◆ BuildModelParametersFromFlags()

RoutingModelParameters operations_research::BuildModelParametersFromFlags ( )

Builds routing search parameters from flags.

◆ BuildSearchParametersFromFlags()

RoutingSearchParameters operations_research::BuildSearchParametersFromFlags ( )

Builds routing search parameters from flags.

describe a valid set of routing search parameters.

◆ ConstraintSolverParameters_TrailCompression_descriptor()

const ::PROTOBUF_NAMESPACE_ID::EnumDescriptor* operations_research::ConstraintSolverParameters_TrailCompression_descriptor ( )

◆ ConstraintSolverParameters_TrailCompression_IsValid()

bool operations_research::ConstraintSolverParameters_TrailCompression_IsValid ( int value )

◆ ConstraintSolverParameters_TrailCompression_Name()

const std::string& operations_research::ConstraintSolverParameters_TrailCompression_Name ( T enum_t_value )

inline

Definition at line 81 of file solver_parameters.pb.h.

◆ ConstraintSolverParameters_TrailCompression_Parse()

bool operations_research::ConstraintSolverParameters_TrailCompression_Parse	(	const std::string &	name,
		ConstraintSolverParameters_TrailCompression *	value
	)

inline

Definition at line 88 of file solver_parameters.pb.h.

◆ DefaultRoutingModelParameters()

RoutingModelParameters operations_research::DefaultRoutingModelParameters ( )

◆ DefaultRoutingSearchParameters()

RoutingSearchParameters operations_research::DefaultRoutingSearchParameters ( )

◆ DEFINE_INT_TYPE() [1/5]

operations_research::DEFINE_INT_TYPE	(	RoutingCostClassIndex	,
		int
	)

◆ DEFINE_INT_TYPE() [2/5]

operations_research::DEFINE_INT_TYPE	(	RoutingDimensionIndex	,
		int
	)

◆ DEFINE_INT_TYPE() [3/5]

operations_research::DEFINE_INT_TYPE	(	RoutingDisjunctionIndex	,
		int
	)

◆ DEFINE_INT_TYPE() [4/5]

operations_research::DEFINE_INT_TYPE	(	RoutingNodeIndex	,
		int
	)

Defining common types used in the routing library outside the main RoutingModel class has several purposes: 1) It allows some small libraries to avoid a dependency on routing.

{h,cc}, eg. routing_neighborhoods.h. 2) It allows an easier wrapping via SWIG, which can have issues with intra-class types.

Users that depend on routing.{h,cc} should just use the RoutingModel:: equivalent, eg. RoutingModel::NodeIndex.

◆ DEFINE_INT_TYPE() [5/5]

operations_research::DEFINE_INT_TYPE	(	RoutingVehicleClassIndex	,
		int
	)

◆ FillPathEvaluation()

void operations_research::FillPathEvaluation	(	const std::vector< int64 > &	path,
		const RoutingModel::TransitCallback2 &	evaluator,
		std::vector< int64 > *	values
	)

◆ FillValues()

void operations_research::FillValues	(	const std::vector< IntVar * > &	vars,
		std::vector< int64 > *const	values
	)

inline

Definition at line 2966 of file constraint_solveri.h.

◆ FindErrorInRoutingSearchParameters()

std::string operations_research::FindErrorInRoutingSearchParameters ( const RoutingSearchParameters & search_parameters )

Returns an empty std::string if the routing search parameters are valid, and a non-empty, human readable error description if they're not.

◆ FirstSolutionStrategy_Value_descriptor()

const ::PROTOBUF_NAMESPACE_ID::EnumDescriptor* operations_research::FirstSolutionStrategy_Value_descriptor ( )

◆ FirstSolutionStrategy_Value_IsValid()

bool operations_research::FirstSolutionStrategy_Value_IsValid ( int value )

◆ FirstSolutionStrategy_Value_Name()

const std::string& operations_research::FirstSolutionStrategy_Value_Name ( T enum_t_value )

inline

Definition at line 99 of file routing_enums.pb.h.

◆ FirstSolutionStrategy_Value_Parse()

bool operations_research::FirstSolutionStrategy_Value_Parse	(	const std::string &	name,
		FirstSolutionStrategy_Value *	value
	)

inline

Definition at line 106 of file routing_enums.pb.h.

◆ Hash1() [1/7]

uint64 operations_research::Hash1 ( const std::vector< int64 > & ptrs )

inline

Definition at line 271 of file constraint_solveri.h.

◆ Hash1() [2/7]

uint64 operations_research::Hash1 ( const std::vector< T * > & ptrs )

Definition at line 257 of file constraint_solveri.h.

◆ Hash1() [3/7]

uint64 operations_research::Hash1 ( int value )

inline

Definition at line 246 of file constraint_solveri.h.

◆ Hash1() [4/7]

uint64 operations_research::Hash1 ( int64 value )

inline

Definition at line 244 of file constraint_solveri.h.

◆ Hash1() [5/7]

uint64 operations_research::Hash1 ( uint32 value )

inline

Definition at line 233 of file constraint_solveri.h.

◆ Hash1() [6/7]

uint64 operations_research::Hash1 ( uint64 value )

inline

Hash functions.

value = (value << 21) - value - 1;

value * 265

value * 21

Definition at line 222 of file constraint_solveri.h.

◆ Hash1() [7/7]

uint64 operations_research::Hash1 ( void *const ptr )

inline

Definition at line 248 of file constraint_solveri.h.

◆ IsArrayBoolean()

bool operations_research::IsArrayBoolean ( const std::vector< T > & values )

Definition at line 2820 of file constraint_solveri.h.

◆ IsArrayConstant()

bool operations_research::IsArrayConstant	(	const std::vector< T > &	values,
		const T &	value
	)

Definition at line 2810 of file constraint_solveri.h.

◆ IsArrayInRange()

bool operations_research::IsArrayInRange	(	const std::vector< IntVar * > &	vars,
		T	range_min,
		T	range_max
	)

Definition at line 2900 of file constraint_solveri.h.

◆ IsIncreasing()

bool operations_research::IsIncreasing ( const std::vector< T > & values )

Definition at line 2890 of file constraint_solveri.h.

◆ IsIncreasingContiguous()

bool operations_research::IsIncreasingContiguous ( const std::vector< T > & values )

Definition at line 2880 of file constraint_solveri.h.

◆ LocalSearchMetaheuristic_Value_descriptor()

const ::PROTOBUF_NAMESPACE_ID::EnumDescriptor* operations_research::LocalSearchMetaheuristic_Value_descriptor ( )

◆ LocalSearchMetaheuristic_Value_IsValid()

bool operations_research::LocalSearchMetaheuristic_Value_IsValid ( int value )

◆ LocalSearchMetaheuristic_Value_Name()

const std::string& operations_research::LocalSearchMetaheuristic_Value_Name ( T enum_t_value )

inline

Definition at line 129 of file routing_enums.pb.h.

◆ LocalSearchMetaheuristic_Value_Parse()

bool operations_research::LocalSearchMetaheuristic_Value_Parse	(	const std::string &	name,
		LocalSearchMetaheuristic_Value *	value
	)

inline

Definition at line 136 of file routing_enums.pb.h.

◆ MakeConstraintDemon0()

Demon* operations_research::MakeConstraintDemon0	(	Solver *const	s,
		T *const	ct,
		void(T::*)()	method,
		const std::string &	name
	)

Definition at line 532 of file constraint_solveri.h.

◆ MakeConstraintDemon1()

Demon* operations_research::MakeConstraintDemon1	(	Solver *const	s,
		T *const	ct,
		void(T::*)(P)	method,
		const std::string &	name,
		P	param1
	)

Definition at line 573 of file constraint_solveri.h.

◆ MakeConstraintDemon2()

Demon* operations_research::MakeConstraintDemon2	(	Solver *const	s,
		T *const	ct,
		void(T::*)(P, Q)	method,
		const std::string &	name,
		P	param1,
		Q	param2
	)

Definition at line 612 of file constraint_solveri.h.

◆ MakeConstraintDemon3()

Demon* operations_research::MakeConstraintDemon3	(	Solver *const	s,
		T *const	ct,
		void(T::*)(P, Q, R)	method,
		const std::string &	name,
		P	param1,
		Q	param2,
		R	param3
	)

Definition at line 655 of file constraint_solveri.h.

◆ MakeCPFeasibilityFilter()

IntVarLocalSearchFilter* operations_research::MakeCPFeasibilityFilter ( const RoutingModel * routing_model )

◆ MakeCumulBoundsPropagatorFilter()

IntVarLocalSearchFilter* operations_research::MakeCumulBoundsPropagatorFilter ( const RoutingDimension & dimension )

◆ MakeDelayedConstraintDemon0()

Demon* operations_research::MakeDelayedConstraintDemon0	(	Solver *const	s,
		T *const	ct,
		void(T::*)()	method,
		const std::string &	name
	)

Definition at line 695 of file constraint_solveri.h.

◆ MakeDelayedConstraintDemon1()

Demon* operations_research::MakeDelayedConstraintDemon1	(	Solver *const	s,
		T *const	ct,
		void(T::*)(P)	method,
		const std::string &	name,
		P	param1
	)

Definition at line 731 of file constraint_solveri.h.

◆ MakeDelayedConstraintDemon2()

Demon* operations_research::MakeDelayedConstraintDemon2	(	Solver *const	s,
		T *const	ct,
		void(T::*)(P, Q)	method,
		const std::string &	name,
		P	param1,
		Q	param2
	)

Definition at line 775 of file constraint_solveri.h.

◆ MakeGlobalLPCumulFilter()

IntVarLocalSearchFilter* operations_research::MakeGlobalLPCumulFilter	(	GlobalDimensionCumulOptimizer *	optimizer,
		bool	filter_objective_cost
	)

◆ MakeLocalSearchOperator()

LocalSearchOperator* operations_research::MakeLocalSearchOperator	(	Solver *	solver,
		const std::vector< IntVar * > &	vars,
		const std::vector< IntVar * > &	secondary_vars,
		std::function< int(int64)>	start_empty_path_class
	)

Operator Factories.

◆ MakeNodeDisjunctionFilter()

IntVarLocalSearchFilter* operations_research::MakeNodeDisjunctionFilter ( const RoutingModel & routing_model )

◆ MakePathCumulFilter()

IntVarLocalSearchFilter* operations_research::MakePathCumulFilter	(	const RoutingDimension &	dimension,
		const RoutingSearchParameters &	parameters,
		bool	propagate_own_objective_value,
		bool	filter_objective_cost
	)

◆ MakePathStateFilter()

LocalSearchFilter* operations_research::MakePathStateFilter	(	Solver *	solver,
		std::unique_ptr< PathState >	path_state,
		const std::vector< IntVar * > &	nexts
	)

◆ MakePickupDeliveryFilter()

IntVarLocalSearchFilter* operations_research::MakePickupDeliveryFilter	(	const RoutingModel &	routing_model,
		const RoutingModel::IndexPairs &	pairs,
		const std::vector< RoutingModel::PickupAndDeliveryPolicy > &	vehicle_policies
	)

◆ MakeSetValuesFromTargets()

DecisionBuilder* operations_research::MakeSetValuesFromTargets	(	Solver *	solver,
		std::vector< IntVar * >	variables,
		std::vector< int64 >	targets
	)

A decision builder which tries to assign values to variables as close as possible to target values first.

◆ MakeTypeRegulationsFilter()

IntVarLocalSearchFilter* operations_research::MakeTypeRegulationsFilter ( const RoutingModel & routing_model )

◆ MakeUnaryDimensionFilter()

LocalSearchFilter* operations_research::MakeUnaryDimensionFilter	(	Solver *	solver,
		std::unique_ptr< UnaryDimensionChecker >	checker
	)

◆ MakeVehicleAmortizedCostFilter()

IntVarLocalSearchFilter* operations_research::MakeVehicleAmortizedCostFilter ( const RoutingModel & routing_model )

◆ MakeVehicleBreaksFilter()

IntVarLocalSearchFilter* operations_research::MakeVehicleBreaksFilter	(	const RoutingModel &	routing_model,
		const RoutingDimension &	dimension
	)

◆ MakeVehicleVarFilter()

IntVarLocalSearchFilter* operations_research::MakeVehicleVarFilter ( const RoutingModel & routing_model )

◆ MaxVarArray()

int64 operations_research::MaxVarArray ( const std::vector< IntVar * > & vars )

inline

The std::max<int64> is needed for compilation on MSVC.

Definition at line 2946 of file constraint_solveri.h.

◆ MinVarArray()

int64 operations_research::MinVarArray ( const std::vector< IntVar * > & vars )

inline

The std::min<int64> is needed for compilation on MSVC.

Definition at line 2956 of file constraint_solveri.h.

◆ ParameterDebugString() [1/2]

std::string operations_research::ParameterDebugString ( P * param )

Support limited to pointers to classes which define DebugString().

Definition at line 544 of file constraint_solveri.h.

◆ ParameterDebugString() [2/2]

std::string operations_research::ParameterDebugString ( P param )

Definition at line 538 of file constraint_solveri.h.

◆ PosIntDivDown()

int64 operations_research::PosIntDivDown	(	int64	e,
		int64	v
	)

inline

Definition at line 2984 of file constraint_solveri.h.

◆ PosIntDivUp()

int64 operations_research::PosIntDivUp	(	int64	e,
		int64	v
	)

inline

Definition at line 2975 of file constraint_solveri.h.

◆ RoutingSearchParameters_SchedulingSolver_descriptor()

const ::PROTOBUF_NAMESPACE_ID::EnumDescriptor* operations_research::RoutingSearchParameters_SchedulingSolver_descriptor ( )

◆ RoutingSearchParameters_SchedulingSolver_IsValid()

bool operations_research::RoutingSearchParameters_SchedulingSolver_IsValid ( int value )

◆ RoutingSearchParameters_SchedulingSolver_Name()

const std::string& operations_research::RoutingSearchParameters_SchedulingSolver_Name ( T enum_t_value )

inline

Definition at line 94 of file routing_parameters.pb.h.

◆ RoutingSearchParameters_SchedulingSolver_Parse()

bool operations_research::RoutingSearchParameters_SchedulingSolver_Parse	(	const std::string &	name,
		RoutingSearchParameters_SchedulingSolver *	value
	)

inline

Definition at line 101 of file routing_parameters.pb.h.

◆ SolveModelWithSat()

bool operations_research::SolveModelWithSat	(	const RoutingModel &	model,
		const RoutingSearchParameters &	search_parameters,
		const Assignment *	initial_solution,
		Assignment *	solution
	)

Attempts to solve the model using the cp-sat solver.

As of 5/2019, will solve the TSP corresponding to the model if it has a single vehicle. Therefore the resulting solution might not actually be feasible. Will return false if a solution could not be found.

◆ ToInt64Vector()

std::vector<int64> operations_research::ToInt64Vector ( const std::vector< int > & input )

Variable Documentation

◆ _AssignmentProto_default_instance_

AssignmentProtoDefaultTypeInternal _AssignmentProto_default_instance_

◆ _ConstraintRuns_default_instance_

ConstraintRunsDefaultTypeInternal _ConstraintRuns_default_instance_

◆ _ConstraintSolverParameters_default_instance_

ConstraintSolverParametersDefaultTypeInternal _ConstraintSolverParameters_default_instance_

◆ _DemonRuns_default_instance_

DemonRunsDefaultTypeInternal _DemonRuns_default_instance_

◆ _FirstSolutionStrategy_default_instance_

FirstSolutionStrategyDefaultTypeInternal _FirstSolutionStrategy_default_instance_

◆ _IntervalVarAssignment_default_instance_

IntervalVarAssignmentDefaultTypeInternal _IntervalVarAssignment_default_instance_

◆ _IntVarAssignment_default_instance_

IntVarAssignmentDefaultTypeInternal _IntVarAssignment_default_instance_

◆ _LocalSearchMetaheuristic_default_instance_

LocalSearchMetaheuristicDefaultTypeInternal _LocalSearchMetaheuristic_default_instance_

◆ _RegularLimitParameters_default_instance_

RegularLimitParametersDefaultTypeInternal _RegularLimitParameters_default_instance_

◆ _RoutingModelParameters_default_instance_

RoutingModelParametersDefaultTypeInternal _RoutingModelParameters_default_instance_

◆ _RoutingSearchParameters_default_instance_

RoutingSearchParametersDefaultTypeInternal _RoutingSearchParameters_default_instance_

◆ _RoutingSearchParameters_LocalSearchNeighborhoodOperators_default_instance_

RoutingSearchParameters_LocalSearchNeighborhoodOperatorsDefaultTypeInternal _RoutingSearchParameters_LocalSearchNeighborhoodOperators_default_instance_

◆ _SequenceVarAssignment_default_instance_

SequenceVarAssignmentDefaultTypeInternal _SequenceVarAssignment_default_instance_

◆ _WorkerInfo_default_instance_

WorkerInfoDefaultTypeInternal _WorkerInfo_default_instance_

◆ ConstraintSolverParameters_TrailCompression_TrailCompression_ARRAYSIZE

constexpr int ConstraintSolverParameters_TrailCompression_TrailCompression_ARRAYSIZE = ConstraintSolverParameters_TrailCompression_TrailCompression_MAX + 1

constexpr

Definition at line 77 of file solver_parameters.pb.h.

◆ ConstraintSolverParameters_TrailCompression_TrailCompression_MAX

constexpr ConstraintSolverParameters_TrailCompression ConstraintSolverParameters_TrailCompression_TrailCompression_MAX = ConstraintSolverParameters_TrailCompression_COMPRESS_WITH_ZLIB

constexpr

Definition at line 76 of file solver_parameters.pb.h.

◆ ConstraintSolverParameters_TrailCompression_TrailCompression_MIN

constexpr ConstraintSolverParameters_TrailCompression ConstraintSolverParameters_TrailCompression_TrailCompression_MIN = ConstraintSolverParameters_TrailCompression_NO_COMPRESSION

constexpr

Definition at line 75 of file solver_parameters.pb.h.

◆ FirstSolutionStrategy_Value_Value_ARRAYSIZE

constexpr int FirstSolutionStrategy_Value_Value_ARRAYSIZE = FirstSolutionStrategy_Value_Value_MAX + 1

constexpr

Definition at line 95 of file routing_enums.pb.h.

◆ FirstSolutionStrategy_Value_Value_MAX

constexpr FirstSolutionStrategy_Value FirstSolutionStrategy_Value_Value_MAX = FirstSolutionStrategy_Value_AUTOMATIC

constexpr

Definition at line 94 of file routing_enums.pb.h.

◆ FirstSolutionStrategy_Value_Value_MIN

constexpr FirstSolutionStrategy_Value FirstSolutionStrategy_Value_Value_MIN = FirstSolutionStrategy_Value_UNSET

constexpr

Definition at line 93 of file routing_enums.pb.h.

◆ LocalSearchMetaheuristic_Value_Value_ARRAYSIZE

constexpr int LocalSearchMetaheuristic_Value_Value_ARRAYSIZE = LocalSearchMetaheuristic_Value_Value_MAX + 1

constexpr

Definition at line 125 of file routing_enums.pb.h.

◆ LocalSearchMetaheuristic_Value_Value_MAX

constexpr LocalSearchMetaheuristic_Value LocalSearchMetaheuristic_Value_Value_MAX = LocalSearchMetaheuristic_Value_AUTOMATIC

constexpr

Definition at line 124 of file routing_enums.pb.h.

◆ LocalSearchMetaheuristic_Value_Value_MIN

constexpr LocalSearchMetaheuristic_Value LocalSearchMetaheuristic_Value_Value_MIN = LocalSearchMetaheuristic_Value_UNSET

constexpr

Definition at line 123 of file routing_enums.pb.h.

◆ RoutingSearchParameters_SchedulingSolver_SchedulingSolver_ARRAYSIZE

constexpr int RoutingSearchParameters_SchedulingSolver_SchedulingSolver_ARRAYSIZE = RoutingSearchParameters_SchedulingSolver_SchedulingSolver_MAX + 1

constexpr

Definition at line 90 of file routing_parameters.pb.h.

◆ RoutingSearchParameters_SchedulingSolver_SchedulingSolver_MAX

constexpr RoutingSearchParameters_SchedulingSolver RoutingSearchParameters_SchedulingSolver_SchedulingSolver_MAX = RoutingSearchParameters_SchedulingSolver_CP_SAT

constexpr

Definition at line 89 of file routing_parameters.pb.h.

◆ RoutingSearchParameters_SchedulingSolver_SchedulingSolver_MIN

constexpr RoutingSearchParameters_SchedulingSolver RoutingSearchParameters_SchedulingSolver_SchedulingSolver_MIN = RoutingSearchParameters_SchedulingSolver_UNSET

constexpr

Definition at line 88 of file routing_parameters.pb.h.

C++ Reference

C++ Reference: Routing

Classes

Typedefs

Enumerations

Functions

Variables

Detailed Description

Typedef Documentation

◆ RoutingIndexPair

◆ RoutingIndexPairs

◆ RoutingTransitCallback1

◆ RoutingTransitCallback2

◆ SequenceVarLocalSearchOperatorTemplate

Enumeration Type Documentation

◆ ConstraintSolverParameters_TrailCompression

◆ DimensionSchedulingStatus

◆ FirstSolutionStrategy_Value

◆ LocalSearchMetaheuristic_Value

◆ RoutingSearchParameters_SchedulingSolver

◆ VarTypes

Function Documentation

◆ AppendDimensionCumulFilters()

◆ AppendTasksFromIntervals()

◆ AppendTasksFromPath()

◆ AreAllBooleans()

◆ AreAllBound()

◆ AreAllBoundOrNull()

◆ AreAllBoundTo()

◆ AreAllGreaterOrEqual()

◆ AreAllLessOrEqual()

◆ AreAllNegative()

◆ AreAllNull()

◆ AreAllOnes()

◆ AreAllPositive()

◆ AreAllStrictlyNegative()

◆ AreAllStrictlyPositive()

◆ BuildModelParametersFromFlags()

◆ BuildSearchParametersFromFlags()

◆ ConstraintSolverParameters_TrailCompression_descriptor()

◆ ConstraintSolverParameters_TrailCompression_IsValid()

◆ ConstraintSolverParameters_TrailCompression_Name()

◆ ConstraintSolverParameters_TrailCompression_Parse()

◆ DefaultRoutingModelParameters()

◆ DefaultRoutingSearchParameters()

◆ DEFINE_INT_TYPE() [1/5]

◆ DEFINE_INT_TYPE() [2/5]

◆ DEFINE_INT_TYPE() [3/5]

◆ DEFINE_INT_TYPE() [4/5]

◆ DEFINE_INT_TYPE() [5/5]

◆ FillPathEvaluation()

◆ FillValues()

◆ FindErrorInRoutingSearchParameters()

◆ FirstSolutionStrategy_Value_descriptor()

◆ FirstSolutionStrategy_Value_IsValid()

◆ FirstSolutionStrategy_Value_Name()

◆ FirstSolutionStrategy_Value_Parse()

◆ Hash1() [1/7]

◆ Hash1() [2/7]

◆ Hash1() [3/7]

◆ Hash1() [4/7]

◆ Hash1() [5/7]

◆ Hash1() [6/7]

◆ Hash1() [7/7]

◆ IsArrayBoolean()

◆ IsArrayConstant()

◆ IsArrayInRange()

◆ IsIncreasing()

◆ IsIncreasingContiguous()

◆ LocalSearchMetaheuristic_Value_descriptor()

◆ LocalSearchMetaheuristic_Value_IsValid()

◆ LocalSearchMetaheuristic_Value_Name()

◆ LocalSearchMetaheuristic_Value_Parse()

◆ MakeConstraintDemon0()

◆ MakeConstraintDemon1()

◆ MakeConstraintDemon2()

◆ MakeConstraintDemon3()

◆ MakeCPFeasibilityFilter()

◆ MakeCumulBoundsPropagatorFilter()

◆ MakeDelayedConstraintDemon0()