Destination Time Windows 2018-11-27

Generating random pickup and delivery pairs has been a pain point for me in the past. The problem comes with generating reasonable destination time windows. In my latest cycle of coding up a test environment for pickup and delivery problems with time windows (PDPTW), I had an insight that both makes generating random deliveries easier, and also improves the actual solution process of the PDPTW problem.

Random time windows and business logic

Pickup and delivery problems with time windows (PDPTW) are a well known class of routing problems that extend the normal vehicle routing problem (VRP). In the vehicle routing problem, the core abstraction is that a vehicle has to deliver items to locations. The items are already on the van, and the only task of the solver is to build an efficient route to each destination. The pickup and delivery problem extends this to include the idea that each location has one or more items that need to be picked up and delivered to another location. The solver then has to find an efficient route between every pickup location as well as every delivery destination. In addition, pickups of items must happen before the item is delivered, and in multi-vehicle problems, the same vehicle must be used for both the pickup and delivery of an item. Finally, the vehicles will typically have a finite capacity, such that deliveries must be made in order to free up space for more pickups.

The PDPTW models several real-world problems, such as the pickup of passengers using a multi-passenger van and short haul messenger services. I believe this problem also models an autonomous vehicle-based transportation system, in which passengers request rides from shared-use robot cars.

Google’s OR Tools comes with a wide range of example programs, including an example in C++ of a PDPTW, and a handful of vehicle routing problem examples in Python. However, while the VRP examples generate random demands in in space with random time windows, the PDPTW example relies on the specification of standard problem sets in the format defined by Li and Lim (see https://www.sintef.no/projectweb/top/pdptw/li-lim-benchmark/documentation/). I wanted to generate my own random problem sets.

As a first step towards a random generator, I just modified the Python VRPTW code to generate random destination locations and time windows. However, before I even ran the code I recognized a problem. The destination time window only makes sense in the context of the origin time window. If the pickup is on Tuesday between 9 and 11, the delivery shouldn’t be the preceding Monday between 3 and 6. Further, if it takes a few hours to get from the origin to the destination, then this travel time should be incorporated into the time window at the destination.

My first solution was to generate delivery time windows explicitly. If the pickup time window is Tuesday from 9 to 11, and the drive to the destination is one hour, then the destination time window should be Tuesday from 10 to noon. This was pretty simple to code up, using a quick loop over the origins that generated a random destination, computed the travel time, and then shifted the origin time window appropriately.

That worked okay, but didn’t model the usual “business logic” of the problem. Imagine the items being picked up and delivered are passengers. People don’t want to sit around any more than they have to. But by setting the destination time window based on the original time window, that means the time the item spends in the vehicle can be as long as the time window. Back to the running example, if the pickup is Tuesday at 9am, the delivery could be as late as noon, even though the trip from origin to destination only takes one hour.

A better approach would be to set the maximum allowed travel time. For example, a business logic rule might be that the item (whether a person or a package) can only spend at most 150% of the original travel time in the vehicle, with a maximum additional time of 1 hour. So if the trip is one hour, the 150% rule would mean that the item can only be in a vehicle for one and a half hours. If the travel time is five hours, the maximum in-vehicle time would be six hours. But for the longest time I couldn’t see how to set up this constraint. The solution though is blindingly obvious. You can set it up exactly the way the pickup and delivery time constraint is set. Specifically, the standard constraints used in the pdptw.cc example program are:

// ... inside of a loop over all nodes ...
// ... index is origin, delivery_index is destination ...
solver->AddConstraint(solver->MakeEquality(
    routing.VehicleVar(index), routing.VehicleVar(delivery_index)));
solver->AddConstraint(
    solver->MakeLessOrEqual(time_dimension.CumulVar(index),
                            time_dimension.CumulVar(delivery_index)));
routing.AddPickupAndDelivery(i, deliveries[i.value()]);
IntVar* const cumul = time_dimension.CumulVar(index);
cumul->SetMin(kScalingFactor * open_times[i.value()]);
cumul->SetMax(kScalingFactor * close_times[i.value()]);

Translated, the first constraint forces both the pickup and the delivery to be served by the same vehicle. The second constraint forces the pickup to be served first, and then the delivery. There is a standard library call AddPickupAndDelivery to tell the solver that this is a pickup and delivery pair. Finally, the SetMin and SetMax calls set the time windows for all nodes.

In Python, my code does approximately the same thing:

for e in events.events:
    time_dimension.CumulVar(routing.NodeToIndex(e.index)).SetRange(
        int(e.tw_open.total_seconds()), int(e.tw_close.total_seconds()))

for pair in  pd_pairs.values():
    pickup_index = routing.NodeToIndex(pair[0])
    deliver_index = routing.NodeToIndex(pair[1])

    # same vehicle requirement
    solver.AddConstraint(
        routing.VehicleVar(pickup_index) == routing.VehicleVar(deliver_index))

    # deliver *after* pickup
    solver.AddConstraint(
        time_dimension.CumulVar(pickup_index) <=
            time_dimension.CumulVar(deliver_index))

    # not sure what this does, but it can't hurt
    routing.AddPickupAndDelivery(pair[0],pair[1])

I’ve flipped the order a bit from the C++ example. The first loop goes over all nodes, and sets the range for the time dimension based on the time window of the node. The second loop just examines the pickup and delivery node pairs (I have other types of nodes to visit) and sets up the same vehicle and pickup before delivery constraints. To implement my “max time in vehicle constraint” all I have to do is add another constraint on the pickup and delivery times:

def max_allowed_vehicle_time_fn(a,b):
    travel_time = traveltime_lookup[a][b] # travel time in seconds
    additional = min(60*60,int(1.5*travel_time))
    return travel_time + additional

# ... then later, inside the above loop ...

    max_travel_time = max_allowed_vehicle_time_fn(pair[0],pair[1])
    solver.AddConstraint(
        time_dimension.CumulVar(deliver_index) <=
            time_dimension.CumulVar(pickup_index) + max_travel_time )

The “great insight” that I couldn’t see (forest for the trees) is that the constraints “know” the pickup times and delivery times. That is, even though the solver hasn’t been run, you can set up constraints that act on values that the solver will figure out. In this case, the solver will choose a suitable pickup time, and then the travel time constraint says that the delivery time must be less than or equal to the pickup time plus the maximum allowed travel time between the locations.

Because I’m setting both the min and max times on the delivery nodes, the first loop can omit those values as they are redundant. The final code looks like:

for e in events.events:
    if e.event_type != "delivery":
        time_dimension.CumulVar(routing.NodeToIndex(e.index)).SetRange(
            int(e.tw_open.total_seconds()), int(e.tw_close.total_seconds()))

for pair in  pd_pairs.values():
    pickup_index = routing.NodeToIndex(pair[0])
    deliver_index = routing.NodeToIndex(pair[1])

    # same vehicle requirement
    solver.AddConstraint(
        routing.VehicleVar(pickup_index) == routing.VehicleVar(deliver_index))

    # deliver *after* pickup
    solver.AddConstraint(
        time_dimension.CumulVar(pickup_index) <=
            time_dimension.CumulVar(deliver_index))

    max_travel_time = max_allowed_vehicle_time_fn(pair[0],pair[1])
    solver.AddConstraint(
        time_dimension.CumulVar(deliver_index) <=
            time_dimension.CumulVar(pickup_index) + max_travel_time )

    # not sure what this does, but it can't hurt
    routing.AddPickupAndDelivery(pair[0],pair[1])

With that bit of code, it is now a cinch to generate destinations. All I have to do is randomly generate locations in space—no time window is necessary. The delivery time will be entirely set based on the pickup time and the travel time from origin to destination.

Some lingering questions and some test results

Finally, I wasn’t sure whether it is beneficial to drop the max time on the destination nodes. That is, my generator routine creates a time window for destinations that is the same as the time window for the origin but shifted by one hour. My original setup code applied this full range to the drop off nodes, as well as the constraint that the drop off be less than the computed maximum allowed in-vehicle time. So I set up an if statement:

if test_case:
    if (e.tw_open is not None and
        e.event_type != "dropoff"
    ):
        time_dimension.CumulVar(routing.NodeToIndex(e.index)).SetRange(
            int(e.tw_open.total_seconds()), int(e.tw_close.total_seconds()))
    if e.event_type == "dropoff":
        # deliver *after* pickup
        # set delivery time bounds
        pickup_event = dp_pairs[e.index]
        pickup_time = pickup_event.tw_open.total_seconds()
        time_dimension.CumulVar(routing.NodeToIndex(e.index)).SetMin(
        int(pickup_time))
else:
    if (e.tw_open is not None):
        time_dimension.CumulVar(routing.NodeToIndex(e.index)).SetRange(
            int(e.tw_open.total_seconds()), int(e.tw_close.total_seconds()))

When test_case is true, I do the new approach and just set the lower bound of the time window for the destination to be equal to the earliest pickup time. When test_case is false, it follows my earlier case of assigning the opening and closing time of the destination node.

Using python’s timeit module, I set up two different test cases, one taking the true path, the other the false. With about 40 pickups and 40 dropoffs, ten runs of each case gives:

test case true= 468.9647588099997
test case false= 503.90997449299994

So faster by about 3.5 seconds per run to set just the min time on destinations.

Noting that these are random test cases, I ran the comparison again with 50 repeats each, again with 40 pickup and dropoff pairs. The result again was slightly faster for the test_case=True case.

test case true= 2350.723477585001
test case false= 2529.3777841400006

This translates to about 3.6 seconds per run advantage to just setting the minimum time boundary on the destinations. So the old rule of thumb that goes “try it at least 10 times” seems to hold here.

I also tested the case of also not setting the minimum time for the delivery node. In other words, the delivery node time windows are entirely set by the constraint that the delivery must occur after the pickup but not more than an hour after the pickup time plus travel time. In that case, the test case (not setting any time bounds) is slower than the case of setting just the minimum time bound.

test case true= 2930.7029229839973
test case false= 2602.7342191679927

Out of curiosity, I bumped the demands up to 120 pickups and 120 deliveries at 50 repeats each, and also increased the maximum running time of the solver to 15 minutes. What I’m wondering is whether the change makes much difference for more difficult solutions. With 240 nodes to visit, the solver often drops nodes and takes much longer to converge. If each run takes 15 minutes, then I shouldn’t see much difference. Of course, 15 minutes times 100 runs means I had to wait a long time, but it was worth the wait.

test case true= 45534.30551476999
test case false= 45519.966883589004

Here the order has flipped, with the false case running slightly faster. But for all intents and purposes, the two cases have the same running times. The absolute running time of the test was 1,517 minutes, which is just a little more than 1,500 minutes I’d expect for the 100 solver runs:

real	1517m35.017s
user	1516m41.093s
sys	0m48.484s

So in this case, the solver maxed out to time_limit_ms almost every time. It might be that the true case gives slightly better solutions, but in terms of absolute running time for harder problems, the difference is negligible. On the other hand, there is clearly no benefit to adding the approximate time windows of the destination nodes, so I will continue to leave them out.