Solving Capacitated Vehicle Routing Problem (CVRP) for the Environments with Circular Obstacles

Abstract

In capacitated vehicle routing problem (CVRP), a fleet of vehicles with a certain capacity starts at a central depot and returns to this starting point after serving some customers by using the optimal set of routes with the minimum cost. However, in real-life, environments may include obstacles such as holes, machines, or trees of different sizes. In this research, a CVRP extension is proposed that is the problem of the classical one for the environments with various sized circular obstacles. To solve this problem, a hybrid meta-heuristic algorithm based on genetic algorithms improved by a local search was developed. Additionally, a visual simulation tool was designed to place obstacles and locations in the working space. The developed algorithm was tested for different customer-obstacle counts and obstacle sizes with various obstacle occupancies in the environment. The results obtained are presented and the problem’s potential applications are discussed.

Keywords

• Capacitated vehicle routing problem (CVRP)
• Circular obstacles
• Meta-heuristic
• Genetic algorithms
• Local search
• Simulation

Kapasiteli Araç Rotalama Probleminin (KARP) Dairesel Engeller İçeren Ortamlar için Çözümü

Abstract

Kapasiteli araç rotalama probleminde (KARP), belirli kapasitedeki bir araç filosu merkezî bir depodan harekete geçer ve en düşük maliyetli en uygun rota kümesini kullanarak birtakım müşterilere hizmet verip bu başlangıç noktasına geri döner. Gerçek hayatta ise ortamlar farklı büyüklüklerdeki delik, makine veya ağaç gibi engeller içerebilmektedir. Bu çalışmada, klasik KARP’nin çeşitli büyüklüklerdeki dairesel engeller içeren ortamlar için genişletilmiş bir biçimi önerilmektedir. Bu problemi çözmek için yerel arama ile iyileştirilmiş genetik algoritmalar tabanlı melez bir üst-sezgisel algoritma geliştirilmiştir. Ek olarak, çalışma uzayına engeller ve konumlar yerleştirmek için bir görsel benzetim aracı tasarlanmıştır. Geliştirilen algoritma ortam üzerinde çeşitli engel doluluklarıyla farklı müşteri-engel sayıları ve engel büyüklükleri için sınanmıştır. Elde edilen sonuçlar sunulmuş ve problemin potansiyel uygulamaları tartışılmıştır.

Keywords

• Kapasiteli araç rotalama problemi (KARP)
• Dairesel engeller
• Üst-sezgi
• Genetik algoritmalar
• Yerel arama
• Benzetim

References

1. [1] Dantzig, G. B., Ramser, J. H. 1959. The truck dispatching problem. Management Science, 6(1), 80-91.
2. [2] Boonsam, P., Suthikarnnarunai, N., Chitphaiboon, W. 2011. Assignment problem and vehicle routing problem for an improvement of cash distribution. World Congress on Engineering and Computer Science (WCECS), Vol II, October 19-21, San Francisco, USA.
3. [3] Qureshi, G., Bajaj, P. R., Puranik, P. V. 2012. Particle swarm optimization with genetic operators for vehicle routing problem. International Journal of Engineering Science and Technology (IJEST), 4(7), 3086-3090.
4. [4] Yücenur, G. N., Demirel, N. Ç. 2011. A hybrid algorithm with genetic algorithm and ant colony optimization for solving multi-depot vehicle routing problems. Journal of Engineering and Natural Sciences, Sigma 29(3), 340-350.
5. [5] Wang, C. H., Lu, J. Z. 2009. A hybrid genetic algorithm that optimizes capacitated vehicle routing problems. Expert Systems with Applications, 36(2), 2921-2936.
6. [6] Yurtkuran, A., Emel, E. 2010. A new hybrid electromagnetism-like algorithm for capacitated vehicle routing problems. Expert Systems with Applications, 37(4), 3427-3433.
7. [7] Fung, R. Y. K., Liu, R., Jiang, Z. 2013. A memetic algorithm for the open capacitated arc routing problem. Transportation Research Part E: Logistics and Transportation Review, 50, 53-67.
8. [8] Longo, H., de Aragão, M. P., Uchoa, E. 2006. Solving capacitated arc routing problems using a transformation to the CVRP. Computers & Operations Research, 33(6), 1823-1837.

