KAPASİTE KISITLI ARAÇ ROTALAMA PROBLEMİ İÇİN SEZGİSEL YÖNTEMLER: ETİCARET TEDARİKÇİLERİNE YÖNELİK BİR UYGULAMA

Günümüzde teknolojinin gelişmesiyle birlikte birçok üründe arz, ürüne olan talebi geçmiş bu da işletmeler arasındaki rekabeti arttırmıştır. İşletmeler bu ortamda ayakta kalabilmek için ürünlerinde müşteri isteklerini dikkate almalı, daha düşük maliyetlerde istenen kalitede ürünü üretmeli ve müşteriye ulaşabilmelidirler. İşletmelerin üretim/hizmet maliyetlerini arttıran en önemli unsurlardan biri lojistik faaliyetleridir. Araç Rotalama Problemi lojistik yönetiminin ilgilendiği konulardan biridir. Bu çalışmada İstanbul’da bulunan e-ticaret sitelerinden gelen kargo taleplerini toplayan ve istenilen lokasyona gönderimini sağlayan bir aracı şirketin araç rotalama problemine yönelik çözüm önerileri geliştirilmesi amaçlanmıştır. Şirketin uzun dönemli planları içerisinde toplama maliyetlerini azaltmak amacıyla işletme kısıtlarına özgü bir araç rotalama modülü entegrasyonu da yer almaktadır. İşletmenin çeşitli pazaryerlerine hizmet vermesi(i) ve bu pazaryerlerinde satılan ürün gamının çeşitliliği(ii), bu ürünleri sağlayan işletmelerin sayısı(iii) dikkate alındığında çalışmada ele alınan problem, polinomsal zamanda çözüm elde edilemeyen (NP-Zor) problem sınıfındadır. Bu tür problemlerin çözümünde literatürde deterministik modellerden ziyade sezgisel ya da meta sezgisel yöntemler tercih edilmektedir. Çalışma kapsamında, işletme kısıtlarına yönelik birçok sezgisel algoritma denenmesine rağmen en iyi çözümü veren Süpürme algoritmalı 2-Opt tur geliştirici sezgiseli ve Google OR çözüm araçlarından Guided Local Search sezgiselinden elde edilen sonuçlar sunulmuştur. Algoritmalar Python dilinde kodlanmıştır ve çözümler Windows 8.1, i7 4710MQ, 8 Gb Ram özelliklerine sahip bilgisayar kullanılarak elde edilmiştir. Guided Local Search gerek toplama süresinde gerekse de ihtiyaç duyulan araç sayısı bakımından en iyi sonucu vermiştir. Her iki sezgisel, şirketin araç filosundaki araç sayının yarıya indirebileceği sonucunu ortaya koymuştur.

HEURISTIC METHODS FOR THE CAPACITATED VEHICLE ROUTING PROBLEM: AN APPLICATION OF E-COMMERCE SUPPLIERS

Nowadays, with the development of technology, supply of many products has exceeded the demand, and this has increased the competition among the business enterprises. In order to survive in a competitive environment, business enterprises should take into account customers’ requirements, produce products of the desired quality at lower costs and reach the customers. One of the most important factors that increase the production/service costs of enterprises is logistics activity. Vehicle Routing Problem is also one of the most important issues in logistics management. Within the scope of this study, it has been aimed to develop solutions for the vehicle routing problem of a brokerage company that collects the cargo demands of the e-commerce sites located in Istanbul and sends them to the desired location. In a long term, the company desires to integrate a vehicle routing module which considers the company’s constraints in order to reduce service costs. Since (i.)the company provides services to various marketplaces, (ii.)the variety of products sold in these marketplaces has been large, and (iii.)the number of supplier enterprises providing these products is enormous, the problem considered within the scope of the study is NP-Hard problem class. In this study, although many heuristic algorithms have been utilized for the constraints of the company, the best results obtained from the Sweep algorithm with 2-Opt heuristic and Guided Local Search heuristic from Google OR solution tools are presented. Algorithms are coded in Python and solutions are obtained by using computer with Windows 8.1, i7 4710MQ, 8 Gb Ram. Furthermore, Guided Local Search produced the best results in terms of total pickup time and the number of the required vehicles. Both heuristics prove that vehicle fleet should be halved.

