An Application for the Homogeneous and Heterogeneous Fleet, Capacity Constrained Vehicle Routing Problem

Abstract

In today's competitive world, companies make a maximum effort to provide logistics support, which is of great importance, during the delivery of their products to their customers. Vehicle routing problems (VRP) are the most important last stage of Logistics problems. Vehicle routing problems are the problems of finding near-optimal routes with vehicles of the same or different capacities from a warehouse to meet the demands of customers in the shortest distance and in the shortest time. VRP continues to offer the best results to companies with its increasing variety. In this study, routes were created by using the actual distances and coordinates used by a bread factory during the distribution of bread to 20 markets. In modelling this real-life problem, the classical capacity vehicle routing model is modelled as both homogeneous and heterogeneous fleets. Then ear-optimal solution for the problem is calculated in Matlab using the Simulated Annealing (SA) algorithm. The meta-heuristic solutions obtained with TB were compared with the bread factory's own routes. Then ear-optimal results obtained with the TB gave better results than the total route distances of the furnace itself in all tests. Using the TB algorithm, the greatest difference between the total route distance and the furnace during the distribution with two vehicles is 8.8 km. The greatest difference between the total route distance and the furnace during the distribution made with three vehicles in the TB was calculated as 6.5 km.

Keywords

• Optimization
• Vehicle Routing
• Simulated Annealing

Homojen ve Heterojen Filolu, Kapasite Kısıtlı Araç Rotalama Problemi İçin Bir Uygulama

Abstract

Günümüz rekabet dünyasında firmalar ürünlerinin müşterilerine ulaştırılması aşamasında, büyük bir öneme sahip olan lojistik desteği sağlamak adına maksimum bir çaba içerisindedirler. Araç rotalama problemleri (ARP), Lojistik problemlerinin en önemli son aşamasıdır. Araç rotalama problemleri, en kısa mesafede ve en kısa sürede müşterilerinin taleplerini karşılayacak şekilde bir depodan aynı veya farklı kapasitelerdeki araçlar ile optimale yakın rotaların bulunması problemleridir. ARP, artan çeşitleri ile firmalara en iyi sonuçları sunmaya devam etmektedir. Bu çalışmada bir ekmek fabrikasının 20 markete ekmek dağıtımı sırasında kullandığı gerçek mesafeler ve koordinatlar kullanılarak rotalar oluşturulmuştur. Bu gerçek hayat problemini modellemede klasik kapasiteli araç rotalama modeli hem homojen hem de heterojen filolu olarak modellenmiştir. Problem için optimale yakın çözümü, tavlama benzetimi (TB) algoritması kullanılarak Matlab’da hesaplanmıştır. TB ile elde edilen meta sezgisel çözümler ekmek fabrikasının kendi rotaları ile karşılaştırılmıştır. TB ile elde edilen optimale yakın sonuçlar yapılan tüm testlerde fırının kendi toplam rota mesafelerinden daha iyi sonuçlar vermiştir. TB algoritmasını kullanarak, iki araç ile yapılan dağıtım sırasında oluşan toplam rota mesafesinin fırın ile en büyük farkı 8,8 km’dir. TB’de üç araç ile yapılan dağıtım sırasında oluşan toplam rota mesafesinin fırın ile en büyük farkı 6,5 km olarak hesaplanmıştır.

Keywords

• Optimizasyon
• Araç Rotalama
• Tavlama Benzetimi

References

