Обзор нечетких задач маршрутизации транспорта

Введение. Статья посвящена рассмотрению различных алгоритмов решения нечетких задач маршрутизации транспорта. Целью работы явилось исследование современных методов оптимального решения нечетких, случайных и грубых задач маршрутизации транспорта.

Материалы и методы. В работе проведен обзор нечетких задач маршрутизации транспорта, существующих методов и подходов их решения. Выделены наиболее эффективные особенности некоторых подходов к решению нечетких задач маршрутизации транспорта с учетом их специфики.

Результаты исследования. Нечеткая задача маршрутизации транспорта FVRP (Fuzzy Vehicle Routing Problem) возникает всякий раз, когда данные для маршрутизации расплывчаты, неясны или неоднозначны. Зачастую такие нечеткие элементы могут лучше отражать реальность. Однако очень сложно использовать алгоритмы решения детерминированных VRP (Vehicle Routing Problem) для решения FVRP, поскольку несколько фундаментальных свойств детерминированных задач больше не выполняются в FVRP. Поэтому для решения таких задач необходимо ввести новые модели и алгоритмы нечеткого программирования. Таким образом, использование методов теории нечетких множеств позволит успешно моделировать задачи, содержащие элементы неопределенности и субъективности.

Обсуждение и заключения. В результате проведенного обзора различных методов и подходов решения задач маршрутизации транспорта сделаны выводы о том, что разработка и исследование новых решений привлекает на сегодняшний день большое внимание исследователей, но степень проработанности различных вариантов различается. Методы оптимального решения нечетких задач маршрутизации транспорта ограничиваются, в основном, какой-то одной нечеткой переменной. Работ, которые рассматривают большее число нечетких переменных, существует очень ограниченное количество

1. Dantzig, G.B. The Truck Dispatching Problem / G.B. Dantzig, J.H. Ramser // Management science. — 1959. — Vol. 6, no. 1. — P. 80−91.

2. Liu, B. Uncertain programming with applications / B. Liu, R. Zhao, G. Wang // Beijing: Chinese Tsinghua University Press, 2003. — P. 52−43.

3. Erbao, C. The Open Vehicle Routing Problem with Fuzzy Demands / C. Erbao, L. Mingyong // Expert Systems with Applications. — 2010. — Vol. 37, no. 3. — P. 2405−2411.

4. Кубил, В. Н. Обзор обобщений и расширений задачи маршрутизации транспорта / В. Н. Кубил // Вестник РГУПС. — 2018. — № 2. — С. 97–109.

5. Erbao, C. Research on Vehicle Routing Problems Models and Algorithms of Logistics Distribution, Ph.D. thesis / C. Erbao. — China: Hunan University, 2008. — P. 89−92.

6. Chen, D. Nondeterministic Vehicle Routing Problem: A Review / D. Chen, D. Chen, Y. Yang // Advances in Information Sciences and Service Sciences. — 2013. —Vol. 5, no. 9. — P. 485−493.

7. Gendreau, M. Stochastic vehicle routing / M. Gendreau, G. Laporte, R. Séguin //European Journal of Operational Research. — 1996. — Vol. 88, no. 1. — P. 3−12.

8. Teodorović, D. The fuzzy set theory approach to the vehicle routing problem when demand at nodes is uncertain / D. Teodorović, G. Pavković // Fuzzy sets and systems. — 1996. — Vol. 82, no. 3 — P. 307−317.

9. Zhang, J. A hybrid genetic algorithm to fuzzy vehicle routing problem / J. Zhang, J. Li // Journal of Industrial Engineering. — 2005. — P. 23-26. DOI: 10.1109/FSKD.2014.6980823

10. Xu, J. Genetic algorithm for the vehicle routing problem with time windows and fuzzy demand / J. Xu, G. Goncalves, T. Hsu // IEEE Congress on Evolutionary Computation. — 2008. — P. 4125−4129. DOI: 10.1109/CEC.2008.4631360

11. Ye, X. A fuzzy vehicle routing assignment model with connection network based on priority-based genetic algorithm / X. Ye, J. Xu // World Journal of Modelling and Simulation. — 2008. — Vol. 4, no. 4. — P. 257−268.

12. Peng, Y. A particle swarm optimization to vehicle routing problem with fuzzy demands / Y. Peng, Y. Qian // Journal of Convergence Information Technology. — 2010. — Vol. 5, no. 6. — P. 112−119.

13. Tian, J. Emergency supplies distributing and vehicle routes programming based on particle swarm optimization / J. Tian, W.Z. Ma, Y.L. Wang [et al.] // Systems Engineering-Theory & Practice. — 2002. — Vol. 30, no. 5. — P. 898−906.

14. Chen, B. Vehicle routing problem with fuzzy demands and its heuristic ant colony algorithm / B. Chen, S. Song, X. Chen // Journal of Computer Applications. — 2006. — Vol. 11. — P. 25−35.

15. Erbao, C. A hybrid differential evolution algorithm to vehicle routing problem with fuzzy demands / C. Erbao, L. Mingyong // Journal of Computational and Applied Mathematics, Vol. 231, No. 1, 2009. pp. 302−310.

16. Wang, H.F. Time-constrained Chinese postman problems / H.F. Wang, Y.P. Wen// Comput. Math. Appl. — 2002. — Vol. 44. — P. 375−387.

17. Tang, J. Vehicle routing problem with fuzzy time windows / J.Tang, Z. Pan, R.Y. Fung [et al.] // Fuzzy Sets and Systems. — 2009. — Vol. 160, no. 5. — P. 683−695.

