Name
Abstract | ||
|---|---|---|
This paper studies a min-max 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 min-max 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. |
Year | DOI | Venue |
|---|---|---|
2012 | 10.1016/j.dam.2011.09.014 | Discrete Applied Mathematics |
Keywords | Field | DocType |
best approximation ratio,approximation result,constant ratio approximation algorithm,approximation ratio,min-max location-routing problem,paper study,previous literature,approximation algorithm,new approximation algorithm,home depot,min-max objective | Approximation algorithm,Graph,Combinatorics,Vehicle routing problem,Mathematical optimization,Unique games conjecture,Working time,Hardness of approximation,Minimax approximation algorithm,Algorithm,Polynomial-time approximation scheme,Mathematics | Journal |
Volume | Issue | ISSN |
160 | 3 | 0166-218X |
Citations | PageRank | References |
11 | 0.58 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zhou Xu | 1 | 208 | 14.97 |
| Dongsheng Xu | 2 | 40 | 2.03 |
| Wenbin Zhu | 3 | 214 | 15.34 |