Capacity Restricted Vehicle Routing Optimization with an Annealing Simulation Based Approach: Black Sea Region Case

Year 2021, Issue: 22, 239 - 248, 31.01.2021

Ayten Yılmaz Yalçıner

https://doi.org/10.31590/ejosat.851540

Cited By: 2

Abstract

In the logistics sector, which is one of the most critical and strategic areas of today, businesses want to minimize costs by minimizing both the number of vehicles and the distance they travel. In this context, Vehicle Routing Problems (ARP), which is a widely used optimization type, offers effective solution alternatives with different techniques for different situations. It is important that the algorithm developed in Capacity Restricted Vehicle Routing (KKAR) problems, which is an important type of ARP, gives consistent and good results. In this study, it is aimed to present an optimization model aiming to find the shortest distance for these models in line with certain constraints by creating different models for problems involving variable location (location / city) number and variable number of vehicles, which can be applied to many businesses. Simulated Annealing algorithm, which is one of the meta-heuristic solution methods, was used in the application. The algorithm established with a data set obtained from online accessible databases was tested, and then the application study was carried out with the scenario where distribution is made to the provinces of the Black Sea Region from the distribution center, whose central warehouse is Istanbul.

Keywords

Vehicle Routing Problem, Capacity Limited Vehicle Routing, Simulated Annealing Method

Tavlama Benzetimi Temelli Yaklaşım ile Kapasite Kısıtlı Araç Rotalama Optimizasyonu: Karadeniz Bölgesi Örneği

Abstract

Yoğun rekabet baskısı altındaki firmaların dünyanın dört bir yanına ürünlerini, mallarını etkin dağıtım kanalları aracılığıyla ulaştırmaları günümüzde rekabet açısından kritik bir unsurdur. Kilit sektörlerden lojistikte maliyetlerin büyük bir bölümünü taşıma maliyetleri oluşturmaktadır. Taşıma maliyetleri kapsamında hem araç sayılarını, hem kat ettikleri mesafeyi hem de maliyeti minimize etmek isteyen işletmeler farklı çözüm arayışlarına gitmektedirler. Bu kapsamda Araç Rotalama Problemleri (ARP) farklı durumlara farklı teknikleri ile etkin çözüm alternatifleri sunmaktadır. Araç sayısı, kat edilen mesafe ve maliyet kısıtları üzerinden eniyileme konusuna odaklanan ve etkili çözümler sunarak yaygın kullanım alanına sahip bir optimizasyon çeşidi olan ARP’nin önemli bir türü olan Kapasite Kısıtlı Araç Rotalama (KKAR) problemlerinde müşteri taleplerini karşılamak ve aynı zamanda katedilen mesafeyi azaltmak için geliştirilen algoritmanın tutarlı ve iyi sonuçlar vermesi önemlidir.
Bu çalışmada birçok işletme için uygulanabilecek, değişken konum (lokasyon/şehir) sayısı ve değişken araç sayısı içeren problemlere yönelik farklı modeller oluşturarak bu modeller için belirli kısıtlar doğrultusunda en kısa mesafeyi bulmayı hedefleyen bir optimizasyon modeli sunulmak amaçlanmıştır. Uygulamada Kapasite Kısıtlı Araç Rotalama Problemlerinde sıklıkla kullanılan, iyi sonuçlar veren, meta sezgisel çözüm yöntemlerinden biri olan Tavlama Benzetimi algoritması kullanılmıştır. Geliştirilen algoritma MATLAB R2017 programı ile çalıştırılmıştır. Koordinatların, araç sayısının ve şehir sayısının bilindiği modeller için uygulanabilir formdaki algoritma ile belli bir işletmeye özgü olmayan, genel bir araç rotalama problemi çözümü elde etmek istenmiştir. Talep miktarının az olduğu işletmeler için uygun olan modelde müşteri talepleri göz önünde bulundurulmaktadır ve birden fazla araç için çözüm üretilebilmektedir. Online erişilebilir hazır veritabanlarından elde edilen bir veri seti ile öncelikle kurulan algoritma test edilmiş, daha sonra da Karadeniz Bölgesi illerine İstanbul merkezli bir depodan dağıtım gerçekleştirildiği düşünülen bir uygulama gerçekleştirilmiştir. Yöntem için elde edilen gerekli parametreler belirlenerek elde edilen çözümler tablo haline dönüştürülüp listelenmiş ve bilinen en iyi çözümle karşılaştırılması sunulmuştur.

Keywords

Araç Rotalama Problemi, Kapasite kısıtlı araç rotalama, Tavlama Benzetimi, Lineer Programlama

References

