Analytics For Vehicle Routing (and for Santa)
JeanFrancoisPuget 2700028FGP Visits (11912)
How could we have helped Santa deliver its gifts as fast as possible? An OR practitioner will probably model Santa's problem as a traveling salesman problem (TSP). Indeed Santa needs to compute the shortest route through all kids homes. The same OR practitioner may also want to model that deliveries must occur at night. Instead of a TSP, the problem becomes a vehicle routing with time windows (VRPTW) problem. Although common wisdom, these models may miss the point as we shall see below.
Before discussing what might be wrong, let us look at the positive side. The good news is that many OR algorithms have been devised to efficiently solve TSP and VRPTW. See for instance Sant
Santa could be happy with these algorithms, but something is bothering him because they aren't solving the right problem. He doesn't care much about the distance he travels and is rather interested in coming back home as soon as possible. The above algorithms compute shortest distance routes when what Santa needs is shortest time routes, aka fastest routes.
Good news again, there is a simple trick that allows to compute the right routes. Instead of using actual distances between pairs of locations, one merely needs to use travel time between locations. One way to move from distance to travel is to divide distance by average speed. Then Santa can rely on his algorithm of choice to compute fastest routes.
Santa is happy, and we are done for our blog entry today.
Wait a minute.
What precedes may be good enough for Santa because he can travel at constant speed straight from one location to the next one via air.
But let us look at the case where we are forced to use transportation means available to humans, e.g. delivery trucks. Is the above still relevant to us? For instance, assume we are helping Santa deliver few parcels in a city because he got the order very late and could not handle them in his main delivery route. We get few kids home locations in a city, and we need to visit all of them in the shortest possible time to deliver their gifts. Can we use average speed as described above to compute our route? There is only one way to answer: look at the data. The figure below is actual travel time on a given route in the city of Lyon in France. It was collected as part of the Optimod project where IBM and partners deliver innovating transportation management and traffic prediction tools to the city of Lyon.
Travel time histogram. Average is 10 min, Standard deviation is 15 min.
We see that travel time varies a lot. It is rather short in off peak hours, and can be very long at rush hours. Every driver knows that, yet this is almost always ignored by vehicle routing algorithms.
Given that, can we rely on average speed to compute fastest route? I don't know about you, but I would not trust any route based on such average. If we happen to be stuck in a traffic jam then our delivery will be severely compromised for instance. If we use a conservative approach, eg, taking the longest measured travel time, then we might get a safe route, but it is probably not even close to the fastest one.
Well, if travel time depends on being on rush hours or not, then we might just take the average per time of the day. For instance, when we plan a delivery at rush hours, then we use the travel time at rush hours. This way we should be immune to the dispersion of travel time shown above.
In fact this is not as good as it may seem. The figure below shows taxi travel time from IBM Manhattan office to JFK Airport, in New York, (source).
The average is shown by the blue line.
We clearly see that travel time is still quite spread out. Relying on that average for travel time will still suffer fom the issue we discussed above.
A better way is to use current travel time when computing our route. That way we cope with traffic condition changes, and may get different routes depending on such conditions. The key to make this useful is to get accurate data about current traffic conditions, and algorithms fast enough to compute routes in a very short time. The former is provided by Optimod partners. The later is provided by our cons
Thanks to Optimod, information about real time traffic conditions can be provided to various users: the traffic regulation authorities, drivers via panels on the road, and mobile users, as shown below. The system can also issue alerts when there are significant traffic changes, e.g. an accident blocking a street.
Optimod provides traffic information via several means.
The second piece is to efficiently compute routes using that data. As said before, we use our CPO technology for it. The example below shows an example of fastest route. There are 12 visits represented by letters from A to L in the order they happen. Note that the route crosses itself at the upper left corner, because of one way streets.
A fastest route
To show the influence of real time traffic information, consider the same visits when there is construction work on a street. The routing algorithm gets the fact that traffic is blocked on that street and routes the delivery truck around the blocked part.
Another route avoiding blocked street
Let me insist on one item: one way streets, and more generally, the fact that some times it is not possible to cross streets for delivery For that reason it is very important that the locations are positioned on the correct side of the street. The picture below shows how a mispositioned location result in a silly shortest route between locations A and B.
That example is using Google Maps, where one location is shown on the wrong side of the street, but any mapping service could have a similar issue. Point is that great care must be taken of data quality or we get silly results.
Assuming we have accurate location data, we see that we can use real time traffic data to generate accurate fastest routes.
Are we done?
Can you guess why we are not yet solving the right routing problem?
The issue is that the traffic conditions may change between the time we compute the route and when we actually drive. Here is an example of a potential issue. We have started a 11 visit route when we get a real time alert that there is an accident on the street right before visit B, indicated in red in the figure below..
A natural reaction is, as in the previous case, to reroute around the red part. Issue is that all drivers will have the same thought, and traffic will quickly get congested around the red portion of the map. We should rather compute a new route taking this probable evolution into account. This is what we do in Optimod, resulting in a new route that avoids the future congested area.
This route is much longer, but it is the fastest one given current and predicted traffic conditions.
Let's look at the key ingredients here. We have been using three kind of analytics algorithms:
The three flavors of analytics for routing can be summarized as follow:
Readers of my blog will recognize a pattern I blogged about no later than last week. The pattern is the three levels of analytics, each level answering a different business question:
Update on Dec 31. Comments made by Patrick Viry and Nathan Brixius on Linkedin (see below) made me add some information on Orion. Orion is arguable the largest deployment of VRPTW software in the world. Indeed, it is a system developed by UPS for routing all of its pick up and delivery trucks. One thing that was highlighted when Orion was unveiled is that it avoids making left turns. Indeed, a left turn usually implies longer waiting time than going straight ahead or turning right at intersections. This shows that every detail counts here, and that waiting time for green light can be a significant factor in travel time. This is made even more important in the US where it is often possible to turn right without having to wait for green light. In that case turning right is way better than turning left.
More information about Orion can be found here.
Another comment by Paul Rubin on twitter points to Amazon being hot for drones. I read it as a reference to experiments with drone delivery (Ama
Update on Jan 9, 2015. Added the NY taxi trip time data and discussion around it.