Refinements of the column generation process for the Vehicle Routing Problem with Time Windows

Abstract

The Vehicle Routing Problem with Time Windows is a generalization of the well known capacity constrained Vehicle Routing Problem. A homogeneous fleet of vehicles has to service a set of customers. The service of the customers can only start within a well-defined time interval denoted the time window. The objective is to determine routes for the vehicles that minimizes the accumulated cost (or distance). Currently the best approaches for determining optimal solutions are based on column generation and Branch-and-Bound, also known as Branch-and-Price. This paper presents two ideas for run-time improvements of the Branch-and-Price framework for the Vehicle Routing Problem with Time Windows. Both ideas reveal a significant potential for run-time refinements when speeding up an exact approach without compromising optimality.

Keywords

Vehicle routing / time windows / column generation / shortest path / branch-and-bound

References

[1] Barnhart C., Johnson E.L., Nemhauser G.L., Savelsbergh M.W.P., Vance P. H.. Branch-and-price: Column generation for solving huge integer programs. Operations Research, 1998, 46(3): 316-329.

[2] Desrochers M., Desrosiers J., Solomon M.. A new optimization algorithm for the vehicle routing problem with time windows. Operations Research, 1992, 40(2): 342-354.

[3] Desrochers, M., “An algorithm for the shortest path problem with resource constraints”, Technical Report G-88-27, GERAD,’ Ecole des Hautes’ Etudes Commerciales, Universit’e de Montr’eal, September 1988.

[4] G’elinas S., Desrochers M., Desrosiers J., Solomon M. M.. A new branching strategy for time constrained routing problems with application to backhauling. Annals of Operations Research, 1995, 61: 91-109.

[5] Halse, K., “Modeling and solving complex vehicle routing problems”, PhD thesis, Department for Mathematical Modeling, Technical University of Denmark, 1992.

[6] Houck D.J., Picard J., Queyranne M., Vemuganti R. R.. The travelling salesman problem as a constrained shortest path problem: Theory and computational experience. Opsearch, 1980, 17(2&3): 93-109.

[7] Kohl, N., J. Desrosiers, O.B.G. Madsen, M.M. Solomon, and F. Soumis, “k-path cuts for the vehicle routing problem with time windows”, Technical Report IMM-REP-1997-12, Department of Mathematical Modelling, Technical University of Denmark, 1997.

[8] Kohl, N., “Exact methods for time constained routing and related scheduling problems”, PhD thesis, Department of Mathematical Modelling, Technical University of Denmark, 1995. IMM-PHD-1995-16.

[9] Kolen A.W.J., Kaan A.H.G.R., Trienekens H.W.J.M.. Vehicle routing with time windows. Operations Research, 1987, 35(2): 266-273.

[10] Larsen, J., “Parallellization of the vehicle routing problem with time windows”, PhD thesis, Department of Mathematical Modelling, Technical University of Denmark, 1999. IMM-PHD-1999-62.

[11] Wolsey, L.A., Integer Programming, Wiley-Interscience, 1998.