Vehicle Routing Problem with elementary shortest path based column generation

Vehicle Routing Problem with elementary shortest path based column generation

0.00 Avg rating0 Votes
Article ID: iaor20072323
Country: United Kingdom
Volume: 33
Issue: 10
Start Page Number: 2972
End Page Number: 2990
Publication Date: Oct 2006
Journal: Computers and Operations Research
Authors:
Keywords: networks: path
Abstract:

The usual column generation model for a Vehicle Routing Problem involves an elementary shortest-path subproblem. The worst-case complexity of the known algorithms for this problem being too high, the elementary-path constraint is usually relaxed. Indeed, as each customer must be visited exactly once, the two problems with and without the elementary-path constraint have the same optimal integer solutions. In this article, we propose one theoretical and several practical improvements to the algorithm for elementary paths. We obtain better lower bounds and pruning of the search tree, and these improvements allowed us to find an exact solution to 17 instances of the Solomon benchmark suite which were previously open.

Reviews

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