Approximation results for a min-max location-routing problem

Zhou Xu, Dongsheng Xu, Wenbin Zhu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

23 Citations (Scopus)


This paper studies a minmax location-routing problem, which aims to determine both the home depots and the tours for a set of vehicles to service all the customers in a given weighted graph, so that the maximum working time of the vehicles is minimized. The minmax objective is motivated by the needs of balancing or fairness in vehicle routing applications. We have proved that unless NP=P, it is impossible for the problem to have an approximation algorithm that achieves an approximation ratio of less than 4/3. Thus, we have developed the first constant ratio approximation algorithm for the problem. Moreover, we have developed new approximation algorithms for several variants, which improve the existing best approximation ratios in the previous literature.
Original languageEnglish
Pages (from-to)306-320
Number of pages15
JournalDiscrete Applied Mathematics
Issue number3
Publication statusPublished - 1 Feb 2012


  • Approximation algorithm
  • Approximation hardness
  • Minmax location-routing

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this