Top

Published in:

2020 | OriginalPaper | Chapter

An Extension of the Das and Mathieu QPTAS to the Case of Polylog Capacity Constrained CVRP in Metric Spaces of a Fixed Doubling Dimension

Authors : Michael Khachay, Yuri Ogorodnikov, Daniel Khachay

Published in: Mathematical Optimization Theory and Operations Research

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

The Capacitated Vehicle Routing Problem (CVRP) is the well-known combinatorial optimization problem having numerous practically important applications. CVRP is strongly NP-hard (even on the Euclidean plane), hard to approximate in the general case and APX-complete for an arbitrary metric. Meanwhile, for the geometric settings of the problem, there are known a number of quasi-polynomial and even polynomial time approximation schemes. Among these results, the well-known QPTAS proposed by A. Das and C. Mathieu appears to be the most general. In this paper, we propose the first extension of this scheme to a more wide class of metric spaces. Actually, we show that the metric CVRP has a QPTAS any time when the problem is set up in the metric space of any fixed doubling dimension \(d>1\) and the capacity does not exceed \(\mathrm {polylog}\,{(}n)\).

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter On Symmetry Groups of Some Quadratic Programming Problems

next chapter Using Integer Programming to Search for Counterexamples: A Case Study

And the notation \(\mathrm {CVRP\text {-}SD}({Z,D,w,q})\) and \(\mathrm {CVRP\text {-}SD}^*(Z,D,w,q)\) for the case of CVRP-SD as well.

In Sect. 4.4, we provide a dynamic programming algorithm, which finds such a solution for any given random clustering.

The general case can be treated similarly, we postpone its consideration to the forthcoming paper.

Abraham, I., Bartal, Y., Neiman, O.: Advances in metric embedding theory. Adv. Math. 228(6), 3026–3126 (2011). https://doi.org/10.1016/j.aim.2011.08.003MathSciNetCrossRefMATH

Adamaszek, A., Czumaj, A., Lingas, A.: PTAS for k-tour cover problem on the plane rof moderately large values of \(k\). Int. J. Found. Comput. Sci. 21(6), 893–904 (2010). https://doi.org/10.1142/S0129054110007623CrossRefMATH

Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45, 753–782 (1998)MathSciNetCrossRef

Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J. ACM 45, 70–122 (1998). https://doi.org/10.1145/273865.273901MathSciNetCrossRefMATH

Asano, T., Katoh, N., Tamaki, H., Tokuyama, T.: Covering points in the plane by k-tours: towards a polynomial time approximation scheme for general k. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, STOC 1997, pp. 275–283. ACM, New York (1997). https://doi.org/10.1145/258533.258602

Avdoshin, S., Beresneva, E.: Local search metaheuristics for capacitated vehicle routing problem: a comparative study. Proc. Inst. Syst. Program. RAS 31, 121–138 (2019). https://doi.org/10.15514/ISPRAS-2019-31(4)-8CrossRef

Bartal, Y., Gottlieb, L.A., Krauthgamer, R.: The traveling salesman problem: low-dimensionality implies a polynomial time approximation scheme. SIAM J. Comput. 45(4), 1563–1581 (2016). https://doi.org/10.1137/130913328MathSciNetCrossRefMATH

Becker, A., Klein, P.N., Schild, A.: A PTAS for bounded-capacity vehicle routing in planar graphs. In: Friggstad, Z., Sack, J.-R., Salavatipour, M.R. (eds.) WADS 2019. LNCS, vol. 11646, pp. 99–111. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-24766-9_8CrossRef

Chen, J., Gui, P., Ding, T., Zhou, Y.: Optimization of transportation routing problem for fresh food by improved ant colony algorithm based on Tabu search. Sustainability 11 (2019). https://doi.org/10.3390/su11236584

10.

Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manage. Sci. 6(1), 80–91 (1959)MathSciNetCrossRef

11.

Das, A., Mathieu, C.: A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing. Algorithmica 73(1), 115–142 (2014). https://doi.org/10.1007/s00453-014-9906-4MathSciNetCrossRefMATH

12.

Demir, E., Huckle, K., Syntetos, A., Lahy, A., Wilson, M.: Vehicle routing problem: past and future. In: Wells, P. (ed.) Contemporary Operations and Logistics, pp. 97–117. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-14493-7_7CrossRef

13.

Frifita, S., Masmoudi, M.: VNS methods for home care routing and scheduling problem with temporal dependencies, and multiple structures and specialties. Int. Trans. Oper. Res. 27(1), 291–313 (2020). https://doi.org/10.1111/itor.12604MathSciNetCrossRef

14.

Gupta, A., Krauthgamer, R., Lee, J.R.: Bounded geometries, fractals, and low-distortion embeddings. In: 44th Annual IEEE Symposium on Foundations of Computer Science 2003, Proceedings, pp. 534–543 (2003). https://doi.org/10.1109/SFCS.2003.1238226

15.

