M.Yu. Khachai, Yu.Yu. Ogorodnikov. Haimovich–Rinnooy Kan polynomial-time approximation scheme for the CVRP in metric spaces of a fixed doubling dimension ... P. 235-248

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.

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

Received August 30, 2019

Revised September 30, 2019

Accepted October 7, 2019

Funding Agency: This research is supported by the Russian Foundation for Basic Research (projects no. 19-07-01243 and 17-08-01385).

Mikhail Yur’evich Khachai, Dr. Phys.-Math. Sci., Prof., Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia; Ural Federal University, Yekaterinburg, 620083 Russia; Omsk State Technical University, Omsk, 644050 Russia, e-mail: mkhachay@imm.uran.ru

Yurii Yur’evich Ogorodnikov, Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620108 Russia, Ural Federal University, Yekaterinburg, 6200083 Russia, e-mail: yogorodnikov@gmail.com

REFERENCES

1.   Abraham I., Bartal Y., Neiman O. Advances in metric embedding theory. Advances in Mathematics, 2011, vol. 228, no. 6, pp. 3026–3126. https://doi.org/10.1016/j.aim.2011.08.003

2.   Adamaszek A., Czumaj A., Lingas A. PTAS for $k$-tour cover problem on the plane for moderately large values of $k$. Inter. J. Foundations of Computer Science, 2010, vol. 21, no. 06, pp. 893–904. https://doi.org/10.1142/S0129054110007623

3.   Arnold F., S$\ddot{\mathrm{o}}$rensen K. Knowledge-guided local search for the vehicle routing problem. Comput. Oper. Res., 2019, vol. 105, pp. 32–46. https://doi.org/10.1016/j.cor.2019.01.002

4.   Arora S. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM, 1998, vol. 45, pp. 753–782.

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$. In: Proc. of the Twenty-ninth Annual ACM Symposium on Theory of Computing (STOC ’97), N Y, USA: ACM, 1997. P. 275–283. https://doi.org/10.1145/258533.258602 

6.   Assouad P. Plongements lipschitziens dans $\mathbb{R}^n$. Bulletin de la Soci$\acute{e}$t$\acute{e}$ Math$\acute{e}$matique de France, 1983, vol. 111, pp. 429–448. http://eudml.org/doc/87452

7.   Bartal Y., Gottlieb L. A., Krauthgamer R. The traveling salesman problem: Low-dimensionality implies a polynomial time approximation scheme. SIAM J. on Computing, 2016, vol. 45, no. 4, pp. 1563–1581. https://doi.org/10.1137/130913328

8.   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. (eds), Algorithms and Data Structures, 2019, Lecture Notes in Computer Science, vol. 11646, Cham: Springer, pp. 99–111.

9.   Dantzig G. B., Ramser J. H. The truck dispatching problem. Management science, 1959, vol. 6, no. 1, pp. 80–91.

10.   Das A., Mathieu C. A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing. Algorithmica, 2015, vol. 73, pp. 115–142. https://doi.org/10.1007/s00453-014-9906-4

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

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

13.   van Hoorn J. J. Dynamic programming for routing and scheduling: Optimizing sequences of decisions. Ph. D. thesis, 2016, 210 p. https://doi.org/10.13140/RG.2.2.14344.88329

14.   Khachay M., Ogorodnikov Y. Efficient PTAS for the Euclidean CVRP with time windows. In: van der Aalst W. et al. (eds), Analysis of Images, Social Networks and Texts (AIST 2018), Lecture Notes in Computer Science, vol. 11179, Cham: Springer, 2018, pp. 318–328.
https://doi.org/10.1007/978-3-030-11027-7_30

15.   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), Mathematical Optimization Theory and Operations Research (MOTOR 2019), Lecture Notes in Computer Science, vol. 11548, Cham: Springer, 2019, pp. 309–327. https://doi.org/10.1007/978-3-030-22629-9_22

16.   Khachay M., Ogorodnikov Y. Improved polynomial time approximation scheme for capacitated vehicle routing problem with time windows. In: Evtushenko Y., Jacimovic M., Khachay M., Kochetov Y., Malkova V., Posypkin M. (eds), Optimization and Applications (OPTIMA 2018), Communications in Computer and Information Science, vol. 974, Cham: Springer, 2019, pp. 155–169. https://doi.org/10.1007/978-3-030-10934-9_12

17.   Khachay M., Dubinin R. PTAS for the Euclidean capacitated vehicle routing problem in Rd. In: Kochetov Y., Khachay M., Beresnev V., Nurminski E., Pardalos P. (eds), Discrete Optimization and Operations Research, Lecture Notes in Computer Science, vol. 9869, Cham: Springer, 2016, pp. 193–205. https://doi.org/10.1007/978-3-319-44914-2_16

18.   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), Combinatorial Optimization and Applications, Lecture Notes in Computer Science, vol. 9486, Cham: Springer, 2015, pp. 178–190. https://doi.org/10.1007/978-3-319-26626-8_14

19.   Nalepa J., Blocho M. Adaptive memetic algorithm for minimizing distance in the vehicle routing problem with time windows. Soft Computing, 2016, vol. 20, no. 6, pp. 2309–2327. https://doi.org/10.1007/s00500-015-1642-4

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, pp. 2480–2487. https://doi.org/10.1109/CEC.2017.7969606

21.   Papadimitriou C. Euclidean TSP is NP-complete. Theoret. Comput. Sci., 1977, vol. 4, pp. 237–244.

22.   Pecin D., Pessoa A., Poggi M., Uchoa E. Improved branch-cut-and-price for capacitated vehicle routing. Math. Programming Computation, 2017, vol. 9, no. 1, pp. 61–100. https://doi.org/10.1007/s12532-016-0108-8

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

24.   Pessoa A. A., Sadykov R., Uchoa E., Vanderbeck F. A generic exact solver for vehicle routing and related problems. In: Lodi A., Nagarajan V. (eds), Proc. 20th Inter. Conf. “Integer Programming and Combinatorial Optimization” (IPCO), Lecture Notes in Computer Science, vol. 11480, Cham: Springer, 2019, pp. 354–369. https://doi.org/10.1007/978-3-030-17953-3_27

25.   Polat O. A parallel variable neighborhood search for the vehicle routing problem with divisible deliveries and pickups. Comput. Oper. Res., 2017, vol. 85, pp. 71–86. https://doi.org/10.1016/j.cor.2017.03.009

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., 2018, vol. 100, pp. 102–116. https://doi.org/10.1016/j.cor.2018.07.021

27.   Toth P., Vigo D. Vehicle routing: Problems, methods and applications. Philadelphia: SIAM, 2014, 481 p.

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., 2013, vol. 40, no. 1, pp. 475–489. https://doi.org/10.1016/j.cor.2012.07.018

Cite this article as: M.Yu.Khachai, Yu.Yu.Ogorodnikov. 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, 2019, vol. 25, no. 4, pp. 235–248.