Skewed General Variable Neighborhood Search to Solve the Multi-compartment Vehicle Routing Problem
DOI:
https://doi.org/10.2298/YJOR220615041AKeywords:
Variable neighbourhood search, vehicle routing problem, multi-compartment vehicle routing problemAbstract
Skewed General Variable Neighborhood Search (SGVNS) is shown to be a powerful and robust methodology for solving vehicle routing problems. In this paper we suggest new SGVNS for solving the multi-compartment vehicle routing problem (MCVRP). The problem of multi-compartment vehicle routing is of practical importance in the petrol and food delivery and waste collection industries. A comparison between our algorithm and the memetic algorithm and the tabu search is provided. It was clear that the proposed algorithm is capable of solving the available instances. Skewed General Variable Neighborhood Search was used because it makes it easy to explore the space of realizable solutions for MCVRP. As a result, the SGVNS is much faster and more effective. It is able to solve 50 to 484 customers from the literature.References
A. El Fallahi, C. Prins, and R. Wolfler Calvo, ”A memetic algorithm and a tabu search for the multi-compartment vehicle routing problem,” Computers and Operations Research, vol. 35, no.5, 2008, pp. 1725-1741.
A. Mjirda, B. Jarboui, R. Macedo, S. Hanafi, and N. Mladenovic, ”A two phase variable neighborhood search for the multi-product inventory routing problem,” Computers and Operations Research, vol. 52, Part B, 2014, pp. 291-299.
G.G. Brown and W.G. Graves, ”Real-time dispatching of petroleum tank trucks,” Management Science, vol. 27, no. 1, 1981, pp. 19-32.
G.G. Brown, C.J. Ellis, W.G. Graves, and D. Ronen, ”Real-time, wide area dispatch of Mobil tank trucks,” Interfaces, vol. 17, no. 1, Franz Edelman Award Papers (Jan. - Feb., 1987), pp. 107-120.
S. Apotheker, ”Curbside collection: Complete separation versus commingled collection,” Resource Recycling, 1990.
M. Jahre, ”Logistics systems for recycling-efficient collection of household waste,” Ph.D. thesis, Chalmers University of Technology, 1995.
I. Kaabachi, H. Yahyaouia, S. Krichena, and A. Dekdoukb, ”Measuring and evaluating hybrid metaheuristics for solving the multi-compartment vehicle routing problem, Measurement,” Measurement, vol. 141, July 2019, pp. 407-419.
T. Henke, M. Grazia Speranza, and G. Wäscher, ”A branch-and-cut algorithm for the multi-compartment vehicle routing problem with flexible compartment sizes,” Annals of Operations Research, vol 275, 2019. pp. 321-338.
R. Eshtehadi, E. Demirb, and Y. Huang, ”Solving the vehicle routing problem with multicompartment vehicles for city logistics,” Computers and Operations Research, vol 115, March 2020, 104859.
S. Martins, M. Ostermeier, P. Amorim, A. Hübner, and B. Almadalobo, ”Product-oriented time window assignment for a multi-compartment vehicle routing problem,” European Journal of Operational Research, vol 276, no 3, August 2019, pp. 893-909.
P.V. Silvestrin, and M. Ritt, ”An iterated tabu search for the multi-compartment vehicle routing problem,” Computers & Operations Research, vol. 81, 2017, pp. 192-202.
M. Ostermeiera, and A. Hübnerb, ”Vehicle selection for a multi-compartment vehicle routing problem,” European Journal of Operational Research, vol. 269, no. 2, September 2018, pp. 682-694.
R. Lahyani, L. C. Coelho, M. Khemakhem, G. Laporte, and F. Semet, ”A Multi-Compartment Vehicle Routing Problem Arising in the Collection of Olive Oil in Tunisia,” CIRRELT, 2014.
M. Reed, A. Yiannakou, and R. Evering, ”An ant colony algorithm for the multicompartment vehicle routing problem,” Applied Soft Computing, vol 15, February 2014, pp. 169-176.
M.S. Abdulkader, Y. GajpalbTarek, and Y. ElMekkawy, ”Hybridized ant colony algorithm for the Multi Compartment Vehicle Routing Problem,” Applied Soft Computing, vol. 37, December 2015, pp. 196-203.
S. Toumi, M. Cheikh, and B. Jarboui, ”0-1 Quadratic Knapsack Problem solved with VNS algorithm,” Electronic Notes in Discrete Mathematics, vol. 47, February 2015, pp. 269-276.
M. Gendreau, A. Hertz, and G. Laporte, ”A tabu search heuristic for the vehicle routing problem,” Management Science, vol. 40, no. 10, October 1994, pp. 1207-1393.
P. Hansen, N. Mladenović, and J.A. Moreno-Pérez, Variable neighbourhood search: methods and applications (invited survey). Annals of Operation Research, 367- 407.
B. Jarboui, H. Derbel, S. Hanafi, and N. Mladenovic, Variable neighborhood search for location routing. Computers and Operations Research, 2013.
P. C. Pop, and A. Horvat-Marc, Local search heuristics for the generalized vehicle routing problem. International Conference on System Modeling and Optimization, 2012.
Henke Tino, M. Grazia Speranza and Gerhard Wäscher. The multi-compartment vehicle routing problem with flexible compartment sizes. European Journal of Operational Research, 2015.
M. Ostermeier, T. Henke, A. Hübner, G. Wascher. Multi-compartment vehicle routing problems: State-of-the-art, modeling framework and future directions. European Journal of Operational Research, 2021.
P. VitorSilvestrin, M. Ritt. An iterated tabu search for the multi-compartment vehicle routing problem. Computers and Operations Research, 2021.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
