Google’s OR Tools is incredibly useful, but can be tricky to use. I subscribe to the mailing list to keep up on other users’ questions and solutions, and usually I just read and learn. But yesterday a question popped up on the OR-Tools mailing list that I could answer: how to force some node to occur before another node.

## Make the `A`

event occur before the `B`

event

The original question is
here.
Basically the question asks how to make some node `A`

be visited before
some other node `B`

, with any number of nodes in between.

The answer is super simple. Just require that the time at `A`

be less than the
time at `B`

. Unfortunately, while that answer is obvious, getting
there in the context of the OR Tools routing solver isn’t. The
difficulty is that there is no notion of time aside from what is
programmed into your solver parameters.

In the OR Tools approach to route optimization, time isn’t defined via some external ticking clock. Instead, it is actually some quantity that gets accumulated at each stop. This is a really weird concept at first, but makes sense once you get the hang of it. The idea is to set up a dimension for time. This dimension then accumulates hours, minutes, and seconds based on a user-supplied callback function that reports how long it takes to get from any node to any other. Then when the model considers whether to move a vehicle from one node to some other node, this callback function is consulted to determine how much time would be accumulated for each move. The callback can also handle such things as dwell time at each node.

To illustrate this, I’m going to crib some lines from the pdptw.cc example. The time dimension is defined as follows:

```
routing.AddDimension(
NewPermanentCallback(
&TravelPlusServiceTime, const_cast<const Coordinates*>(&coords),
const_cast<const std::vector<int64>*>(&service_times)),
kScalingFactor * horizon, kScalingFactor * horizon,
/*fix_start_cumul_to_zero=*/true, "time");
const RoutingDimension& time_dimension = routing.GetDimensionOrDie("time");
```

Ignoring the language semantics, the `AddDimension`

call takes a
callback function as its first argument, which in this case is a
partially-invoked version of `TravelPlusServiceTime`

with the first
two arguments of that function given as `coords`

and `service_times`

.

The `TravelPlusServiceTime`

function looks like:

```
int64 TravelPlusServiceTime(const Coordinates* const coords,
const std::vector<int64>* const service_times,
RoutingModel::NodeIndex from,
RoutingModel::NodeIndex to) {
return ServiceTime(service_times, from) + Travel(coords, from, to);
}
```

So the partial invocation done when making the permanent callback sets
up the coordinates and the node-specific service times. Then inside
of the solver process, the solver will supply the `from`

and `to`

nodes, and this callback function will return the sum of the service
time at the `from`

node and the travel time between the two nodes.
The time dimension then adds up each of these results as the vehicle
makes its way from location to location.

So the “time” at any node is just the value of the time dimension at
that node, or how much accumulated travel and service has happened up
to that point. Therefore, to add a constraint that `A`

is visited before `B`

,
you *just* have to add a constraint that the value of the time dimension
at node `A`

is less than or equal to the value of the time dimension at
`B`

.

So, in pseudo C++, you’d do something like:

```
const int64 A_index = routing.NodeToIndex(A);
const int64 B_index = routing.NodeToIndex(B);
solver->AddConstraint(
solver->MakeLessOrEqual(time_dimension.CumulVar(A_index),
time_dimension.CumulVar(B_index)));
```

So that’s what I replied to the mailing list, as it is almost just cut and paste from the pdptw.cc example code.

## Handling zero travel time from `A`

to `B`

However, there is a possible wrinkle here that I did not mention in my
reply. It could be the case that
there is zero travel time from `A`

to `B`

. For example the nodes might
be unloading items from a van at the same location. In the pick up
and delivery problem with time windows, it is often the case that
items that are picked up at different locations need to be delivered
to the same physical location, but with different logical nodes. In
this situation, node `A`

might represent delivering a refrigerator,
and node `B`

might represent delivering cold beer. The business logic
might require that the refrigerator be delivered before the beer, but
if they’re both being delivered to StartUpsRUs.com, then the travel
time from `A`

to `B`

would be zero. In practice, I actually ran into
a case where I wanted to “deliver” items of a particular type first
strictly for book-keeping purposes—those items had the longest
unload time, and I wanted to make sure the solver accounted for the
most expensive unload time.

Regardless, if delivery or pickup nodes `A`

and `B`

are colocated in
space, you can’t use the usual time dimension to guarantee `A`

comes
before `B`

. The constraint is a “less than or equal to” type, and
will be satisfied even if `B`

is served before `A`

. The
easiest solution is to make another dimension that is constantly
increasing no matter what. A dimension that isn’t time, and has no
relation to reality, but that just adds one with each event.

Revisiting the original time dimension, it looks like this:

```
routing.AddDimension(
NewPermanentCallback(
&TravelPlusServiceTime, const_cast<const Coordinates*>(&coords),
const_cast<const std::vector<int64>*>(&service_times)),
kScalingFactor * horizon, kScalingFactor * horizon,
/*fix_start_cumul_to_zero=*/true, "time");
const RoutingDimension& time_dimension = routing.GetDimensionOrDie("time");
```

In that call, the `TravelPlusServiceTime`

function is a callback that
gives the travel and service time between any two nodes. For a new
“increment by one” dimension, the callback function can be much
simpler:

```
int64 AddOne(RoutingModel::NodeIndex from,
RoutingModel::NodeIndex to) {
return 1;
}
```

That function has to have the useless `from`

and `to`

arguments or
else the solver will complain. The callback returns 1 every time, so
every event in the routing model costs 1 to serve. This means the
dimension that uses this callback will be monotonically increasing,
and there can be no ties.

This function can be used to define a new dimension as follows:

```
routing.AddDimension(
NewPermanentCallback( &AddOne ),
num_nodes, num_nodes,
/*fix_start_cumul_to_zero=*/true, "counter");
const RoutingDimension& counter_dimension = routing.GetDimensionOrDie("counter");
// ... then later ...
const int64 A_index = routing.NodeToIndex(A);
const int64 B_index = routing.NodeToIndex(B);
solver->AddConstraint(
solver->MakeLessOrEqual(counter_dimension.CumulVar(A_index),
counter_dimension.CumulVar(B_index)));
```

Also note another difference. The `horizon`

is set to the number of
nodes, rather than the end of the day. You could set this lower if
desired, perhaps to enable a way to split service somewhat evenly
between vehicles, as the dimension will max out when it hits the
horizon value.

One final note here. The `counter_dimension`

is only valid when
comparing same-vehicle events. If two or more vehicles are being
used, then the count value between the two vehicles will have no
relationship to time. In that case, the constraint either has to
apply only when the vehicles are the same, or else needs to be
combined with a parallel constraint on the actual `time_dimension`

.
This latter is easiest to do, something like:

```
const int64 A_index = routing.NodeToIndex(A);
const int64 B_index = routing.NodeToIndex(B);
solver->AddConstraint(
solver->MakeLessOrEqual(time_dimension.CumulVar(A_index),
time_dimension.CumulVar(B_index)));
solver->AddConstraint(
solver->MakeLessOrEqual(counter_dimension.CumulVar(A_index),
counter_dimension.CumulVar(B_index)));
```

I haven’t actually coded that up and run it, but to the extent that copy/paste/edit programming is mostly correct, That Should Work Fine.™

There are still more interesting wrinkles that could be added, but I’ll leave that to a future post, while I create a program that actually uses this counter dimension.