18. Adelzadeh, M. A mathematical model and a solving procedure for multi-depot vehicle routing problem with fuzzy time window and heterogeneous vehicle / M. Adelzadeh, V.M. Asl, M. Koosha // The International Journal of Advanced Manufacturing Technology. — 2014. — Vol. 75, no. 5-8. — P. 793−802.

19. Yan, F. Modeling and solving the vehicle routing problem with multiple fuzzy time windows / F. Yan, Y. Wang // International Conference on Management Science and Engineering Management. Springer, Cham, 2017. — P. 847−857.

20. Cao, Q.K. Vehicle bonk routing optimization with multiple fuzzy time windows based on improved wolf pack algorithm / Q. K. Cao, K. W. Yang, X. Y. Ren // Advances in Production Engineering & Management. — 2017. — Vol. 12, no. 4. — P. 401−411. DOI: 10.14743/apem2017.4.267

21. Cheng, R. Vehicle routing problem with fuzzy due-time using genetic algorithms / R. Cheng, M. Gen, T. Tozawa // Journal of Japan Society for Fuzzy Theory and Systems. — 1995. — Vol. 7, no. 5. — P. 1050−1061.

22. Teodorovic, D. A fuzzy logic approach to dynamic dial-a-ride problem / D. Teodorovic, G. Radivojevic // Fuzzy sets and systems. — 2000. — Vol. 116, no. 1. — P. 23−33.

23. Zhang, J. Insertion heuristic algorithm for dynamic vehicle routing problem with fuzzy due-time / J. Zhang, J. Li, Y. Guo // Journal of Southwest Jiaotong University. — 2008. — Vol. 43, no. 1. — P. 107−113.

24. Gendreau, M. Metaheuristics for the vehicle routing problem and its extensions: A categorized bibliography / M. Gendreau, J.Y. Potvin, O. Bräumlaysy [et al.] // In: The Vehicle Routing Problem: Latest Advances and New Challenges. Springer US. — 2008. — Vol. 43. — P. 143−169.

25. Teodorović, D. Application of fuzzy sets theory to the saving based vehicle routing algorithm / D. Teodorović, S. Kikuchi // Civil Engineering Systems. — 1991. — Vol. 8, no. 2. — P. 87−93.

26. Chen, J. A new algorithm for a fuzzy vehicle routing and scheduling problem: imperialist competitive algorithm / J. Chen, Y. Zhang, G. Wang // JCIT: Journal of Convergence Information Technology.  2011. — Vol. 6, no. 7. — P. 303−311.

27. Zheng, Y. Fuzzy vehicle routing model with credibility measure and its hybrid intelligent algorithm / Y. Zheng, B. Liu // Applied mathematics and computation.  2006. — Vol. 176, no. 2. — P. 673−683.

28. Jia, J. Genetic algorithm for fuzzy logistics distribution vehicle routing problem / J. Jia, N. Liu, R. Wang // IEEE International Conference on Service Operations and Logistics, and Informatics. — 2008. — Vol. 1. — P. 1427−1432.

29. Brito, J. Fuzzy approach for vehicle routing problems with fuzzy travel time / J. Brito, F.J. Martinez, J.A. Moreno [et al.] // IEEE International Conference on Fuzzy Systems. — 2010. — P. 1−8.

30. Zhang, J. A hybrid genetic algorithm to the vehicle routing problem with fuzzy cost coefficients / J. Zhang, J. Li // IEEE 11th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD). — 2014. — P. 147−152.

31. Kuo, R. J. Application of a fuzzy ant colony system to solve the dynamic vehicle routing problem with uncertain service time / R. J. Kuo, B. S. Wibowo, F. E. Zulvia // Applied Mathematical Modelling. — 2016. — Vol. 40, no. 23−24. — P. 9990−10001.

32. Zhang, J. Modified Clark-Wright Algorithm for Vehicle Scheduling Problem with Fuzzy Cost Coefficients / J. Zhang, J. Li, Y. Guo // Journal of Southwest Jiaotong University. — 2008. — Vol. 39, no. 6. — P. 281−284.

33. Tang, J. Vehicle routing problem with fuzzy time windows / J. Tang, Z. Pan, R. Y. Fung [et al.] // Fuzzy Sets and Systems. — 2009. — Vol. 160, no. 5. — P. 683−695.

34. Lu, L. Study Dynamic vehicle scheduling problem model under fuzzy information / L. Lu, Q. Tan // Chinese Journal of Management Science. — 2006. — Iss. z1. — P. 156−160.

35. Jiang, Z. Research on Bi-objective fuzzy programming model and algorithm of logistics distribution vehicle routing problem / Z. Jiang, Y. Sheng, D. Wang [et al.] // Chinese Journal of Enterprise Operation Research. — 2008. — No. 1. — P. 19−27.

36. Абрамова, И. О. Зеленая транспортная логистика как инструмент совершенствования хозяйственной деятельности транспортных компаний / И. О. Абрамова, М. Ш. Муртазина. // Вестник евразийской науки. — 2018. — Т. 10, № 3. — С. 2–12.

37. Erdoğan, S. A green vehicle routing problem / S. Erdoğan, E. Miller-Hooks // Transportation Research Part E: Logistics and Transportation Review. — 2012. — Vol. 48, no. 1. — P. 100−114.

38. Wang, R. Solving the green-fuzzy vehicle routing problem using a revised hybrid intelligent algorithm / R. Wang, J. Zhou, X. Yi [et al.] // Journal of Ambient Intelligence and Humanized Computing. — 2019. — Vol. 10, no. 1. — P. 321−332.