# 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](https://developers.google.com/optimization/routing/cvrptw) 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](https://developers.google.com/optimization/routing/cvrp) 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

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

### C++

```c++
routing.AddDimension(
    callback_index,
    slack_max,
    capacity,
    fix_start_cumul_to_zero,
    dimension_name)
```

### Java

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

### C#

```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](https://developers.google.com/optimization/routing/dimensions#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](https://developers.google.com/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.
- `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](https://developers.google.com/optimization/routing/cvrptw) or problems with [resource constraints](https://developers.google.com/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.
- `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`](https://or-tools.github.io/docs/cpp/routing_8h.html) reference
page for other methods that create dimensions.

The section
[Save the solution time windows to a list or array](https://developers.google.com/optimization/routing/vrptw#get-cumulative-data)
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](https://developers.google.com/optimization/routing/vrptw#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)
```

<br />

For more details about dimensions, see `RoutingDimension` in the reference
section.