Probabilistic analysis of unit-demand vehicle routeing problems

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

Research output: Contribution to journalArticlepeer-review

9 Scopus citations


We analyze the unit-demand Euclidean vehicle routeing problem, where n customers are modeled as independent, identically distributed uniform points and have unit demand. We show new lower bounds on the optimal cost for the metric vehicle routeing problem and analyze them in this setting. We prove that there exists a constant ĉ > 0 such that the iterated tour partitioning heuristic given by Haimovich and Rinnooy Kan (1985) is a (2 - ĉ)-approximation algorithm with probability arbitrarily close to 1 as the number of customers goes to ∞. It has been a longstanding open problem as to whether one can improve upon the factor of 2 given by Haimovich and Rinnooy Kan. We also generalize this, and previous results, to the multidepot case.

Original languageEnglish (US)
Pages (from-to)259-278
Number of pages20
JournalJournal of Applied Probability
Issue number1
StatePublished - Mar 2007


  • Heuristic
  • Probabilistic analysis of algorithms
  • Vehicle routeing problem

ASJC Scopus subject areas

  • Statistics and Probability
  • General Mathematics
  • Statistics, Probability and Uncertainty


Dive into the research topics of 'Probabilistic analysis of unit-demand vehicle routeing problems'. Together they form a unique fingerprint.

Cite this