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 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 Das and 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)}\).
Similar content being viewed by others
Notes
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
e.g., \(\beta =3/2\) for the well-known Christofides–Serdyukov algorithm
References
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.003
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/S0129054110007623
Arnold, F., Sörensen, K.: Knowledge-guided local search for the vehicle routing problem. Comput. Oper. Res. 105, 32–46 (2019). https://doi.org/10.1016/j.cor.2019.01.002
Arora, S.: Polynomial time approximation schemes for Euclidean traveling Salesman and other geometric problems. J. ACM 45, 753–782 (1998)
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.273901
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 ’97, 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)-8
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/130913328
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.) Algorithms and Data Structures, pp. 99–111. Springer, Cham, Berlin (2019). https://doi.org/10.1007/978-3-030-24766-9_8
Chen, G., Ding, Z.: Optimization of transportation routing problem for fresh food by improved ant colony algorithm based on tabu search. Sustainability (2019). https://doi.org/10.3390/su11236584
Dantzig, G.B., Ramser, J.H.: The truck dispatching problem. Manag. Sci. 6(1), 80–91 (1959)
Das, A., Mathieu, C.: A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing. Algorithmica 73, 115–142 (2015). https://doi.org/10.1007/s00453-014-9906-4
Demir, E., Huckle, K., Syntetos, A., Lahy, A., Wilson, M.: Vehicle Routing Problem: Past and Future, pp. 97–117. Springer, Berlin (2019). https://doi.org/10.1007/978-3-030-14493-7_7
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.12604
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
Haimovich, M.: Bounds and heuristics for capacitated routing problems. Math. Oper. Res. 10(4), 527–542 (1985). https://doi.org/10.1287/moor.10.4.527
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.013
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
Khachai, M., Ogorodnikov, Y.: Polynomial-time approximation scheme for the capacitated vehicle routing problem with time windows. Proc. Steklov Inst. Math. 307(suppl. 1), S51–S63 (2019). https://doi.org/10.1134/S0081543819070058
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/S0081543817050133
Khachay, M., Dubinin, R.: PTAS for the Euclidean capacitated vehicle routing problem in \(R^d\), LNCS, vol. 9869, pp. 193–205. Springer, Cham, Berlin (2016). https://doi.org/10.1007/978-3-319-44914-2_16
Khachay, M., Ogorodnikov, Y.: Efficient PTAS for the Euclidean CVRP with time windows. In: Analysis of Images, Social Networks and Texts—7th International Conference, AIST 2018, LNCS, vol. 11179, pp. 318–328. Springer, Cham (2018). https://doi.org/10.1007/978-3-030-11027-7_30
Khachay, M., Ogorodnikov, Y.: Approximation scheme for the capacitated vehicle routing problem with time windows and non-uniform demand. In: Mathematical Optimization Theory and Operations Research—18th International Conference (MOTOR 2019). Proceedings, LNCS, vol. 11548, pp. 309–327. Springer, Berlin (2019). https://doi.org/10.1007/978-3-030-22629-9_22
Khachay, M., Ogorodnikov, Y.: Efficient approximation of the capacitated vehicle routing problem in a metric space of an arbitrary fixed doubling dimension. Dokl. Math. 102, 3234–329 (2020). https://doi.org/10.1134/S1064562420040080
Khachay, M., Ogorodnikov, Y., Khachay, D.: An extension of the Das and Mathieu QPTAS to the case of polylog capacity constrained CVRP in metric spaces of a fixed doubling dimension (accepted). In: Mathematical Optimization Theory and Operations Research—19th International Conference (MOTOR 2020). Proceedings, LNCS, vol. 12095. Springer, Berlin (2020)
Khachay, M., Zaytseva, H.: Polynomial time approximation scheme for single-depot Euclidean capacitated vehicle routing problem, LNCS, vol. 9486, pp. 178–190. Springer, Cham, Berlin (2015). https://doi.org/10.1007/978-3-319-26626-8_14
Laporte, G.: Fifty years of vehicle routing. Transp. Sci. 43, 408–416 (2009). https://doi.org/10.1287/trsc.1090.0301
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). https://doi.org/10.1007/s00500-015-1642-4
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’18, pp. 9861–9871. Curran Associates Inc., Red Hook (2018)
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
Papadimitriou, C.: Euclidean TSP is NP-complete. Theoret. Comput. Sci. 4, 237–244 (1977)
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.009
Polat, O.: A parallel variable neighborhood search for the vehicle routing problem with divisible deliveries and pickups. Comput. Oper. Res. 85, 71–86 (2017). https://doi.org/10.1016/j.cor.2017.03.009
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.021
Smid, M.: On some combinatorial problems in metricspaces of bounded doubling dimension (2010). https://people.scs.carleton.ca/ michiel/mst-ann-doubling.pdf. Accessed Dec 6, 2020
Su-Ping, Y., Wei-Wei, M.: An improved ant colony optimization for vrp with time windows. Int. J. Signal Process. Image Process. Pattern Recognit. 9, 327–334 (2016). https://doi.org/10.14257/ijsip.2016.9.10.31
Talwar, K.: Bypassing the embedding: Algorithms for low dimensional metrics. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, STOC ’04, pp. 281–290. Association for Computing Machinery, New York (2004). https://doi.org/10.1145/1007352.1007399
Toth, P., Vigo, D.: Vehicle Routing: Problems, Methods, and Applications. MOS-Siam Series on Optimization, 2nd edn. SIAM, New Delhi (2014)
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.018
Acknowledgements
Michael Khachay and Yuri Ogorodnikov were supported by the Ural Mathematical Center and funded by the Russian Foundation for Basic Research, Grant No. 19-07-01243
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Khachay, M., Ogorodnikov, Y. & Khachay, D. Efficient approximation of the metric CVRP in spaces of fixed doubling dimension. J Glob Optim 80, 679–710 (2021). https://doi.org/10.1007/s10898-020-00990-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10898-020-00990-0