Haimovich, M., Rinnooy Kan, A.H.G.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10(4), 527–542 (1985). https://doi.org/10.1287/moor.10.4.527MathSciNetCrossRefMATH

16.

Hokama, P., Miyazawa, F.K., Xavier, E.C.: A branch-and-cut approach for the vehicle routing problem with loading constraints. Expert Syst. Appl. 47, 1–13 (2016). https://doi.org/10.1016/j.eswa.2015.10.013CrossRef

17.

Khachai, M.Y., Dubinin, R.D.: Approximability of the Vehicle Routing Problem in finite-dimensional Euclidean spaces. Proc. Steklov Inst. Math. 297(1), 117–128 (2017). https://doi.org/10.1134/S0081543817050133MathSciNetCrossRefMATH

18.

Khachai, M., Ogorodnikov, Y.: Haimovich–Rinnooy Kan polynomial-time approximation scheme for the CVRP in metric spaces of a fixed doubling dimension. Trudy instituta matematiki i mekhaniki UrO RAN 25(4), 235–248 (2019). https://doi.org/10.21538/0134-4889-2019-25-4-235-248

19.

Khachai, M.Y., Ogorodnikov, Y.Y.: Polynomial-time approximation scheme for the capacitated vehicle routing problem with time windows. Proc. Steklov Inst. Math. 307(1), 51–63 (2019). https://doi.org/10.1134/S0081543819070058CrossRefMATH

20.

Khachay, M., Ogorodnikov, Y.: Efficient PTAS for the Euclidean CVRP with time windows. In: van der Aalst, W.M.P., et al. (eds.) AIST 2018. LNCS, vol. 11179, pp. 318–328. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-11027-7_30CrossRef

21.

Khachay, M., Ogorodnikov, Y.: Approximation scheme for the capacitated vehicle routing problem with time windows and non-uniform demand. In: Khachay, M., Kochetov, Y., Pardalos, P. (eds.) MOTOR 2019. LNCS, vol. 11548, pp. 309–327. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-22629-9_22CrossRefMATH

22.

Khachay, M., Dubinin, R.: PTAS for the Euclidean capacitated vehicle routing problem in \(R^d\). In: Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P. (eds.) DOOR 2016. LNCS, vol. 9869, pp. 193–205. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44914-2_16CrossRef

23.

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). https://doi.org/10.1007/978-3-319-26626-8_14CrossRef

24.

Nazari, M., Oroojlooy, A., Takáč, M., Snyder, L.V.: Reinforcement learning for solving the vehicle routing problem. In: Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS 2018, pp. 9861–9871. Curran Associates Inc., Red Hook (2018)

25.

Necula, R., Breaban, M., Raschip, M.: Tackling dynamic vehicle routing problem with time windows by means of ant colony system. In: 2017 IEEE Congress on Evolutionary Computation (CEC), pp. 2480–2487 (2017). https://doi.org/10.1109/CEC.2017.7969606

26.

Papadimitriou, C.: Euclidean TSP is NP-complete. Theoret. Comput. Sci. 4, 237–244 (1977)MathSciNetCrossRef

27.

Pessoa, A.A., Sadykov, R., Uchoa, E.: Enhanced branch-cut-and-price algorithm for heterogeneous fleet vehicle routing problems. Eur. J. Oper. Res. 270(2), 530–543 (2018). https://doi.org/10.1016/j.ejor.2018.04.009MathSciNetCrossRefMATH

28.

Qiu, M., Fu, Z., Eglese, R., Tang, Q.: A tabu search algorithm for the vehicle routing problem with discrete split deliveries and pickups. Comput. Oper. Res. 100, 102–116 (2018). https://doi.org/10.1016/j.cor.2018.07.021MathSciNetCrossRefMATH

29.

Talwar, K.: Bypassing the embedding: algorithms for low dimensional metrics. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC 2004, pp. 281–290. Association for Computing Machinery, New York (2004). https://doi.org/10.1145/1007352.1007399

30.

Toth, P., Vigo, D.: Vehicle Routing: Problems, Methods, and Applications. MOS-SIAM Series on Optimization, 2nd edn. SIAM, Philadelphia (2014)CrossRef

31.

Vidal, T., Crainic, T.G., Gendreau, M., Prins, C.: A hybrid genetic algorithm with adaptive diversity management for a large class of vehicle routing problems with time windows. Comput. Oper. Res. 40(1), 475–489 (2013). https://doi.org/10.1016/j.cor.2012.07.018MathSciNetCrossRefMATH

Title: An Extension of the Das and Mathieu QPTAS to the Case of Polylog Capacity Constrained CVRP in Metric Spaces of a Fixed Doubling Dimension
Authors: Michael Khachay
Yuri Ogorodnikov
Daniel Khachay
Publisher: Springer International Publishing
Book: Mathematical Optimization Theory and Operations Research
Print ISBN: 978-3-030-49987-7

Electronic ISBN: 978-3-030-49988-4

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-49988-4_4

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner