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

Year 2020, Prof. Dr. Talha Ustasüleyman Special Issue, 185 - 206, 20.02.2020

Selçuk Çebi , Burak Yıldırım

https://doi.org/10.18092/ulikidince.581841

Cited By: 2

Abstract

Nowadays,
with the development of technology, supply of many products has exceeded the
demand and this has increased the competition among the bussiness enterprises. In
order to survive in a competitive environment, bussiness 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 companys 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 larged, and (iii.)the number of supplier enterprises providing
these products is enarmous, the problem considered within the scope of the
study is NP-Hard problem class. In this study, although many heuristic
algorithms have been utilised 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.

Keywords

Vehicle Routing Problem, Sweep Algorithm, 2-Opt Algorithm, Guided Local Search, e-Commerce

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

Abstract

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 Problem 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ı şirket için 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 pazaryterlerine
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ışma kapsamında ele alınan problem NP-Zor problem sınıfındadır. Bu tür
problemlerin çözümünde literatürde deterministik modellerden ziyade sezigisel
ya da meta sezgisel yöntemler tercih edilmektedir. Çalışma kapsamında, işletme
kısıtlarına yönelik birçok sezgisel algoritma denenenmesine 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 toplam toplama süresinde gerekse de
ihtiyaç duyulan araç sayısı bakımından en yi sonucu vermiştir. Her iki
sezgisel, şirketin araç filosundaki sayının yarıya indirebileceği sonucunu
ortaya koymuştur. 

Keywords

Araç Rotalama Problemi, Süpürme Sezgiseli, 2-Opt Tur Sezgiseli, Guided Local Search

References

• 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 Capacita-ted 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 Ve-hicle 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 Ve-hicle Routing Problem. Computers & Operations Research, 34(7), 2080-2095.
• Christofides, N., Mingozzi, A., Toth, P. (1981), Exact Algorithms for The Vehicle Routing Prob-lem, Based on Spanning Tree and Shortest Path Relaxations. Mathematical Program-ming, 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 So-ciety, 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 Rese-arch Part E: Logistics and Transportation Review, 48(1), 100-114.
• Eryavuz, M., & Gencer, C. (2001), Araç Rotalama Problemine Ait Bir Uygulama. Süleyman Demi-rel Ü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 Simul-taneous 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. Ope-rations research, 22(2), 340-349.
• González, O. M., Segura, C., Peña, S. I. V. (2018) A Parallel Memetic Algorithm to Solve The Ca-pacitated Vehicle Routing Problem with Time Windows. International Journal of Com-binatorial 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 Ca-pacitated Vehicle Routing Problem with Time Windows. International Journal of Com-binatorial Optimization Problems and Informatics, 9(1), 35-45.
• Hemmelmayr, V. C., Doerner, K. F., & Hartl, R. F. (2009)A Variable Neighborhood Search Heuris-tic 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 Ro-uting 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öntemleri-nin 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 Tra-vel Times. Transportation Science, 26(3), 161-170.
• Li, J., Pardalos, P. M., Sun, H., Pei, J., & Zhang, Y. (2015), Iterated Local Search Embedded Adap-tive 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 & Manu-facturing. 1(1): 217–226.
• Novoa-Flores, G. I., Carpente, L., Lorenzo-Freire, S. (2018), A Vehicle Routing Problem with Pe-riodic 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 Maklu-mat, 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-a-ride 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 Ne-ighborhood Search Heuristic for Solving The Vehicle Routing Problem with Simultane-ous 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 Coun-terpart Open Capacitated Vehicle Routing Problem (DRC-OCVRP) Simplification by Applying Preprocessing Techniques in Rubbish Controlling in Sematang Borang Dist-rict, 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 Rou-ting 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 Rou-ting 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. Jo-urnal 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 Prob-lem 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 capacita-ted vehicle routing problem with two-dimensional loading constraints. European Jo-urnal of Operational Research, 243(3), 798-814.
• Xia, Y., Fu, Z., Pan, L., Duan, F. (2018), Tabu Search Algorithm for The Distance-Constrained Ve-hicle 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 Rou-ting at Quality Stores. Interfaces, 17(2), 52-63.
• Yousefikhoshbakht, M., Khorram, E. (2012), Solving the Vehicle Routing Problem by A Hybrid Meta-Heuristic 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 En-gineering 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.