Heuristic algorithms for solving the multi-compartment vehicle routing problem with time windows and heterogeneous fleet

Year 2023, Volume: 29 Issue: 8, 870 - 884, 31.12.2023

Duygu Topaloğlu Olcay Polat , Can Berk Kalaycı

Abstract

The use of multi-compartment vehicles is an efficient solution for distributing different products that cannot be transported in the same compartment. In this study, the vehicle routing problem with time windows is addressed by considering the use of a heterogeneous fleet and multi-compartment vehicles. The variant of the problem discussed in this study is known as the Heterogeneous Fleet Multi-Compartment Vehicle Routing Problem (MCVRPTWHF). In this study, the Variable Neighborhood Search algorithm (VNS) and the Artificial Bee Colony Algorithm (ABCA) have been adapted to solve the problem. Well-known datasets have been adapted to fit the problem structure in order to analyze the performance of the algorithms. Comparative results reveal that the developed algorithms effectively solve the generated datasets. It has been observed that the DKA algorithm has significant numerical superiority compared to YAKA.

Keywords

Logistics, Routing, Split delivery, Multi-compartment, Time window, Heuristic algorithms

Çok kompartımanlı heterojen filolu zaman pencereli araç rotalama probleminin çözümü için sezgisel algoritmalar

Abstract

Aynı kompartımanda taşınamayan farklı ürünlerin dağıtımında çok kompartımanlı araç kullanımı verimli bir çözüm yöntemidir. Bu çalışmada zaman pencereli araç rotalama problemi heterojen filolu ve çok kompartımanlı araçların kullanımı göz önünde bulundurularak ele alınmıştır. Çalışmada ele alınan problemin varyantı heterojen filolu çok kompartımanlı zaman pencereli araç rotalama problemi (HFÇKZPARP) olarak bilinmektedir. Bu çalışmada Değişken Komşuluk Arama algoritması (DKA) ve Yapay Arı Koloni Algoritması (YAKA) problemin çözümü için uyarlanmıştır. Algoritmaların performanslarını analiz edebilmek için iyi bilinen veri setleri problem yapısına uyarlanmıştır. Karşılaştırmalı sonuçlar geliştirilen algoritmaların oluşturulan veri setlerini efektif bir şekilde çözdüğünü ortaya koymaktadır. DKA algoritması YAKA’ya göre sayısal olarak önemli bir üstünlük gösterdiği gözlemlenmiştir.

Keywords

Lojistik, Rotalama, Bölünebilir talep, Çok kompartıman, Zaman penceresi, Sezgisel algoritma

References

• [1] Fallahi AE, Prins C, Wolfler Calvo R. “A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem”. Computers & Operations Research, 35(5), 1725-1741, 2008.
• [2] Alinaghian M, Shokouhi N. “Multi-depot multicompartment vehicle routing problem, solved by a hybrid adaptive large neighborhood search”. Omega, 76, 85-99, 2018.
• [3] Reed M, Yiannakou A, Evering R. “An ant colony algorithm for the multi-compartment vehicle routing problem”. Applied Soft Computing, 15, 169-176, 2014.
• [4] Silvestrin P V, Ritt M. “An iterated tabu search for the multi-compartment vehicle routing problem”. Computers & Operations Research, 81, 192-202, 2017.
• [5] Abdulkader M M S, Gajpal Y, ElMekkawy T Y. “Hybridized ant colony algorithm for the Multi Compartment Vehicle Routing Problem”. Applied Soft Computing, 37, 196-203, 2015.
• [6] Kaabachi I, Yahyaoui H, Krichen S, Dekdouk A. “Measuring and evaluating hybrid metaheuristics for solving the multi-compartment vehicle routing problem”. Measurement, 141, 407-419, 2019.
• [7] Muyldermans L, Pang G. “On the benefits of co-collection: Experiments with a multi-compartment vehicle routing algorithm”. European Journal of Operational Research, 206(1), 93-103, 2010.
• [8] Efthymiadis S, Liapis N, Nenes G. “Solving a heterogeneous fleet multi-compartment vehicle routing problem:a case study”. International Journal of Systems Science: Operations & Logistics, 10(1), 1-15, 2023.
• [9] Mendoza J E, Castanier B, Guéret C, Medaglia A L, Velasco N. “A memetic algorithm for the multi-compartment vehicle routing problem with stochastic demands”. Computers & Operations Research, 37(11), 1886-1898, 2010.
• [10] Mendoza J E, Castanier B, Guéret C, Medaglia A L, Velasco N. “Constructive heuristics for the multicompartment vehicle routing problem with stochastic demands”. Transportation Science, 45(3), 346-363, 2011.
• [11] Goodson J C. “A priori policy evaluation and cyclic-orderbased simulated annealing for the multi-compartment vehicle routing problem with stochastic demands”. European Journal of Operational Research, 241(2), 361-369, 2015.
• [12] Chajakis E D, Guignard M. “Scheduling deliveries in vehicles with multiple compartments”. Journal of Global Optimization, 26(1), 43-78, 2003.
• [13] Hübner A, Ostermeier M. “A multi-compartment vehicle routing problem with loading and unloading costs”. Transportation Science, 53(1), 282-300, 2019.
• [14] Ostermeier M, Martins S, Amorim P, Hübner A. “Loading constraints for a multi-compartment vehicle routing problem”. OR Spectrum, 40(4), 997-1027, 2018.
• [15] Martins S, Ostermeier M, Amorim P, Hübner A, AlmadaLobo B. “Product-oriented time window assignment for a multi-compartment vehicle routing problem”. European Journal of Operational Research, 276(3), 893-909, 2019.
• [16] Henke T, Speranza MG, Wäscher G. “The multicompartment vehicle routing problem with flexible compartment sizes”. European Journal of Operational Research, 246(3), 730-743, 2015.
• [17] Derigs U, Gottlieb J, Kalkoff J, Piesche M, Rothlauf F, Vogel U. “Vehicle routing with compartments: applications, modelling and heuristics”. OR Spectrum, 33(4), 885-914, 2011.
• [18] Shang C, Ma L, Liu Y. “Green location routing problem with flexible multi-compartment for source-separated waste: A Q-learning and multi-strategy-based hyperheuristic algorithm”. Engineering Applications of Artificial Intelligence, 121, 1-17, 2023.
• [19] Wang X, Liang Y, Tang X, Jiang X. “A multi-compartment electric vehicle routing problem with time windows and temperature and humidity settings for perishable product delivery”. Expert Systems with Applications, 233, 1-16, 2023.
• [20] Henke T, Speranza MG, Wäscher G. “A branch-and-cut algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes”. Annals of Operations Research, 275(2), 321-338, 2019.
• [21] Kiilerich L, Wøhlk S. “New large-scale data instances for CARP and new variations of CARP”. INFOR: Information Systems and Operational Research, 56(1), 1-32, 2018.
• [22] Zbib H, Laporte G. “The commodity-split multicompartment capacitated arc routing problem”. Computers & Operations Research, 122, 1-18, 2020.
• [23] Caramia M, Guerriero F. “A milk collection problem with incompatibility constraints”. Interfaces, 40(2), 130-143, 2010.
• [24] Oppen J, Løkketangen A. “A tabu search approach for the livestock collection problem”. Computers & Operations Research, 35(10), 3213-3229, 2008.
• [25] Sethanan K, Pitakaso R. “Differential evolution algorithms for scheduling raw milk transportation”. Computers and Electronics in Agriculture, 121, 245-259, 2016.
• [26] Polat O, Topaloğlu D. "Milk collection network design in a fuzzy environment in" 18th International Conference on Economy & Business. Burgas, Bulgaria, 20-24 August 2019.
• [27] Polat O, Kalaycı C B, Bilgen B, Topaloğlu D. “An integrated mathematical model for the milk collection problem”. Pamukkale University Journal of Engineering Sciences, 25(9), 1087-1096, 2019.
• [28] Popović D, Vidović M, Radivojević G. “Variable neighborhood search heuristic for the inventory routing problem in fuel delivery”. Expert Systems with Applications, 39(18), 13390-13398, 2012.
• [29] Benantar A, Ouafi R, Boukachour J. “A petrol station replenishment problem: new variant and formulation”. Logistics Research, 9(1), 1-18, 2016.
• [30] Cornillier F, Laporte G, Boctor F F, Renaud J. “The petrol station replenishment problem with time windows”. Computers & Operations Research, 36(3), 919-935, 2009.
• [31] Coelho L C, Laporte G. “Classification, models and exact algorithms for multi-compartment delivery problems”. European Journal of Operational Research, 242(3), 854-864, 2015.
• [32] Dantzig G, Fulkerson R, Johnson S. “Solution of a largescale traveling-salesman problem”. Journal of the Operations Research Society of America, 2(4), 393-410, 1954.
• [33] Karaboga D. “An idea based on honey bee swarm for numerical optimization”. Erciyes University, Engineering Faculty, Computer, Report, Technical Report-TR06, 2005.
• [34] Yang XS. Engineering Optimizations via Nature-Inspired Virtual Bee Algorithms. in Artificial Intelligence and Knowledge Engineering Applications: A Bioinspired Approach. 2005. Berlin, Heidelberg: Springer Berlin Heidelberg.
• [35] Irani R, Nasimi R. “Application of artificial bee colonybased neural network in bottom hole pressure prediction in underbalanced drilling”. Journal of Petroleum Science and Engineering, 78(1), 6-12, 2011.
• [36] Szeto WY, Wu Y, Ho SC. “An artificial bee colony algorithm for the capacitated vehicle routing problem”. European Journal of Operational Research, 215(1), 126-135, 2011.
• [37] Zhang S, Lee CKM, Choy KL, Ho W, Ip WH. “Design and development of a hybrid artificial bee colony algorithm for the environmental vehicle routing problem”. Transportation Research Part D: Transport and Environment, 31, 85-99, 2014.
• [38] Ng KKH, Lee CKM, Zhang SZ, Wu K, Ho W. “A multiple colonies artificial bee colony algorithm for a capacitated vehicle routing problem and re-routing strategies under time-dependent traffic congestion”. Computers & Industrial Engineering, 109, 151-168, 2017.
• [39] Kaya E, Gorkemli B, Akay B, Karaboga D. “A review on the studies employing artificial bee colony algorithm to solve combinatorial optimization problems”. Engineering Applications of Artificial Intelligence, 115, 1-30, 2022.
• [40] Mladenovic N, Hansen P. “Variable neighborhood search”. Computers & Operations Research, 24(11), 1097-1100, 1997.
• [41] Hansen P, Mladenović N. “Variable neighborhood search: Principles and applications”. European Journal of Operational Research, 130(3), 449-467, 2001.
• [42] Hansen P, Mladenović N, Moreno Pérez J. “Variable neighbourhood search: methods and applications”. Annals of Operations Research, 175(1), 367-407, 2010.
• [43] Crispim J, Brandao J. "Reactive tabu search and variable neighbourhood descent applied to the vehicle routing problem with backhauls". 4th Metaheuristic International Conference, Porto, Portugal, 16-20 July 2001.
• [44] Kytöjoki J, Nuortio T, Bräysy O, Gendreau M. “An efficient variable neighborhood search heuristic for very large scale vehicle routing problems”. Computers & Operations Research, 34(9), 2743-2757, 2007.
• [45] Fleszar K, Osman I H, Hindi K S. “A variable neighbourhood search algorithm for the open vehicle routing problem”. European Journal of Operational Research, 195(3), 803-809, 2009.
• [46] Kuo Y, Wang C-C. “A variable neighborhood search for the multi-depot vehicle routing problem with loading cost”. Expert Systems with Applications, 39(8), 6949-6954, 2012.
• [47] Stenger A, Vigo D, Enz S, Schwind M. “An adaptive variable neighborhood search algorithm for a vehicle routing problem arising in small package shipping”. Transportation Science, 47(1), 64-80, 2013.
• [48] Salhi S, Imran A, Wassan N A. “The multi-depot vehicle routing problem with heterogeneous vehicle fleet: Formulation and a variable neighborhood search implementation”. Computers & Operations Research, 52, Part B(0), 315-325, 2014.
• [49] Hemmelmayr VC, Doerner KF, Hartl RF. “A variable neighborhood search heuristic for periodic routing problems”. European Journal of Operational Research, 195(3), 791-802, 2009.
• [50] Pirkwieser S, Raidl G, Multiple Variable Neighborhood Search Enriched with ILP Techniques for the Periodic Vehicle Routing Problem with Time Windows, in Hybrid Metaheuristics, M. Blesa, et al., Editors: Springer Berlin Heidelberg, 45-59, 2009.
• [51] Polat O, Kalayci C B, Kulak O, Günther HO. “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, 2015.
• [52] Polat O. “Cooperative variable neighborhood search for the vehicle routing problem with simultaneous pickup and delivery”. International Journal of Industrial Electronics and Electrical Engineering, 4(9), 137-140, 2016.
• [53] Kalayci C B, Kaya C. “An ant colony system empowered variable neighborhood search algorithm for the vehicle routing problem with simultaneous pickup and delivery”. Expert Systems with Applications, 66, 163-175, 2016.
• [54] Polat O. “A parallel variable neighborhood search for the vehicle routing problem with divisible deliveries and pickups”. Computers & Operations Research, 85, 71-86, 2017.
• [55] Beasley J E. “Route first-cluster second methods for vehicle routing”. Omega, 11(4), 403-408, 1983.
• [56] Chen J, Shi J. “A multi-compartment vehicle routing problem with time windows for urban distribution – A comparison study on particle swarm optimization algorithms”. Computers & Industrial Engineering, 133, 95-106, 2019.
• [57] Clarke G, Wright J W. “Scheduling of vehicles from a central depot to a number of delivery points”. Operations Research, 12(4), 568-581, 1964.
• [58] Gillett B E, Miller L R. “A heuristic algorithm for the vehicle-dispatch problem”. Operations Research, 22(2), 340-349, 1974.
• [59] Prins C. “A simple and effective evolutionary algorithm for the vehicle routing problem”. Computers & Operations Research, 31(12), 1985-2002, 2004.
• [60] Wang L, Kinable J, Van Woensel T. “The fuel replenishment problem: A split-delivery multicompartment vehicle routing problem with multiple trips”. Computers & Operations Research, 118, 1-16, 2020.
• [61] Wang Q, Ji Q, Chiu C-H. “Optimal routing for heterogeneous fixed fleets of multicompartment vehicles”. Mathematical Problems in Engineering, 2014, 1-12, 2014.
• [62] Chen L, Liu Y, Langevin A. “A multi-compartment vehicle routing problem in cold-chain distribution”. Computers & Operations Research, 111, 58-66, 2019.
• [63] Jiang J, Ng KM, Poh K L, Teo KM. “Vehicle routing problem with a heterogeneous fleet and time windows”. Expert Systems with Applications, 41(8), 3748-3760, 2014.
• [64] Solomon MM. “Algorithms for the vehicle routing and scheduling problems with time window constraints”. Operations Research, 35(2), 254-265, 1987.