1206 Words

Reading time 6 min

8 routing 1 constraints 18 code

Sequence Constraint

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.