М.Ю. Хачай, Ю.Ю. Огородников. Аппроксимационная схема Хаймовича — Ринноя Кана для CVRP в метрических пространствах фиксированной размерности удвоения ... С. 235-248

УДК 519.16 + 519.85

MSC: 90C27, 90C59, 90B06

DOI: 10.21538/0134-4889-2019-25-4-235-248

Полный текст статьи (Full text)

Работа выполнена при поддержке РФФИ (проекты 19-07-01243 и 17-08-01385).

Задача маршрутизации транспорта с ограничением на грузоподъемность (Capacitated Vehicle Routing Problem, CVRP) - одна из классических маршрутных экстремальных комбинаторных задач, обладающих большим числом приложений в области исследования операций. Оставаясь NP-трудной в сильном смысле как в общем случае, так и на евклидовой плоскости, задача CVRP допускает квазиполиномиальные и даже полиномиальные приближенные схемы (QPTAS и PTAS) в евклидовых пространствах фиксированной размерности. В то же время метрическая постановка задачи APX-полна даже в случае произвольной фиксированной грузоподъемности $q\geq 3$. В данной работе показывается, что классический алгоритм М. Хаймовича и А. Ринноя Кана реализует полиномиальную приближенную схему PTAS и эффективную полиномиальную приближенную схему (EPTAS) в произвольном метрическом пространстве фиксированной размерности при $q=o(\log\log n)$ и произвольной постоянной грузоподъемности соответственно.

Ключевые слова: задача маршрутизации транспорта с ограничением на грузоподъемность (CVRP),  полиномиально приближенная схема (PTAS), метрическое пространство, размерность удвоения

СПИСОК ЛИТЕРАТУРЫ

1.   Abraham I., Bartal Y., Neiman O. Advances in metric embedding theory // Advances in Mathematics. 2011. Vol. 228, no. 6. P. 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. of Foundations of Computer Science. 2010. Vol. 21, no. 06. P. 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. P. 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. P. 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$ // Proceedings of the Twenty-ninth Annual ACM Symposium on Theory of Computing (STOC ’97). N Y: 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{\mathrm{e}}$t$\acute{\mathrm{e}}$ Math$\acute{\mathrm{e}}$matique de France. 1983. Vol. 111. P. 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. Computing. 2016. Vol. 45, no. 4. P. 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 // Algorithms and Data Structures / eds. Z. Friggstad., J.-R. Sack, M. Salavatipour. Cham: Springer, 2019. P. 99–111. (Lecture Notes in Computer Science; vol. 11646).

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

10.   Das A., Mathieu C. A quasipolynomial time approximation scheme for Euclidean capacitated vehicle routing // Algorithmica. 2015. Vol. 73. P. 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 // Contemporary Operations and Logistics / ed. P. Wells Cham: Springer, 2019. P. 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. P. 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 // Analysis of Images, Social Networks and Texts (AIST 2018) / ed. van der W. Aalst. Cham: Springer, 2018. P. 318–328. (Lecture Notes in Computer Science; vol. 11179).
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 // Mathematical Optimization Theory and Operations Research (MOTOR 2019) / eds. M. Khachay, Y. Kochetov, P. Pardalos. Cham: Springer, 2019. P. 309–327. (Lecture Notes in Computer Science; vol. 11548). 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 // Optimization and Applications (OPTIMA 2018) / Y. Evtushenko, M. Jacimovic, M. Khachay, Y. Kochetov, V. Malkova, M. Posypkin. Cham: Springer, 2019. P. 155–169. (Communications in Computer and Information Science; vol. 974). 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 $R^d$ // Discrete Optimization and Operations Research / eds. Y. Kochetov, M. Khachay, V. Beresnev, E. Nurminski, P. Pardalos. Cham: Springer, 2016. P. 193–205. (Lecture Notes in Computer Science,;vol. 9869). 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 // Combinatorial Optimization and Applications / eds. Z. Lu, D. Kim, W. Wu, W. Li, D.Z Du. Cham: Springer, 2015. P. 178–190. (Lecture Notes in Computer Science; vol. 9486). 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. P. 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. P. 2480–2487. https://doi.org/10.1109/CEC.2017.7969606

21.   Papadimitriou C. Euclidean TSP is NP-complete // Theoret. Comput. Sci. 1977. Vol. 4. P. 237–244.

22.   Pecin D., Pessoa A., Poggi M., Uchoa E. Improved branch-cut-and-price for capacitated vehicle routing // Mathematical Programming Computation. 2017. Vol. 9, no. 1. P. 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. P. 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 // Integer Programming and Combinatorial Optimization: Proc. 20th Inter. Conf. / eds. A. Lodi, V. Nagarajan. Cham: Springer, 2019, pp. 354–369. (Lecture Notes in Computer Science; vol. 11480). 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. P. 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. P. 102–116. https://doi.org/10.1016/j.cor.2018.07.021

27.   Toth P., Vigo D. Vehicle routing: Problems, methods and applications. Second Edition. MOS-Siam Series on Optimization, SIAM, 2 edn. 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. P. 475–489. https://doi.org/10.1016/j.cor.2012.07.018

Поступила 30.08.2019

После доработки 30.09.2019

Принята к публикации 7.10.2019

Хачай Михаил Юрьевич
д-р физ.-мат. наук
профессор РАН
зав. отделом
Инcтитут математики и механики им. Н.Н.Красовского УрО РАН;
Уральский федеральный университет им. Б.Н. Ельцина
г. Екатеринбург
Омский государственный технический университет
г. Омск
e-mail: mkhachay@imm.uran.ru

Огородников Юрий Юрьевич
науч. сотрудник
Инcтитут математики и механики им. Н.Н.Красовского УрО РАН;
Уральский федеральный университет им. Б.Н.Ельцина
г. Екатеринбург
e-mail: yogorodnikov@gmail.com

Ссылка на статью: М.Ю. Хачай, Ю.Ю. Огородников. Аппроксимационная схема Хаймовича — Ринноя Кана для CVRP в метрических пространствах фиксированной размерности удвоения // Тр. Ин-та математики и механики УрО РАН. 2019. Т. 25, № 4. С. 235-248.

English

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

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

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.