• Baños, R.,Ortega, J., Gil, C., Fernández,A., & Toro, F. (2013). A simulated annealing-based parallel multi-objective approach to vehicle routing problems with time windows, Expert Systems with Applications 40 (5), 1696–1707
• Choosak, P. (2014). A particle swarm optimization for the vehicle routing problem. University of Rhode Island, Dissertation, Doctor of Philosophy in Industrial and Systems Engineering.
• Dorigo, M., Birattari, M. & Stutzle, T. (2006). Ant colony optimization, in IEEE Computational Intelligence Magazine, 1, 4,. 28-39, doi: 10.1109/MCI.2006.329691.
• Ekizler, H. (2011). Araç rotalama probleminin çözümünde karınca kolonisi optimizasyonu algoritmasının kullanılması. Yüksek Lisans Tezi. İstanbul Üniversitesi Fen Bilimleri Enstitüsü Endüstri Mühendisliği Anabilim Dalı.
• Erol, V. (2006). Araç rotalama sistemleri için popülasyon ve komşuluk tabanlı metasezgisel bir algoritmanın tasarımı ve uygulaması. Yüksek Lisans Tezi. Yıldız Teknik Üniversitesi, Fen Bilimleri Enstitüsü.
• Ezugwua, A.E., Adewumi, A.O., Frîncu, M.E. (2017). Simulated annealing based symbiotic organisms search optimization algorithm for traveling salesman problem, Expert Systems With Applications, 77, 189–210.
• Karagül, 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, 2016.
• Kaya, C. (2017). Eş zamanlı topla dağıt araç rotalama problemi için karınca koloni sistemi ile güçlendirilmiş değişken komşuluk arama algoritması. Yüksek Lisans Tezi. Pamukkale Üniversitesi Fen Bilimleri Enstitüsü Endüstri Mühendisliği Anabilim Dalı.
• Kızıloğlu, K. (2017). Stokastik talepli çok Depolu Araç Rotalama Problemi İçin Sezgisel Bir Çözüm Yaklaşımı. Yüksek Lisans Tezi. Gazi Üniversitesi Fen Bilimleri Enstitüsü.
• Koç, Ç., (2012). Zaman bağımlı araç rotalama problemi. Yüksek Lisans Tezi. Selçuk Üniversitesi, Fen Bilimleri Enstitüsü.
• Kumar, S.N., Panneerselvam, R. (2012). A survey on the vehicle routing problem and its variants. Intelligent Information Management,04, 03. 10.4236/iim.2012.43010
• Mahmudy, W.F. (2014). Improved simulated annealing for optimization of vehicle routing problem with time windows (VRPTW), Jurnal Ilmiah KURSOR. 7 (3), 109-116, Mu, D., Wang, C., Zhao, F. & Sutherland, J.W. (2016 ). Solving vehicle routing problem with simultaneous pickup and delivery using parallel simulated annealing algorithm, Int. J. Shipping and Transport Logistics 8, 1, ,81–106.
• Singh, V.P., Sharma, K. (2021). Capacitated Vehicle Routing Problem with Interval Type-2 Fuzzy Demands. In: Kalamkar V., Monkova K. (eds) Advances in Mechanical Engineering. Lecture Notes in Mechanical Engineering. Springer, Singapore. https://doi.org/10.1007/978-981-15-3639-7_11
• Sitek, P., Wikarek, J. (2019). Capacitated vehicle routing problem with pick-up and alternative delivery (CVRPPAD): model and implementation using hybrid approach, Ann Oper Res 273, 257–277, https://doi.org/10.1007/s10479-017-2722-x
• Şahin, Y., Eroğlu, A. (2014). Kapasite kısıtlı araç rotalama problemi için metasezgisel yöntemler: Bilimsel yazın taraması, Süleyman Demirel Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 19 (4), 337-355.
• Taş, O. (2007). Havayolu Şirketlerinde Uçuşların Atanması Probleminin Tavlama Benzetimi Yöntemi İle Çözülmesi. Yüksek Lisans Tezi. Çukurova Üniversitesi.
• Toth, P., Vigo, D. (2002). The Vehicle Routing Problem, Society For Industrial And Applied Mathematics.. https://epubs.siam.org/doi/pdf/10.1137/1.9780898718515.fm
• Uyumaz, D. (2017). Kapasite kısıtlı araç rotalama probleminin paralel genetik algoritma ile çözümü. Yüksek Lisans Tezi. Karabük Üniversitesi, Fen Bilimleri Enstitüsü Bilgisayar Mühendisliği Anabilim Dalı.
• Wang, J., Jagannathan, A.K.R., Zuo, X., Murray, C.C. (2017). Two-layer simulated annealing and tabu search heuristics for a vehicle routing problem with cross docks and split deliveries, Computers & Industrial Engineering, 112, 84–98.
• Wei, L., Zhang, Z., Zhang, D., Leung, S.C.H. (2018). A simulated annealing algorithm for the capacitated vehicle routing problem with two-dimensional loading constraints, European Journal of Operational Research 265, 843–859.
• http://vrp.atd-lab.inf.puc-rio.br/index.php/en/
• https://www.kgm.gov.tr/SiteCollectionDocuments/KGMdocuments/Root/Uzakliklar/ilmesafe.xls