УДК 519.16 + 519.85
MSC: 90C27, 90C59, 90B06
DOI: 10.21538/0134-4889-2018-24-3-233-246
Полный текст статьи
Работа первого автора выполнена при поддержке РНФ (проект 14-11-00109).
Задача маршрутизации транспорта с ограничениями на грузоподъемность и временные промежутки обслуживания (CVRPTW) является широко известной NP-трудной задачей комбинаторной оптимизации. В настоящей работе представлено дальнейшее развитие подхода, представленного впервые в работе М. Хаймовича и А. Ринной Кана. Предложенный алгоритм для произвольного $\varepsilon>0$ за время $\mathrm {TIME}(\mathrm {TSP},\rho,n)+O(n^2)+ O\bigl( e^{O(q\,(\frac{q}{\varepsilon})^3(p\rho)^2 \log (p\rho))}\bigr)$ находит $(1+\varepsilon)$-приближенное решение задачи CVRPTW на евклидовой плоскости, где $q$ - верхняя оценка грузоподъемности транспортных средств, $p$ - число промежутков обслуживания (временных окон) и $\mathrm {TIME}(\mathrm {TSP},\rho,n)$ - трудоемкость поиска $\rho$-приближенного решения вспомогательной постановки метрической задачи коммивояжера. Тем самым, алгоритм является полиномиальной приближенной схемой (PTAS) для постановки задачи CVRPTW, в которой $p^3q^4=O(\log n)$, и эффективной полиномиальной схемой (EPTAS) при произвольных фиксированных значения $p$ и $q$.
Ключевые слова: задача маршрутизации транспорта с ограничением на грузоподъемность, временные окна, эффективная полиномиально приближенная схема.
СПИСОК ЛИТЕРАТУРЫ
1. Andrews G. E., Eriksson K. Integer partitions. Cambridge: Cambridge University Press, 2nd edn., 2004. 152 p.
2. Arora S. Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems // J. ACM. 1998. Vol. 45, no. 5. P. 753–782. doi: 10.1145/290179.290180 .
3. Covering points in the plane by k-tours: towards a polynomial time approximation scheme for general k / T. Asano, N. Katoh, H. Tamaki, T. Tokuyama // Proc. of the twenty-ninth annual ACM symposium on theory of computing (STOC ’97). N Y: ACM, 1997. P. 275–283. doi: 10.1145/258533.258602 .
4. Chrisofides N. Worst-case analysis of a new heuristic for the Traveling Salesman Problem. Management Sciences Research Report 388. US, Pennsylvania: Carnegie-Mellon University, 1976. 11 p.
5. Dantzig G., Ramser J. The truck dispatching problem // Management science. 1959. Vol. 6, no. 1. P. 80–91.
6. Das A., Mathieu C. A quasi-polynomial time approximation scheme for Euclidean capacitated vehicle routing // Algorithmica. 2015. Vol. 73, no. 1. P. 115–142. doi: 10.1007/s00453-014-9906-4 .
7. Haimovich M., Rinnooy Kan A.H.G. Bounds and heuristics for capacitated routing problems // Math. Operations Research. 1985. Vol. 10, no. 4. P. 527–542.
doi: 10.1287/moor.10.4.527 .
8. Khachay M., Ogorodnikov Y. Efficient PTAS for the Euclidean CVRP with time windows // Analysis of Images, Social Networks and Texts: Revised Selected Papers 7th International Conf. (AIST-2018). Cham: Springer International Publishing, 2018. P. 1–11. (Lecture Notes in Computer Science; vol. 11179).
9. Khachay M., Dubinin R. PTAS for the Euclidean Capacitated Vehicle Routing Problem in Rd // Proc. DOOR 2016. Cham: Springer International Publishing, 2016. P. 193–205. (Lecture Notes in Computer Science; vol. 9869). doi: 10.1007/978-3-319-44914-2_16 .
10. Khachay M., Zaytseva H. Polynomial time approximation scheme for single-depot Euclidean Capacitated Vehicle Routing Problem // Proc. COCOA 2015. Cham: Springer International Publishing, 2015. P. 178–190. (Lecture Notes in Computer Science; vol. 9486). doi: 10.1007/978-3-319-26626-8_14 .
11. Kumar S., Panneerselvam R. A survey on the vehicle routing problem and its variants Intelligent Information Management. 2012. Vol. 4, no. 3. P. 66–74. doi: 10.4236/iim.2012.43010 .
12. Сердюков А.И. О некоторых оптимальных обходах в графах. Управляемые системы. 1978. Вып. 17. С. 76–79.
13. Song L., Huang H. The Euclidean Vehicle Routing Problem with multiple depots and time windows // Proc. COCOA 2017, Part II. Cham: Springer International Publishing, 2017. P. 449–456. (Lecture Notes in Computer Science; vol. 10627). doi: 10.1007/978-3-319-71147-8_31 .
14. Song L., Huang H., Du H. Approximation schemes for euclidean vehicle routing problems with time windows // J. Combinatorial Optim. 2016. Vol. 32, no. 4. P. 1217–1231. doi: 10.1007/s10878-015-9931-5 .
15. Toth P., Vigo D. Vehicle Routing: problems, methods and applications / eds. P. Toth, D. Vigo. 2 edn. 2014. 480 p. (MOS-Siam Series on Optimization, SIAM). ISBN: 978-1-611973-58-7 .
Поступила 29.05.2018
Хачай Михаил Юрьевич
д-р физ.-мат. наук, зав. отделом, профессор РАН
Инcтитут математики и механики им. Н.Н.Красовского УрО РАН;
Уральский федеральный университет,
г. Екатеринбург;
Омский государственный технический университет,
г. Омск
e-mail: mkhachay@imm.uran.ru
Огородников Юрий Юрьевич
младший науч. сотрудник
Инcтитут математики и механики им. Н.Н.Красовского УрО РАН,
Уральский федеральный университет,
г. Екатеринбург
e-mail: yogorodnikov@gmail.com
English
M.Yu. Khachai, Yu.Yu. Ogorodnikov. Polynomial time approximation scheme for the capacitated vehicle routing problem with time windows
The capacitated vehicle routing problem with time windows (CVRPTW) is a well-known NP-hard combinatorial optimization problem. We present a further development of the approach first proposed by M. Haimovich and A.H.G. Rinnooy Kan and propose an algorithm that finds for arbitrary $\varepsilon>0$ a $(1+\varepsilon)$-approximate solution for Eucidean CVRPTW in $\mathrm {TIME}(\mathrm {TSP},\rho,n)+O(n^2)+O\bigl( e^{O(q\,(\frac{q}{\varepsilon})^3(p\rho)^2\log (p\rho))}\bigr)$, where $q$ is an upper bound for the capacities of the vehicles, $p$ is the number of time windows, and $\mathrm {TIME}(\mathrm {TSP},\rho,n)$ is the complexity of finding a $\rho$-approximation solution of an auxiliary instance of Euclidean TSP. Thus, the algorithm is a polynomial time approximation scheme for CVRPTW with $p^3q^4=O(\log n)$ and an efficient polynomial time approximation scheme (EPTAS) for arbitrary fixed values of $p$ and $q$.
Keywords: capacitated vehicle routing problem, time windows, efficient polynomial time approximation scheme
The paper was received by the Editorial Office on May 29, 2018.
Funding Agency: The first author is supported by the Russian Science Foundation (project no. 14-11-00109).
Mikhail Yur’evich Khachai, Dr. Phys.-Math. Sci., Prof., Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Yekaterinburg, 620990 Russia; Ural Federal University, Yekaterinburg, 620002 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, 620990 Russia, Ural Federal University, Yekaterinburg, 620002 Russia, e-mail: yogorodnikov@gmail.com
[References -> on the "English" button bottom right]
