Improved Pruning in Column Generation of a Vehicle Routing Problem

In: Annals of Operations Research. To Appear, available at ftp://www.mathematik.uni-kl.de/pub/scripts/krumke/mista05.pdf, 2006

Authors

• Stephan Westphal
• Sven O. Krumke

Abstract

Column generation techniques have become a widely used technique to successfully solve large (integer) linear programs. One of the keys to obtaining a practically efficient algorithm is to have a fast method to limit the pricing of new columns to a small set. We study a large scale real-world vehicle dispatching problem with soft time windows which can be modelled as an integer linear program of set partitioning type. We develop a new pruning scheme based on matchings in order to speed up the branch-and-bound enumeration in the column generation process. Computational results on real-world data illustrate the effectiveness of the new pruning scheme.

BibTeX

 
@Article{ Westphal+Krumke:matching-pruning:journal, 
   title = { Improved Pruning in Column Generation of a Vehicle Routing Problem }, 
   author = { Stephan Westphal and Sven O. Krumke },    
   journal = { Annals of Operations Research },           
   note = { To Appear, available at ftp://www.mathematik.uni-kl.de/pub/scripts/krumke/mista05.pdf },  
   year = 2006, 
} 

---

This publication belongs to the project DeNDeMA.