| Article ID: | iaor20071231 |
| Country: | Netherlands |
| Volume: | 3 |
| Issue: | 4 |
| Start Page Number: | 299 |
| End Page Number: | 316 |
| Publication Date: | Dec 2006 |
| Journal: | Discrete Optimization |
| Authors: | Dror Moshe, Orlin James B., Bompadre Agustn |
We present lower bounds for the vehicle routing problem with and without split deliveries, improving the well-known bound of Haimovich and Rinnooy Kan. These bounds are then utilized in a design of best-to-date approximation algorithms.