Haimovich-Rinnooy Kan polynomial-time approximation scheme for the CVRP in metric spaces of a fixed doubling dimension

M. Yu. Khachay ; Yu. Yu. Ogorodnikov

Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 25 (2019) no. 4, pp. 235-248

Résumé

The Capacitated Vehicle Routing Problem (CVRP) is a classical extremal combinatorial routing problem with numerous applications in operations research. Although the CVRP is strongly NP-hard both in the general case and in the Euclidean plane, it admits quasipolynomial- and even polynomial-time approximation schemes (QPTAS and PTAS) in Euclidean spaces of fixed dimension. At the same time, the metric setting of the problem is APX-complete even for an arbitrary fixed capacity $q\geq 3$. In this paper, we show that the classical Haimovich–Rinnooy Kan algorithm implements a PTAS and an Efficient Polynomial-Time Approximation Scheme (EPTAS) in an arbitrary metric space of fixed doubling dimension for $q=o(\log\log n)$ and for an arbitrary constant capacity, respectively.

Détail

Keywords: Capacitated Vehicle Routing Problem (CVRP), Polynomial-Time Approximation Scheme (PTAS), metric space, doubling dimension.

Bibliographie

[1] Abraham I., Bartal Y., Neiman O., “Advances in metric embedding theory”, Advances in Mathematics, 228:6 (2011), 3026–3126 | DOI | MR | Zbl

[2] Adamaszek A., Czumaj A., Lingas A., “PTAS for k-tour cover problem on the plane for moderately large values of k”, Inter. J. of Foundations of Computer Science, 21:06 (2010), 893–904 | DOI | MR | Zbl

[3] Arnold F., Sorensen K., “Knowledge-guided local search for the vehicle routing problem”, Comput. Oper. Res., 105 (2019), 32–46 | DOI | MR | Zbl

[4] Arora S., “Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems”, J. ACM, 45 (1998), 753–782 | DOI | MR | Zbl

[5] 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$”, Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing (STOC '97), ACM, N Y, 1997, 275–283 | DOI | MR

[6] Assouad P., “Plongements lipschitziens dans $\mathbb{R}^n$”, Bulletin de la Societe Mathematique de France, 111 (1983), 429–448 URL: http://eudml.org/doc/87452 | DOI | MR | Zbl

[7] Bartal Y., Gottlieb L. A., Krauthgamer R., “The traveling salesman problem: Low-dimensionality implies a polynomial time approximation scheme”, SIAM J. Computing, 45:4 (2016), 1563–1581 | DOI | MR | Zbl

[8] Becker A., Klein P. N., Schild A., “A PTAS for bounded-capacity vehicle routing in planar graphs”, Algorithms and Data Structures, Lecture Notes in Computer Science, 11646, eds. Z. Friggstad., J.-R. Sack, M. Salavatipour, Springer, Cham, 2019, 99–111 | DOI | MR

[9] Dantzig G. B., Ramser J. H., “The truck dispatching problem”, Management science, 6:1 (1959), 80–91 | DOI | MR | Zbl

[10] Das A., Mathieu C., “A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing”, Algorithmica, 73 (2015), 115–142 | DOI | MR | Zbl

[11] Demir E., Huckle K., Syntetos A., Lahy A., Wilson M., “Vehicle routing problem: Past and future”, Contemporary Operations and Logistics, ed. P. Wells, Springer, Cham, 2019, 97–117 | DOI

[12] Haimovich M., Rinnooy Kan A. H. G., “Bounds and heuristics for capacitated routing problems”, Math. Oper. Res., 10:4 (1985), 527–542 | DOI | MR | Zbl

[13] van Hoorn J. J., Dynamic programming for routing and scheduling: Optimizing sequences of decisions, Ph. D. thesis, 2016, 210 pp. | DOI

[14] Khachay M., Ogorodnikov Y., “Efficient PTAS for the Euclidean CVRP with time windows”, Analysis of Images, Social Networks and Texts (AIST 2018), Lecture Notes in Computer Science, 11179, ed. van der W. Aalst, Springer, Cham, 2018, 318–328 | DOI

[15] Khachay M., Ogorodnikov Y., “Approximation scheme for the capacitated vehicle routing problem with time windows and non-uniform demand”, Mathematical Optimization Theory and Operations Research (MOTOR 2019), Lecture Notes in Computer Science, 11548, eds. M. Khachay, Y. Kochetov, P. Pardalos, Springer, Cham, 2019, 309–327 | DOI | MR

[16] Khachay M., Ogorodnikov Y., “Improved polynomial time approximation scheme for capacitated vehicle routing problem with time windows”, Optimization and Applications (OPTIMA 2018), Communications in Computer and Information Science, 974, eds. Y. Evtushenko, M. Jacimovic, M. Khachay, Y. Kochetov, V. Malkova, M. Posypkin, Springer, Cham, 2019, 155–169 | DOI

[17] Khachay M., Dubinin R., “PTAS for the Euclidean capacitated vehicle routing problem in $R^d$”, Discrete Optimization and Operations Research, Lecture Notes in Computer Science, 9869, eds. Y. Kochetov, M. Khachay, V. Beresnev, E. Nurminski, P. Pardalos, Springer, Cham, 2016, 193–205 | DOI | MR | Zbl

[18] Khachay M., Zaytseva H., “Polynomial time approximation scheme for single-depot Euclidean capacitated vehicle routing problem”, Combinatorial Optimization and Applications, Lecture Notes in Computer Science, 9486, eds. Z. Lu, D. Kim, W. Wu, W. Li, D.Z Du., Springer, Cham, 2015, 178–190 | DOI | MR | Zbl

[19] Nalepa J., Blocho M., “Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows”, Soft Computing, 20:6 (2016), 2309–2327 | DOI

[20] Necula R., Breaban M., Raschip M., “Tackling dynamic vehicle routing problem with time windows by means of ant colony system”, IEEE Congress on Evolutionary Computation (CEC), 2017, 2480–2487 | DOI

[21] Papadimitriou C., “Euclidean TSP is NP-complete”, Theoret. Comput. Sci., 4 (1977), 237–244 | DOI | MR | Zbl

[22] Pecin D., Pessoa A., Poggi M., Uchoa E., “Improved branch-cut-and-price for capacitated vehicle routing”, Mathematical Programming Computation, 9:1 (2017), 61–100 | DOI | MR | Zbl

[23] Pessoa A. A., Sadykov R., Uchoa E., “Enhanced branch-cut-and-price algorithm for heterogeneous fleet vehicle routing problems”, European J. Oper. Res., 270:2 (2018), 530–543 | DOI | MR | Zbl

[24] Pessoa A. A., Sadykov R., Uchoa E., Vanderbeck F., “A generic exact solver for vehicle routing and related problems”, Integer Programming and Combinatorial Optimization, Proc. 20th Inter. Conf., Lecture Notes in Computer Science, 11480, eds. A. Lodi, V. Nagarajan, Springer, Cham, 2019, 354–369 | DOI | MR

[25] Polat O., “A parallel variable neighborhood search for the vehicle routing problem with divisible deliveries and pickups”, Comput. Oper. Res., 85 (2017), 71–86 | DOI | MR | Zbl

[26] 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 (2018), 102–116 | DOI | MR | Zbl

[27] Toth P., Vigo D., Vehicle routing: Problems, methods and applications.Second Edition, MOS-Siam Series on Optimization, 2 edn, SIAM, 2014, 481 pp. | MR

[28] 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 (2013), 475–489 | DOI | MR | Zbl