PDF

___

Archetti, C., Bianchessi, N., & Speranza, M. G. (2014), Branch-and-cut Algorithms for The Split Delivery Vehicle Routing Problem. European Journal of Operational Research, 238(3), 685- 698.

Baldacci, R., Hadjiconstantinou, E., & Mingozzi, A. (2004), An Exact Algorithm for The Capacitated Vehicle Routing Problem Based on a Two-commodity Network Flow Formulation. Operations Research, 52(5), 723-738.

Baldacci, R., Mingozzi, A., Roberti, R., & Calvo, R. W. (2013), An Exact Algorithm for The Two-echelon Capacitated Vehicle Routing Problem. Operations Research, 61(2), 298-314.

Barthélemy, T., Rossi, A., Sevaux, M., & Sörensen, K. (2010), Metaheuristic Approach for The Clustered VRP. In EU/MEeting: 10th Anniversary of the Metaheuristics Community-Université de Bretagne Sud, France

Battarra, M., Erdoğan, G., & Vigo, D. (2014), Exact Algorithms for The Clustered Vehicle Routing Problem. Operations Research, 62(1), 58-71.

Bell, J. E., McMullen, P. R. (2004), Ant Colony Optimization Techniques for The Vehicle Routing Problem. Advanced Engineering Informatics, 18(1), 41-48.

Bozyer, Z., Alkan, A., & Fığlalı, A. (2014), Kapasite Kısıtlı Araç Rotalama Probleminin Çözümü İçin Önce Grupla Sonra Rotala Merkezli Sezgisel Algoritma Önerisi. Bilişim Teknolojileri Dergisi, 7(2), 29-37.

Bullnheimer, B., Hartl, R. F., Strauss, C. (1999), An Improved Ant System Algorithm for The Vehicle Routing Problem. Annals of Operations Research, 89, 319-328.

Cacchiani, V., Hemmelmayr, V. C., Tricoire, F. (2014), A Set-Covering Based Heuristic Algorithm For The Periodic Vehicle Routing Problem. Discrete Applied Mathematics, 163, 53-64.

Choi, E., & Tcha, D. W. (2007), A Column Generation Approach to The Heterogeneous Fleet Vehicle Routing Problem. Computers & Operations Research, 34(7), 2080-2095.

Christofides, N., Mingozzi, A., Toth, P. (1981), Exact Algorithms for The Vehicle Routing Problem, Based on Spanning Tree and Shortest Path Relaxations. Mathematical Programming, 20(1), 255-282.

Clarke, G., & Wright, J. W. (1964), Scheduling of Vehicles From a Central Depot to a Number of Delivery Points. Operations Research, 12(4), 568-581.

Cornillier, F., Boctor, F. F., Laporte, G., & Renaud, J. (2008), An Exact Algorithm for The Petrol Station Replenishment Problem. Journal of the Operational Research Society, 59(5), 607-615.

Crispim, J., & Brandão, J. (2005), Metaheuristics Applied to Mixed and Simultaneous Extensions of Vehicle Routing Problems with Backhauls. Journal of the Operational Research Society, 56(11), 1296-1302.

Croes, G.A., (1958), A Method for Solving Traveling-Salesman Problems. Operations Research, 6, 791-812.

Demirtaş, Y., & Özdemir, E. (2017), Dinamik Araç Rotalama Problemleri İçin Yeni Bir Çözüm Önerisi. Süleyman Demirel Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 22(3), 807-823.

Erdoğan, S., Miller-Hooks, E. (2012), A Green Vehicle Routing Problem. Transportation Research Part E: Logistics and Transportation Review, 48(1), 100-114.

Eryavuz, M., & Gencer, C. (2001), Araç Rotalama Problemine Ait Bir Uygulama. Süleyman Demirel Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 6(1), 139-155.

Gajpal, Y., & Abad, P. (2010), Saving-based Algorithms for Vehicle Routing Problem with Simultaneous Pickup and Delivery. Journal of the Operational Research Society, 61(10), 1498- 1509.

