![]() |
OR-Tools
8.2
|
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 most 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)> delays) |
Deprecated, sets pre_travel(i, j) = node_visit_transit[i] and post_travel(i, j) = 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 |
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 * (span - bound)^2. More... | |
bool | HasQuadraticCostSoftSpanUpperBounds () const |
SimpleBoundCosts::BoundCost | GetQuadraticCostSoftSpanUpperBoundForVehicle (int vehicle) const |
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).
~RoutingDimension | ( | ) |
Definition at line 5960 of file routing.cc.
|
inline |
|
inline |
|
inline |
|
inline |
Like CumulVar(), TransitVar(), SlackVar() but return the whole variable vectors instead (indexed by int64 var index).
|
inline |
|
inline |
SortedDisjointIntervalList GetAllowedIntervalsInRange | ( | int64 | index, |
int64 | min_value, | ||
int64 | max_value | ||
) | const |
Returns allowed intervals for a given node in a given interval.
Definition at line 6563 of file routing.cc.
const std::vector< std::pair< int64, int64 > > & GetBreakDistanceDurationOfVehicle | ( | int | vehicle | ) | const |
Returns the pairs (distance, duration) specified by break distance constraints.
Definition at line 6939 of file routing.cc.
const std::vector< IntervalVar * > & GetBreakIntervalsOfVehicle | ( | int | vehicle | ) | const |
Returns the break intervals set by SetBreakIntervalsOfVehicle().
Definition at line 6904 of file routing.cc.
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.
Definition at line 6636 of file routing.cc.
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.
Definition at line 6743 of file routing.cc.
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.
Definition at line 6751 of file routing.cc.
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.
Definition at line 6692 of file routing.cc.
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.
Definition at line 6700 of file routing.cc.
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.
|
inline |
|
inline |
|
inline |
int64 GetPickupToDeliveryLimitForPair | ( | int | pair_index, |
int | pickup, | ||
int | delivery | ||
) | const |
Definition at line 6959 of file routing.cc.
int GetPostTravelEvaluatorOfVehicle | ( | int | vehicle | ) | const |
Definition at line 6917 of file routing.cc.
int GetPreTravelEvaluatorOfVehicle | ( | int | vehicle | ) | const |
!defined(SWIGPYTHON)
Definition at line 6911 of file routing.cc.
|
inline |
|
inline |
|
inline |
|
inline |
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'.
Definition at line 6557 of file routing.cc.
|
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()).
|
inline |
bool HasBreakConstraints | ( | ) | const |
Returns true if any break interval or break distance was defined.
Definition at line 6900 of file routing.cc.
bool HasCumulVarPiecewiseLinearCost | ( | int64 | index | ) | const |
Returns true if a piecewise linear cost has been set for a given variable index.
Definition at line 6631 of file routing.cc.
bool HasCumulVarSoftLowerBound | ( | int64 | index | ) | const |
Returns true if a soft lower bound has been set for a given variable index.
Definition at line 6738 of file routing.cc.
bool HasCumulVarSoftUpperBound | ( | int64 | index | ) | const |
Returns true if a soft upper bound has been set for a given variable index.
Definition at line 6687 of file routing.cc.
bool HasPickupToDeliveryLimits | ( | ) | const |
Definition at line 6955 of file routing.cc.
|
inline |
void InitializeBreaks | ( | ) |
Sets up vehicle_break_intervals_, vehicle_break_distance_duration_, pre_travel_evaluators and post_travel_evaluators.
Definition at line 6890 of file routing.cc.
|
inline |
|
inline |
With breaks supposed to be consecutive, this forces the distance between breaks of size at least minimum_break_duration to be at most distance.
This supposes that the time until route start and after route end are infinite breaks.
Definition at line 6923 of file routing.cc.
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.
Definition at line 6861 of file routing.cc.
void SetBreakIntervalsOfVehicle | ( | std::vector< IntervalVar * > | breaks, |
int | vehicle, | ||
std::vector< int64 > | node_visit_transits | ||
) |
Deprecated, sets pre_travel(i, j) = node_visit_transit[i].
Definition at line 6835 of file routing.cc.
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, j).
Definition at line 6846 of file routing.cc.
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.
Definition at line 6612 of file routing.cc.
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.
Definition at line 6729 of file routing.cc.
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.
Definition at line 6678 of file routing.cc.
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)).
Definition at line 6607 of file routing.cc.
void SetPickupToDeliveryLimitFunctionForPair | ( | PickupToDeliveryLimitFunction | limit_function, |
int | pair_index | ||
) |
Definition at line 6945 of file routing.cc.
|
inline |
|
inline |
void SetSpanCostCoefficientForAllVehicles | ( | int64 | coefficient | ) |
Definition at line 6602 of file routing.cc.
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).
Definition at line 6594 of file routing.cc.
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.
Definition at line 6586 of file routing.cc.
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
Definition at line 6169 of file routing_search.cc.
|
inline |
|
inline |
|
inline |
|
inline |
|
inline |