Karınca Kolonisi Algoritmasının Gerçek Hayat Kapasiteli Araç Rotalama Problemi İçin Uygulanması

Abstract

Bu çalışmada Türkiye’nin Kayseri ilinde faaliyet gösteren bir lojistik firmasının gerçek verileri kullanılarak, firmanın karşı karşıya kaldığı homojen kapasiteli çok araçlı araç rotalama problemi ele alınmıştır. Firma Kayseri’de bulunan depodan, 50 farklı konumda bulunan talep noktalarının siparişlerini haftalık periyotlar ile karşılayacak sevkiyat rotasını, elde bulunan araç sayısını aşmadan, minimum maliyet ile elde etmek istemektedir. Problemin çözümü için literatürde yer alan lineer matematiksel model OpenSolver yazılımı ile üzerinde kodlanmıştır. Matematiksel model 10, 15 ve 20 talep noktalı küçük alt problemler için optimum çözüm elde edebilmiştir. 50 talep noktalı gerçek problem için Karınca kolonisi metasezgiseli kodlanmıştır. Metasezgisel modelin kodlanmasında Pycharm paket program ara yüzü üzerinden Python programlama dili kullanılmıştır. Metasezgisel çözümlerinin kalitesi matematiksel çözümler ile ispat edilmiştir. Metasezgisel model ile elde edilen gerçek problem çözümü firmanın mevcut durum değerleri ile kıyaslanmıştır. Elde edilen çözüm firmanın mevcut politikasına oranla %297,6 daha iyi maliyet, %236,61 daha az mesafe sonucunu sağlamıştır.

Keywords

• Karınca Kolonisi Algoritması
• Kapasite Kısıtlı Araç Rotalama
• Matematiksel Modelleme
• Yapay Zeka ile optimizasyon
• Gerçek Hayat Uygulaması

Ant Colony Algorithm for Capacitated Vehicle Routing Problem: A Real Life Application

Abstract

In this study, using the real data of a logistics company operating in Kayseri, Turkey, the homogeneous capacity multi-vehicle vehicle routing problem faced by the company is discussed. The company wants to obtain the shipment route that will meet the orders of demand points in 50 different locations on a weekly basis from the warehouse in Kayseri, without exceeding the number of vehicles at hand, with minimum cost. For the solution of the problem, the linear mathematical model in the literature was coded with OpenSolver software. The mathematical model was able to obtain the optimum solution for small subproblems with 10, 15 and 20 demand points. Ant colony metaheuristic is coded for the real problem with 50 demand points. In the coding of the metaheuristic model, Python programming language was used over the Pycharm package program interface. The quality of metaheuristic solutions has been proven by mathematical solutions. The real problem solution obtained with the metaheuristic model is compared with the current state values ​​of the company. The solution obtained provided the result of 297.6% better cost and 236.61% less distance compared to the current policy of the company.

Keywords

• Ant Colony Algorithm
• Capacitated Vehicle Routing
• Mathematical Modelling
• Artificial Intelligence
• Real Life Application

References

1. [1] Irnich S., Toth P., and Vigo D., “Vehicle Routing, Chapter 1: The Family of Vehicle Routing Problems, MOS-SIAM Series on Optimization”, Philadelphia, pp.1 – 33, (2014).
2. [2] Vukadinovic K., Teodorovic D., Pavkovic G.Ö “ An application of neurofuzzy modeling: The vehicle assignment problem”, European Journal of Operational Research 114, 474-488 (1999)
3. [3] Bashiri M., Rasoulinejad Z. & Fallahzade E. “A new approach on auxiliary vehicle assignment in capacitated location routing problem”, International Journal of Systems Science, 47:4, (2016)
4. [4] Liong C-Y., Omar K., “Vehicle routing problem: Models and solutions”, Journal of Quality Measurement and Analysis JQMA 4(1), 205-218, (2008)
5. [5] Cordeau J-F., Laporte G. & Mercier A, “A unified tabu search heuristic for vehicle routing problems with time Windows”, Journal of the Operational Research Society, 52:8, 928-936, (2001)
6. [6] KESKİNTÜRK T., TOPUK & ÖZYEŞİL O., “Araç Rotalama Problemleri ile Çözüm Yöntemlerinin Sınıflandırılması ve Bir Uygulama”, İşletme Bilimi Dergisi Cilt:3 Sayı:2 77-107, (2015)
7. [7] Chang M-S. “A vehicle routing problem with time windows and stochastic demands”, Journal of the Chinese Institute of Engineers, 28:5, 783-794, (2005)
8. [8] Khodabandeh E., Bai L., Heragu S-S., Evans G-W., Elrod T. & Shirkness M. “Modelling and solution of a large-scale vehicle routing problem at GE appliances & lighting”, International Journal of Production Research, 55:4, 1100-1116, (2017)