Gendreau, M., Hertz, A., & Laporte, G. (1994), A Tabu Search Heuristic for The Vehicle Routing Problem. Management Science, 40(10), 1276-1290.

Gillett, B. E., Miller, L. R. (1974), A Heuristic Algorithm for The Vehicle-Dispatch Problem. Operations research, 22(2), 340-349.

González, O. M., Segura, C., Peña, S. I. V. (2018) A Parallel Memetic Algorithm to Solve The Capacitated Vehicle Routing Problem with Time Windows. International Journal of Combinatorial Optimization Problems and Informatics, 9(1), 35-45.

González, O. M., Segura, C., Peña, S. I. V. (2018), A Parallel Memetic Algorithm to Solve The Capacitated Vehicle Routing Problem with Time Windows. International Journal of Combinatorial Optimization Problems and Informatics, 9(1), 35-45.

Hemmelmayr, V. C., Doerner, K. F., & Hartl, R. F. (2009)A Variable Neighborhood Search Heuristic for Periodic Routing Problems. European Journal of Operational Research, 195(3), 791- 802.

Kachitvichyanukul, V. (2009)A Particle Swarm Optimization for Vehicle Routing Problem with Time Windows. Int. J. Oper. Res., 6(4), 519-537.

Kallehauge, B., Larsen, J., & Madsen, O. B. (2006) Lagrangian Duality Applied to The Vehicle Routing Problem with Time Windows. Computers & Operations Research, 33(5), 1464-1487.

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. 3(2)

Korablev, V., Makeev, I., Kharitonov, E., Tshukin, B., Romanov, I. (2016), Approaches to Solve The Vehicle Routing Problem in The Valuables Delivery Domain. Procedia Computer Science, 88, 487-492.

Kosif, B., & Ekmekçi, İ. (2012) Araç Rotalama Sistemleri ve Tasarruf Algoritması Uygulaması. İstanbul Ticaret Üniversitesi Fen Bilimleri Dergisi. 11 (21), 41-51.

Laporte, G., Louveaux, F., Mercure, H. (1992) The Vehicle Routing Problem with Stochastic Travel Times. Transportation Science, 26(3), 161-170.

Li, J., Pardalos, P. M., Sun, H., Pei, J., & Zhang, Y. (2015), Iterated Local Search Embedded Adaptive Neighborhood Selection Approach for The Multi-Depot Vehicle Routing Problem With Simultaneous Deliveries and Pickups. Expert Systems with Applications, 42(7), 3551-3561.

Liu, W., Lin, C., Chiu, C., Wang, Q. (2014), Minimizing the Carbon Footprint for The Time-Dependent Heterogeneous Fleet Vehicle Routing Problem with Alternative Paths. Sustainability, 6, 4658-4684.

Lysgaard, J., Letchford, A. N., & Eglese, R. W. (2004), A New Branch-And-Cut Algorithm for The Capacitated Vehicle Routing Problem. Mathematical Programming, 100(2), 423-445.

Montemanni, R., Gambardella, L. M., Rizzoli, A. E., Donati, A. V. (2005), Ant Colony System for A Dynamic Vehicle Routing Problem. Journal of Combinatorial Optimization, 10(4), 327-343.

Nakao Y, Nagamochi H. (2007), A DP-Based Heuristic Algorithm for The Discrete Split Delivery Vehicle Routing Problem. Journal of Advanced Mechanical Design Systems & Manufacturing. 1(1): 217–226.

Novoa-Flores, G. I., Carpente, L., Lorenzo-Freire, S. (2018), A Vehicle Routing Problem with Periodic Replanning. Multidisciplinary Digital Publishing Institute Proceedings, 2(18), 1192.

Nurcahyo, G. W., Alias, R. A., Shamsuddin, S. M., & Sap, M. N. M. (2002), Sweep Algorithm in Vehicle Routing Problem for Public Transport. Jurnal Antarabangsa Teknologi Maklumat, 2, 51-64.

Osman, I. H. (1993), Metastrategy Simulated Annealing and Tabu Search Algorithms for The Vehicle Routing Problem. Annals of Operations Research, 41(4), 421-451.

Parragh, S. N., Doerner, K. F., & Hartl, R. F. (2010), Variable Neighborhood Search for The Dial-aride Problem. Computers & Operations Research, 37(6), 1129-1138.