9. [9] Luo, J., Chen, M. R. 2014. Improved shuffled frog leaping algorithm and its multi-phase model for multi-depot vehicle routing problem. Expert Systems with Applications, 41(5), 2535-2545.
10. [10] Stanojević, M., Stanojević, B., Vujošević, M. 2013. Enhanced savings calculation and its applications for solving capacitated vehicle routing problem. Applied Mathematics and Computation, 219(20), 10302-10312.
11. [11] Tlili, T., Faiz, S., Krichen, S. 2014. A hybrid metaheuristic for the distance-constrained capacitated vehicle routing problem. Procedia - Social and Behavioral Sciences, 109, 779-783, 2nd World Conference on Business, Economics and Management.
12. [12] Marinakis, Y., Iordanidou, G. R., Marinaki, M. 2013. Particle swarm optimization for the vehicle routing problem with stochastic demands. Applied Soft Computing, 13(4), 1693-1704.
13. [13] Bortfeldt, A. 2012. A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints. Computers & Operations Research, 39(9), 2248-2257.
14. [14] Cacchiani, V., Hemmelmayr, V. C., Tricoire, F. 2014. A set-covering based heuristic algorithm for the periodic vehicle routing problem. Discrete Applied Mathematics, 163(1), 53-64.
15. [15] Hà, M. H., Bostel, N., Langevin, A., Rousseau, L. M. 2014. An exact algorithm and a metaheuristic for the generalized vehicle routing problem with flexible fleet size. Computers & Operations Research, 43, 9-19.
16. [16] Patle, B. K., Ganesh Babu L, Anish Pandey, Parhi, D. R. K., Jagadeesh, A. 2019. A review: On path planning strategies for navigation of mobile robot. Defence Technology, 15 (4), August, 582 - 606.
17. [17] Patle, B. K., Parhi, D. R. K., Jagadeesh, A., Kashyap, S. K. 2018. Matrix-Binary Codes based Genetic Algorithm for path planning of mobile robot. Computers & Electrical Engineering, 67, April, 708 - 728.
18. [18] Nguyen, H. T., Le, H. X. 2016. Path planning and Obstacle avoidance approaches for Mobile robot. IJCSI International Journal of Computer Science Issues, 13 (4), July.
19. [19] Sudhakara, P., Ganapathy, V., Priyadharshini, B., and Sundaran, K. 2018. Obstacle Avoidance and Navigation Planning of a Wheeled Mobile Robot using Amended Artificial Potential Field Method. Procedia Computer Science, 133, 998 - 1004. International Conference on Robotics and Smart Manufacturing (RoSMa2018).
20. [20] Hassani, I., Maalej, I., Rekik, C. 2018. Robot Path Planning with Avoiding Obstacles in Known Environment Using Free Segments and Turning Points Algorithm. Hindawi Mathematical Problems in Engineering, Article ID 2163278, 13 pages.
21. [21] Sun, G., Zhou, R., Di, B., Dong, Z., Wang, Y. 2019. A Novel Cooperative Path Planning for Multi-robot Persistent Coverage with Obstacles and Coverage Period Constraints. Sensors, 19, 1994.
22. [22] Bai, X., Yan, W., Cao, M., Xue, D. 2019. Distributed multi-vehicle task assignment in a time- invariant drift field with obstacles. IET Control Theory & Applications, 13 (17), Special Issue: Distributed Optimisation and Learning for Networked Systems.
23. [23] Wang, P., Gao, S., Li, L., Sun, B., Cheng, S. 2019. Obstacle Avoidance Path Planning Design for Autonomous Driving Vehicles Based on an Improved Artificial Potential Field Algorithm. Energies, 12, 2342.
24. [24] Moscato, P., Cotta, C. 2003. A gentle introduction to memetic algorithms. pp 105-144. Glover, F., Kochenberger, G. A., ed. Handbook of Metaheuristics, Springer US, 57, Boston MA, 560p.
25. [25] Uğur, A. 2008. Path planning on a cuboid using genetic algorithms. Information Sciences, 178(16), 3275-3287.
26. [26] Chand, P., Mohanty, J. R. 2013. Solving vehicle routing problem with proposed non-dominated sorting genetic algorithm and comparison with classical evolutionary algorithms. International Journal of Computer Applications (IJCA), 69(26), 34-41.
27. [27] Networking and Emerging Optimization. 2013. Capacitated VRP Instances | Vehicle Routing Problem. http://neo.lcc.uma.es/vrp/vrp-instances/capacitated-vrp-instances/ (Access Date: 03.10.2020).
28. [28] Computational Infrastructure for Operations Research. 2003. Vehicle Routing Data Sets. http://www.coin-or.org/SYMPHONY/branchandcut/VRP/data/index.htm.old (Access Date: 03.10.2020).