9. [9] Cantu-Funes R., Salazar-Aguilar M-A. & Boyer V. “Multi-depot periodic vehicle routing problem with due dates and time Windows”, Journal of the Operational Research Society, 69:2, 296-306, (2018)
10. [10] Crainic T-G., Gajpal Y.& Gendreau M., “Multi-Zone Multi-Trip Vehicle Routing Problem with Time Windows”, INFOR: Information Systems and Operational Research, 53:2, 49-67, (2015)
11. [11] Giosa I-D., Tansini I-L. & Viera I-O., “New assignment algorithms for the multi-depot vehicle routing problem”, Journal of the Operational Research Society, 53:9, 977-984, (2002)
12. [12] Ng W-L., Leung S-C-H., Lam J-K-P. & Pan S-W., “Petrol delivery tanker assignment and routing: a case study in Hong Kong”, Journal of the Operational Research Society, 59:9, 1191-1200, (2008)
13. [13] Liu F-H. & Shen S-Y., “The fleet size and mix vehicle routing problem with time windows”, Journal of the Operational Research Society, 50:7, 721-732, (1999)
14. [14] ALAYKIRAN K., ENGİN O., “Karınca Kolonileri Metasezgiseli ve Gezgin Satıcı Problemleri Üzerinde Bir Uygulaması”, Gazi Üniv. Müh. Mim. Fak. Der. Cilt 20, No 1, 69-76, (2005)
15. [15] KESKİNTÜRK T., SÖYLER H., “Global Karınca Kolonisi Optimizasyonu”, Gazi Üniv. Müh. Mim. Fak. Der. Cilt 21, No 4, 689-698, (2006)
16. [16] ATAN M., ŞİMŞEK P., “Doğrusal Programlama ile Araç Atama Probleminin Çözümlenmesi”, Gazi Üniversitesi Sosyal Bilimler Dergisi Vol/Cilt:4, No/Sayı:11, 339-358, (2017)
17. [17] GÜZEL D., ERDAL H. & ACAR E. “Kolluk Kuvvetlerinin Hizmet Üretim Etkinliğinin Artırılmasına Yönelik Bir Model Önerisi: Bütünleşik Araç Atama Modeli”, International Journal of Social Science, Number: 40, p. 463-483, (2015)
18. [18] Kiremitci B., Kiremitci S. ve Keskintürk T., “Zaman pencereli çok araçlı dağıtım toplamalı rotalama problemi için gerçek değerli genetik algoritma yaklaşımı”, İstanbul Üniversitesi İşletme Fakültesi Dergisi Istanbul University Journal of the School of Business Cilt/Vol:43, Sayı/No:2, 391-403 ISSN: 1303-1732, (2014)
19. [19] GÖÇKEN T., YAKTUBAY M. ve KILIÇ F., “Zaman Pencereli Araç Rotalama Problemi Çözümü İçin Çok Amaçlı Genetik Algoritma Yaklaşımı”, Gazi Üniversitesi Fen Bilimleri Dergisi Part C: Tasarım ve Teknoloji, GU J Sci, Part C, 6(4): 774-786,(2018)
20. [20] KOÇ Ç. ve KARAOĞLAN İ., “Çok Kullanımlı ve Zaman Pencereli Araç Rotalama Problemi İçin Bir Matematiksel Model”, Gazi Üni. Müh. Mim. Fak. Der. Cilt 27, No 3, 569-576, 2012
21. [21] CEVRE U., “Çoklu Gezgin Satıcı Probleminin Çözümü İçin Bir Eniyileme Kütüphanesinin Tasarımı ve Görsel Yazılımı Geliştirme Ortamı ile birlikte gerçekleştirimi”, Yüksek Lisans Tezi, Bornova – İzmir, 2008
22. [22] ULUTAŞ A., BAYRAKÇIL A-O. ve KUTLU M-B., “Araç Rotalama Probleminin Tasarruf Algoritması ile Çözümü”, İdari Bilimler Dergisi, Cilt 18, Sayı 1, 2017
23. [23] ÖNDER E., “İstanbul halk ekmek A.Ş. (İHE)'ye Ait Çok Depolu Araç Rotalama Probleminin Meta-Sezgisel Yöntemi ile Optimizasyonu”, yönetim yılı: 22 sayı 70, 2011
24. [24] SÖYLER H. ve KESKİNTÜRK T., “Karınca Kolonisi Algoritması İle Gezgin Satıcı Probleminin Çözümü”, 8. Türkiye Ekonometri ve İstatistik Kongresi 24-25 Mayıs 2007 – İnönü Üniversitesi Malatya
25. [25] YARDIMCI İ., VAYVAY Ö. ve TANYAŞ M., “Kentsel Lojistikte Araç Rotalama”, V. Ulusal Lojistik ve Tedarik Zinciri Kongresi 2016 Toros Üniversitesi / Mersin
26. [26] Boer J-W. “Approximate Models and Solution Approaches For The Vehicle Routing Problem With Multiple Use Of Vehicles And Time Windows”, A Thesis Submitted to The Graduate School Of Natural and Applied Sciences Of Middle East Technical University, (2008)
27. [27] DURSUN P., “Zaman Pencereli Araç Rotalama Problemi’nin Genetik Algoritma ile Modellenmesi”, İTÜ -Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi, (2009)
28. [28] SÖYLER H. ve KESKİNTÜRK T., “Karınca Kolonisi Algoritması İle Gezgin Satıcı Probleminin Çözümü”, 8. Türkiye Ekonometri ve İstatistik Kongresi 24-25 Mayıs 2007 – İnönü Üniversitesi Malatya
29. [29] SÖZEN S., “Bir Kamu Kurumunda Görev Yapan Denetim Görevlileri İçin Görev Atama Problemi ve Çözümü”, Gazi Üniversitesi Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi Endüstri Mühendisliği Anabilim Dalı, 2016
30. [30] KÜÇÜK M. Ve TOPALOĞLU YILDIZ Ş., “Zaman pencereli toplama ve dağıtım problemi için kısıt programlama yaklaşımı”, Pamukkale Uni. Müh. Bilim Derg., 25(9), 1041-1049, 2019.
31. [31] Dethloff J., “Vehicle routing and reverse logistics: the vehicle routing problem with simultaneous delivery and pick-up”, OR Spektrum 23: 79–96, (2001)
32. [32] EKİZLER H., “Araç Rotalama Probleminin Çözümünde Karınca Kolonisi Optimizasyonu Algoritmasının Kullanılması”, İstanbul Üni. Fen Bilimleri Enstitüsü, Yüksek Lisans Tezi, Endüstri Mühendisliği Anabilim Dalı, İstanbul, (2011)
33. [33] KAYA C., “Eş Zamanlı Topla-Dağıt Rotalama Problemi İçin Karınca Koloni Sistemi ile Güçlendirilmiş Değişken Komşuluk Arama Algoritması”, Pamukkale Üniversitesi Fen Bilimleri Enstitüsü Yüksek Lisans Tezi, Endüstri Mühendisliği Anabilim Dalı, Denizli, (2017).”
34. [34] GÜLSOY N., “Av Arama Algoritması ile Sıkı Zaman Pencereli Araç Rotalama Problemlerinin çözümü”, Erciyes Üniversitesi Fen Bilimleri Enstitüsü Yüksek Lisans Tezi, Endüstri Mühendisliği Anabilim Dalı, Kayseri, (2013),
35. [35] Ioannou G & Kritikos M-N., “A synthesis of assignment and heuristic solutions for vehicle routing with time windows”, Journal of the Operational Research Society, 55:1,2-11, (2004).