Dimensions

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.

Python

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

C++

routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)

Java

routing.addDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

C#

routing.AddDimension(
    callbackIndex,
    slackMax,
    capacity,
    fixStartCumulToZero,
    dimensionName)

The AddDimension method has the following inputs:

  • 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.

The section Save the solution time windows to a list or array presents functions that save the cumulative data in a dimension in a list or array.

Slack variables

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.