Approximation results for a min-max location-routing problem

Zhou Xu, Dongsheng Xu, Wenbin Zhu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

18 Citations (Scopus)

Abstract

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
Volume160
Issue number3
DOIs
Publication statusPublished - 1 Feb 2012

Keywords

  • Approximation algorithm
  • Approximation hardness
  • Minmax location-routing

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Cite this