Vehicle Routing Using Machine Learning Based Ant Colony Optimization

Abstract

Vehicle routing problems are a very important subject area used in many sectors. The fact that heuristic and metaheuristic methods, which are mainly used for vehicle routing problem solutions, do not provide an optimum solution, directs new approaches and algorithm development studies. Therefore, within the scope of this study, solutions were produced to the time-dependent vehicle routing problem by determining the most suitable routes for the route plan created by applying ant colony optimization together with machine learning algorithms, which is an application of artificial intelligence, by determining the shortest and least costly routes. These solutions were also compared with different datasets and heuristic methods. In the study, an advanced new practical approach is presented to the literature by combining machine learning and ant colony optimization to solve heuristic optimization problems. In addition, this study, in which machine learning and ant colony optimization are used together for the solution of vehicle routing problems, has been brought to the literature with this subject.

Keywords

• Vehicle Routing
• Traveling Salesman Problem
• Ant Colony Optimization
• Clustering
• Machine Learning

Makine Öğrenmesi Tabanlı Karınca Kolonisi Optimizasyonu Kullanarak Araç Rotalama

Abstract

Araç rotalama problemleri birçok sektörde kullanılan çok önemli bir konu alanıdır. Araç rotalama problem çözümleri için ağırlıklı olarak kullanılan sezgisel ve metasezgisel yöntemlerin optimum bir çözüm sunmaması yeni yaklaşım ve algoritma geliştirme çalışmalarına yön vermektedir. Bu yüzden bu çalışma kapsamında zaman bağımlı araç rotalama problemine, yapay zekanın bir uygulaması olan makine öğrenmesi algoritmaları ile birlikte karınca kolonisi optimizasyonu uygulanarak oluşturulan rota planı için en uygun rotalar en kısa ve az maliyetle belirlenerek çözümler üretilmiştir. Üretilen bu çözümler farklı veri kümeleri ve sezgisel yöntemlerle de karşılaştırılmıştır. Çalışmada sezgisel optimizasyon problemlerini çözmek için makine öğrenimi ve karınca kolonisi optimizasyonu birleştirilerek literatüre gelişmiş yeni bir pratik yaklaşım sunulmuştur. Ayrıca araç rotalama problemlerinin çözümü için makine öğrenmesi ve karınca kolonisi optimizasyonunun bir arada kullanıldığı bu çalışma bu konu ile literatüre kazandırılmıştır.

Keywords

• Araç Rotalama
• Gezgin Satıcı Problemi
• Karınca Kolonisi Optimizasyonu
• Kümeleme
• Makine Öğrenmesi

References

1. Bajpai A., Yadav R. (2015) Ant Colony Optimization (ACO) for The Traveling Salesman Problem (TSP) Using Partitioning, International Journal of Scientific & Technology Research, 4(09): 376-381.
2. Castillo O., Neyoy H., Soria J., et al. (2015) A New Approach for Dynamic Fuzzy Logic Parameter Tuning in Ant Colony Optimization and its Application in Fuzzy Control of a Mobile Robot, Applied Soft Computing, vol. 28, pp. 150-159.
3. Cheng B., Lu H., Huang Y., Xu K. (2016) An Improved Particle Swarm Optimization Algorithm Based on Cauchy Operator and 3-Opt for TSP, 17th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT), pp. 177-182.
4. Dikmen H., Dikmen H., Elbir A., Ekşi Z., Çelik F. (2014) Gezgin Satıcı Probleminin Karınca Kolonisi ve Genetik Algoritmalarla Eniyilemesi ve Karşılaştırılması, Süleyman Demirel Üniversitesi Fen Bilimleri Enstitüsü Dergisi, 18(1): 8-13.
5. Dorigo M., Birattari M. (2011) Ant Colony Optimization, In Encyclopedia of Machine Learning, pp. 36-39, Boston, MA: Springer.
6. Dorigo M., Di Caro G. (1999) Ant Colony Optimization: A New Meta-heuristic, Congress on Evolutionary Computation-CEC 99, vol. 2, pp. 1470-1477.
7. Ebadinezhad S. (2020) DEACO: Adopting Dynamic Evaporation Strategy to Enhance ACO Algorithm for the Traveling Salesman Problem, Engineering Applications of Artificial Intelligence, vol. 92.
8. Eren Şenaras A., İnanç Ş. (2017) GSP Çözümü için Karınca Kolonisi Optimizasyonu, International Congress of Management Economy and Policy (ICOMEP), İstanbul, Türkiye, 20-21 Mayıs, 58-67.

