C++ Reference

C++ Reference: Routing

operations_research Namespace Reference

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  Assignment
 An Assignment is a variable -> domains mapping, used to report solutions to the user. More...
 
class  AssignmentContainer
 
class  AssignmentElement
 
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  BaseObject
 A BaseObject is the root of all reversibly allocated objects. 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  CastConstraint
 Cast constraints are special channeling constraints designed to keep a variable in sync with an expression. 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  Constraint
 A constraint is the main modeling object. More...
 
class  CPFeasibilityFilter
 This filter accepts deltas for which the assignment satisfies the constraints of the Solver. More...
 
class  CumulBoundsPropagator
 
class  Decision
 A Decision represents a choice point in the search tree. More...
 
class  DecisionBuilder
 A DecisionBuilder is responsible for creating the search tree. More...
 
class  DecisionVisitor
 A DecisionVisitor is used to inspect a decision. More...
 
struct  DefaultPhaseParameters
 This struct holds all parameters for the default search. More...
 
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  Demon
 A Demon is the base element of a propagation queue. More...
 
class  DimensionCumulOptimizerCore
 
class  DisjunctiveConstraint
 
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  FilteredHeuristicCloseNodesLNSOperator
 Filtered heuristic LNS operator, where the destruction phase consists of removing a node and the 'num_close_nodes' nodes closest to it, along with each of their corresponding sibling pickup/deliveries that are performed. More...
 
class  FilteredHeuristicExpensiveChainLNSOperator
 Similar to the heuristic path LNS 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  FilteredHeuristicLocalSearchOperator
 Class of operators using a RoutingFilteredHeuristic to insert unperformed nodes after changes have been made to the current solution. 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  ImprovementSearchLimit
 
class  IndexPairSwapActiveOperator
 Operator which inserts inactive nodes into a path and makes a pair of active nodes inactive. More...
 
class  InitAndGetValues
 Utility class to encapsulate an IntVarIterator and use it in a range-based loop. More...
 
class  IntervalVar
 Interval variables are often used in scheduling. More...
 
class  IntervalVarElement
 
class  IntExpr
 The class IntExpr is the base of all integer expressions in constraint programming. More...
 
class  IntVar
 The class IntVar is a subset of IntExpr. More...
 
class  IntVarElement
 
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  IntVarIterator
 The class Iterator has two direct subclasses. 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  ModelVisitor
 Model visitor. More...
 
class  NumericalRev
 Subclass of Rev<T> which adds numerical operations. More...
 
class  NumericalRevArray
 Subclass of RevArray<T> which adds numerical operations. More...
 
class  OptimizeVar
 This class encapsulates an objective. More...
 
class  Pack
 
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  PropagationBaseObject
 NOLINT. More...
 
class  PropagationMonitor
 
class  RegularLimit
 Usual limit based on wall_time, number of explored branches and number of failures in the search tree. More...
 
class  RelocateExpensiveChain
 RelocateExpensiveChain. More...
 
class  RelocatePathAndHeuristicInsertUnperformedOperator
 Heuristic-based local search operator which relocates an entire route to an empty vehicle of different vehicle class and then tries to insert unperformed nodes using the heuristic. More...
 
class  RelocateSubtrip
 Tries to move subtrips after an insertion node. More...
 
class  Rev
 This class adds reversibility to a POD type. More...
 
class  RevArray
 Reversible array of POD types. 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  SearchLimit
 Base class of all search limits. More...
 
class  SearchLog
 The base class of all search logs that periodically outputs information when the search is running. More...
 
class  SearchMonitor
 A search monitor is a simple set of callbacks to monitor all search events. More...
 
class  SequenceVar
 A sequence variable is a variable whose domain is a set of possible orderings of the interval variables. More...
 
class  SequenceVarElement
 The SequenceVarElement stores a partial representation of ranked interval variables in the underlying sequence variable. 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  SolutionCollector
 This class is the root class of all solution collectors. More...
 
class  SolutionPool
 This class is used to manage a pool of solutions. More...
 
class  Solver
 Solver Class. 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...
 
struct  TravelBounds
 
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...
 
class  VehicleTypeCurator
 Helper class that manages vehicles. More...
 

Typedefs

typedef VarLocalSearchOperator< SequenceVar, std::vector< int >, SequenceVarLocalSearchHandlerSequenceVarLocalSearchOperatorTemplate
 
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< RoutingIndexPairRoutingIndexPairs
 

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 class  DimensionSchedulingStatus { OPTIMAL , RELAXED_OPTIMAL_ONLY , INFEASIBLE }
 

Functions

int64 CpRandomSeed ()
 
