Overview of fuzzy vehicle routing problems
https://doi.org/10.23947/2687-1653-2020-20-3-325-331
Abstract
Introduction. Various algorithms for solving fuzzy vehicle routing problems are considered. The work objective was to study modern methods for the optimal solution to fuzzy, random and rough vehicle routing problems.
Materials and Methods. The paper reviews fuzzy vehicle routing problems, existing methods and approaches to their solution. The most effective features of some approaches to solving fuzzy vehicle routing problems considering their specificity, are highlighted.
Results. The Fuzzy Vehicle Routing Problem (FVRP) occurs whenever the routing data is vague, unclear, or ambiguous. In many cases, these fuzzy elements can better reflect reality. However, it is very difficult to use Vehicle Routing Problem (VRP) solving algorithms to solve FVRP since several fundamental properties of deterministic problems are no longer fulfilled in FVRP. Therefore, it is required to introduce new models and algorithms of fuzzy programming to solve such problems. Thus, the use of methods of the theory of fuzzy sets will provide successful simulation of the problems containing elements of uncertainty and subjectivity.
Discussion and conclusions. As a result of reviewing various methods and approaches to solving vehicle routing problems, it is concluded that the development and study of new solutions come into sharp focus of researchers nowadays, but the degree of elaboration of various options varies. Methods for the optimal solution of FVRP are limited, in general, to some single fuzzy variable. There is a very limited number of papers that consider a large number of fuzzy variables.
About the Authors
Yu. O. ChernyshevRussian Federation
V. N. Kubil
Russian Federation
A. V. Trebukhin
Russian Federation
References
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.
Review
For citations:
Chernyshev Yu.O., Kubil V.N., Trebukhin A.V. Overview of fuzzy vehicle routing problems. Advanced Engineering Research (Rostov-on-Don). 2020;20(3):325-331. https://doi.org/10.23947/2687-1653-2020-20-3-325-331