Pichpibul, T., & Kawtummachai, R. (2012), An Improved Clarke and Wright Savings Algorithm for The Capacitated Vehicle Routing Problem. ScienceAsia, 38(3), 307-318.

Pisinger, D., Ropke, S. (2007), A General Heuristic for Vehicle Routing Problems. Computers & Operations Research, 34(8), 2403-2435.

Polat, O., Kalayci, C. B., Kulak, O., & Günther, H. O. (2015), A Perturbation Based Variable Neighborhood Search Heuristic for Solving The Vehicle Routing Problem with Simultaneous Pickup and Delivery with Time Limit. European Journal of Operational Research, 242(2), 369- 382.

Puspita, F. M., Cahyono, E. S., Rahayu, S., Sintia, B. L. (2018) Model of Demand Robust Counterpart Open Capacitated Vehicle Routing Problem (DRC-OCVRP) Simplification by Applying Preprocessing Techniques in Rubbish Controlling in Sematang Borang District, Palembang. In E3S Web of Conferences (Vol. 68, p. 01025). EDP Sciences.

Qureshi, A. G., Taniguchi, E., & Yamada, T. (2009), An Exact Solution Approach for Vehicle Routing and Scheduling Problems with Soft Time Windows. Transportation Research Part E: Logistics And Transportation Review, 45(6), 960-977.

Ralphs, T. K., Kopman, L., Pulleyblank, W. R., & Trotter, L. E. (2003), On The Capacitated Vehicle Routing Problem. Mathematical Programming, 94(2-3), 343-359.

Renaud, J., Boctor, F. F., & Laporte, G. (1996), An Improved Petal Heuristic for The Vehicle Routing Problem. Journal of The Operational Research Society, 47(2), 329-336.

Sariklis, D., & Powell, S. (2000), A Heuristic Method for The Open Vehicle Routing Problem. Journal of the Operational Research Society, 51(5), 564-573.

Taillard, É., Badeau, P., Gendreau, M., Guertin, F., Potvin, J. Y. (1997), A Tabu Search Heuristic for The Vehicle Routing Problem with Soft Time Windows. Transportation Science, 31(2), 170- 186.

Tasan, A. S., & Gen, M. (2012), A Genetic Algorithm Based Approach to Vehicle Routing Problem with Simultaneous Pick-Up and Deliveries. Computers & Industrial Engineering, 62(3), 755- 761.

URL1. https://developers.google.com/optimization/routing/ (Erişim Tarihi 19.04.2019) Wei, L., Zhang, Z., Zhang, D., & Lim, A. (2015), A variable neighborhood search for the capacitated vehicle routing problem with two-dimensional loading constraints. European Journal of Operational Research, 243(3), 798-814.

Xia, Y., Fu, Z., Pan, L., Duan, F. (2018), Tabu Search Algorithm for The Distance-Constrained Vehicle Routing Problem with Split Deliveries by Order. PloS One, 13(5), doi: 10.1371/journal.pone.0195457.

Yano, C. A., Chan, T. J., Richter, L. K., Cutler, T., Murty, K. G., McGettigan, D. (1987), Vehicle Routing at Quality Stores. Interfaces, 17(2), 52-63.

Yousefikhoshbakht, M., Khorram, E. (2012), Solving the Vehicle Routing Problem by A Hybrid MetaHeuristic Algorithm. Journal of Industrial Engineering International, 8(11), 1-9.

Yu, B., Yang, Z. Z., Yao, B. (2009), An Improved Ant Colony Optimization for Vehicle Routing Problem. European Journal of Operational Research, 196(1), 171-176.

Yücenur, G. N., & Demirel, N. Ç. A (2011), Hybrid Algorithm with Genetic Algorithm and Ant Colony Optimization for Solving Multi-Depot Vehicle Routing Problems. Journal of Engineering and Natural Sciences, 29, 340-350.

Zhang, Y., Shi, L., Chen, J., Li, X. (2017), Analysis of an Automated Vehicle Routing Problem in Logistics Considering Path Interruption. Journal of Advanced Transportation,2,1-10.