std::ostream & operator<< (std::ostream &out, const Solver *const s)
 
int64 Zero ()
 NOLINT. More...
 
int64 One ()
 This method returns 1. More...
 
std::ostream & operator<< (std::ostream &out, const BaseObject *o)
 
std::ostream & operator<< (std::ostream &out, const Assignment &assignment)
 
void SetAssignmentFromAssignment (Assignment *target_assignment, const std::vector< IntVar * > &target_vars, const Assignment *source_assignment, const std::vector< IntVar * > &source_vars)
 NOLINT. More...
 
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 >
LocalSearchOperatorMakeLocalSearchOperator (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)
 
LocalSearchFilterMakePathStateFilter (Solver *solver, std::unique_ptr< PathState > path_state, const std::vector< IntVar * > &nexts)
 
LocalSearchFilterMakeUnaryDimensionFilter (Solver *solver, std::unique_ptr< UnaryDimensionChecker > checker)
 
void AppendTasksFromPath (const std::vector< int64 > &path, const TravelBounds &travel_bounds, 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)
 
void FillTravelBoundsOfVehicle (int vehicle, const std::vector< int64 > &path, const RoutingDimension &dimension, TravelBounds *travel_bounds)
 
DecisionBuilderMakeSetValuesFromTargets (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...
 
IntVarLocalSearchFilterMakeMaxActiveVehiclesFilter (const RoutingModel &routing_model)
 
IntVarLocalSearchFilterMakeNodeDisjunctionFilter (const RoutingModel &routing_model)
 
IntVarLocalSearchFilterMakeVehicleAmortizedCostFilter (const RoutingModel &routing_model)
 
IntVarLocalSearchFilterMakeTypeRegulationsFilter (const RoutingModel &routing_model)
 
void AppendDimensionCumulFilters (const std::vector< RoutingDimension * > &dimensions, const RoutingSearchParameters &parameters, bool filter_objective_cost, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
 
void AppendLightWeightDimensionFilters (const PathState *path_state, const std::vector< RoutingDimension * > &dimensions, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
 
IntVarLocalSearchFilterMakePathCumulFilter (const RoutingDimension &dimension, const RoutingSearchParameters &parameters, bool propagate_own_objective_value, bool filter_objective_cost, bool can_use_lp=true)
 
IntVarLocalSearchFilterMakeCumulBoundsPropagatorFilter (const RoutingDimension &dimension)
 
IntVarLocalSearchFilterMakeGlobalLPCumulFilter (GlobalDimensionCumulOptimizer *optimizer, bool filter_objective_cost)
 
IntVarLocalSearchFilterMakePickupDeliveryFilter (const RoutingModel &routing_model, const RoutingModel::IndexPairs &pairs, const std::vector< RoutingModel::PickupAndDeliveryPolicy > &vehicle_policies)
 
IntVarLocalSearchFilterMakeVehicleVarFilter (const RoutingModel &routing_model)
 
IntVarLocalSearchFilterMakeVehicleBreaksFilter (const RoutingModel &routing_model, const RoutingDimension &dimension)
 
IntVarLocalSearchFilterMakeCPFeasibilityFilter (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)
 
template<class T >
DemonMakeConstraintDemon0 (Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
 
template<class P >
std::string ParameterDebugString (P param)
 
template<class P >
std::string ParameterDebugString (P *param)
 Support limited to pointers to classes which define DebugString(). More...
 
template<class T , class P >
DemonMakeConstraintDemon1 (Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
 
template<class T , class P , class Q >
DemonMakeConstraintDemon2 (Solver *const s, T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
 
template<class T , class P , class Q , class R >
DemonMakeConstraintDemon3 (Solver *const s, T *const ct, void(T::*method)(P, Q, R), const std::string &name, P param1, Q param2, R param3)
 
template<class T >
DemonMakeDelayedConstraintDemon0 (Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
 
template<class T , class P >
DemonMakeDelayedConstraintDemon1 (Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
 
template<class T , class P , class Q >
DemonMakeDelayedConstraintDemon2 (Solver *const s, T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
 

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:

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

Enumeration Type Documentation

◆ DimensionSchedulingStatus

enum class DimensionSchedulingStatus
strong
Enumerator
OPTIMAL 
RELAXED_OPTIMAL_ONLY 
INFEASIBLE 

Definition at line 126 of file routing_lp_scheduling.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 AppendDimensionCumulFilters ( const std::vector< RoutingDimension * > &  dimensions,
const RoutingSearchParameters &  parameters,
bool  filter_objective_cost,
std::vector< LocalSearchFilterManager::FilterEvent > *  filters 
)

◆ AppendLightWeightDimensionFilters()

void AppendLightWeightDimensionFilters ( const PathState path_state,
const std::vector< RoutingDimension * > &  dimensions,
std::vector< LocalSearchFilterManager::FilterEvent > *  filters 
)

◆ AppendTasksFromIntervals()

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

◆ AppendTasksFromPath()

void AppendTasksFromPath ( const std::vector< int64 > &  path,
const TravelBounds travel_bounds,
const RoutingDimension dimension,
DisjunctivePropagator::Tasks tasks 
)

◆ AreAllBooleans()

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

Definition at line 2937 of file constraint_solveri.h.

◆ AreAllBound()

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

Definition at line 2928 of file constraint_solveri.h.

◆ AreAllBoundOrNull()

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.

Definition at line 2944 of file constraint_solveri.h.

◆ AreAllBoundTo()

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

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

Definition at line 2955 of file constraint_solveri.h.

◆ AreAllGreaterOrEqual()

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

Definition at line 2858 of file constraint_solveri.h.

◆ AreAllLessOrEqual()

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

Definition at line 2868 of file constraint_solveri.h.

◆ AreAllNegative()

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

Definition at line 2883 of file constraint_solveri.h.

◆ AreAllNull()

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

Definition at line 2853 of file constraint_solveri.h.

◆ AreAllOnes()

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

Definition at line 2848 of file constraint_solveri.h.

◆ AreAllPositive()

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

Definition at line 2878 of file constraint_solveri.h.

◆ AreAllStrictlyNegative()

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

Definition at line 2893 of file constraint_solveri.h.

◆ AreAllStrictlyPositive()

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

Definition at line 2888 of file constraint_solveri.h.

◆ BuildModelParametersFromFlags()

RoutingModelParameters BuildModelParametersFromFlags ( )

Builds routing search parameters from flags.

◆ BuildSearchParametersFromFlags()

RoutingSearchParameters BuildSearchParametersFromFlags ( )

Builds routing search parameters from flags.

describe a valid set of routing search parameters.

◆ CpRandomSeed()

int64 CpRandomSeed ( )
inline

Definition at line 168 of file constraint_solver.h.

◆ DefaultRoutingModelParameters()

RoutingModelParameters DefaultRoutingModelParameters ( )

◆ DefaultRoutingSearchParameters()

RoutingSearchParameters DefaultRoutingSearchParameters ( )

◆ DEFINE_INT_TYPE() [1/5]

DEFINE_INT_TYPE ( RoutingCostClassIndex  ,
int   
)

◆ DEFINE_INT_TYPE() [2/5]

DEFINE_INT_TYPE ( RoutingDimensionIndex  ,
int   
)

◆ DEFINE_INT_TYPE() [3/5]

DEFINE_INT_TYPE ( RoutingDisjunctionIndex  ,
int   
)

◆ DEFINE_INT_TYPE() [4/5]

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]

DEFINE_INT_TYPE ( RoutingVehicleClassIndex  ,
int   
)

◆ FillPathEvaluation()

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

◆ FillTravelBoundsOfVehicle()

void FillTravelBoundsOfVehicle ( int  vehicle,
const std::vector< int64 > &  path,
const RoutingDimension dimension,
TravelBounds travel_bounds 
)

◆ FillValues()

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

Definition at line 2984 of file constraint_solveri.h.

◆ FindErrorInRoutingSearchParameters()

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.

◆ Hash1() [1/7]

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

Definition at line 268 of file constraint_solveri.h.

◆ Hash1() [2/7]

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

Definition at line 258 of file constraint_solveri.h.

◆ Hash1() [3/7]

uint64 Hash1 ( int  value)
inline

Definition at line 246 of file constraint_solveri.h.

◆ Hash1() [4/7]

uint64 Hash1 ( int64  value)
inline

Definition at line 244 of file constraint_solveri.h.

◆ Hash1() [5/7]

uint64 Hash1 ( uint32  value)
inline

Definition at line 233 of file constraint_solveri.h.

◆ Hash1() [6/7]

uint64 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 Hash1 ( void *const  ptr)
inline

Definition at line 248 of file constraint_solveri.h.

◆ IsArrayBoolean()

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

Definition at line 2838 of file constraint_solveri.h.

◆ IsArrayConstant()

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

Definition at line 2828 of file constraint_solveri.h.

◆ IsArrayInRange()

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

Definition at line 2918 of file constraint_solveri.h.

◆ IsIncreasing()

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

Definition at line 2908 of file constraint_solveri.h.

◆ IsIncreasingContiguous()

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

Definition at line 2898 of file constraint_solveri.h.

◆ MakeConstraintDemon0()

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

Definition at line 525 of file constraint_solveri.h.

◆ MakeConstraintDemon1()

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

Definition at line 566 of file constraint_solveri.h.

◆ MakeConstraintDemon2()

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

Definition at line 605 of file constraint_solveri.h.

◆ MakeConstraintDemon3()

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

Definition at line 648 of file constraint_solveri.h.

◆ MakeCPFeasibilityFilter()

IntVarLocalSearchFilter * MakeCPFeasibilityFilter ( RoutingModel routing_model)

◆ MakeCumulBoundsPropagatorFilter()

IntVarLocalSearchFilter * MakeCumulBoundsPropagatorFilter ( const RoutingDimension dimension)

◆ MakeDelayedConstraintDemon0()

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

Definition at line 688 of file constraint_solveri.h.

◆ MakeDelayedConstraintDemon1()

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

Definition at line 724 of file constraint_solveri.h.

◆ MakeDelayedConstraintDemon2()

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

Definition at line 768 of file constraint_solveri.h.

◆ MakeGlobalLPCumulFilter()

IntVarLocalSearchFilter * MakeGlobalLPCumulFilter ( GlobalDimensionCumulOptimizer optimizer,
bool  filter_objective_cost 
)

◆ MakeLocalSearchOperator()

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.

◆ MakeMaxActiveVehiclesFilter()

IntVarLocalSearchFilter * MakeMaxActiveVehiclesFilter ( const RoutingModel routing_model)

◆ MakeNodeDisjunctionFilter()

IntVarLocalSearchFilter * MakeNodeDisjunctionFilter ( const RoutingModel routing_model)

◆ MakePathCumulFilter()

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

◆ MakePathStateFilter()

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

◆ MakePickupDeliveryFilter()

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

◆ MakeSetValuesFromTargets()

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.

◆ MakeTypeRegulationsFilter()

IntVarLocalSearchFilter * MakeTypeRegulationsFilter ( const RoutingModel routing_model)

◆ MakeUnaryDimensionFilter()

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

◆ MakeVehicleAmortizedCostFilter()

IntVarLocalSearchFilter * MakeVehicleAmortizedCostFilter ( const RoutingModel routing_model)

◆ MakeVehicleBreaksFilter()

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

◆ MakeVehicleVarFilter()

IntVarLocalSearchFilter * MakeVehicleVarFilter ( const RoutingModel routing_model)

◆ MaxVarArray()

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

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

Definition at line 2964 of file constraint_solveri.h.

◆ MinVarArray()

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

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

Definition at line 2974 of file constraint_solveri.h.

◆ One()

int64 One ( )
inline

This method returns 1.

Definition at line 3147 of file constraint_solver.h.

◆ operator<<() [1/3]

std::ostream & operator<< ( std::ostream &  out,
const Assignment assignment 
)

◆ operator<<() [2/3]

std::ostream & operator<< ( std::ostream &  out,
const BaseObject o 
)

◆ operator<<() [3/3]

std::ostream & operator<< ( std::ostream &  out,
const Solver *const  s 
)

◆ ParameterDebugString() [1/2]

std::string ParameterDebugString ( P *  param)

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

Definition at line 537 of file constraint_solveri.h.

◆ ParameterDebugString() [2/2]

std::string ParameterDebugString ( param)

Definition at line 531 of file constraint_solveri.h.

◆ PosIntDivDown()

int64 PosIntDivDown ( int64  e,
int64  v 
)
inline

Definition at line 2998 of file constraint_solveri.h.

◆ PosIntDivUp()

int64 PosIntDivUp ( int64  e,
int64  v 
)
inline

Definition at line 2993 of file constraint_solveri.h.

◆ SetAssignmentFromAssignment()

void SetAssignmentFromAssignment ( Assignment target_assignment,
const std::vector< IntVar * > &  target_vars,
const Assignment source_assignment,
const std::vector< IntVar * > &  source_vars 
)

NOLINT.

Given a "source_assignment", clears the "target_assignment" and adds all IntVars in "target_vars", with the values of the variables set according to the corresponding values of "source_vars" in "source_assignment". source_vars and target_vars must have the same number of elements. The source and target assignments can belong to different Solvers.

◆ SolveModelWithSat()

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.

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 > ToInt64Vector ( const std::vector< int > &  input)

◆ Zero()

int64 Zero ( )
inline

NOLINT.

This method returns 0. It is useful when 0 can be cast either as a pointer or as an integer value and thus lead to an ambiguous function call.

Definition at line 3144 of file constraint_solver.h.