Pruning in column generation for service vehicle dispatching

Pruning in column generation for service vehicle dispatching

0.00 Avg rating0 Votes
Article ID: iaor20091069
Country: Netherlands
Volume: 159
Issue: 1
Start Page Number: 355
End Page Number: 371
Publication Date: Mar 2008
Journal: Annals of Operations Research
Authors: ,
Keywords: scheduling
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 modeled 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.

Reviews

Required fields are marked *. Your email address will not be published.