C++ Reference
C++ Reference: Routing
Detailed Description
Dimensions represent quantities accumulated at nodes along the routes.
They represent quantities such as weights or volumes carried along the route, or distance or times.
Quantities at a node are represented by "cumul" variables and the increase or decrease of quantities between nodes are represented by "transit" variables. These variables are linked as follows:
if j == next(i), cumuls(j) = cumuls(i) + transits(i) + slacks(i) + state_dependent_transits(i)
where slack is a positive slack variable (can represent waiting times for a time dimension), and state_dependent_transits is a non-purely functional version of transits_. Favour transits over state_dependent_transits when possible, because purely functional callbacks allow more optimisations and make the model faster and easier to solve. for a given vehicle, it is passed as an external vector, it would be better to have this information here.
Classes | |
| struct | NodePrecedence |
Public Types | |
| typedef std::function< int64(int, int)> | PickupToDeliveryLimitFunction |
| Limits, in terms of maximum difference between the cumul variables, between the pickup and delivery alternatives belonging to a single pickup/delivery pair in the RoutingModel. More... | |
Public Member Functions | |
| ~RoutingDimension () | |
| RoutingModel * | model () const |
| Returns the model on which the dimension was created. More... | |
| 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 the corresponding transit variable when the 'next' variable for 'from_index' is bound to 'to_index'. More... | |
| 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 vehicle can be obtained with vehicle_to_class()). More... | |
| IntVar * | CumulVar (int64 index) const |
| Get the cumul, transit and slack variables for the given node (given as int64 var index). More... | |
| IntVar * | TransitVar (int64 index) const |
| IntVar * | FixedTransitVar (int64 index) const |
| IntVar * | SlackVar (int64 index) const |
| const std::vector< IntVar * > & | cumuls () const |
| Like CumulVar(), TransitVar(), SlackVar() but return the whole variable vectors instead (indexed by int64 var index). More... | |
| const std::vector< IntVar * > & | fixed_transits () const |
| const std::vector< IntVar * > & | transits () const |
| const std::vector< IntVar * > & | slacks () const |
| const std::vector< SortedDisjointIntervalList > & | forbidden_intervals () const |
| Returns forbidden intervals for each node. More... | |
| SortedDisjointIntervalList | GetAllowedIntervalsInRange (int64 index, int64 min_value, int64 max_value) const |
| Returns allowed intervals for a given node in a given interval. More... | |
| int64 | GetFirstPossibleGreaterOrEqualValueForNode (int64 index, int64 min_value) const |
| Returns the smallest value outside the forbidden intervals of node 'index' that is greater than or equal to a given 'min_value'. More... | |
| 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 to a given 'max_value'. More... | |
| const std::vector< int64 > & | vehicle_capacities () const |
| Returns the capacities for all vehicles. More... | |
| const RoutingModel::TransitCallback2 & | transit_evaluator (int vehicle) const |
| Returns the callback evaluating the transit value between two node indices for a given vehicle. More... | |
| const RoutingModel::TransitCallback1 & | GetUnaryTransitEvaluator (int vehicle) const |
| Returns the unary callback evaluating the transit value between two node indices for a given vehicle. More... | |
| bool | AreVehicleTransitsPositive (int vehicle) const |
| Returns true iff the transit evaluator of 'vehicle' is positive for all arcs. More... | |
| int | vehicle_to_class (int vehicle) const |
| void | SetSpanUpperBoundForVehicle (int64 upper_bound, int vehicle) |
| !defined(SWIGCSHARP) && !defined(SWIGJAVA) !defined(SWIGPYTHON) More... | |
| void | SetSpanCostCoefficientForVehicle (int64 coefficient, int vehicle) |
| Sets a cost proportional to the dimension span on a given vehicle, or on all vehicles at once. More... | |
| void | SetSpanCostCoefficientForAllVehicles (int64 coefficient) |
| void | SetGlobalSpanCostCoefficient (int64 coefficient) |
| Sets a cost proportional to the global dimension span, that is the difference between the largest value of route end cumul variables and the smallest value of route start cumul variables. More... | |
| void | SetCumulVarPiecewiseLinearCost (int64 index, const PiecewiseLinearFunction &cost) |
| Sets a piecewise linear cost on the cumul variable of a given variable index. More... | |
| bool | HasCumulVarPiecewiseLinearCost (int64 index) const |
| Returns true if a piecewise linear cost has been set for a given variable index. More... | |
| const PiecewiseLinearFunction * | GetCumulVarPiecewiseLinearCost (int64 index) const |
| Returns the piecewise linear cost of a cumul variable for a given variable index. More... | |
| void | SetCumulVarSoftUpperBound (int64 index, int64 upper_bound, int64 coefficient) |
| Sets a soft upper bound to the cumul variable of a given variable index. More... | |
| bool | HasCumulVarSoftUpperBound (int64 index) const |
| Returns true if a soft upper bound has been set for a given variable index. More... | |
| int64 | GetCumulVarSoftUpperBound (int64 index) const |
| Returns the soft upper bound of a cumul variable for a given variable index. More... | |
| int64 | GetCumulVarSoftUpperBoundCoefficient (int64 index) const |
| Returns the cost coefficient of the soft upper bound of a cumul variable for a given variable index. More... | |
| void | SetCumulVarSoftLowerBound (int64 index, int64 lower_bound, int64 coefficient) |
| Sets a soft lower bound to the cumul variable of a given variable index. More... | |
| bool | HasCumulVarSoftLowerBound (int64 index) const |
| Returns true if a soft lower bound has been set for a given variable index. More... | |
| int64 | GetCumulVarSoftLowerBound (int64 index) const |
| Returns the soft lower bound of a cumul variable for a given variable index. More... | |
| int64 | GetCumulVarSoftLowerBoundCoefficient (int64 index) const |
| Returns the cost coefficient of the soft lower bound of a cumul variable for a given variable index. More... | |
| void | SetBreakIntervalsOfVehicle (std::vector< IntervalVar * > breaks, int vehicle, int pre_travel_evaluator, int post_travel_evaluator) |
| Sets the breaks for a given vehicle. More... | |
| void | SetBreakIntervalsOfVehicle (std::vector< IntervalVar * > breaks, int vehicle, std::vector< int64 > node_visit_transits) |
| Deprecated, sets pre_travel(i, j) = node_visit_transit[i]. More... | |
| void | SetBreakDistanceDurationOfVehicle (int64 distance, int64 duration, int vehicle) |
| With breaks supposed to be consecutive, this forces the distance between breaks of size at least minimum_break_duration to be at least distance. More... | |
| void | InitializeBreaks () |
| Sets up vehicle_break_intervals_, vehicle_break_distance_duration_, pre_travel_evaluators and post_travel_evaluators. More... | |
| bool | HasBreakConstraints () const |
| Returns true if any break interval or break distance was defined. More... | |
| void | SetBreakIntervalsOfVehicle (std::vector< IntervalVar * > breaks, int vehicle, std::vector< int64 > node_visit_transits, std::function< int64(int64, int64)> group_delays) |
| Deprecated, sets pre_travel(i, j) = node_visit_transit[i] and post_travel(i, j) = group_delays(i, j). More... | |
| const std::vector< IntervalVar * > & | GetBreakIntervalsOfVehicle (int vehicle) const |
| Returns the break intervals set by SetBreakIntervalsOfVehicle(). More... | |
| const std::vector< std::pair< int64, int64 > > & | GetBreakDistanceDurationOfVehicle (int vehicle) const |
| Returns the pairs (distance, duration) specified by break distance constraints. More... | |
| int | GetPreTravelEvaluatorOfVehicle (int vehicle) const |
| !defined(SWIGPYTHON) More... | |
| int | GetPostTravelEvaluatorOfVehicle (int vehicle) const |
| const RoutingDimension * | base_dimension () const |
| Returns the parent in the dependency tree if any or nullptr otherwise. More... | |
| int64 | ShortestTransitionSlack (int64 node) const |
| It makes sense to use the function only for self-dependent dimension. More... | |
| const std::string & | name () const |
| Returns the name of the dimension. More... | |
| const ReverseArcListGraph< int, int > & | GetPathPrecedenceGraph () const |
| Accessors. More... | |
| void | SetPickupToDeliveryLimitFunctionForPair (PickupToDeliveryLimitFunction limit_function, int pair_index) |
| bool | HasPickupToDeliveryLimits () const |
| int64 | GetPickupToDeliveryLimitForPair (int pair_index, int pickup, int delivery) const |
| void | AddNodePrecedence (NodePrecedence precedence) |
| const std::vector< NodePrecedence > & | GetNodePrecedences () const |
| void | AddNodePrecedence (int64 first_node, int64 second_node, int64 offset) |
| int64 | GetSpanUpperBoundForVehicle (int vehicle) const |
| const std::vector< int64 > & | vehicle_span_upper_bounds () const |
| int64 | GetSpanCostCoefficientForVehicle (int vehicle) const |
| const std::vector< int64 > & | vehicle_span_cost_coefficients () const |
| int64 | global_span_cost_coefficient () const |
| int64 | GetGlobalOptimizerOffset () const |
| int64 | GetLocalOptimizerOffsetForVehicle (int vehicle) const |
| 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 * (span - bound). More... | |
| bool | HasSoftSpanUpperBounds () const |
| SimpleBoundCosts::BoundCost | GetSoftSpanUpperBoundForVehicle (int vehicle) const |
Member Typedef Documentation
◆ PickupToDeliveryLimitFunction
| typedef std::function<int64(int, int)> PickupToDeliveryLimitFunction |
Limits, in terms of maximum difference between the cumul variables, between the pickup and delivery alternatives belonging to a single pickup/delivery pair in the RoutingModel.
The indices passed to the function respectively correspond to the position of the pickup in the vector of pickup alternatives, and delivery position in the delivery alternatives for this pickup/delivery pair. These limits should only be set when each node index appears in at most one pickup/delivery pair, i.e. each pickup (delivery) index is in a single pickup/delivery pair.first (pair.second).
Constructor & Destructor Documentation
◆ ~RoutingDimension()
| ~RoutingDimension | ( | ) |
Member Function Documentation
◆ AddNodePrecedence() [1/2]
|
inline |
◆ AddNodePrecedence() [2/2]
|
inline |
◆ AreVehicleTransitsPositive()
|
inline |
◆ base_dimension()
|
inline |
◆ cumuls()
|
inline |
Like CumulVar(), TransitVar(), SlackVar() but return the whole variable vectors instead (indexed by int64 var index).
◆ CumulVar()
|
inline |
◆ fixed_transits()
|
inline |
◆ FixedTransitVar()
◆ forbidden_intervals()
|
inline |
◆ GetAllowedIntervalsInRange()
| SortedDisjointIntervalList GetAllowedIntervalsInRange | ( | int64 | index, |
| int64 | min_value, | ||
| int64 | max_value | ||
| ) | const |
Returns allowed intervals for a given node in a given interval.
◆ GetBreakDistanceDurationOfVehicle()
| const std::vector<std::pair<int64, int64> >& GetBreakDistanceDurationOfVehicle | ( | int | vehicle | ) | const |
Returns the pairs (distance, duration) specified by break distance constraints.
◆ GetBreakIntervalsOfVehicle()
| const std::vector<IntervalVar*>& GetBreakIntervalsOfVehicle | ( | int | vehicle | ) | const |
Returns the break intervals set by SetBreakIntervalsOfVehicle().
◆ GetCumulVarPiecewiseLinearCost()
| const PiecewiseLinearFunction* GetCumulVarPiecewiseLinearCost | ( | int64 | index | ) | const |
Returns the piecewise linear cost of a cumul variable for a given variable index.
The returned pointer has the same validity as this class.
◆ GetCumulVarSoftLowerBound()
| int64 GetCumulVarSoftLowerBound | ( | int64 | index | ) | const |
Returns the soft lower bound of a cumul variable for a given variable index.
The "hard" lower bound of the variable is returned if no soft lower bound has been set.
◆ GetCumulVarSoftLowerBoundCoefficient()
| int64 GetCumulVarSoftLowerBoundCoefficient | ( | int64 | index | ) | const |
Returns the cost coefficient of the soft lower bound of a cumul variable for a given variable index.
If no soft lower bound has been set, 0 is returned.
◆ GetCumulVarSoftUpperBound()
| int64 GetCumulVarSoftUpperBound | ( | int64 | index | ) | const |
Returns the soft upper bound of a cumul variable for a given variable index.
The "hard" upper bound of the variable is returned if no soft upper bound has been set.
◆ GetCumulVarSoftUpperBoundCoefficient()
| int64 GetCumulVarSoftUpperBoundCoefficient | ( | int64 | index | ) | const |
Returns the cost coefficient of the soft upper bound of a cumul variable for a given variable index.
If no soft upper bound has been set, 0 is returned.
◆ GetFirstPossibleGreaterOrEqualValueForNode()
|
inline |
◆ GetGlobalOptimizerOffset()
◆ GetLastPossibleLessOrEqualValueForNode()
|
inline |
Returns the largest value outside the forbidden intervals of node 'index' that is less than or equal to a given 'max_value'.
NOTE: If this method is called with a max_value lower than the node's cumul min, it will return -1.
max_value is in a forbidden interval.
max_value is not forbidden.
◆ GetLocalOptimizerOffsetForVehicle()
|
inline |
◆ GetNodePrecedences()
|
inline |
◆ GetPathPrecedenceGraph()
|
inline |
◆ GetPickupToDeliveryLimitForPair()
| int64 GetPickupToDeliveryLimitForPair | ( | int | pair_index, |
| int | pickup, | ||
| int | delivery | ||
| ) | const |
◆ GetPostTravelEvaluatorOfVehicle()
| int GetPostTravelEvaluatorOfVehicle | ( | int | vehicle | ) | const |
◆ GetPreTravelEvaluatorOfVehicle()
| int GetPreTravelEvaluatorOfVehicle | ( | int | vehicle | ) | const |
!defined(SWIGPYTHON)
◆ GetSoftSpanUpperBoundForVehicle()
|
inline |
◆ GetSpanCostCoefficientForVehicle()
|
inline |
◆ GetSpanUpperBoundForVehicle()
|
inline |
◆ GetTransitValue()
| 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 the corresponding transit variable when the 'next' variable for 'from_index' is bound to 'to_index'.
◆ GetTransitValueFromClass()
|
inline |
Same as above but taking a vehicle class of the dimension instead of a vehicle (the class of a vehicle can be obtained with vehicle_to_class()).
◆ GetUnaryTransitEvaluator()
|
inline |
◆ global_span_cost_coefficient()
◆ HasBreakConstraints()
| bool HasBreakConstraints | ( | ) | const |
Returns true if any break interval or break distance was defined.
◆ HasCumulVarPiecewiseLinearCost()
| bool HasCumulVarPiecewiseLinearCost | ( | int64 | index | ) | const |
Returns true if a piecewise linear cost has been set for a given variable index.
◆ HasCumulVarSoftLowerBound()
| bool HasCumulVarSoftLowerBound | ( | int64 | index | ) | const |
Returns true if a soft lower bound has been set for a given variable index.
◆ HasCumulVarSoftUpperBound()
| bool HasCumulVarSoftUpperBound | ( | int64 | index | ) | const |
Returns true if a soft upper bound has been set for a given variable index.
◆ HasPickupToDeliveryLimits()
| bool HasPickupToDeliveryLimits | ( | ) | const |
◆ HasSoftSpanUpperBounds()
◆ InitializeBreaks()
| void InitializeBreaks | ( | ) |
Sets up vehicle_break_intervals_, vehicle_break_distance_duration_, pre_travel_evaluators and post_travel_evaluators.
◆ model()
|
inline |
◆ name()
|
inline |
◆ SetBreakDistanceDurationOfVehicle()
| void SetBreakDistanceDurationOfVehicle | ( | int64 | distance, |
| int64 | duration, | ||
| int | vehicle | ||
| ) |
With breaks supposed to be consecutive, this forces the distance between breaks of size at least minimum_break_duration to be at least distance.
This supposes that the time until route start and after route end are infinite breaks.
◆ SetBreakIntervalsOfVehicle() [1/3]
| void SetBreakIntervalsOfVehicle | ( | std::vector< IntervalVar * > | breaks, |
| int | vehicle, | ||
| int | pre_travel_evaluator, | ||
| int | post_travel_evaluator | ||
| ) |
Sets the breaks for a given vehicle.
Breaks are represented by IntervalVars. They may interrupt transits between nodes and increase the value of corresponding slack variables. A break may take place before the start of a vehicle, after the end of a vehicle, or during a travel i -> j.
In that case, the interval [break.Start(), break.End()) must be a subset of [CumulVar(i) + pre_travel(i, j), CumulVar(j) - post_travel(i, j)). In other words, a break may not overlap any node n's visit, given by [CumulVar(n) - post_travel(_, n), CumulVar(n) + pre_travel(n, _)). This formula considers post_travel(_, start) and pre_travel(end, _) to be 0; pre_travel will never be called on any (_, start) and post_travel will never we called on any (end, _). If pre_travel_evaluator or post_travel_evaluator is -1, it will be taken as a function that always returns 0.
◆ SetBreakIntervalsOfVehicle() [2/3]
| void SetBreakIntervalsOfVehicle | ( | std::vector< IntervalVar * > | breaks, |
| int | vehicle, | ||
| std::vector< int64 > | node_visit_transits | ||
| ) |
Deprecated, sets pre_travel(i, j) = node_visit_transit[i].
◆ SetBreakIntervalsOfVehicle() [3/3]
| void SetBreakIntervalsOfVehicle | ( | std::vector< IntervalVar * > | breaks, |
| int | vehicle, | ||
| std::vector< int64 > | node_visit_transits, | ||
| std::function< int64(int64, int64)> | group_delays | ||
| ) |
Deprecated, sets pre_travel(i, j) = node_visit_transit[i] and post_travel(i, j) = group_delays(i, j).
◆ SetCumulVarPiecewiseLinearCost()
| void SetCumulVarPiecewiseLinearCost | ( | int64 | index, |
| const PiecewiseLinearFunction & | cost | ||
| ) |
Sets a piecewise linear cost on the cumul variable of a given variable index.
If f is a piecewise linear function, the resulting cost at 'index' will be f(CumulVar(index)). As of 3/2017, only non-decreasing positive cost functions are supported.
◆ SetCumulVarSoftLowerBound()
| void SetCumulVarSoftLowerBound | ( | int64 | index, |
| int64 | lower_bound, | ||
| int64 | coefficient | ||
| ) |
Sets a soft lower bound to the cumul variable of a given variable index.
If the value of the cumul variable is less than the bound, a cost proportional to the difference between this value and the bound is added to the cost function of the model: cumulVar > lower_bound -> cost = 0 cumulVar <= lower_bound -> cost = coefficient * (lower_bound - cumulVar). This is also handy to model earliness costs when the dimension represents time. Note: Using soft lower and upper bounds or span costs together is, as of 6/2014, not well supported in the sense that an optimal schedule is not guaranteed.
◆ SetCumulVarSoftUpperBound()
| void SetCumulVarSoftUpperBound | ( | int64 | index, |
| int64 | upper_bound, | ||
| int64 | coefficient | ||
| ) |
Sets a soft upper bound to the cumul variable of a given variable index.
If the value of the cumul variable is greater than the bound, a cost proportional to the difference between this value and the bound is added to the cost function of the model: cumulVar <= upper_bound -> cost = 0 cumulVar > upper_bound -> cost = coefficient * (cumulVar - upper_bound) This is also handy to model tardiness costs when the dimension represents time.
◆ SetGlobalSpanCostCoefficient()
| void SetGlobalSpanCostCoefficient | ( | int64 | coefficient | ) |
Sets a cost proportional to the global dimension span, that is the difference between the largest value of route end cumul variables and the smallest value of route start cumul variables.
In other words: global_span_cost = coefficient * (Max(dimension end value) - Min(dimension start value)).
◆ SetPickupToDeliveryLimitFunctionForPair()
| void SetPickupToDeliveryLimitFunctionForPair | ( | PickupToDeliveryLimitFunction | limit_function, |
| int | pair_index | ||
| ) |
◆ SetSoftSpanUpperBoundForVehicle()
|
inline |
◆ SetSpanCostCoefficientForAllVehicles()
| void SetSpanCostCoefficientForAllVehicles | ( | int64 | coefficient | ) |
◆ SetSpanCostCoefficientForVehicle()
| void SetSpanCostCoefficientForVehicle | ( | int64 | coefficient, |
| int | vehicle | ||
| ) |
Sets a cost proportional to the dimension span on a given vehicle, or on all vehicles at once.
"coefficient" must be nonnegative. This is handy to model costs proportional to idle time when the dimension represents time. The cost for a vehicle is span_cost = coefficient * (dimension end value - dimension start value).
◆ SetSpanUpperBoundForVehicle()
| void SetSpanUpperBoundForVehicle | ( | int64 | upper_bound, |
| int | vehicle | ||
| ) |
!defined(SWIGCSHARP) && !defined(SWIGJAVA) !defined(SWIGPYTHON)
Sets an upper bound on the dimension span on a given vehicle. This is the preferred way to limit the "length" of the route of a vehicle according to a dimension.
◆ ShortestTransitionSlack()
| int64 ShortestTransitionSlack | ( | int64 | node | ) | const |
It makes sense to use the function only for self-dependent dimension.
For such dimensions the value of the slack of a node determines the transition cost of the next transit. Provided that
- cumul[node] is fixed,
- next[node] and next[next[node]] (if exists) are fixed, the value of slack[node] for which cumul[next[node]] + transit[next[node]] is minimized can be found in O(1) using this function.
◆ slacks()
◆ SlackVar()
◆ transit_evaluator()
|
inline |
◆ transits()
◆ TransitVar()
◆ vehicle_capacities()
|
inline |
◆ vehicle_span_cost_coefficients()
|
inline |
◆ vehicle_span_upper_bounds()
|
inline |
◆ vehicle_to_class()
The documentation for this class was generated from the following file: