Cluster-First, Then-Route Based Heuristic Algorithm for the Solution of Capacitated Vehicle Routing Problem

Year 2014, Volume: 7 Issue: 2, 29 - 37, 21.02.2014

Zafer Bozyer , Atakan Alkan , Alpaslan Fığlalı

Abstract

– Logistics has important effects on human life throughout the history. Within the past century the need to convey customer demands shortly and efficiently has resulted in the increasing importance of the vehicle routing problems (VRPs) that included in logistics activities. Different methods have been developed in order to solve vehicle routing problems that are subject of various researchs due to its increasing importance day by day.More computation time is required to the methods that provides to find the optimal results while the problem size increases.Therefore, pretty much work has been done about heuristic methods that provide access to acceptable results in a shorter time. In this paper, a “cluster-first, then-route” based heuristic algorithm is proposed for the solution of Capacitated Vehicle Routing Problem (CVRP). The membership degrees of demand points to each potential route are calculated by using fuzzy c-means in clustering step; and then the routes are improved by using a search procedure based on Tabu Search algorithm in the routing step. As a result of, the capacitated vehicle routing problems can be solved by conversion to the traveling salesman problem has been observed. The proposed method is applied on literature problems and the results are discussed.

Keywords

Vehicle routing problem, cluster-first then-route, tabu search, fuzzy c-means, clustering

Kapasite Kısıtlı Araç Rotalama Probleminin Çözümü için Önce Grupla Sonra Rotala Merkezli Sezgisel Algoritma Önerisi

Abstract

Lojistik, insanoğlunun uzun zamandır üzerinde çalıştığı en temel konulardan birisidir. Son yüzyıl içerisinde müşteri taleplerinin kısa zamanda ve verimli bir şekilde ulaştırılabilmesi ihtiyacı, lojistik faaliyetlerinin içerisinde yer alan araç rotalama problemlerinin (ARP) öneminin artmasına neden olmuştur. Gün geçtikçe artan önemi nedeniyle birçok araştırmaya konu olan araç rotalama problemlerinin çözülebilmesi için farklı yöntemler geliştirilmiştir. En iyi sonuca ulaşmayı mümkün kılan yöntemlerde problem boyutu arttıkça daha fazla hesaplama süresine ihtiyaç duyulmaktadır. Bundan dolayı daha kısa sürede kabul edilebilir sonuçlara ulaşmayı sağlayan sezgisel yöntemler hakkında da oldukça fazla çalışma yapılmıştır. Bu çalışmada da, kapasite kısıtlı araç rotalama problemlerinin (KKARP) çözümüne yönelik önce grupla sonra rotala prensibine dayanan sezgisel bir yöntem önerilmiştir. Gruplandırma adımında, talep noktalarının bulanık c-ortalama kümeleme yöntemi ile olası tüm rotalara 0-1 arasında üyelik dereceleri hesaplanmıştır. Rotalama adımında ise sezgisel bir algoritma olan tabu arama prensiplerine dayanan bir arama algoritması ile rotalar iyileştirilmeye çalışılmıştır. Sonuç olarak KKARP’lerinin gezgin satıcı problemine dönüştürülerek çözülebileceği görülmüştür. Önerilen yöntem literatürde yer alan veri kümelerine uygulanmış ve elde edilen sonuçlar tartışılmıştır.

Keywords

Araç rotalama problemi, önce grupla sonra rotala, tabu arama, bulanık c-ortalama, kümeleme

References

• (REFERENCES) Ö.B. Tek, E. Ozgul, Modern Pazarlama İlkeleri: Uygulamalı Yönetimsel Yaklaşım, 3.Baskı, Birleşik Matbaacılık, İzmir, 20 K.C. Tan, “A Framework of Supply Chain Management Literature”, European J. of Purchasing & Supply Management, 7(1), 39-48, 2001.
• A. Rushton, P. Croucher, P. Baker, The Handbook of Logistics and Distribution Management, 4rd ed., Kogan Page, London, 200 M.H.F. Zarandi, M. Hossein, S. Davari, I.B. Turksen, "Capacitated Location-Routing Problem with Time Windows Under Uncertainty." Knowledge-Based Systems, 37, 480-489, 20 J.B. Sheu, “A Hybrid Fuzzy-Optimization Approach to Customer Grouping-Based Logistics Distribution Operations”, Applied Mathematical Modelling, 31(6), 1048-1066, 2007.
• L.T. Hu, J.B. Sheu, “A fuzzy-based customer classification method for demand-responsive logistical distribution operations”, Fuzzy Sets and Systems, 139(2), 431-450, 2003.
• D. Applegate, R. Bixby, V. Chavátal, W. Cook, “On the Solution of Traveling Salesman Problems”, Documenta Mathematica, 645656, 1998.
• P. Toth, D. Vigo, “An Overview of Vehicle Routing Problems”, The Vehicle Routing Problem, Editör: P. Toth, D. Vigo, SIAM, Philadelphia, 1-26, 2002.
• Ç, Alabaş, B. Dengiz, “Yerel Arama Yöntemlerinde Yöre Yapısı: Araç Rotalama Problemine Bir Uygulama”, Yöneylem Araştırması ve Endüstri Mühendisliği XXIV. Ulusal Kongresi, Çukurova Üniversitesi, Adana, 333-335, 15-18 Haziran, 2004.
• Toth, P., Vigo, D, The Vehicle Routing Problem, Society for Industrial and Applied Mathematics, SIAM Monographs On Discrete Mathematics And Applications, Philadelphia, 2002.
• E. Vural, Araç Rotalama Problemleri İçin Populasyon 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ü, 2006.
• P. Toth, D. Vigo, “Exact Solution of the Vehicle Routing Problem”, Fleet Management and Logistic, Editör: T.G. Crainic, G. Laporte, Kluwer Academic, Boston, 1-31, 1998.
• M. Dell’Amico, G. Righini, M. Salani, “A Branch-And-Price Approach to the Vehicle Routing Problem with Simultaneous Distribution and Collection”, Transportation Science, 40(2), 235247 2006.
• P. Toth, D. Vigo, “An Exact Algorithm for the Vehicle Routing Problem with Backhauls”, Transportation Science, 31(4), 372385, 1997.
• Z. Başkaya, B. Avcı Öztürk, “Tamsayılı Programlamada Dal Kesme Yöntemi ve Bir Ekmek Fabrikasında Oluşturulan Araç Rotalama Problemine Uygulanması”, Uludağ Üniversitesi İktisadi ve İdari Bilimler Fakültesi Dergisi, 24(1), 101-114, 2005.
• C.D. Tarantilis, G. Ioannou, G. Prastacos, “Advanced Vehicle Routing Algorithms for Complex Operations Management Problems”, Journal of Food Engineering, 70(3), 455-471, 2005.
• H. Paessens, “The Savings Algorithm for the Vehicle Routing Problem”, European Journal of Operational Research, 34(3), 336-344, 1988.
• G. Clarke, J.W. Wright, “Scheduling of Vehicles from a Central Depot to a Number of Delivery Points”, Operations Research, 12(4), 568-581, 1964. A.V. Breedam, “Comparing Descent Heuristics and Metaheuristics for the Vehicle Routing Problem”, Computers & Operations Research, 28(4), 289-315, 2001.
• G. Laporte, M. Gendreau, J.Y. Potvin, F. Semet, “Classical and Modern Heuristics for the Vehicle Routing Problem”, International Transactions in Operation Research, 7(4-5), 285300, 2000.
• I.K. Altınel, T, Öncan, “A New Enhancement of the Clarke and Wright Savings Heuristic for the Capacitated Vehicle Routing Problem”, Journal of the Operational Research Society, 56(8), 954-961, 2005.
• G. Laporte, F. Semet, “Classical Heuristics for the Vehicle Routing Problem”, The Vehicle Routing Problem, Editör: P. Toth, D. Vigo, SIAM, Philadelphia, 109-128, 2002.
• A. Hertz, M. Widmer, “Guidelines for the Use of Meta-Heuristics in Combinatorial Optimization”, European Journal of Operation Research, 151(2), 247-252, 2003.
• M. Gendreau, G. Laporte, J.Y. Potvin, “Metaheuristics for the Capacitated VRP”, The Vehicle Routing Problem, Editör: P. Toth, D. Vigo, SIAM, Philadelphia, 129-154, 2002.
• B. Eksioglu, A.V. Vural, A. Reisman, “The Vehicle Routing Problem: A Taxonomic Review”, Computers & Industrial Engineering, 57(4), 1472-1483, 2009.
• J. Dréo, A. Pétrowski, P. Siarry, E. Taillard, A. Chatterjee, Metaheuristics for Hard Optimization: Methods and Case Studies, 1th ed., Springer, Berlin, 2006.
• T. Vidal, T.G. Crainic, M. Gendreau, C. Prins, “Heuristics for Multi-Attribute Vehicle Routing Problems: A Survey and Synthesis”, European Journal of Operational Research, 231(1), 1-21, 2013.
• R. Kruse, C. Borgelt, D. Nauck, “Fuzzy Data Analysis: Challenges and Perspectives”, IEEE International Conference on Fuzzy Systems, Seoul, South Korea, 22-25 Ağustos, 12111216, 1999.
• W.C. Chen, M.S. Wang, “A Fuzzy C-Means Clustering-Based Fragile Watermarking Scheme for Image Authentication”, Expert System with Application, 36(2), 1300-1307, 2009.
• J.F. Cordeau, M. Gendreau, G. Laporte, J.Y. Potvin, F. Semet, “A Guide to Vehicle Routing Heuristics”, Journal of the Operational Research Society, 53(5), 512-522, 2002.
• D. Karaboğa, Yapay Zekâ Optimizasyon Algoritmaları, 2. baskı, Nobel Yayın Dağıtım, Ankara, 2011.
• M. Gendreau, A. Hertz, G. Laporte, “A Tabu Search Heuristic for the Vehicle Routing Problem”, Management Science, 40(10), 1276-1290, 1994.
• E.D. Taillard, “Parallel Iterative Search Methods for Vehicle Routing Problem”, Networks, 23(8), 661-673, 1993.
• Y. Rochat, E.D. Taillard, “Probabilistic Diversification and Intensification in Local Search for Vehicle Routing”, Journal of Heuristics, 1(1), 147-167, 1995.
• J. Xu, J.P. Kelly, “A Network Flow-Based Tabu Search Heuristic for the Vehicle Routing Problem”, Transportation Science, 30(4), 379-393, 1996.
• G. Barbarosoğlu, D. Özgür, “A Tabu Search Algorithm for the Vehicle Routing Problem”, Computers & Operations Research, 26(3), 255-270, 1999.
• J.F. Cordeau, M. Gendreau, G. Laporte, “A Tabu Search Heuristic for Periodic and Multi-Depot Vehicle Routing Problems”, Networks, 30(2), 105-119, 1997. Internet: Vehicle Routing Data Sets, http://www.coinor.org/SYMPHONY/branchandcut/VRP/data/index.htm.old#E, 02014.