PTAS for the Euclidean Capacitated Vehicle Routing Problem in \(R^d\)

详细信息    查看全文

• 关键词：Vehicle routing ; Euclidean space ; EPTAS
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9869
• 期：1
• 页码：193-205
• 全文大小：247 KB
• 参考文献：1.Arora, S.: Polynomial time approximation schemes for euclidean traveling salesman and other geometric problems. J. ACM 45, 753–782 (1998)MathSciNet CrossRef MATH
  2.Asano, T., Katoh, N., Tamaki, H., Tokuyama, T.: Covering points in the plane by k-tours: a polynomial time approximation scheme for fixed k. IBM Tokyo Research (1996)
  3.Cardon, S., Dommers, S., Eksin, C., Sitters, R., Stougie, A., Stougie, L.: A PTAS for the multiple depot vehicle routing problem. Technical Report 2008.03, Eindhoven Univ. of Technology, March 2008. http://​www.​win.​tue.​nl/​bs/​spor/​2008-03.​pdf
  4.Christofides, N.: Worst-case analysis of a new heuristic for the traveling salesman problem. In: Symposium on New Directions and Recent Results in Algorithms and Complexity, p. 441 (1975)
  5.Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manage. Sci. 6(1), 80–91 (1959)MathSciNet CrossRef MATH
  6.Das, A., Mathieu, C.: A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing. In: Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms. pp. 390–403. SODA 2010, Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2010)
  7.Das, A., Mathieu, C.: A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing. Algorithmica 73, 115–142 (2015)MathSciNet CrossRef MATH
  8.Gimadi, E.K., Rykov, I.A.: On the asymptotic optimality of a solution of the euclidean problem of covering a graph by m nonadjacent cycles of maximum total weight. Dokl. Math. 93(1), 117–120 (2016)CrossRef MATH
  9.Golden, B.L., Raghavan, S., Wasil, E.A. (eds.): The Vehicle Routing Problem: Latest Advances and New Challenges. Operations Research/Computer Science Interfaces Series, vol. 43. Springer, Heidelberg (2008)MATH
  10.Haimovich, M., Rinnooy Kan, A.H.G.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10(4), 527–542 (1985)MathSciNet CrossRef MATH
  11.Hubbert, S., Gia, Q.T.L., Morton, T.M.: Spherical Radial Basis Functions, Theory and Applications. SpringerBriefs in Mathematics, 1st edn. Springer International Publishing, Heidelberg (2015)MATH
  12.Khachay, M., Neznakhina, K.: Approximability of the minimum-weight k-size cycle cover problem. J. Global Optim. (2015). http://​dx.​doi.​org/​10.​1007/​s10898-015-0391-3
  13.Khachay, M., Zaytseva, H.: Polynomial time approximation scheme for single-depot euclidean capacitated vehicle routing problem. In: Lu, Z., Kim, D., Wu, W., Li, W., Du, D.-Z. (eds.) COCOA 2015. LNCS, vol. 9486, pp. 178–190. Springer, Cham (2015). http://​dx.​doi.​org/​10.​1007/​978-3-319-26626-8_​14
  14.Kumar, S., Panneerselvam, R.: A survey on the vehicle routing problem and its variants. Intell. Inf. Manage. 4, 66–74 (2012)
  15.Papadimitriou, C.: Euclidean TSP is NP-complete. Theor. Comput. Sci. 4, 237–244 (1997)MathSciNet CrossRef
  16.Sutherland, W.A.: Introduction to Metric and Topological Spaces, 2nd edn. Oxford University Press, Oxford (2009). [Oxford Mathematics]MATH
  17.Toth, P., Vigo, D. (eds.): The Vehicle Routing Problem. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (2001)
  
• 作者单位：Michael Khachay (18) (19) (20)
  Roman Dubinin (19)
  
  18. Krasovskii Institute of Mathematics and Mechanics, Ekaterinburg, Russia
  19. Ural Federal University, Ekaterinburg, Russia
  20. Omsk State Technical University, Omsk, Russia
  
• 丛书名：Discrete Optimization and Operations Research
• ISBN：978-3-319-44914-2
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9869

文摘

Capacitated Vehicle Routing Problem (CVRP) is the well-known combinatorial optimization problem remaining NP-hard even in the Euclidean spaces of fixed dimension. Thirty years ago, in their celebrated paper, M. Haimovich and A. Rinnoy Kan proposed the first PTAS for the Planar Single Depot CVRP based on their Iterated Tour Partition heuristic. For decades, this result was extended by many authors to numerous useful modifications of the problem taking into account multiple depots, pick up and delivery options, time window restrictions, etc. But, to the best of our knowledge, almost none of these results go beyond the Euclidean plane. In this paper, we try to bridge this gap and propose an EPTAS for the Euclidean CVRP for any fixed dimension.