Approximation results for min-max path cover problems in vehicle routing

Research output: Journal article publicationJournal articleAcademic researchpeer-review

16 Citations (Scopus)

Abstract

This article studies a min-max path cover problem, which is to determine a set of paths for k capacitated vehicles to service all the customers in a given weighted graph so that the largest path cost is minimized. The problem has wide applications in vehicle routing, especially when the minimization of the latest service completion time is a critical performance measure. We have analyzed four typical variants of this problem, where the vehicles have either unlimited or limited capacities, and they start from either a given depot or any depot of a given depot set. We have developed approximation algorithms for these four variants, which achieve approximation ratios of max{3 -2/k,2}, 5, max{5 -2/k,4}, and 7, respectively. We have also analyzed the approximation hardness of these variants by showing that, unless P = NP, it is impossible for them to achieve approximation ratios less than 4/3, 3/2, 3/2, and 2, respectively. We have further extended the techniques and results developed for this problem to other min-max vehicle routing problems.
Original languageEnglish
Pages (from-to)728-748
Number of pages21
JournalNaval Research Logistics
Volume57
Issue number8
DOIs
Publication statusPublished - 1 Dec 2010

Keywords

  • Approximation algorithms
  • Approximation hardness
  • Min-max path cover
  • Vehicle routing

ASJC Scopus subject areas

  • Modelling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research

Cite this