Back

G-2010-22

The Vehicle Routing Problem with Time Windows: State-of-the-Art Exact Solution Methods

, , and

BibTeX reference

The vehicle routing problem with time windows VRPTW consists of finding least-cost vehicle routes to service given customers exactly once each while satisfying the vehicle capacity and customer time windows. The VRPTW has been widely studied. We present here a short survey on the successful exact methods for solving it. These are branch-cut-and-price algorithms, except the most efficient one which solves, by a mixed-integer programming solver, a reduced set partitioning model obtained by performing variable elimination based on reduced cost. This method was able to solve all well-known Solomon's benchmark instances except one, outperforming all the other algorithms previously published.

, 13 pages

Research Axis

Research application

Publication

The vehicle routing problem with time windows : State-of-the-art exact solution methods
, , and
J.J. Cochran, Wiley Encyclopedia of Operations Reseach and Management Science, 2011 BibTeX reference