1. Ruiz, R., Maroto, C., & Alcaraz, J. (2004). A Decision Support System for a Real Vehicle Routing Problem. European Journal of Operational Research, 153, 593-606.
2. Shen, Z., Ordónez, F., & Dessouky. M. M. (2009). The Stochastic Vehicle Routing Problem for Minimum Unmet Demand. In Optimization and Logistics Challenges in the Enterprise, Springer, Boston, MA, 349-371.
3. Garey, M. R., & Johnson, D. S. (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. WH Freeman & Co. New York, NY, USA.
4. Dantzig, G. B., & Ramser, J. H. (1959). The Truck Dispatching Problem. Management Science, 6(1), 80-91.
5. Clarke, G., & Wright, J. W. (1964). Scheduling of Vehicles from a Central Depotto a Number of Delivery Points. Operations Research,12(4), 568-581.
6. Bramel, J., & Simchi-Levi, D.(1999). The Logics of Logistics, Theory, Algorithms, and Applications for Logistics Management, second ed. In: Springer Series in Operations Research. Springer-Verlag, New York.
7. Toth, P., & Vigo, D. (Eds.). (2002). The Vehicle Routing Problem. Society for Industrial and Applied Mathematics.
8. Kirkpatrick, S., Gelatt, C. D., & Vecchi, M. P. (1983). Optimization by Simulated Annealing. Science, 220 (4598), 671-680.

9. Cerny, V. (1985). Thermodynamical Approach to The Traveling Salesman Problem: An Efficient Simulation Algorithm. Journal of Optimization Theory and Applications, 45 (1), 41–51.
10. Osman, I. H. (1993). Metastrategy Simulated Annealing and Tabu Search Algorithms for The Vehicle Routing Problem. Annals of Operations Research, 41, 421–451.
11. Breedam, A. V. (1995). Improvement Heuristics for The Vehicle Routing Problem Based on Simulated Annealing. European Journal of Operations Research, 86(3), 480–490.
12. Chiang, W. C., & Russell, R. A. (1996). Simulated Annealing Metaheuristics for The Vehicle Routing Problem with Time Windows. Annals of Operations Research, 63(1), 3–27.
13. Rabbouch, B., Saadaui, F., & Mraihi, R. (2020). Empirical-Type Simulated Annealing For Solving The Capacitated Vehicle Routing Problem, Journal of Experimental & Theoretical Artificial Intelligence, 32 (3), 437-452.
14. İlhan, İ. A. (2020). Population Based Simulated Annealing Algorithm for Capacitated Vehicle Routing Problem. Turkish Journal of Electrical Engineering & Computer Sciences, 28, 1217 – 1235.
15. 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.
16. Tavakkoli-Moghaddam, R., Safaei, N., & Gholipour, Y. (2006). A Hybrid Simulated Annealing for Capacitated Vehicle Routing Problems With The İndependent Route Length. Applied Mathematics and Computation,176(2), 445-454.
17. Xiao, Y.,Zhao, Q., Kaku, I., & Xu, Y. (2012). Development of a Fuel Consumption Optimization Model for The Capacitated Vehicle Routing Problem, Computers & Operations Research, 39(7), 1419-1431.
18. Yalçıner, A. Y. (2021). Tavlama Benzetimi Temelli Yaklaşım ile Kapasite Kısıtlı Araç Rotalama Optimizasyonu: Karadeniz Bölgesi Örneği. Avrupa Bilim ve Teknoloji Dergisi, 22, 239-248.
19. Ulutaş, A., Bayrakçıl, A. O., & Kutlu, B. (2017). Araç Rotalama Probleminin Tasarruf Algoritması ile Çözümü: Sivas’ta Bir Ekmek Fırını İçin Uygulama. Cumhuriyet Üniversitesi İktisadi ve İdari Bilimler Dergisi,18(1),185-197.
20. Okur, E., & Atlas, Ü. M. (2020). Araç Rotalama Probleminin Genetik Algoritma ile Çözümü. Anadolu University Journal of Social Sciences, 20(3), 227-254.
21. Taillard, É. D. 1999. A heuristic column generation method for the heterogeneous fleet VRP. RAIRO-Operations Research, 33(1), 1-14.
22. Yousefikhoshbakht, M., Didehvar, F., & Rahmati, F. (2014). Solving the heterogeneous fixed fleet open vehicle routing problem by a combined metaheuristic algorithm. International Journal of Production Research, 52(9), 2565-2575.
23. Çetin, S., & Gencer, C. (2011). Heterojen araç filolu zaman pencereli eş zamanlı dağıtım-toplamalı araç rotalama problemleri: matematiksel model. International Journal of Engineering Research and Development, 3(1), 19-27.
24. Ağayeva Ç., & Takan M. A. (2020). Stokastik Talepli Kapasite Kısıtlı Araç Rotalama Problemine Yönelik Karşılaştırmalı Bir Yaklaşım. Bilecik Şeyh Edebali Üniversitesi Fen Bilimleri Dergisi, 7(2), 971-979.
25. Cömert, S. E., Yazgan, H. R., & Kılıç, E. N. (2020). Araç Rotalama Probleminin Sezgisel Algoritmalar ile Çözülmesi: Bir Boya Fabrikasında Uygulama. Journal of Turkish Operations Management, 4 (2), 549-563.
26. 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ü, İstanbul. Metropolis, N., Rosenbluth, A. W., Rosenbluth, M. N., Teller, A. H., & Teller, E. (1953). Equation of State Calculations by Fast Computing Machines. The Journal Of Chemical Physics, 21(6), 1087-1092.
27. Gendreau, M., & Potvin, J. Y. (2005). Metaheuristics in Combinatorial Optimization. Annals of Operations Research,140(1), 189-213.
28. Kızıloğlu, K. (2017). Stokastik Talepli Çok Depolu Araç Rotalama Problemi için Sezgisel Bir Çözüm Yaklaşımı. Yüksek Lisan Tezi, Gazi Üniversitesi Fen Bilimleri Enstitüsü, Ankara.
29. Güden, H., Vakvak, B., Özkan, B. E., Altıparmak, F., & Dengiz, B. (2005). Genel Amaçlı Arama Algoritmaları ile Benzetim Eniyilemesi: En İyi Kanban Sayısının Bulunması. Endüstri Mühendisliği,16(1), 2-15.
30. Güner, E., & Altıparmak, F. (2003). İki Ölçütlü Tek Makineli Çizelgeleme Problemi için Sezgisel Bir Yaklaşım, Gazi Üni. Müh-Mim. Fak. Dergisi,18(3), 27-42.
31. Aydoğdu, B. (2017). Dinamik Eş Zamanlı Topla-Dağıt Araç Rotalama Problemi İçin Matematiksel Model ve Sezgisel Yaklaşımlar, Doktora tezi, Gazi Üniversitesi, Fen Bilimleri Enstitüsü, Ankara.