C++ Reference

C++ Reference: Routing

Classes | Typedefs | Enumerations | Functions | Variables
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  PROTOBUF_FINAL
 
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
 

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

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 >
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 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)
 
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 * MakeMaxActiveVehiclesFilter (const RoutingModel &routing_model)
 
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< LocalSearchFilterManager::FilterEvent > *filters)
 
void AppendLightWeightDimensionFilters (const PathState *path_state, const std::vector< RoutingDimension * > &dimensions, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
 
IntVarLocalSearchFilter * MakePathCumulFilter (const RoutingDimension &dimension, const RoutingSearchParameters &parameters, bool propagate_own_objective_value, bool filter_objective_cost, bool can_use_lp=true)
 
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 (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 (::PROTOBUF_NAMESPACE_ID::ConstStringParam 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 (::PROTOBUF_NAMESPACE_ID::ConstStringParam 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 (::PROTOBUF_NAMESPACE_ID::ConstStringParam 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 (::PROTOBUF_NAMESPACE_ID::ConstStringParam name, ConstraintSolverParameters_TrailCompression *value)
 
template<class T >
Demon * MakeConstraintDemon0 (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 >
Demon * MakeConstraintDemon1 (Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
 
template<class T , class P , class Q >
Demon * MakeConstraintDemon2 (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 >
Demon * MakeConstraintDemon3 (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 >
Demon * MakeDelayedConstraintDemon0 (Solver *const s, T *const ct, void(T::*method)(), const std::string &name)
 
template<class T , class P >
Demon * MakeDelayedConstraintDemon1 (Solver *const s, T *const ct, void(T::*method)(P), const std::string &name, P param1)
 
template<class T , class P , class Q >
Demon * MakeDelayedConstraintDemon2 (Solver *const s, T *const ct, void(T::*method)(P, Q), const std::string &name, P param1, Q param2)
 

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_ImprovementSearchLimitParametersDefaultTypeInternal _RoutingSearchParameters_ImprovementSearchLimitParameters_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:

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 1154 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 67 of file solver_parameters.pb.h.

◆ DimensionSchedulingStatus

enum DimensionSchedulingStatus
strong
Enumerator
OPTIMAL 
RELAXED_OPTIMAL_ONLY 
INFEASIBLE 

Definition at line 126 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 71 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 110 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 83 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< LocalSearchFilterManager::FilterEvent > *  filters 
)

◆ AppendLightWeightDimensionFilters()

void operations_research::AppendLightWeightDimensionFilters ( const PathState *  path_state,
const std::vector< RoutingDimension * > &  dimensions,
std::vector< LocalSearchFilterManager::FilterEvent > *  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 TravelBounds &  travel_bounds,
const RoutingDimension &  dimension,
DisjunctivePropagator::Tasks *  tasks 
)

◆ AreAllBooleans()

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

Definition at line 2937 of file constraint_solveri.h.

◆ AreAllBound()

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

Definition at line 2928 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 2944 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 2955 of file constraint_solveri.h.

◆ AreAllGreaterOrEqual()

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

Definition at line 2858 of file constraint_solveri.h.

◆ AreAllLessOrEqual()

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

Definition at line 2868 of file constraint_solveri.h.

◆ AreAllNegative()

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

Definition at line 2883 of file constraint_solveri.h.

◆ AreAllNull()

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

Definition at line 2853 of file constraint_solveri.h.

◆ AreAllOnes()

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

Definition at line 2848 of file constraint_solveri.h.

◆ AreAllPositive()

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

Definition at line 2878 of file constraint_solveri.h.

◆ AreAllStrictlyNegative()

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

Definition at line 2893 of file constraint_solveri.h.

◆ AreAllStrictlyPositive()

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

Definition at line 2888 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 80 of file solver_parameters.pb.h.

◆ ConstraintSolverParameters_TrailCompression_Parse()

bool operations_research::ConstraintSolverParameters_TrailCompression_Parse ( ::PROTOBUF_NAMESPACE_ID::ConstStringParam  name,
ConstraintSolverParameters_TrailCompression *  value 
)
inline

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

◆ CpRandomSeed()

int64 operations_research::CpRandomSeed ( )
inline

Definition at line 163 of file constraint_solver.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 
)

◆ FillTravelBoundsOfVehicle()

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

◆ FillValues()

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

Definition at line 2984 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 98 of file routing_enums.pb.h.

◆ FirstSolutionStrategy_Value_Parse()

bool operations_research::FirstSolutionStrategy_Value_Parse ( ::PROTOBUF_NAMESPACE_ID::ConstStringParam  name,
FirstSolutionStrategy_Value *  value 
)
inline

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

◆ Hash1() [1/7]

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

Definition at line 268 of file constraint_solveri.h.

◆ Hash1() [2/7]

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

Definition at line 258 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 2838 of file constraint_solveri.h.

◆ IsArrayConstant()

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

Definition at line 2828 of file constraint_solveri.h.

◆ IsArrayInRange()

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

Definition at line 2918 of file constraint_solveri.h.

◆ IsIncreasing()

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

Definition at line 2908 of file constraint_solveri.h.

◆ IsIncreasingContiguous()

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

Definition at line 2898 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 128 of file routing_enums.pb.h.

◆ LocalSearchMetaheuristic_Value_Parse()

bool operations_research::LocalSearchMetaheuristic_Value_Parse ( ::PROTOBUF_NAMESPACE_ID::ConstStringParam  name,
LocalSearchMetaheuristic_Value *  value 
)
inline

Definition at line 135 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 525 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 566 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 605 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 648 of file constraint_solveri.h.

◆ MakeCPFeasibilityFilter()

IntVarLocalSearchFilter* operations_research::MakeCPFeasibilityFilter ( 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 688 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 724 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 768 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.

◆ MakeMaxActiveVehiclesFilter()

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

◆ 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,
bool  can_use_lp = true 
)

◆ 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 2964 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 2974 of file constraint_solveri.h.

◆ One()

int64 operations_research::One ( )
inline

This method returns 1.

Definition at line 3142 of file constraint_solver.h.

◆ operator<<() [1/3]

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

◆ operator<<() [2/3]

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

◆ operator<<() [3/3]

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

◆ ParameterDebugString() [1/2]

std::string operations_research::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 operations_research::ParameterDebugString ( P  param)

Definition at line 531 of file constraint_solveri.h.

◆ PosIntDivDown()

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

Definition at line 2998 of file constraint_solveri.h.

◆ PosIntDivUp()

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

Definition at line 2993 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 97 of file routing_parameters.pb.h.

◆ RoutingSearchParameters_SchedulingSolver_Parse()

bool operations_research::RoutingSearchParameters_SchedulingSolver_Parse ( ::PROTOBUF_NAMESPACE_ID::ConstStringParam  name,
RoutingSearchParameters_SchedulingSolver *  value 
)
inline

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

◆ SetAssignmentFromAssignment()

void operations_research::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 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)

◆ Zero()

int64 operations_research::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 3139 of file constraint_solver.h.

Variable Documentation

◆ _AssignmentProto_default_instance_

AssignmentProtoDefaultTypeInternal _AssignmentProto_default_instance_
extern

◆ _ConstraintRuns_default_instance_

ConstraintRunsDefaultTypeInternal _ConstraintRuns_default_instance_
extern

◆ _ConstraintSolverParameters_default_instance_

ConstraintSolverParametersDefaultTypeInternal _ConstraintSolverParameters_default_instance_
extern

◆ _DemonRuns_default_instance_

DemonRunsDefaultTypeInternal _DemonRuns_default_instance_
extern

◆ _FirstSolutionStrategy_default_instance_

FirstSolutionStrategyDefaultTypeInternal _FirstSolutionStrategy_default_instance_
extern

◆ _IntervalVarAssignment_default_instance_

IntervalVarAssignmentDefaultTypeInternal _IntervalVarAssignment_default_instance_
extern

◆ _IntVarAssignment_default_instance_

IntVarAssignmentDefaultTypeInternal _IntVarAssignment_default_instance_
extern

◆ _LocalSearchMetaheuristic_default_instance_

LocalSearchMetaheuristicDefaultTypeInternal _LocalSearchMetaheuristic_default_instance_
extern

◆ _RegularLimitParameters_default_instance_

RegularLimitParametersDefaultTypeInternal _RegularLimitParameters_default_instance_
extern

◆ _RoutingModelParameters_default_instance_

RoutingModelParametersDefaultTypeInternal _RoutingModelParameters_default_instance_
extern

◆ _RoutingSearchParameters_default_instance_

RoutingSearchParametersDefaultTypeInternal _RoutingSearchParameters_default_instance_
extern

◆ _RoutingSearchParameters_ImprovementSearchLimitParameters_default_instance_

RoutingSearchParameters_ImprovementSearchLimitParametersDefaultTypeInternal _RoutingSearchParameters_ImprovementSearchLimitParameters_default_instance_
extern

◆ _RoutingSearchParameters_LocalSearchNeighborhoodOperators_default_instance_

RoutingSearchParameters_LocalSearchNeighborhoodOperatorsDefaultTypeInternal _RoutingSearchParameters_LocalSearchNeighborhoodOperators_default_instance_
extern

◆ _SequenceVarAssignment_default_instance_

SequenceVarAssignmentDefaultTypeInternal _SequenceVarAssignment_default_instance_
extern

◆ _WorkerInfo_default_instance_

WorkerInfoDefaultTypeInternal _WorkerInfo_default_instance_
extern

◆ ConstraintSolverParameters_TrailCompression_TrailCompression_ARRAYSIZE

constexpr int ConstraintSolverParameters_TrailCompression_TrailCompression_ARRAYSIZE = ConstraintSolverParameters_TrailCompression_TrailCompression_MAX + 1
constexpr

Definition at line 76 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 75 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 74 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 94 of file routing_enums.pb.h.

◆ FirstSolutionStrategy_Value_Value_MAX

constexpr FirstSolutionStrategy_Value FirstSolutionStrategy_Value_Value_MAX = FirstSolutionStrategy_Value_AUTOMATIC
constexpr

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

◆ FirstSolutionStrategy_Value_Value_MIN

constexpr FirstSolutionStrategy_Value FirstSolutionStrategy_Value_Value_MIN = FirstSolutionStrategy_Value_UNSET
constexpr

Definition at line 92 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 124 of file routing_enums.pb.h.

◆ LocalSearchMetaheuristic_Value_Value_MAX

constexpr LocalSearchMetaheuristic_Value LocalSearchMetaheuristic_Value_Value_MAX = LocalSearchMetaheuristic_Value_AUTOMATIC
constexpr

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

◆ LocalSearchMetaheuristic_Value_Value_MIN

constexpr LocalSearchMetaheuristic_Value LocalSearchMetaheuristic_Value_Value_MIN = LocalSearchMetaheuristic_Value_UNSET
constexpr

Definition at line 122 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 93 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 92 of file routing_parameters.pb.h.

◆ RoutingSearchParameters_SchedulingSolver_SchedulingSolver_MIN

constexpr RoutingSearchParameters_SchedulingSolver RoutingSearchParameters_SchedulingSolver_SchedulingSolver_MIN = RoutingSearchParameters_SchedulingSolver_UNSET
constexpr

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