Improved bounds for vehicle routing solutions

Agustín Bompadre, Moshe Dror, James B. Orlin

Research output: Contribution to journalArticlepeer-review

25 Scopus citations


We present lower bounds for the vehicle routing problem (VRP) 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.

Original languageEnglish (US)
Pages (from-to)299-316
Number of pages18
JournalDiscrete Optimization
Issue number4
StatePublished - Dec 1 2006
Externally publishedYes


  • Approximation algorithm
  • Lower bound
  • Vehicle routing problem

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'Improved bounds for vehicle routing solutions'. Together they form a unique fingerprint.

Cite this