C++ Reference
C++ Reference: Routing
routing.h
Go to the documentation of this file.
227 };
237 };
658 int64 GetDisjunctionPenalty(DisjunctionIndex index) const {
773 enum VisitTypePolicy {
789 };
813 void AddHardTypeIncompatibility(int type1, int type2);
1972 int64 span_min = 0;
1973 int64 span_max = kint64max;
An Assignment is a variable -> domains mapping, used to report solutions to the user.
Definition: constraint_solver.h:5038
A BaseObject is the root of all reversibly allocated objects.
Definition: constraint_solver.h:3152
const std::vector< int64 > & GetTouchedPathStarts() const
Definition: routing.h:3853
static const int64 kUnassigned
Definition: routing.h:3841
bool Accept(const Assignment *delta, const Assignment *deltadelta, int64 objective_min, int64 objective_max) override
Accepts a "delta" given the assignment with which the filter has been synchronized; the delta holds t...
const std::vector< int64 > & GetNewSynchronizedUnperformedNodes() const
Definition: routing.h:3856
BasePathFilter(const std::vector< IntVar * > &nexts, int next_domain_size)
~BasePathFilter() override
Definition: routing.h:3835
int64 GetNext(int64 node) const
Definition: routing.h:3843
void OnSynchronize(const Assignment *delta) override
This filter accepts deltas for which the assignment satisfies the constraints of the Solver.
Definition: routing.h:3908
bool Accept(const Assignment *delta, const Assignment *deltadelta, int64 objective_min, int64 objective_max) override
Accepts a "delta" given the assignment with which the filter has been synchronized; the delta holds t...
CPFeasibilityFilter(RoutingModel *routing_model)
std::string DebugString() const override
Definition: routing.h:3912
void OnSynchronize(const Assignment *delta) override
~CPFeasibilityFilter() override
Definition: routing.h:3911
Filtered-base decision builder based on the addition heuristic, extending a path from its start node ...
Definition: routing.h:3543
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
~CheapestAdditionFilteredHeuristic() override
Definition: routing.h:3547
CheapestAdditionFilteredHeuristic(RoutingModel *model, LocalSearchFilterManager *filter_manager)
CheapestInsertionFilteredHeuristic(RoutingModel *model, std::function< int64(int64, int64, int64)> evaluator, std::function< int64(int64)> penalty_evaluator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
std::vector< std::vector< StartEndValue > > ComputeStartEndDistanceForVehicles(const std::vector< int > &vehicles)
Computes and returns the distance of each uninserted node to every vehicle in "vehicles" as a std::ve...
std::function< int64(int64)> penalty_evaluator_
Definition: routing.h:3185
std::function< int64(int64, int64, int64)> evaluator_
Definition: routing.h:3184
void InsertBetween(int64 node, int64 predecessor, int64 successor)
Inserts 'node' just after 'predecessor', and just before 'successor', resulting in the following subs...
void InitializePriorityQueue(std::vector< std::vector< StartEndValue > > *start_end_distances_per_node, Queue *priority_queue)
Initializes the priority_queue by inserting the best entry corresponding to each node,...
std::pair< int64, int64 > ValuedPosition
Definition: routing.h:3127
~CheapestInsertionFilteredHeuristic() override
Definition: routing.h:3124
void AppendEvaluatedPositionsAfter(int64 node_to_insert, int64 start, int64 next_after_start, int64 vehicle, std::vector< ValuedPosition > *valued_positions)
Helper method to the ComputeEvaluatorSortedPositions* methods.
int64 GetUnperformedValue(int64 node_to_insert) const
Returns the cost of unperforming node 'node_to_insert'.
std::pair< StartEndValue, int > Seed
Definition: routing.h:3137
int64 GetInsertionCostForNodeAtPosition(int64 node_to_insert, int64 insert_after, int64 insert_before, int vehicle) const
Returns the cost of inserting 'node_to_insert' between 'insert_after' and 'insert_before' on the 'veh...
Christofides addition heuristic.
Definition: routing.h:3805
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
~ChristofidesFilteredHeuristic() override
Definition: routing.h:3810
std::string DebugString() const override
Definition: routing.h:3812
ChristofidesFilteredHeuristic(RoutingModel *model, LocalSearchFilterManager *filter_manager, bool use_minimum_matching)
A CheapestAdditionFilteredHeuristic where the notion of 'cheapest arc' comes from an arc comparator.
Definition: routing.h:3607
ComparatorCheapestAdditionFilteredHeuristic(RoutingModel *model, Solver::VariableValueComparator comparator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
~ComparatorCheapestAdditionFilteredHeuristic() override
Definition: routing.h:3613
std::string DebugString() const override
Definition: routing.h:3614
A constraint is the main modeling object.
Definition: constraint_solver.h:3584
A DecisionBuilder is responsible for creating the search tree.
Definition: constraint_solver.h:3268
A Decision represents a choice point in the search tree.
Definition: constraint_solver.h:3228
This class acts like a CP propagator: it takes a set of tasks given by their start/duration/end featu...
Definition: routing.h:1954
bool EdgeFinding(Tasks *tasks)
Does edge-finding deductions on all tasks.
bool Precedences(Tasks *tasks)
Propagates the deductions from the chain of precedences, if there is one.
bool DistanceDuration(Tasks *tasks)
Propagates distance_duration constraints, if any.
bool MirrorTasks(Tasks *tasks)
Transforms the problem with a time symmetry centered in 0.
bool ForbiddenIntervals(Tasks *tasks)
Tasks might have holes in their domain, this enforces such holes.
bool Propagate(Tasks *tasks)
Computes new bounds for all tasks, returns false if infeasible.
bool DetectablePrecedencesWithChain(Tasks *tasks)
Does detectable precedences deductions on tasks in the chain precedence, taking the time windows of n...
bool ChainSpanMinDynamic(Tasks *tasks)
Computes a lower bound of the span of the chain, taking into account only the first nonchain task.
bool ChainSpanMin(Tasks *tasks)
Propagates a lower bound of the chain span, end[num_chain_tasks] - start[0], to span_min.
A CheapestAdditionFilteredHeuristic where the notion of 'cheapest arc' comes from an arc evaluator.
Definition: routing.h:3584
EvaluatorCheapestAdditionFilteredHeuristic(RoutingModel *model, std::function< int64(int64, int64)> evaluator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
~EvaluatorCheapestAdditionFilteredHeuristic() override
Definition: routing.h:3590
std::string DebugString() const override
Definition: routing.h:3591
Filter-based decision builder which builds a solution by inserting nodes at their cheapest position o...
Definition: routing.h:3196
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
GlobalCheapestInsertionFilteredHeuristic(RoutingModel *model, std::function< int64(int64, int64, int64)> evaluator, std::function< int64(int64)> penalty_evaluator, LocalSearchFilterManager *filter_manager, GlobalCheapestInsertionParameters parameters)
Takes ownership of evaluators.
~GlobalCheapestInsertionFilteredHeuristic() override
Definition: routing.h:3228
std::string DebugString() const override
Definition: routing.h:3230
GlobalVehicleBreaksConstraint ensures breaks constraints are enforced on all vehicles in the dimensio...
Definition: routing.h:2062
void Post() override
This method is called when the constraint is processed by the solver.
void InitialPropagate() override
This method performs the initial propagation of the constraint.
GlobalVehicleBreaksConstraint(const RoutingDimension *dimension)
std::string DebugString() const override
Definition: routing.h:2065
Decision builder building a solution using heuristics with local search filters to evaluate its feasi...
Definition: routing.h:2977
Decision * Next(Solver *solver) override
This is the main method of the decision builder class.
~IntVarFilteredDecisionBuilder() override
Definition: routing.h:2982
int64 number_of_rejects() const
int64 number_of_decisions() const
Returns statistics from its underlying heuristic.
IntVarFilteredDecisionBuilder(std::unique_ptr< IntVarFilteredHeuristic > heuristic)
std::string DebugString() const override
Generic filter-based heuristic applied to IntVars.
Definition: routing.h:2997
virtual bool BuildSolutionInternal()=0
Virtual method to redefine how to build a solution.
int Size() const
Returns the number of variables the decision builder is trying to instantiate.
Definition: routing.h:3050
bool Contains(int64 index) const
Returns true if the variable of index 'index' is in the current solution.
Definition: routing.h:3045
int64 Value(int64 index) const
Returns the value of the variable of index 'index' in the last committed solution.
Definition: routing.h:3041
bool Commit()
Commits the modifications to the current solution if these modifications are "filter-feasible",...
virtual ~IntVarFilteredHeuristic()
Definition: routing.h:3002
Assignment *const BuildSolution()
Builds a solution.
Assignment *const assignment_
Definition: routing.h:3056
void ResetSolution()
Resets the data members for a new solution.
void SynchronizeFilters()
Synchronizes filters with an assignment (the current solution).
virtual std::string DebugString() const
Definition: routing.h:3013
virtual bool InitializeSolution()
Virtual method to initialize the solution.
Definition: routing.h:3019
int64 number_of_rejects() const
Definition: routing.h:3011
int64 number_of_decisions() const
Returns statistics on search, number of decisions sent to filters, number of decisions rejected by fi...
Definition: routing.h:3010
void SetValue(int64 index, int64 value)
Modifies the current solution by setting the variable of index 'index' to value 'value'.
Definition: routing.h:3030
IntVarFilteredHeuristic(Solver *solver, const std::vector< IntVar * > &vars, LocalSearchFilterManager *filter_manager)
The class IntVar is a subset of IntExpr.
Definition: constraint_solver.h:3997
Interval variables are often used in scheduling.
Definition: constraint_solver.h:4394
Filter-base decision builder which builds a solution by inserting nodes at their cheapest position.
Definition: routing.h:3510
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
~LocalCheapestInsertionFilteredHeuristic() override
Definition: routing.h:3516
LocalCheapestInsertionFilteredHeuristic(RoutingModel *model, std::function< int64(int64, int64, int64)> evaluator, LocalSearchFilterManager *filter_manager)
Takes ownership of evaluator.
std::string DebugString() const override
Definition: routing.h:3518
Local Search Filters are used for fast neighbor pruning.
Definition: constraint_solveri.h:1719
Filter manager: when a move is made, filters are executed to decide whether the solution is feasible ...
Definition: constraint_solveri.h:1763
The base class for all local search operators.
Definition: constraint_solveri.h:798
ParallelSavingsFilteredHeuristic(RoutingModel *model, const RoutingIndexManager *manager, SavingsParameters parameters, LocalSearchFilterManager *filter_manager)
Definition: routing.h:3760
~ParallelSavingsFilteredHeuristic() override
Definition: routing.h:3765
std::string DebugString() const override
Definition: routing.h:3766
Dimensions represent quantities accumulated at nodes along the routes.
Definition: routing.h:2368
void SetQuadraticCostSoftSpanUpperBoundForVehicle(SimpleBoundCosts::BoundCost bound_cost, int vehicle)
If the span of vehicle on this dimension is larger than bound, the cost will be increased by cost * (...
Definition: routing.h:2717
void SetCumulVarPiecewiseLinearCost(int64 index, const PiecewiseLinearFunction &cost)
Sets a piecewise linear cost on the cumul variable of a given variable index.
SimpleBoundCosts::BoundCost GetSoftSpanUpperBoundForVehicle(int vehicle) const
Definition: routing.h:2710
friend void AppendDimensionCumulFilters(const std::vector< RoutingDimension * > &dimensions, const RoutingSearchParameters ¶meters, bool filter_objective_cost, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
const std::vector< IntervalVar * > & GetBreakIntervalsOfVehicle(int vehicle) const
Returns the break intervals set by SetBreakIntervalsOfVehicle().
void AddNodePrecedence(int64 first_node, int64 second_node, int64 offset)
Definition: routing.h:2661
int64 GetTransitValueFromClass(int64 from_index, int64 to_index, int64 vehicle_class) const
Same as above but taking a vehicle class of the dimension instead of a vehicle (the class of a vehicl...
Definition: routing.h:2379
const std::vector< IntVar * > & cumuls() const
Like CumulVar(), TransitVar(), SlackVar() but return the whole variable vectors instead (indexed by i...
Definition: routing.h:2394
int64 global_span_cost_coefficient() const
Definition: routing.h:2681
int64 GetSpanCostCoefficientForVehicle(int vehicle) const
Definition: routing.h:2673
void SetSoftSpanUpperBoundForVehicle(SimpleBoundCosts::BoundCost bound_cost, int vehicle)
If the span of vehicle on this dimension is larger than bound, the cost will be increased by cost * (...
Definition: routing.h:2699
RoutingModel * model() const
Returns the model on which the dimension was created.
Definition: routing.h:2372
void SetSpanUpperBoundForVehicle(int64 upper_bound, int vehicle)
!defined(SWIGCSHARP) && !defined(SWIGJAVA) !defined(SWIGPYTHON)
bool HasPickupToDeliveryLimits() const
int64 GetGlobalOptimizerOffset() const
Definition: routing.h:2685
IntVar * CumulVar(int64 index) const
Get the cumul, transit and slack variables for the given node (given as int64 var index).
Definition: routing.h:2386
const RoutingModel::TransitCallback1 & GetUnaryTransitEvaluator(int vehicle) const
Returns the unary callback evaluating the transit value between two node indices for a given vehicle.
Definition: routing.h:2456
int64 GetCumulVarSoftLowerBoundCoefficient(int64 index) const
Returns the cost coefficient of the soft lower bound of a cumul variable for a given variable index.
bool HasCumulVarSoftLowerBound(int64 index) const
Returns true if a soft lower bound has been set for a given variable index.
IntVar * FixedTransitVar(int64 index) const
Definition: routing.h:2388
const std::vector< int64 > & vehicle_capacities() const
Returns the capacities for all vehicles.
Definition: routing.h:2444
void SetSpanCostCoefficientForAllVehicles(int64 coefficient)
int64 GetCumulVarSoftLowerBound(int64 index) const
Returns the soft lower bound of a cumul variable for a given variable index.
std::function< int64(int, int)> PickupToDeliveryLimitFunction
Limits, in terms of maximum difference between the cumul variables, between the pickup and delivery a...
Definition: routing.h:2637
bool AreVehicleTransitsPositive(int vehicle) const
Returns true iff the transit evaluator of 'vehicle' is positive for all arcs.
Definition: routing.h:2463
void SetBreakDistanceDurationOfVehicle(int64 distance, int64 duration, int vehicle)
With breaks supposed to be consecutive, this forces the distance between breaks of size at least mini...
const std::vector< IntVar * > & fixed_transits() const
Definition: routing.h:2395
bool HasBreakConstraints() const
Returns true if any break interval or break distance was defined.
const std::vector< IntVar * > & transits() const
Definition: routing.h:2396
const PiecewiseLinearFunction * GetCumulVarPiecewiseLinearCost(int64 index) const
Returns the piecewise linear cost of a cumul variable for a given variable index.
const RoutingDimension * base_dimension() const
Returns the parent in the dependency tree if any or nullptr otherwise.
Definition: routing.h:2608
void InitializeBreaks()
Sets up vehicle_break_intervals_, vehicle_break_distance_duration_, pre_travel_evaluators and post_tr...
int64 GetTransitValue(int64 from_index, int64 to_index, int64 vehicle) const
Returns the transition value for a given pair of nodes (as var index); this value is the one taken by...
void AddNodePrecedence(NodePrecedence precedence)
Definition: routing.h:2653
int64 GetLocalOptimizerOffsetForVehicle(int vehicle) const
Definition: routing.h:2689
const std::vector< int64 > & vehicle_span_upper_bounds() const
Definition: routing.h:2669
int GetPreTravelEvaluatorOfVehicle(int vehicle) const
!defined(SWIGPYTHON)
bool HasQuadraticCostSoftSpanUpperBounds() const
Definition: routing.h:2727
void SetPickupToDeliveryLimitFunctionForPair(PickupToDeliveryLimitFunction limit_function, int pair_index)
int64 GetFirstPossibleGreaterOrEqualValueForNode(int64 index, int64 min_value) const
Returns the smallest value outside the forbidden intervals of node 'index' that is greater than or eq...
Definition: routing.h:2409
int vehicle_to_class(int vehicle) const
Definition: routing.h:2467
int64 GetPickupToDeliveryLimitForPair(int pair_index, int pickup, int delivery) const
void SetSpanCostCoefficientForVehicle(int64 coefficient, int vehicle)
Sets a cost proportional to the dimension span on a given vehicle, or on all vehicles at once.
int64 GetCumulVarSoftUpperBound(int64 index) const
Returns the soft upper bound of a cumul variable for a given variable index.
const RoutingModel::TransitCallback2 & transit_evaluator(int vehicle) const
Returns the callback evaluating the transit value between two node indices for a given vehicle.
Definition: routing.h:2449
void SetBreakIntervalsOfVehicle(std::vector< IntervalVar * > breaks, int vehicle, std::vector< int64 > node_visit_transits, std::function< int64(int64, int64)> delays)
Deprecated, sets pre_travel(i, j) = node_visit_transit[i] and post_travel(i, j) = delays(i,...
int64 GetLastPossibleLessOrEqualValueForNode(int64 index, int64 max_value) const
Returns the largest value outside the forbidden intervals of node 'index' that is less than or equal ...
Definition: routing.h:2428
int64 ShortestTransitionSlack(int64 node) const
It makes sense to use the function only for self-dependent dimension.
void SetCumulVarSoftUpperBound(int64 index, int64 upper_bound, int64 coefficient)
Sets a soft upper bound to the cumul variable of a given variable index.
IntVar * TransitVar(int64 index) const
Definition: routing.h:2387
IntVar * SlackVar(int64 index) const
Definition: routing.h:2389
const std::vector< int64 > & vehicle_span_cost_coefficients() const
Definition: routing.h:2677
const std::vector< std::pair< int64, int64 > > & GetBreakDistanceDurationOfVehicle(int vehicle) const
Returns the pairs (distance, duration) specified by break distance constraints.
SortedDisjointIntervalList GetAllowedIntervalsInRange(int64 index, int64 min_value, int64 max_value) const
Returns allowed intervals for a given node in a given interval.
const ReverseArcListGraph< int, int > & GetPathPrecedenceGraph() const
Accessors.
Definition: routing.h:2623
void SetCumulVarSoftLowerBound(int64 index, int64 lower_bound, int64 coefficient)
Sets a soft lower bound to the cumul variable of a given variable index.
const std::vector< IntVar * > & slacks() const
Definition: routing.h:2397
void SetBreakIntervalsOfVehicle(std::vector< IntervalVar * > breaks, int vehicle, std::vector< int64 > node_visit_transits)
Deprecated, sets pre_travel(i, j) = node_visit_transit[i].
void SetBreakIntervalsOfVehicle(std::vector< IntervalVar * > breaks, int vehicle, int pre_travel_evaluator, int post_travel_evaluator)
Sets the breaks for a given vehicle.
const std::vector< NodePrecedence > & GetNodePrecedences() const
Definition: routing.h:2656
bool HasCumulVarPiecewiseLinearCost(int64 index) const
Returns true if a piecewise linear cost has been set for a given variable index.
void SetGlobalSpanCostCoefficient(int64 coefficient)
Sets a cost proportional to the global dimension span, that is the difference between the largest val...
bool HasCumulVarSoftUpperBound(int64 index) const
Returns true if a soft upper bound has been set for a given variable index.
bool HasSoftSpanUpperBounds() const
Definition: routing.h:2707
int64 GetCumulVarSoftUpperBoundCoefficient(int64 index) const
Returns the cost coefficient of the soft upper bound of a cumul variable for a given variable index.
~RoutingDimension()
int GetPostTravelEvaluatorOfVehicle(int vehicle) const
SimpleBoundCosts::BoundCost GetQuadraticCostSoftSpanUpperBoundForVehicle(int vehicle) const
Definition: routing.h:2730
const std::vector< SortedDisjointIntervalList > & forbidden_intervals() const
Returns forbidden intervals for each node.
Definition: routing.h:2400
int64 GetSpanUpperBoundForVehicle(int vehicle) const
Definition: routing.h:2665
Filter-based heuristic dedicated to routing.
Definition: routing.h:3076
~RoutingFilteredHeuristic() override
Definition: routing.h:3080
int GetStartChainEnd(int vehicle) const
Returns the end of the start chain of vehicle,.
Definition: routing.h:3086
RoutingModel * model() const
Definition: routing.h:3084
int GetEndChainStart(int vehicle) const
Returns the start of the end chain of vehicle,.
Definition: routing.h:3088
virtual void SetVehicleIndex(int64 node, int vehicle)
Definition: routing.h:3102
void MakeUnassignedNodesUnperformed()
Make all unassigned nodes unperformed.
void MakeDisjunctionNodesUnperformed(int64 node)
Make nodes in the same disjunction as 'node' unperformed.
const Assignment * BuildSolutionFromRoutes(const std::function< int64(int64)> &next_accessor)
Builds a solution starting from the routes formed by the next accessor.
virtual void ResetVehicleIndices()
Definition: routing.h:3103
void MakePartiallyPerformedPairsUnperformed()
Make all partially performed pickup and delivery pairs unperformed.
bool VehicleIsEmpty(int vehicle) const
Definition: routing.h:3104
RoutingFilteredHeuristic(RoutingModel *model, LocalSearchFilterManager *filter_manager)
Manager for any NodeIndex <-> variable index conversion.
Definition: routing_index_manager.h:48
Definition: routing.h:213
std::pair< int, bool > AddConstantDimensionWithSlack(int64 value, int64 capacity, int64 slack_max, bool fix_start_cumul_to_zero, const std::string &name)
Creates a dimension where the transit variable is constrained to be equal to 'value'; 'capacity' is t...
bool AddDimensionWithVehicleTransitAndCapacity(const std::vector< int > &evaluator_indices, int64 slack_max, std::vector< int64 > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
int64 GetNumberOfDecisionsInFirstSolution(const RoutingSearchParameters &search_parameters) const
Returns statistics on first solution search, number of decisions sent to filters, number of decisions...
std::pair< int, bool > AddConstantDimension(int64 value, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
Definition: routing.h:473
const std::vector< std::pair< DisjunctionIndex, DisjunctionIndex > > & GetPickupAndDeliveryDisjunctions() const
Definition: routing.h:750
void SetFixedCostOfAllVehicles(int64 cost)
Sets the fixed cost of all vehicle routes.
void AddAtSolutionCallback(std::function< void()> callback)
Adds a callback called each time a solution is found during the search.
const std::string & GetPrimaryConstrainedDimension() const
Get the primary constrained dimension, or an empty string if it is unset.
Definition: routing.h:608
std::function< std::vector< operations_research::IntVar * >(RoutingModel *)> GetTabuVarsCallback
Sets the callback returning the variable to use for the Tabu Search metaheuristic.
Definition: routing.h:1368
void AddSearchMonitor(SearchMonitor *const monitor)
Adds a search monitor to the search used to solve the routing model.
int nodes() const
Sizes and indices Returns the number of nodes in the model.
Definition: routing.h:1343
const std::vector< int > & GetSameVehicleIndicesOfIndex(int node) const
Returns variable indices of nodes constrained to be on the same route.
Definition: routing.h:1280
bool ArcIsMoreConstrainedThanArc(int64 from, int64 to1, int64 to2)
Returns whether the arc from->to1 is more constrained than from->to2, taking into account,...
int64 GetDisjunctionMaxCardinality(DisjunctionIndex index) const
Returns the maximum number of possible active nodes of the node disjunction of index 'index'.
Definition: routing.h:663
const std::vector< absl::flat_hash_set< int > > & GetRequiredTypeAlternativesWhenRemovingType(int type) const
Returns the set of requirement alternatives when removing the given type.
void AddLocalSearchOperator(LocalSearchOperator *ls_operator)
Adds a local search operator to the set of operators used to solve the vehicle routing problem.
void AddVariableTargetToFinalizer(IntVar *var, int64 target)
Add a variable to set the closest possible to the target value in the solution finalizer.
GlobalDimensionCumulOptimizer * GetMutableGlobalCumulOptimizer(const RoutingDimension &dimension) const
Returns the global/local dimension cumul optimizer for a given dimension, or nullptr if there is none...
Assignment * CompactAssignment(const Assignment &assignment) const
Returns a compacted version of the given assignment, in which all vehicles with id lower or equal to ...
IntVar * ActiveVehicleVar(int vehicle) const
Returns the active variable of the vehicle.
Definition: routing.h:1212
int64 End(int vehicle) const
Returns the variable index of the ending node of a vehicle route.
Definition: routing.h:1182
const std::vector< absl::flat_hash_set< int > > & GetRequiredTypeAlternativesWhenAddingType(int type) const
Returns the set of requirement alternatives when adding the given type.
RoutingTransitCallback1 TransitCallback1
Definition: routing.h:242
DecisionBuilder * MakeGuidedSlackFinalizer(const RoutingDimension *dimension, std::function< int64(int64)> initializer)
The next few members are in the public section only for testing purposes.
void AddPickupAndDelivery(int64 pickup, int64 delivery)
Notifies that index1 and index2 form a pair of nodes which should belong to the same route.
int GetNumberOfVisitTypes() const
Definition: routing.h:801
std::string DebugOutputAssignment(const Assignment &solution_assignment, const std::string &dimension_to_print) const
Print some debugging information about an assignment, including the feasible intervals of the CumulVa...
std::vector< std::vector< int64 > > GetRoutesFromAssignment(const Assignment &assignment)
Converts the solution in the given assignment to routes for all vehicles.
std::vector< std::pair< int64, int64 > > GetPerfectBinaryDisjunctions() const
Returns the list of all perfect binary disjunctions, as pairs of variable indices: a disjunction is "...
const std::vector< std::vector< int > > & GetTopologicallySortedVisitTypes() const
Definition: routing.h:803
void ForEachNodeInDisjunctionWithMaxCardinalityFromIndex(int64 index, int64 max_cardinality, F f) const
Calls f for each variable index of indices in the same disjunctions as the node corresponding to the ...
Definition: routing.h:639
CostClassIndex GetCostClassIndexOfVehicle(int64 vehicle) const
Get the cost class index of the given vehicle.
Definition: routing.h:1251
RoutingModel(const RoutingIndexManager &index_manager, const RoutingModelParameters ¶meters)
int GetVehicleClassesCount() const
Returns the number of different vehicle classes in the model.
Definition: routing.h:1278
int64 UnperformedPenalty(int64 var_index) const
Get the "unperformed" penalty of a node.
void SetPickupAndDeliveryPolicyOfAllVehicles(PickupAndDeliveryPolicy policy)
Sets the Pickup and delivery policy of all vehicles.
std::pair< int, bool > AddMatrixDimension(std::vector< std::vector< int64 > > values, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
Creates a dimension where the transit variable is constrained to be equal to 'values[i][next(i)]' for...
Assignment * MutablePreAssignment()
Definition: routing.h:1067
Assignment * CompactAndCheckAssignment(const Assignment &assignment) const
Same as CompactAssignment() but also checks the validity of the final compact solution; if it is not ...
bool ApplyLocksToAllVehicles(const std::vector< std::vector< int64 >> &locks, bool close_routes)
Applies lock chains to all vehicles to the next search, such that locks[p] is the lock chain for rout...
static RoutingModel::StateDependentTransit MakeStateDependentTransit(const std::function< int64(int64)> &f, int64 domain_start, int64 domain_end)
Creates a cached StateDependentTransit from an std::function.
int RegisterStateDependentTransitCallback(VariableIndexEvaluator2 callback)
const std::vector< std::pair< int, int > > & GetDeliveryIndexPairs(int64 node_index) const
Same as above for deliveries.
void AddToAssignment(IntVar *const var)
Adds an extra variable to the vehicle routing assignment.
bool IsVehicleAllowedForIndex(int vehicle, int64 index)
Returns true if a vehicle is allowed to visit a given node.
Definition: routing.h:694
const std::vector< std::unique_ptr< LocalDimensionCumulOptimizer > > & GetLocalDimensionCumulOptimizers() const
Definition: routing.h:572
const TransitCallback1 & UnaryTransitCallbackOrNull(int callback_index) const
Definition: routing.h:417
int64 Next(const Assignment &assignment, int64 index) const
Assignment inspection Returns the variable index of the node directly after the node corresponding to...
void AddVariableMinimizedByFinalizer(IntVar *var)
Adds a variable to minimize in the solution finalizer.
VisitTypePolicy
Set the node visit types and incompatibilities/requirements between the types (see below).
Definition: routing.h:773
@ TYPE_ADDED_TO_VEHICLE
When visited, the number of types 'T' on the vehicle increases by one.
Definition: routing.h:775
@ ADDED_TYPE_REMOVED_FROM_VEHICLE
When visited, one instance of type 'T' previously added to the route (TYPE_ADDED_TO_VEHICLE),...
Definition: routing.h:780
@ TYPE_ON_VEHICLE_UP_TO_VISIT
With the following policy, the visit enforces that type 'T' is considered on the route from its start...
Definition: routing.h:783
bool AddDimensionDependentDimensionWithVehicleCapacity(const std::vector< int > &pure_transits, const std::vector< int > &dependent_transits, const RoutingDimension *base_dimension, int64 slack_max, std::vector< int64 > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
Creates a dimension with transits depending on the cumuls of another dimension.
Definition: routing.h:510
int64 GetFixedCostOfVehicle(int vehicle) const
Returns the route fixed cost taken into account if the route of the vehicle is not empty,...
void SetFixedCostOfVehicle(int64 cost, int vehicle)
Sets the fixed cost of one vehicle route.
int64 GetArcCostForVehicle(int64 from_index, int64 to_index, int64 vehicle) const
Returns the cost of the transit arc between two nodes for a given vehicle.
LocalDimensionCumulOptimizer * GetMutableLocalCumulOptimizer(const RoutingDimension &dimension) const
const absl::flat_hash_set< int > & GetHardTypeIncompatibilitiesOfType(int type) const
Returns visit types incompatible with a given type.
const Assignment * Solve(const Assignment *assignment=nullptr)
Solves the current routing model; closes the current model.
void AddLocalSearchFilter(LocalSearchFilter *filter)
Adds a custom local search filter to the list of filters used to speed up local search by pruning unf...
Definition: routing.h:1169
Assignment * RestoreAssignment(const Assignment &solution)
Restores an assignment as a solution in the routing model and returns the new solution.
DecisionBuilder * MakeSelfDependentDimensionFinalizer(const RoutingDimension *dimension)
SWIG
const Assignment * SolveFromAssignmentWithParameters(const Assignment *assignment, const RoutingSearchParameters &search_parameters, std::vector< const Assignment * > *solutions=nullptr)
const Assignment * PackCumulsOfOptimizerDimensionsFromAssignment(const Assignment *original_assignment, absl::Duration duration_limit)
For every dimension in the model with an optimizer in local/global_dimension_optimizers_,...
bool HasTemporalTypeRequirements() const
Definition: routing.h:870
void AddPickupAndDeliverySets(DisjunctionIndex pickup_disjunction, DisjunctionIndex delivery_disjunction)
Same as AddPickupAndDelivery but notifying that the performed node from the disjunction of index 'pic...
RoutingTransitCallback2 TransitCallback2
Definition: routing.h:243
LocalDimensionCumulOptimizer * GetMutableLocalCumulMPOptimizer(const RoutingDimension &dimension) const
const std::vector< std::pair< int, int > > & GetPickupIndexPairs(int64 node_index) const
Returns pairs for which the node is a pickup; the first element of each pair is the index in the pick...
const std::vector< RoutingDimension * > & GetDimensions() const
Returns all dimensions of the model.
Definition: routing.h:559
int64 GetArcCostForFirstSolution(int64 from_index, int64 to_index) const
Returns the cost of the arc in the context of the first solution strategy.
const Solver::IndexEvaluator2 & first_solution_evaluator() const
Gets/sets the evaluator used during the search.
Definition: routing.h:963
bool AddDimensionWithVehicleTransits(const std::vector< int > &evaluator_indices, int64 slack_max, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
std::function< StateDependentTransit(int64, int64)> VariableIndexEvaluator2
Definition: routing.h:269
@ ROUTING_SUCCESS
Problem solved successfully after calling RoutingModel::Solve().
Definition: routing.h:220
@ ROUTING_FAIL
No solution found to the problem after calling RoutingModel::Solve().
Definition: routing.h:222
@ ROUTING_NOT_SOLVED
Problem not solved yet (before calling RoutingModel::Solve()).
Definition: routing.h:218
@ ROUTING_FAIL_TIMEOUT
Time limit reached before finding a solution with RoutingModel::Solve().
Definition: routing.h:224
bool HasVehicleWithCostClassIndex(CostClassIndex cost_class_index) const
Returns true iff the model contains a vehicle with the given cost_class_index.
Definition: routing.h:1260
void SetSweepArranger(SweepArranger *sweep_arranger)
Definition: routing.h:1158
void AddTemporalTypeIncompatibility(int type1, int type2)
SweepArranger * sweep_arranger() const
Returns the sweep arranger to be used by routing heuristics.
Definition: routing.h:1162
Assignment * ReadAssignment(const std::string &file_name)
Reads an assignment from a file and returns the current solution.
void SetVisitType(int64 index, int type, VisitTypePolicy type_policy)
bool RoutesToAssignment(const std::vector< std::vector< int64 >> &routes, bool ignore_inactive_indices, bool close_routes, Assignment *const assignment) const
Fills an assignment from a specification of the routes of the vehicles.
VehicleClassIndex GetVehicleClassIndexOfVehicle(int64 vehicle) const
Definition: routing.h:1273
IntVar * VehicleCostsConsideredVar(int vehicle) const
Returns the variable specifying whether or not costs are considered for vehicle.
Definition: routing.h:1217
void ConsiderEmptyRouteCostsForVehicle(bool consider_costs, int vehicle)
Definition: routing.h:950
int RegisterPositiveUnaryTransitCallback(TransitCallback1 callback)
void SetTabuVarsCallback(GetTabuVarsCallback tabu_var_callback)
const std::vector< IntVar * > & VehicleVars() const
Returns all vehicle variables of the model, such that VehicleVars(i) is the vehicle variable of the n...
Definition: routing.h:1203
void CloseVisitTypes()
This function should be called once all node visit types have been set and prior to adding any incomp...
void SetMaximumNumberOfActiveVehicles(int max_active_vehicles)
Constrains the maximum number of active vehicles, aka the number of vehicles which do not have an emp...
Definition: routing.h:900
const IndexPairs & GetImplicitUniquePickupAndDeliveryPairs() const
Returns implicit pickup and delivery pairs currently in the model.
Definition: routing.h:757
const std::vector< DisjunctionIndex > & GetDisjunctionIndices(int64 index) const
Returns the indices of the disjunctions to which an index belongs.
Definition: routing.h:631
static const int64 kNoPenalty
Constant used to express a hard constraint instead of a soft penalty.
Definition: routing.h:384
std::vector< RoutingDimension * > GetDimensionsWithSoftOrSpanCosts() const
Returns dimensions with soft or vehicle span costs.
void IgnoreDisjunctionsAlreadyForcedToZero()
SPECIAL: Makes the solver ignore all the disjunctions whose active variables are all trivially zero (...
void SetPickupAndDeliveryPolicyOfVehicle(PickupAndDeliveryPolicy policy, int vehicle)
int RegisterTransitCallback(TransitCallback2 callback)
IntVar * VehicleVar(int64 index) const
Returns the vehicle variable of the node corresponding to index.
Definition: routing.h:1222
const std::vector< std::unique_ptr< LocalDimensionCumulOptimizer > > & GetLocalDimensionCumulMPOptimizers() const
Definition: routing.h:576
int64 GetArcCostForClass(int64 from_index, int64 to_index, int64 cost_class_index) const
Returns the cost of the segment between two nodes for a given cost class.
void AddWeightedVariableMinimizedByFinalizer(IntVar *var, int64 cost)
Adds a variable to minimize in the solution finalizer, with a weighted priority: the higher the more ...
int GetMaximumNumberOfActiveVehicles() const
Returns the maximum number of active vehicles.
Definition: routing.h:904
int GetVisitType(int64 index) const
RoutingDimensionIndex DimensionIndex
Definition: routing.h:239
bool AddDimensionDependentDimensionWithVehicleCapacity(int transit, const RoutingDimension *base_dimension, int64 slack_max, int64 vehicle_capacity, bool fix_start_cumul_to_zero, const std::string &name)
Homogeneous versions of the functions above.
void AssignmentToRoutes(const Assignment &assignment, std::vector< std::vector< int64 >> *const routes) const
Converts the solution in the given assignment to routes for all vehicles.
Assignment * ReadAssignmentFromRoutes(const std::vector< std::vector< int64 >> &routes, bool ignore_inactive_indices)
Restores the routes as the current solution.
void AddSoftSameVehicleConstraint(const std::vector< int64 > &indices, int64 cost)
Adds a soft constraint to force a set of variable indices to be on the same vehicle.
const absl::flat_hash_set< int > & GetTemporalTypeIncompatibilitiesOfType(int type) const
const std::vector< int > & GetPairIndicesOfType(int type) const
const IndexPairs & GetPickupAndDeliveryPairs() const
Returns pickup and delivery pairs currently in the model.
Definition: routing.h:746
const std::vector< int64 > & GetAmortizedLinearCostFactorOfVehicles() const
Definition: routing.h:943
void AddRequiredTypeAlternativesWhenRemovingType(int dependent_type, absl::flat_hash_set< int > required_type_alternatives)
The following requirements apply when visiting dependent nodes that remove their type from the route,...
static std::unique_ptr< LocalSearchOperator > MakeGreedyDescentLSOperator(std::vector< IntVar * > variables)
Perhaps move it to constraint_solver.h.
int64 GetHomogeneousCost(int64 from_index, int64 to_index) const
Returns the cost of the segment between two nodes supposing all vehicle costs are the same (returns t...
Definition: routing.h:1236
bool AddDimensionDependentDimensionWithVehicleCapacity(const std::vector< int > &transits, const RoutingDimension *base_dimension, int64 slack_max, std::vector< int64 > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
As above, but pure_transits are taken to be zero evaluators.
int RegisterPositiveTransitCallback(TransitCallback2 callback)
PickupAndDeliveryPolicy
Types of precedence policy applied to pickup and delivery pairs.
Definition: routing.h:230
@ PICKUP_AND_DELIVERY_LIFO
Deliveries must be performed in reverse order of pickups.
Definition: routing.h:234
@ PICKUP_AND_DELIVERY_FIFO
Deliveries must be performed in the same order as pickups.
Definition: routing.h:236
DisjunctionIndex AddDisjunction(const std::vector< int64 > &indices, int64 penalty=kNoPenalty, int64 max_cardinality=1)
Adds a disjunction constraint on the indices: exactly 'max_cardinality' of the indices are active.
void CloseModelWithParameters(const RoutingSearchParameters &search_parameters)
Same as above taking search parameters (as of 10/2015 some the parameters have to be set when closing...
int GetNumberOfDisjunctions() const
Returns the number of node disjunctions in the model.
Definition: routing.h:667
void AddVariableMaximizedByFinalizer(IntVar *var)
Adds a variable to maximize in the solution finalizer (see above for information on the solution fina...
const std::vector< IntVar * > & Nexts() const
Returns all next variables of the model, such that Nexts(i) is the next variable of the node correspo...
Definition: routing.h:1200
const std::vector< int64 > & GetAmortizedQuadraticCostFactorOfVehicles() const
Definition: routing.h:946
IntVar * ApplyLocks(const std::vector< int64 > &locks)
Applies a lock chain to the next search.
int VehicleIndex(int64 index) const
Returns the vehicle of the given start/end index, and -1 if the given index is not a vehicle start/en...
Definition: routing.h:1189
bool HasTypeRegulations() const
Returns true iff the model has any incompatibilities or requirements set on node types.
Definition: routing.h:876
void SetFirstSolutionEvaluator(Solver::IndexEvaluator2 evaluator)
Takes ownership of evaluator.
Definition: routing.h:968
RoutingVehicleClassIndex VehicleClassIndex
Definition: routing.h:241
int RegisterUnaryTransitVector(std::vector< int64 > values)
Registers 'callback' and returns its index.
bool AddDimension(int evaluator_index, int64 slack_max, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
Model creation.
void AddIntervalToAssignment(IntervalVar *const interval)
void SetArcCostEvaluatorOfAllVehicles(int evaluator_index)
Sets the cost function of the model such that the cost of a segment of a route between node 'from' an...
void SetAmortizedCostFactorsOfAllVehicles(int64 linear_cost_factor, int64 quadratic_cost_factor)
The following methods set the linear and quadratic cost factors of vehicles (must be positive values)...
int GetNonZeroCostClassesCount() const
Ditto, minus the 'always zero', built-in cost class.
Definition: routing.h:1270
bool HasSameVehicleTypeRequirements() const
Returns true iff any same-route (resp.
Definition: routing.h:867
IntVar * CostVar() const
Returns the global cost variable which is being minimized.
Definition: routing.h:1224
void SetPrimaryConstrainedDimension(const std::string &dimension_name)
Set the given dimension as "primary constrained".
Definition: routing.h:603
Constraint * MakePathSpansAndTotalSlacks(const RoutingDimension *dimension, std::vector< IntVar * > spans, std::vector< IntVar * > total_slacks)
For every vehicle of the routing model:
const VariableIndexEvaluator2 & StateDependentTransitCallback(int callback_index) const
Definition: routing.h:421
VisitTypePolicy GetVisitTypePolicy(int64 index) const
void SetAssignmentFromOtherModelAssignment(Assignment *target_assignment, const RoutingModel *source_model, const Assignment *source_assignment)
Given a "source_model" and its "source_assignment", resets "target_assignment" with the IntVar variab...
void AddSameVehicleRequiredTypeAlternatives(int dependent_type, absl::flat_hash_set< int > required_type_alternatives)
Requirements: NOTE: As of 2019-04, cycles in the requirement graph are not supported,...
int RegisterTransitMatrix(std::vector< std::vector< int64 > > values)
std::vector< std::string > GetAllDimensionNames() const
Outputs the names of all dimensions added to the routing engine.
bool IsMatchingModel() const
Returns true if a vehicle/node matching problem is detected.
RoutingDimension * GetMutableDimension(const std::string &dimension_name) const
Returns a dimension from its name.
bool AddDimensionWithVehicleCapacity(int evaluator_index, int64 slack_max, std::vector< int64 > vehicle_capacities, bool fix_start_cumul_to_zero, const std::string &name)
int RegisterUnaryTransitCallback(TransitCallback1 callback)
int64 GetDepot() const
Returns the variable index of the first starting or ending node of all routes.
bool WriteAssignment(const std::string &file_name) const
Writes the current solution to a file containing an AssignmentProto.
RoutingCostClassIndex CostClassIndex
Definition: routing.h:238
bool HasTemporalTypeIncompatibilities() const
Definition: routing.h:825
int GetCostClassesCount() const
Returns the number of different cost classes in the model.
Definition: routing.h:1268
const TransitCallback2 & TransitCallback(int callback_index) const
Definition: routing.h:413
int GetNumOfSingletonNodes() const
Returns the number of non-start/end nodes which do not appear in a pickup/delivery pair.
const std::vector< std::unique_ptr< GlobalDimensionCumulOptimizer > > & GetGlobalDimensionCumulOptimizers() const
Returns [global|local]_dimension_optimizers_, which are empty if the model has not been closed.
Definition: routing.h:568
void AddRequiredTypeAlternativesWhenAddingType(int dependent_type, absl::flat_hash_set< int > required_type_alternatives)
If type_D depends on type_R when adding type_D, any node_D of type_D and VisitTypePolicy TYPE_ADDED_T...
operations_research::FirstSolutionStrategy::Value GetAutomaticFirstSolutionStrategy() const
Returns the automatic first solution strategy selected.
Definition: routing.h:1357
absl::Duration RemainingTime() const
Returns the time left in the search limit.
Definition: routing.h:1336
~RoutingModel()
void CloseModel()
Closes the current routing model; after this method is called, no modification to the model can be do...
const std::vector< int64 > & GetDisjunctionIndices(DisjunctionIndex index) const
Returns the variable indices of the nodes in the disjunction of index 'index'.
Definition: routing.h:652
static const DimensionIndex kNoDimension
Constant used to express the "no dimension" index, returned when a dimension name does not correspond...
Definition: routing.h:392
const Assignment *const PreAssignment() const
Returns an assignment used to fix some of the variables of the problem.
Definition: routing.h:1066
bool CostsAreHomogeneousAcrossVehicles() const
Whether costs are homogeneous across all vehicles.
Definition: routing.h:1231
PickupAndDeliveryPolicy GetPickupAndDeliveryPolicyOfVehicle(int vehicle) const
void SetAmortizedCostFactorsOfVehicle(int64 linear_cost_factor, int64 quadratic_cost_factor, int vehicle)
Sets the linear and quadratic cost factor of the given vehicle.
bool IsStart(int64 index) const
Returns true if 'index' represents the first node of a route.
bool IsEnd(int64 index) const
Returns true if 'index' represents the last node of a route.
Definition: routing.h:1186
const std::vector< absl::flat_hash_set< int > > & GetSameVehicleRequiredTypeAlternativesOfType(int type) const
Returns the set of same-vehicle requirement alternatives for the given type.
bool AddDimensionDependentDimensionWithVehicleCapacity(int pure_transit, int dependent_transit, const RoutingDimension *base_dimension, int64 slack_max, int64 vehicle_capacity, bool fix_start_cumul_to_zero, const std::string &name)
const VehicleTypeContainer & GetVehicleTypeContainer() const
Definition: routing.h:1285
void SetArcCostEvaluatorOfVehicle(int evaluator_index, int vehicle)
Sets the cost function for a given vehicle route.
int64 UnperformedPenaltyOrValue(int64 default_value, int64 var_index) const
Same as above except that it returns default_value instead of 0 when penalty is not well defined (def...
std::pair< int, bool > AddVectorDimension(std::vector< int64 > values, int64 capacity, bool fix_start_cumul_to_zero, const std::string &name)
Creates a dimension where the transit variable is constrained to be equal to 'values[i]' for node i; ...
int64 ComputeLowerBound()
Computes a lower bound to the routing problem solving a linear assignment problem.
const RoutingDimension & GetDimensionOrDie(const std::string &dimension_name) const
Returns a dimension from its name. Dies if the dimension does not exist.
bool HasDimension(const std::string &dimension_name) const
Returns true if a dimension exists for a given dimension name.
bool AreEmptyRouteCostsConsideredForVehicle(int vehicle) const
Definition: routing.h:955
bool IsVehicleUsed(const Assignment &assignment, int vehicle) const
Returns true if the route of 'vehicle' is non empty in 'assignment'.
int64 GetNumberOfRejectsInFirstSolution(const RoutingSearchParameters &search_parameters) const
static const DisjunctionIndex kNoDisjunction
Constant used to express the "no disjunction" index, returned when a node does not appear in any disj...
Definition: routing.h:388
RoutingModel(const RoutingIndexManager &index_manager)
Constructor taking an index manager.
const Assignment * SolveWithParameters(const RoutingSearchParameters &search_parameters, std::vector< const Assignment * > *solutions=nullptr)
Solves the current routing model with the given parameters.
RoutingDisjunctionIndex DisjunctionIndex
Definition: routing.h:240
IntVar * ActiveVar(int64 index) const
Returns the active variable of the node corresponding to index.
Definition: routing.h:1209
std::vector< std::vector< std::pair< int64, int64 > > > GetCumulBounds(const Assignment &solution_assignment, const RoutingDimension &dimension)
Returns a vector cumul_bounds, for which cumul_bounds[i][j] is a pair containing the minimum and maxi...
const std::vector< int > & GetSingleNodesOfType(int type) const
void SetAllowedVehiclesForIndex(const std::vector< int > &vehicles, int64 index)
Sets the vehicles which can visit a given node.
Filter-based decision builder which builds a solution by using Clarke & Wright's Savings heuristic.
Definition: routing.h:3635
int StartNewRouteWithBestVehicleOfType(int type, int64 before_node, int64 after_node)
Finds the best available vehicle of type "type" to start a new route to serve the arc before_node-->a...
std::unique_ptr< VehicleTypeCurator > vehicle_type_curator_
Definition: routing.h:3699
std::pair< int64, int64 > Saving
Definition: routing.h:3660
bool BuildSolutionInternal() override
Virtual method to redefine how to build a solution.
int64 GetVehicleTypeFromSaving(const Saving &saving) const
Returns the cost class from a saving.
Definition: routing.h:3670
std::unique_ptr< SavingsContainer< Saving > > savings_container_
Definition: routing.h:3697
~SavingsFilteredHeuristic() override
int64 GetSavingValue(const Saving &saving) const
Returns the saving value from a saving.
Definition: routing.h:3682
virtual double ExtraSavingsMemoryMultiplicativeFactor() const =0
int64 GetBeforeNodeFromSaving(const Saving &saving) const
Returns the "before node" from a saving.
Definition: routing.h:3674
int64 GetAfterNodeFromSaving(const Saving &saving) const
Returns the "after node" from a saving.
Definition: routing.h:3678
SavingsFilteredHeuristic(RoutingModel *model, const RoutingIndexManager *manager, SavingsParameters parameters, LocalSearchFilterManager *filter_manager)
virtual void BuildRoutesFromSavings()=0
Base class of all search limits.
Definition: constraint_solver.h:4239
A search monitor is a simple set of callbacks to monitor all search events.
Definition: constraint_solver.h:3635
~SequentialSavingsFilteredHeuristic() override
Definition: routing.h:3744
SequentialSavingsFilteredHeuristic(RoutingModel *model, const RoutingIndexManager *manager, SavingsParameters parameters, LocalSearchFilterManager *filter_manager)
Definition: routing.h:3739
std::string DebugString() const override
Definition: routing.h:3745
A structure meant to store soft bounds and associated violation constants.
Definition: routing.h:2329
BoundCost & bound_cost(int element)
Definition: routing.h:2337
SimpleBoundCosts(int num_bounds, BoundCost default_bound_cost)
Definition: routing.h:2335
BoundCost bound_cost(int element) const
Definition: routing.h:2338
SimpleBoundCosts(const SimpleBoundCosts &)=delete
SimpleBoundCosts operator=(const SimpleBoundCosts &)=delete
std::function< bool(int64, int64, int64)> VariableValueComparator
Definition: constraint_solver.h:756
std::function< int64(int64, int64)> IndexEvaluator2
Definition: constraint_solver.h:744
Class to arrange indices by by their distance and their angles from the depot.
Definition: routing.h:2869
void ArrangeIndices(std::vector< int64 > *indices)
SweepArranger(const std::vector< std::pair< int64, int64 >> &points)
void SetSectors(int sectors)
Definition: routing.h:2874
virtual ~SweepArranger()
Definition: routing.h:2872
Checker for type incompatibilities.
Definition: routing.h:2220
TypeIncompatibilityChecker(const RoutingModel &model, bool check_hard_incompatibilities)
~TypeIncompatibilityChecker() override
Definition: routing.h:2224
virtual bool HasRegulationsToCheck() const =0
virtual ~TypeRegulationsChecker()
Definition: routing.h:2163
virtual bool CheckTypeRegulations(int type, VisitTypePolicy policy, int pos)=0
bool CheckVehicle(int vehicle, const std::function< int64(int64)> &next_accessor)
virtual void OnInitializeCheck()
Definition: routing.h:2206
TypeRegulationsChecker(const RoutingModel &model)
virtual bool FinalizeCheck() const
Definition: routing.h:2210
bool TypeCurrentlyOnRoute(int type, int pos) const
Returns true iff there's at least one instance of the given type on the route when scanning the route...
const RoutingModel & model_
Definition: routing.h:2212
void InitializeCheck(int vehicle, const std::function< int64(int64)> &next_accessor)
bool TypeOccursOnRoute(int type) const
Returns true iff any occurrence of the given type was seen on the route, i.e.
The following constraint ensures that incompatibilities and requirements between types are respected.
Definition: routing.h:2300
void Post() override
This method is called when the constraint is processed by the solver.
void InitialPropagate() override
This method performs the initial propagation of the constraint.
TypeRegulationsConstraint(const RoutingModel &model)
~TypeRequirementChecker() override
Definition: routing.h:2240
TypeRequirementChecker(const RoutingModel &model)
Definition: routing.h:2238
Helper class that manages vehicles.
Definition: routing.h:2894
void Update(const std::function< bool(int)> &remove_vehicle)
Goes through all the currently stored vehicles and removes vehicles for which remove_vehicle() return...
std::pair< int, int > GetCompatibleVehicleOfType(int type, std::function< bool(int)> vehicle_is_compatible, std::function< bool(int)> stop_and_return_vehicle)
Searches for the best compatible vehicle of the given type, i.e.
VehicleTypeCurator(const RoutingModel::VehicleTypeContainer &vehicle_type_container)
Definition: routing.h:2896
void Reset(const std::function< bool(int)> &store_vehicle)
Resets the vehicles stored, storing only vehicles from the vehicle_type_container_ for which store_ve...
void ReinjectVehicleOfClass(int vehicle, int vehicle_class, int64 fixed_cost)
Definition: routing.h:2924
int GetLowestFixedCostVehicleOfType(int type) const
Definition: routing.h:2912
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: constraint_solver.h:106
std::pair< std::vector< int64 >, std::vector< int64 > > RoutingIndexPair
Definition: routing_types.h:44
void AppendLightWeightDimensionFilters(const PathState *path_state, const std::vector< RoutingDimension * > &dimensions, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
IntVarLocalSearchFilter * MakeTypeRegulationsFilter(const RoutingModel &routing_model)
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 fi...
void FillPathEvaluation(const std::vector< int64 > &path, const RoutingModel::TransitCallback2 &evaluator, std::vector< int64 > *values)
IntVarLocalSearchFilter * MakePathCumulFilter(const RoutingDimension &dimension, const RoutingSearchParameters ¶meters, bool propagate_own_objective_value, bool filter_objective_cost, bool can_use_lp=true)
IntVarLocalSearchFilter * MakeVehicleVarFilter(const RoutingModel &routing_model)
IntVarLocalSearchFilter * MakeCumulBoundsPropagatorFilter(const RoutingDimension &dimension)
void FillTravelBoundsOfVehicle(int vehicle, const std::vector< int64 > &path, const RoutingDimension &dimension, TravelBounds *travel_bounds)
IntVarLocalSearchFilter * MakeCPFeasibilityFilter(RoutingModel *routing_model)
void AppendTasksFromPath(const std::vector< int64 > &path, const TravelBounds &travel_bounds, const RoutingDimension &dimension, DisjunctivePropagator::Tasks *tasks)
IntVarLocalSearchFilter * MakeMaxActiveVehiclesFilter(const RoutingModel &routing_model)
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.
std::function< int64(int64, int64)> RoutingTransitCallback2
Definition: routing_types.h:42
IntVarLocalSearchFilter * MakeVehicleAmortizedCostFilter(const RoutingModel &routing_model)
std::function< int64(int64)> RoutingTransitCallback1
Definition: routing_types.h:41
void AppendDimensionCumulFilters(const std::vector< RoutingDimension * > &dimensions, const RoutingSearchParameters ¶meters, bool filter_objective_cost, std::vector< LocalSearchFilterManager::FilterEvent > *filters)
IntVarLocalSearchFilter * MakeGlobalLPCumulFilter(GlobalDimensionCumulOptimizer *optimizer, bool filter_objective_cost)
IntVarLocalSearchFilter * MakeNodeDisjunctionFilter(const RoutingModel &routing_model)
IntVarLocalSearchFilter * MakePickupDeliveryFilter(const RoutingModel &routing_model, const RoutingModel::IndexPairs &pairs, const std::vector< RoutingModel::PickupAndDeliveryPolicy > &vehicle_policies)
IntVarLocalSearchFilter * MakeVehicleBreaksFilter(const RoutingModel &routing_model, const RoutingDimension &dimension)
void AppendTasksFromIntervals(const std::vector< IntervalVar * > &intervals, DisjunctivePropagator::Tasks *tasks)
std::vector< RoutingIndexPair > RoutingIndexPairs
Definition: routing_types.h:45
int64 distance
Definition: routing.h:3129
bool operator<(const StartEndValue &other) const
Definition: routing.h:3132
int vehicle
Definition: routing.h:3130
A structure to hold tasks described by their features.
Definition: routing.h:1961
std::vector< int64 > end_max
Definition: routing.h:1968
std::vector< int64 > start_min
Definition: routing.h:1963
std::vector< int64 > duration_min
Definition: routing.h:1965
std::vector< int64 > start_max
Definition: routing.h:1964
std::vector< const SortedDisjointIntervalList * > forbidden_intervals
Definition: routing.h:1970
std::vector< bool > is_preemptible
Definition: routing.h:1969
std::vector< int64 > duration_max
Definition: routing.h:1966
std::vector< std::pair< int64, int64 > > distance_duration
Definition: routing.h:1971
std::vector< int64 > end_min
Definition: routing.h:1967
Definition: routing.h:3198
double neighbors_ratio
If neighbors_ratio < 1 then for each node only this ratio of its neighbors leading to the smallest ar...
Definition: routing.h:3209
bool is_sequential
Whether the routes are constructed sequentially or in parallel.
Definition: routing.h:3200
int64 min_neighbors
Definition: routing.h:3210
double farthest_seeds_ratio
The ratio of routes on which to insert farthest nodes as seeds before starting the cheapest insertion...
Definition: routing.h:3203
bool use_neighbors_ratio_for_initialization
If true, only closest neighbors (see neighbors_ratio and min_neighbors) are considered as insertion p...
Definition: routing.h:3214
bool add_unperformed_entries
If true, entries are created for making the nodes/pairs unperformed, and when the cost of making a no...
Definition: routing.h:3219
int64 first_node
Definition: routing.h:2648
int64 second_node
Definition: routing.h:2649
SUBTLE: The vehicle's fixed cost is skipped on purpose here, because we can afford to do so:
Definition: routing.h:297
const RoutingDimension * dimension
Definition: routing.h:300
int64 transit_evaluator_class
Definition: routing.h:298
int64 cost_coefficient
Definition: routing.h:299
bool operator<(const DimensionCost &cost) const
Definition: routing.h:301
CostClass(int evaluator_index)
Definition: routing.h:311
int evaluator_index
Index of the arc cost evaluator, registered in the RoutingModel class.
Definition: routing.h:275
static bool LessThan(const CostClass &a, const CostClass &b)
Comparator for STL containers and algorithms.
Definition: routing.h:315
operations_research::RoutingModel::CostClass::dimension_transit_evaluator_class_and_cost_coefficient
std::vector< DimensionCost > dimension_transit_evaluator_class_and_cost_coefficient
Definition: routing.h:309
What follows is relevant for models with time/state dependent transits.
Definition: routing.h:264
RangeIntToIntFunction * transit
Definition: routing.h:265
absl::StrongVector< DimensionIndex, int64 > dimension_capacities
Definition: routing.h:343
absl::StrongVector< DimensionIndex, int64 > dimension_evaluator_classes
dimension_evaluators[d]->Run(from, to) is the transit value of arc from->to for a dimension d.
Definition: routing.h:346
static bool LessThan(const VehicleClass &a, const VehicleClass &b)
Comparator for STL containers and algorithms.
absl::StrongVector< DimensionIndex, int64 > dimension_start_cumuls_min
Bounds of cumul variables at start and end vehicle nodes.
Definition: routing.h:339
absl::StrongVector< DimensionIndex, int64 > dimension_end_cumuls_min
Definition: routing.h:341
absl::StrongVector< DimensionIndex, int64 > dimension_end_cumuls_max
Definition: routing.h:342
int end_equivalence_class
Definition: routing.h:336
uint64 unvisitable_nodes_fprint
Fingerprint of unvisitable non-start/end nodes.
Definition: routing.h:348
absl::StrongVector< DimensionIndex, int64 > dimension_start_cumuls_max
Definition: routing.h:340
int64 fixed_cost
Definition: routing.h:361
bool operator<(const VehicleClassEntry &other) const
Definition: routing.h:363
int vehicle_class
Definition: routing.h:360
Struct used to sort and store vehicles by their type.
Definition: routing.h:358
std::vector< int > type_index_of_vehicle
Definition: routing.h:376
int NumTypes() const
Definition: routing.h:369
std::vector< std::set< VehicleClassEntry > > sorted_vehicle_classes_per_type
Definition: routing.h:378
int Type(int vehicle) const
Definition: routing.h:371
std::vector< std::deque< int > > vehicles_per_vehicle_class
Definition: routing.h:379
Definition: routing.h:2031
std::vector< int64 > max_travels
Definition: routing.h:2033
std::vector< int64 > min_travels
Definition: routing.h:2032
std::vector< int64 > post_travels
Definition: routing.h:2035
std::vector< int64 > pre_travels
Definition: routing.h:2034