It is often difficult to explain how difficult it is to come up with an optimal solution to a vehicle routing problem.
I am convinced that part of the problem is that it is so trivial to come up with feasible solutions to a vehicle routing problem: just send out a truck to make every stop or group stops and send a truck to make multiple stops. And, an experienced dispatcher can often quickly improve upon a given schedule by looking at the routes. And, what we've found in practice, the constraints that would make the problem harder (like deliver time windows) are often simply ignored.
However, being about to find a solution to the problem (and maybe even an infeasible one), is not good enough. We've found that using advanced optimization can lead to routes that shave 5-15% of costs (on routes that are already deemed pretty good) and meet all the constraints.
What makes this interesting, is that the optimization is actually very difficult. Mike Trick's recent blog post
highlights some of the difficulty with routing by writing about a Traveling Salesman Problem (TSP) a politician might face in Iowa trying to visit all 99 county seats in the shortest amount of drive time. Mike Trick quotes Bill Cook:
Leaving Des Moines, we have 98 choices for our second stop, then, for
each of these, 97 choices for the third stop, then 96 choices for the
fourth stop, and so on until we hit our last county and drive back to
Des Moines. Multiplying all of these choices gives the number of
possible routes through Iowa. And it is a big number, roughly 9 followed
by 153 zeros. No computer in the world could look through such an
enormous collection of tours one by one.
For vehicle routing (with multiple vehicles, capacities, time windows, and so on), the story gets more complicated. In a 2009 paper by Gilbert Laporte titled "Fifty Years of Vehicle Routing" discusses the progress that has been made in this field. He mentions that the vehicle routing problem "is considerably more difficult to solve than the TSP." Over fifty years of research has led to significant advances in different approaches and algorithms. But, he mentions that the field still has a long way to go to solve larger (and more realistically sized) problems found in industry.
This mirrors our experience with the ILOG optimization for vehicle routing-- these problems can be mathematically challenging. To solve these problems in practice requires an optimization-based approach. We have been working on this since the mid-90's. Some readers may remember the ILOG routing engine called Dispatcher or
the tool Transport PowerOps. This routing engine has found its way into
to the product called Transportation Analyst. And, the underlying
optimization engines are now part of the CPLEX toolkit.