nach oben

Erschienen in:

2020 | OriginalPaper | Buchkapitel

Polynomial Capacity Guarantees PTAS for the Euclidean Capacitated Vehicle Routing Problem Even for Non-uniform Non-splittable Demand

verfasst von : Michael Khachay, Yuri Ogorodnikov

Erschienen in: Optimization and Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The Capacitated Vehicle Routing Problem (CVRP) is the well-known combinatorial optimization problem that has numerous valuable practical applications. It is known, that CVRP is strongly NP-hard even on the Euclidean plane and APX-hard in its metric setting even for any fixed capacity \(q\ge 3\). For the Euclidean setting, there are known several approximation schemes. But, to the best of our knowledge, polynomial bounds for their time complexity were proved either for a fixed capacity q or under the restriction \(q\ll n\). Moreover, most of these schemes were developed for the simplest case, where each customer has a unit demand, and cannot be extended to the general case of a non-uniform demand (both splittable or not) directly.

In this paper, we are managed to significantly relax the restriction on capacity admitting the existence of PTAS for this problem and propose the first approximation scheme for the CVRP on the Euclidean plane with non-uniform non-splittable demand parameterized by an upper bound for the size of an optimum solution. Time complexity of the proposed scheme is polynomial for any fixed parameter values if \(q=poly(n)\).

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel A Smoothing Lagrange Multiplier Method for Solving the Quasi-variational Signorini’s Inequality

Nächstes Kapitel New Version of Mirror Prox for Variational Inequalities with Adaptation to Inexactness

Like the Euclidean Traveling Salesman Problem.

To the best of our knowledge.

At least, the boxes containing the depot.

for any fixed \(J=O(r)=O(1/\varepsilon )\).

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(06), 893–904 (2010)CrossRef

Anbuudayasankar, S.P., Ganesh, K., Mohapatra, S.: Models for Practical Routing Problems in Logistics. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-05035-5CrossRef

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

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, pp. 275–283. STOC 1997. ACM, New York (1997)

Becker, A., Klein, P.N., Saulpic, D.: Polynomial-time approximation schemes for k-center, k-median, and capacitated vehicle routing in bounded highway dimension. In: Azar, Y., Bast, H., Herman, G. (eds.) 26th Annual European Symposium on Algorithms, Helsinki, Finland, ESA 2018, 20–22 August 2018. LIPIcs, vol. 112, pp. 8:1–8:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018). http://www.dagstuhl.de/dagpub/978-3-95977-081-1

Blocho, M., Czech, Z.: A parallel memetic algorithm for the vehicle routing problem with time windows. In: 2013 Eighth International Conference on P2P, Parallel, Grid, Cloud and Internet Computing, pp. 144–151 (2013)

Borčinova, Z.: Two models of the capacitated vehicle routing problem. Croatian Oper. Res. Rev. 8, 463–469 (2017)MathSciNetCrossRef

Bula, G.A., Gonzalez, F.A., Prodhon, C., Afsar, H.M., Velasco, N.M.: Mixed integer linear programming model for vehicle routing problem for hazardous materials transportation. IFAC-PapersOnLine 49(12), 538–543 (2016). http://www.sciencedirect.com/science/article/pii/S2405896316309673CrossRef

Cardon, S., Dommers, S., Eksin, C., Sitters, R., Stougie, A., Stougie, L.: A PTAS for the multiple depot vehicle routing problem. Tech. rep., Eindhoven University of Technology, March 2008. http://www.win.tue.nl/bs/spor/2008-03.pdf

10.

Cattaruzza, D., Absi, N., Feillet, D., González-Feliu, J.: Vehicle routing problems for city logistics. EURO J. Transp. Logistics 6(1), 51–79 (2017). https://doi.org/10.1007/s13676-014-0074-0CrossRef

11.

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

12.

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 (2010)

13.

Das, A., Mathieu, C.: A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing. Algorithmica 73, 115–142 (2015)MathSciNetCrossRef

14.

Haimovich, M., Rinnooy Kan, A.H.G.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10(4), 527–542 (1985)MathSciNetCrossRef

15.

Hashimoto, H., Yagiura, M.: A path relinking approach with an adaptive mechanism to control parameters for the vehicle routing problem with time windows. In: van Hemert, J., Cotta, C. (eds.) EvoCOP 2008. LNCS, vol. 4972, pp. 254–265. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78604-7_22CrossRef

16.

Khachai, M.Y., Dubinin, R.D.: Approximability of the vehicle routing problem in finite-dimensional Euclidean spaces. Proc. Steklov Insts Math. 297(1), 117–128 (2017)MathSciNetCrossRef

17.

Khachay, M., Ogorodnikov, Y.: Improved polynomial time approximation scheme for capacitated vehicle routing problem with time windows. In: Evtushenko, Y., Jaćimović, M., Khachay, M., Kochetov, Y., Malkova, V., Posypkin, M. (eds.) OPTIMA 2018. CCIS, vol. 974, pp. 155–169. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-10934-9_12CrossRef

18.

Khachay, M., Ogorodnikov, Y.: Efficient PTAS for the Euclidean CVRP with time windows. In: van der Aalst, W.M.P., Batagelj, V., Glavaš, G., Ignatov, D.I., Khachay, M., Kuznetsov, S.O., Koltsova, O., Lomazova, I.A., Loukachevitch, N., Napoli, A., Panchenko, A., Pardalos, P.M., Pelillo, M., Savchenko, A.V. (eds.) AIST 2018. LNCS, vol. 11179, pp. 318–328. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-11027-7_30CrossRef

19.

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_22CrossRef

20.

21.

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

22.

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

23.

Nalepa, J., Blocho, M.: Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows. Soft Comput. 20(6), 2309–2327 (2016)CrossRef

24.

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)

25.

Ng, K., Lee, C., Zhang, S., Wu, K., Ho, W.: A multiple colonies artificial bee colony algorithm for a capacitated vehicle routing problem and re-routing strategies under time-dependent traffic congestion, vol. 109, pp. 151–168 (2017). http://www.sciencedirect.com/science/article/pii/S0360835217301948

26.

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

27.

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)MathSciNetCrossRef

28.

Williamson, D.P., Shmoys, D.B.: The Design of Approximation Algorithms, 1st edn. Cambridge University Press, New York (2011)CrossRef

Titel: Polynomial Capacity Guarantees PTAS for the Euclidean Capacitated Vehicle Routing Problem Even for Non-uniform Non-splittable Demand
verfasst von: Michael Khachay
Yuri Ogorodnikov
Verlag: Springer International Publishing
Buch: Optimization and Applications
Print ISBN: 978-3-030-38602-3

Electronic ISBN: 978-3-030-38603-0

Copyright-Jahr: 2020
DOI: https://doi.org/10.1007/978-3-030-38603-0_30

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"