9. Eröz E., Tanyıldızı E. (2018) Güncel Metasezgisel Optimizasyon Algoritmalarının Performans Karşılaştırılması, International Conference on Artificial Intelligence and Data Processing (IDAP), Malatya, Türkiye.
10. Karagul K., Tokat S., Aydemir E. (2016) Kapasite Kısıtlı Araç Rotalama Problemlerinde Başlangıç Rotalarının Kurulması için Yeni Bir Algoritma, Mühendislik Bilimleri ve Tasarım Dergisi, 4(3): 215-226.
11. Keskintürk T., Topuk N., Özyeşil O. (2015) Araç Rotalama Problemleri ile Çözüm Yöntemlerinin Sınıflandırılması ve Bir Uygulama, İşletme Bilimi Dergisi, Cilt:3, Sayı:2.
12. Liu C., Kou G., Zhou X., et al. (2020) Time-Dependent Vehicle Routing Problem with Time Windows of City Logistics with a Congestion Avoidance Approach, Knowledge-Based Systems, vol. 188.
13. Liu Y., Cao B., Li H. (2020) Improving Ant Colony Optimization Algorithm with Epsilon Greedy and Levy Flight, Complex & Intelligent Systems, 7:1711–1722.
14. Necula R., Breaban M., Raschip M. (2017) Tackling Dynamic Vehicle Routing Problem with Time Windows by means of Ant Colony System, IEEE.
15. Oonsrikaw Y., Thammano A. (2018) Enhanced Ant Colony Optimization with Local Search, 17th International Conference on Computer and Information Science (ICIS), pp. 291-296.
16. Pala O., Aksaraylı M. (2018) Çok Amaçlı Kapasite Kısıtlı Araç Rotalama Problemi Çözümünde Bir Karınca Kolonisi Optimizasyon Algoritması Yaklaşımı, Alphanumeric Dergisi, Cilt:6, Sayı:1.
17. Ratanavilisagul C. (2017) Modified Ant Colony Optimization with Pheromone Mutation for Travelling Salesman Problem, 14th International Conference on Electrical Engineering/Electronics, Computer, Telecommunications and Information Technology (ECTI-CON), pp. 411-414.
18. Ratanavilisagul C., Pasaya B. (2018) Modified Ant Colony Optimization with updating Pheromone by Leader and Re-initialization Pheromone for Travelling Salesman Problem, International Conference on Engineering, Applied Sciences, and Technology (ICEAST), pp. 1-4.
19. Reinelt G. (1994) The Traveling Salesman, Computational Solutions for TSP Applications, Springer-Verlag Berlin Heidelberg.
20. Solomon M. M. (1987) Algorithms for the Vehicle Routing and Scheduling Problems with Time Windows Constraints, Operations Research, vol. 35, No. 2, pp. 254-265.
21. Ye D., Wanhong Z., Hongwei L., Yonghui Z. (2018) Multi-Type Ant System Algorithm for the Time Dependent Vehicle Routing Problem with Time Windows, Journal of Systems Engineering and Electronics (BIAI), vol. 29, pp. 625–638.
22. Yücenur G. N., Çetin Demirel N. (2011) Çok Depolu Araç Rotalama Problemlerinin Çözümü için Genetik Algoritma ve Karınca Kolonisi Optimizasyonundan Oluşan Melez Algoritma Tasarımı, Mühendislik ve Fen Bilimleri Dergisi, 340-350.
23. Zhang H., Zhang Q., Ma L., et al. (2019) A Hybrid Ant Colony Optimization Algorithm for a Multi-Objective Vehicle Routing Problem with Flexible Time Windows, Information Sciences, vol. 490, pp. 166-190.
24. Wang Y., Wang L., Chen G., et al. (2020) An Improved Ant Colony Optimization Algorithm to the Periodic Vehicle Routing Problem with Time Window and Service Choice, Swarm and Evolutionary Computation (SWEVO), vol. 55.