A question was posed recently on the Google OR Tools GitHub issues (issue #922) that asked whether it was possible to set up FIFO or LIFO constraints. I’d never done that before, but it seemed straightforward to implement. There were a few wrinkles though, so I thought I’d write them up for my future self.
Pickup and Delivery with Ordering Constraints
In the pickup and delivery problem with time windows (PDPTW), the OR Tools solver does not care about ordering the pickups and deliveries. In the real world, order is often important. For example, if you’re loading up a truck with large items, it might be more efficient to required a Last-In, First-Out (LIFO) constraint. If you’re picking up perishable goods, it might be preferred to set up First-In, First-Out (FIFO) constraints. Or there might be a hybrid setup. For example, a paratransit service might be able to serve ambulatory passengers in any order, but may need to serve wheelchair passengers in LIFO order, since the last wheelchair loaded may block previously loaded wheelchairs. Similarly, if a delivery van loads up a large item like a couch, that large item might block all items previously loaded onto the van, regardless of size, thus forcing a LIFO requirement on just the large items.
The Logic of FIFO Deliveries
As is usual for working with Google OR Tools, it is important to remember how to think about the solver. An initial solution approach might try to track passengers in each vehicle. However the solver does not expose the “…DependentDimension” type API calls to languages other than C++. And even if one could access that API, it would just give you the numbers of items on the vehicle, not the characteristics of those items.
Another approach would be to leverage the travel time callback, perhaps setting things up such that travel from select pickup nodes to certain delivery nodes is penalized by some sort of big-M constraint in order to prevent unwanted deliveries. But I for one couldn’t see how to set that up.
What I ended up doing was rather obvious. For each pickup and delivery pair, just loop over all possible other pickup locations, and set up a conditional constraint. The condition is to test if A is picked up before B. The constraint is that if the condition is me, require A to be delivered before B:
# each pd_pairs entry contains [pickup_object, delivery_object]
for pair in pd_pairs.values():
picku_a = pair[0]
deliv_a = pair[1]
picku_a_index = routing.NodeToIndex(pair[0].index)
deliv_a_index = routing.NodeToIndex(pair[1].index)
for pair_b in pd_pairs.values():
picku_b = pair_b[0]
deliv_b = pair_b[1]
if picku_b.index == picku_a.index :
# same pair, don't constrain
continue
picku_b_index = routing.NodeToIndex(pair_b[0].index)
deliv_b_index = routing.NodeToIndex(pair_b[1].index)
# same vehicle condition: if true, A and B are both served by same vehicle
vehicle_condition = routing.VehicleVar(picku_a_index) == routing.VehicleVar(picku_b_index)
# pickup time condition: if true, A is picked up before B
early_condition = time_dimension.CumulVar(picku_a_index) <= time_dimension.CumulVar(picku_b_index)
# poor man's AND. True * True = True (1), all else equals False (0)
combined_conditions = vehicle_condition * early_condition
# require that delivery of A happens before delivery of B
time_constraint = time_dimension.CumulVar(deliv_a_index) <= time_dimension.CumulVar(deliv_b_index)
expression = solver.ConditionalExpression(
combined_conditions,
time_constraint,
1)
solver.AddConstraint(
expression >= 1
)
The nested for loops iterate over all possible combinations of
pickup nodes. The outer loop is called “A”, and the inner loop is
called “B”. What is needed is a conditional constraint. The
condition is two-fold. First, it must be the case that both A and B
are served by the same vehicle. Second it must be the case that A is
picked up before B. If both of these conditions are true, then a
constraint is applied that requires that the delivery node of A is
served before the delivery node of B. Note that this constraint is
excessive. It may be the case that item A is picked up and
delivered before item B is picked up. In that case, the delivery
constraint is redundant. For now that is fine—we’re just trying to
set things up and see if it works.
The actual conditions and constraints are implemented using the time dimension. The condition requires that the cumulative time dimension value at the pickup node A is less than the cumulative time dimension value at the pickup node B. In code, this is:
early_condition = time_dimension.CumulVar(picku_a_index) <= time_dimension.CumulVar(picku_b_index)
The constraint requires that the accumulated time at the delivery node for A be less than that for B:
time_constraint = time_dimension.CumulVar(deliv_a_index) <= time_dimension.CumulVar(deliv_b_index)
Oops
So that actually doesn’t work. When I ran it the solver completed but then reported the following output (note that I added the “(depot)” notations for clarity):
Route 0: 80-- Load(0) Time(0:00:00, 0:00:00)
-> 82 (depot)-- Load(0) Time(1 day, 18:00:00, 1 day, 18:01:00)
-> 41-- Load(0) Time(2 days, 8:38:42, 2 days, 10:20:47)
-> 60-- Load(1) Time(2 days, 9:32:27, 2 days, 11:14:32)
-> 41--46 Load(2) Time(2 days, 9:54:21, 2 days, 11:36:26)
-> 43-- Load(1) Time(2 days, 10:42:17, 2 days, 12:24:22)
-> 60--65 Load(2) Time(2 days, 11:11:38, 2 days, 12:53:43)
-> 0-- Load(1) Time(2 days, 11:29:34, 2 days, 13:11:39)
-> 43--48 Load(2) Time(2 days, 12:23:52, 2 days, 14:05:57)
-> 1-- Load(1) Time(2 days, 12:46:13, 2 days, 14:28:18)
-> 0--5 Load(2) Time(2 days, 12:55:08, 2 days, 14:37:13)
-> 4-- Load(1) Time(2 days, 13:11:50, 2 days, 14:53:55)
-> 3-- Load(2) Time(2 days, 13:22:12, 2 days, 15:04:17)
-> 3--8 Load(3) Time(2 days, 13:45:26, 2 days, 15:27:31)
-> 1--6 Load(2) Time(2 days, 14:23:35, 2 days, 16:05:40)
-> 4--9 Load(1) Time(2 days, 14:39:25, 2 days, 16:21:30)
-> 2-- Load(0) Time(2 days, 15:08:03, 2 days, 16:50:08)
-> 2--7 Load(1) Time(2 days, 15:42:44, 2 days, 17:24:49)
-> 83 (depot)-- Load(0) Time(2 days, 18:00:00, 2 days, 18:01:00)
...
Day 1 is skipped, and pickups start on day 2 (Tuesday). The first few jobs start off okay. The vehicle loads 41, then 60, then drops 41, then picks up 43, then drops 60 and so on. So far so good. However, the route then picks up 1, 4, and 3, in that order, but drops these loads off in the order of 3, 1, 4. Node 8 (the delivery of node 3) is visited before nodes 6 and 9, whereas the constraint implies that it should be visited after. This wasn’t an artifact of some strange conditions for just this case, but rather happened with every run.
It took me a while to figure this out, but in fact the constraints are not being violated. What I asked for was to require that the dropoff time for 8 be greater than or equal to the dropoff times for 6 and 9. However, what I forgot is that the time values are a range, with a slack value. My output routine is still pretty much the same as that included in the Python example code:
if (drop_pick_map and node in drop_pick_map):
pickup = drop_pick_map[node][0].index
plan_output += \
' {pickup}--{dropoff} Load({load}) Time({tmin}, {tmax}) \n-> '.format(
pickup=pickup,
dropoff=node,
load=plan.Value(load_var),
tmin=str(timedelta(seconds=plan.Min(time_var))),
tmax=str(timedelta(seconds=plan.Max(time_var))))
else:
plan_output += \
' {pickup}-- Load({load}) Time({tmin}, {tmax}) \n-> '.format(
pickup=node,
load=plan.Value(load_var),
tmin=str(timedelta(seconds=plan.Min(time_var))),
tmax=str(timedelta(seconds=plan.Max(time_var))))
So the condition is satisfied in that the range of time for the drop off at node 8 (from 13:45:26 through 15:27:31) could be served after serving node 6 (ranging from 14:23:35 through 16:05:40) and node 9 (ranging from 14:39:25 through 16:21:30). But while the constraint is satisfied, it isn’t accomplishing what I want.
To fix this, I created a new dimension to track the order of pickups and deliveries. This dimension just increases by one monotonically and has zero slack.
routing.AddDimension(
fifo_fn, # total time function callback
0, # allowed time slack
int(total_nodes),
True,
'FIFO')
fifo_dimension = routing.GetDimensionOrDie('FIFO')
Then the constraint loop was rewritten to use this dimension instead of the time dimension:
# (inside nested loop)
# same vehicle condition: if true, A and B are both served by same vehicle
vehicle_condition = routing.VehicleVar(picku_a_index) == routing.VehicleVar(picku_b_index)
# pickup time condition: if true, A is picked up before B
early_condition = fifo_dimension.CumulVar(picku_a_index) <= fifo_dimension.CumulVar(picku_b_index)
# poor man's AND. True * True = True (1), all else equals False (0)
combined_conditions = vehicle_condition * early_condition
# require that delivery of A happens before delivery of B
time_constraint = fifo_dimension.CumulVar(deliv_a_index) <= fifo_dimension.CumulVar(deliv_b_index)
expression = solver.ConditionalExpression(
combined_conditions,
time_constraint,
1)
solver.AddConstraint(
expression >= 1
)
This does work. For example (once again note that I added the “(depot)” notations for clarity):
Route 0: 80 (depot)-- Load(0) Time(0:00:00, 0:00:00)
-> 82 (depot)-- Load(0) Time(1 day, 18:00:00, 1 day, 18:01:00)
-> 83 (depot)-- Load(0) Time(2 days, 18:00:00, 2 days, 18:01:00)
-> 4-- Load(0) Time(3 days, 8:17:47, 3 days, 13:41:52)
-> 3-- Load(1) Time(3 days, 9:07:49, 3 days, 14:31:54)
-> 4--9 Load(2) Time(3 days, 9:49:44, 3 days, 15:22:40)
-> 2-- Load(1) Time(3 days, 10:07:44, 3 days, 16:15:45)
-> 3--8 Load(2) Time(3 days, 10:24:59, 3 days, 16:33:00)
-> 2--7 Load(1) Time(3 days, 10:47:38, 3 days, 17:22:58)
-> 84 (depot)-- Load(0) Time(3 days, 18:00:00, 3 days, 18:01:00)
-> 1-- Load(0) Time(4 days, 8:15:26, 4 days, 14:42:16)
-> 0-- Load(1) Time(4 days, 8:23:02, 4 days, 14:49:52)
-> 42-- Load(2) Time(4 days, 8:48:28, 4 days, 15:15:18)
-> 1--6 Load(3) Time(4 days, 9:25:03, 4 days, 15:51:53)
-> 0--5 Load(2) Time(4 days, 9:54:22, 4 days, 16:21:12)
-> 42--47 Load(1) Time(4 days, 10:04:03, 4 days, 16:30:53)
-> 43-- Load(0) Time(4 days, 10:13:18, 4 days, 16:40:08)
-> 74-- Load(1) Time(4 days, 10:28:24, 4 days, 16:55:14)
-> 43--48 Load(2) Time(4 days, 10:56:02, 4 days, 17:22:52)
-> 74--79 Load(1) Time(4 days, 11:23:40, 4 days, 17:50:30)
-> 85 (depot)-- Load(0) Time(4 days, 18:00:00, 4 days, 18:01:00)
...
The pickup order here for day 3 is [4, 3, 2] and the dropoff order is [9, 8, 7], which is correct. On day 4 the pickups are [1, 0, 42, 43, 74], and the dropoffs are [6, 5, 47, 48, 79], which is correct.
Testing and Timing
I noted earlier that it is a bit overkill to apply the FIFO constraint to every pair of pickups. In practice, the number of conditional constraints can be reduced by applying the constraint to just those pairs for which the B-node pickup window occurs within the A-node pickup window. For cases in which the B node occurs before or after the A node window, the conditional constraint should never be needed.
However, sometimes it doesn’t pay to over-optimize when calling the OR Tools solver. So I set up a test and ran it both ways to see whether there was a significant impact.
First, the code to drop the overlaps just relies on what is known about each node:
for pair in pd_pairs.values():
picku_a = pair[0]
deliv_a = pair[1]
travel_time_a = lookup_fn[picku_a.index][deliv_a.index] + travel_limit
picku_a_early = pair[0].tw_open.total_seconds()
drop_a_late = pair[0].tw_close.total_seconds() + travel_time_a
picku_a_index = routing.NodeToIndex(pair[0].index)
deliv_a_index = routing.NodeToIndex(pair[1].index)
for pair_b in pd_pairs.values():
picku_b = pair_b[0]
deliv_b = pair_b[1]
if picku_b.index == picku_a.index :
# same pair, don't constrain
continue
picku_b_early = pair_b[0].tw_open.total_seconds()
picku_b_late = pair_b[0].tw_close.total_seconds()
picku_b_index = routing.NodeToIndex(pair_b[0].index)
deliv_b_index = routing.NodeToIndex(pair_b[1].index)
# check if overlap. if not, don't bother with constraint
# later. not necessary to get the basics working
if ( test_case and (picku_b_early > drop_a_late or picku_a_early > picku_b_late )):
continue
...
There are two cases to check. First, if the earliest pickup time for node B is after the latest possible time that A can be dropped off, then B will always be served after A and the constraint is meaningless. In order to determine the latest dropoff time for A in this case, I compute the travel time from A to B, and then add the maximum additional travel time allowed. Other implementations I’ve done call a function to compute this value, but regardless, the idea is that there is a maximum amount of time that an item can be in the vehicle, and once this time is reached, it must be delivered.
The second case is simpler. It just checks if the earliest pickup time for A is after the latest pickup time for B. Because this is only about whether the pickup of B can happen after the pickup of A, there is no need to consider B’s travel time.
Finally, the if statement also checks if the test_case variable is
set to true, so that I can run timings on the two different solver setups.
Before getting into the timings, the first lines of the OR Tools logging output show how many constraints are in force. Without dropping the impossible overlaps, there are over 8,000 constraints in effect.
I1205 09:21:44.881886 164 search.cc:244] Start search (memory used = 139.92 MB)
I1205 09:21:44.892966 164 search.cc:244] Root node processed (time = 11 ms, constraints = 8158, memory used = 140.59 MB)
...
By limiting the constraints to just those in which the B pickups happen during the A service time, it is possible to reduce the total number of constraints by about half, from 8,000 to 4,000:
I1205 09:22:57.767992 164 search.cc:244] Start search (memory used = 158.44 MB)
I1205 09:22:57.770002 164 search.cc:244] Root node processed (time = 1 ms, constraints = 4135, memory used = 158.44 MB)
My test showed that even though the extra 4,000+ conditional constraints are not binding and do not affect the final solution, they do affect the total run time. Running twenty cases each, the solver finishes in about one minute for the reduced constraint case, versus about two minutes with all pairs of pickups having the conditional constraints.
test case true= average 61.92, 20 trials
test case false= average 130.08, 20 trials
Again, as documented in an earlier post, my PDPTW code generates random locations and time windows. While a real problem is likely to have less extreme variations run to run, it is safe to assume that the extra constraints slow down the execution of the solver. If you can avoid imposing a conditional constraint a priori, then doing so will have a beneficial impact on running time.