Stay organized with collections
Save and categorize content based on your preferences.
The routing solver uses an object called a dimension to keep track of
quantities that accumulate along a vehicle's route, such as the travel time or,
if the vehicle is making pickups and deliveries, the total weight it is carrying
. If a routing problem involves such a quantity, either in the constraints or
the objective function, you need to define a dimension to specify them.
This section explains how to define and use dimensions.
Examples of dimensions
Here are a couple of examples of dimensions from previous sections.
The VRPTW example creates a dimension to track
each vehicle's cumulative travel time. The solver uses the dimension to enforce
the constraint that a vehicle can only visit a location within the location's
time window.
The CVRP example creates a dimension for the
demands (e.g., weights or volumes of packages to be picked up), which tracks
the cumulative load the vehicle is carrying along its route.
The solver uses the dimension to enforce the constraint that a vehicle's load
can't exceed its capacity.
The examples below define a dimension for the VRPTW using the
AddDimension
method.
callback_index: The index for the callback that returns the quantity. The
index, which is the solver's internal reference to the callback, is created by
methods such as RegisterTransitCallback or RegisterUnitaryTransitCallback.
slack_max: Maximum for the slack, a variable used to represent waiting
times at the locations. See slack variables below for
details.
If the problem doesn't involve waiting time, you can usually set slack_max
to 0.
capacity: Maximum for the total quantity accumulated along each route.
Use capacity to create constraints like those in the
CVRP. If your problem doesn't have such a
constraint, you can set capacity to a value that is sufficiently large to
impose no restrictions on the routes —for example, the sum of all
entries of the matrix or array used to define the callback.
fix_start_cumulative_to_zero: Boolean value. If true, the cumulative value
of the quantity starts at 0. In most cases, this should be set to True.
However, for the VRPTW or problems with
resource constraints, some vehicles
may have to start after time 0 due to time window constraints, so you should
set fix_start_cumulative_to_zero to False for these problems.
dimension_name: String for the name for the dimension, such as 'Distance',
which you can use to access the variables elsewhere in the program.
The CVRP program creates a slightly different type of dimension using the
AddDimensionWithVehicleCapacity
method. This method takes an array of capacities, with one entry for each vehicle.
(In contrast, AddDimension takes a single value for capacity, so all
vehicles are assumed to have the same capacity.)
See the RoutingModel
reference page for other methods that create dimensions.
Here's an example that illustrates slack variables for a problem involving
travel time. Suppose that
a vehicle goes from location i to location j in one step of its route, and that:
The vehicle's cumulative travel time at i is 100 minutes.
The vehicle's cumulative travel time at j is 200 minutes.
The travel time from i to j is 75 minutes.
The vehicle can't leave location i immediately upon arrival, or its cumulative
time at location j would be 175. Instead, vehicle must wait for 25 minutes at
location i before departing; in other words, the slack at location i is 25.
You need to allow slack in a VRPTW because vehicles may have to wait before
visiting a location, due to time window constraints. In a problem like this, set
slack_max to the maximum amount of time you want to allow vehicles to wait at
a location before proceeding to the next location. If it doesn't matter how long
they wait, just set slack_max to a very large number.
For the CVRP, on the other hand, the change in the accumulated load from i to
j always equals the demand at i, so there is no slack. For problems like
this, you can set slack_max to 0.
Next, we'll give the formal definition of slack. Internally, a dimension stores
two types of variables related to quantities that accumulate along routes:
Transit variables: The increase or decrease of the quantity at each step of
a route.
If i -> j is one step in a route, the transit variable is either the i,
j entry of the transit matrix (for a transit callback), or simply the
callback value at location i (if the callback depends on just one location).
Cumulative variables: The total accumulated quantity at each location. You
can access the cumulative variable at location i by
dimension_name.CumulVar(i). For an example, see the
time window constraints
in the VRPTW example.
Assuming that a vehicle goes from location i to location j in one step, the
slack is related to these variables as follows:
slack(i) = cumul(j) - cumul(i) - transit(i, j)
For more details about dimensions, see
RoutingDimension
in the reference section.
[[["Easy to understand","easyToUnderstand","thumb-up"],["Solved my problem","solvedMyProblem","thumb-up"],["Other","otherUp","thumb-up"]],[["Missing the information I need","missingTheInformationINeed","thumb-down"],["Too complicated / too many steps","tooComplicatedTooManySteps","thumb-down"],["Out of date","outOfDate","thumb-down"],["Samples / code issue","samplesCodeIssue","thumb-down"],["Other","otherDown","thumb-down"]],["Last updated 2024-08-28 UTC."],[[["\u003cp\u003eRouting solver uses \u003cem\u003edimensions\u003c/em\u003e to track quantities like travel time or load along a vehicle's route, essential for constraints and objective functions.\u003c/p\u003e\n"],["\u003cp\u003eDimensions are defined using the \u003ccode\u003eAddDimension\u003c/code\u003e method, specifying parameters like callback index, slack, capacity, and whether the cumulative value starts at zero.\u003c/p\u003e\n"],["\u003cp\u003eSlack variables represent waiting times at locations, crucial for problems with time window constraints like VRPTW.\u003c/p\u003e\n"],["\u003cp\u003e\u003ccode\u003eAddDimensionWithVehicleCapacity\u003c/code\u003e allows defining dimensions with varying capacities for different vehicles, unlike \u003ccode\u003eAddDimension\u003c/code\u003e which assumes uniform capacity.\u003c/p\u003e\n"],["\u003cp\u003eTwo key variable types within dimensions: \u003cem\u003etransit variables\u003c/em\u003e representing quantity changes at each step and \u003cem\u003ecumulative variables\u003c/em\u003e representing the total accumulated quantity at each location.\u003c/p\u003e\n"]]],["The routing solver utilizes *dimensions* to track accumulating quantities along vehicle routes, such as travel time or carried weight. To define a dimension, the `AddDimension` method is used, requiring inputs like `callback_index`, `slack_max`, `capacity`, `fix_start_cumul_to_zero`, and `dimension_name`. `AddDimensionWithVehicleCapacity` handles varying capacities per vehicle. Slack variables represent waiting times at locations and are computed using transit and cumulative variables. Dimensions are essential for enforcing constraints and defining the objective function in routing problems.\n"],null,["# Dimensions\n\nThe routing solver uses an object called a *dimension* to keep track of\nquantities that accumulate along a vehicle's route, such as the travel time or,\nif the vehicle is making pickups and deliveries, the total weight it is carrying\n. If a routing problem involves such a quantity, either in the constraints or\nthe objective function, you need to define a dimension to specify them.\n\nThis section explains how to define and use dimensions.\n\nExamples of dimensions\n----------------------\n\nHere are a couple of examples of dimensions from previous sections.\n\n- The [VRPTW example](/optimization/routing/cvrptw) creates a dimension to track\n each vehicle's cumulative travel time. The solver uses the dimension to enforce\n the constraint that a vehicle can only visit a location within the location's\n time window.\n\n- The [CVRP example](/optimization/routing/cvrp) creates a dimension for the\n *demands* (e.g., weights or volumes of packages to be picked up), which tracks\n the cumulative load the vehicle is carrying along its route.\n The solver uses the dimension to enforce the constraint that a vehicle's load\n can't exceed its capacity.\n\nThe examples below define a dimension for the VRPTW using the\n[`AddDimension`](/optimization/reference/constraint_solver/routing/RoutingModel#AddDimension)\nmethod. \n\n### Python\n\n```python\nrouting.AddDimension(\n callback_index,\n slack_max,\n capacity,\n fix_start_cumul_to_zero,\n dimension_name)\n```\n\n### C++\n\n```c++\nrouting.AddDimension(\n callback_index,\n slack_max,\n capacity,\n fix_start_cumul_to_zero,\n dimension_name)\n```\n\n### Java\n\n```java\nrouting.addDimension(\n callbackIndex,\n slackMax,\n capacity,\n fixStartCumulToZero,\n dimensionName)\n```\n\n### C#\n\n```c#\nrouting.AddDimension(\n callbackIndex,\n slackMax,\n capacity,\n fixStartCumulToZero,\n dimensionName)\n```\n\nThe `AddDimension` method has the following inputs:\n\n- `callback_index`: The index for the callback that returns the quantity. The index, which is the solver's internal reference to the callback, is created by methods such as `RegisterTransitCallback` or `RegisterUnitaryTransitCallback`.\n- `slack_max`: Maximum for the *slack* , a variable used to represent waiting times at the locations. See [slack variables](#slack_variables) below for details. If the problem doesn't involve waiting time, you can usually set `slack_max` to 0.\n- `capacity`: Maximum for the total quantity accumulated along each route. Use `capacity` to create constraints like those in the [CVRP](/optimization/routing/cvrp). If your problem doesn't have such a constraint, you can set `capacity` to a value that is sufficiently large to impose no restrictions on the routes ---for example, the sum of all entries of the matrix or array used to define the callback.\n- `fix_start_cumulative_to_zero`: Boolean value. If true, the cumulative value of the quantity starts at 0. In most cases, this should be set to `True`. However, for the [VRPTW](/optimization/routing/cvrptw) or problems with [resource constraints](/optimization/routing/cvrptw_resources), some vehicles may have to start after time 0 due to time window constraints, so you should set `fix_start_cumulative_to_zero` to `False` for these problems.\n- `dimension_name`: String for the name for the dimension, such as `'Distance'`, which you can use to access the variables elsewhere in the program.\n\nThe CVRP program creates a slightly different type of dimension using the\n[`AddDimensionWithVehicleCapacity`](/optimization/reference/constraint_solver/routing/RoutingModel#AddDimensionWithVehicleCapacity)\nmethod. This method takes an array of capacities, with one entry for each vehicle.\n(In contrast, `AddDimension` takes a single value for `capacity`, so all\nvehicles are assumed to have the same capacity.)\n\nSee the [`RoutingModel`](/optimization/reference/constraint_solver/routing/RoutingModel)\nreference page for other methods that create dimensions.\n\nThe section\n[Save the solution time windows to a list or array](/optimization/routing/vrptw#get-cumulative-data)\npresents functions that save the cumulative data in a dimension in a list or array.\n\nSlack variables\n---------------\n\nHere's an example that illustrates slack variables for a problem involving\ntravel time. Suppose that\na vehicle goes from location i to location j in one step of its route, and that:\n\n- The vehicle's cumulative travel time at i is 100 minutes.\n- The vehicle's cumulative travel time at j is 200 minutes.\n- The travel time from i to j is 75 minutes.\n\nThe vehicle can't leave location i immediately upon arrival, or its cumulative\ntime at location j would be 175. Instead, vehicle must wait for 25 minutes at\nlocation i before departing; in other words, the slack at location i is 25.\n\nYou need to allow slack in a VRPTW because vehicles may have to wait before\nvisiting a location, due to time window constraints. In a problem like this, set\n`slack_max` to the maximum amount of time you want to allow vehicles to wait at\na location before proceeding to the next location. If it doesn't matter how long\nthey wait, just set `slack_max` to a very large number.\n\nFor the CVRP, on the other hand, the change in the accumulated load from `i` to\n`j` always equals the demand at `i`, so there is no slack. For problems like\nthis, you can set `slack_max` to 0.\n\nNext, we'll give the formal definition of slack. Internally, a dimension stores\ntwo types of variables related to quantities that accumulate along routes:\n\n- *Transit variables* : The increase or decrease of the quantity at each step of a route. If `i -\u003e j` is one step in a route, the transit variable is either the `i`, `j` entry of the transit matrix (for a transit callback), or simply the callback value at location i (if the callback depends on just one location).\n- *Cumulative variables* : The total accumulated quantity at each location. You can access the cumulative variable at location i by `dimension_name.CumulVar(i)`. For an example, see the [time window constraints](/optimization/routing/vrptw#time_window_constraints) in the VRPTW example.\n\nAssuming that a vehicle goes from location `i` to location `j` in one step, the\nslack is related to these variables as follows: \n\n```\nslack(i) = cumul(j) - cumul(i) - transit(i, j)\n```\n\n\u003cbr /\u003e\n\nFor more details about dimensions, see\n[`RoutingDimension`](/optimization/reference/constraint_solver/routing/RoutingDimension)\nin the reference section."]]