A matheuristic algorithm for the three dimensional loading capacitated vehicle routing problem (3L-CVRP)
DOI:
https://doi.org/10.17533/udea.redin.n78a02Keywords:
vehicle routing problem, matheuristics, branch-and-cut, packingAbstract
This paper presents a hybrid algorithm for solving the Capacitated Vehicle Routing Problem with practical three-dimensional loading constraint. This problem is known as 3L-CVRP (Three-dimensional Loading Capacitated Vehicle Routing Problem). The proposed methodology consists of two phases. The first phase uses an optimization procedure based on cuts to obtain solutions for the well-known Capacitated Vehicle Routing Problem (CVRP). The second phase validates the results of the first phase of a GRASP algorithm (Greedy Randomized Adaptive Search Procedure). In particular, the GRASP approach evaluates the packing constraints for each performed route of the CVRP. The proposed hybrid algorithm uses a relaxation of the classical model of two sub-indices for the vehicle routing problem. Specifically different types of cuts are added: subtour elimination, capacity-cut constraints, and packing-cut constrains. The proposed algorithm is compared with the most efficient approaches for the 3L-CVRP on the set of benchmark instances considered in the literature. The computational results indicate that the proposed approach is able to obtain good solutions, improving some of the best-known solutions from the literature.
Downloads
References
P. Augerat et al., “Computational results with a branch and cut code for the capacitated vehicle routing problem”, Université Joseph Fourier, Grenoble, France, Tech. Rep. 949-M, 1995.
P. Toth and D. Vigo, The Vehicle Routing Problem, Monographs on Discrete Mathematics and Applications, Philadelphia, USA, 2002.
B. Golden, S. Raghavan and E. Wasil, The Vehicle Routing Problem: Latest Advances and New Challenges. USA: Springer, 2008.
R. Baldacci, P. Toth and D. Vigo, “Exact algorithms for routing problems under vehicle capacity constraints”, Annals of Operations Research, vol. 175, no. 1, pp. 213- 245, 2010.
V. Schmid, K. Doerner and G. Laporte, “Rich routing problems arising in supply chain management”, European Journal of Operational Research, vol. 224, no. 3, pp. 435-448, 2013.
A. Lodi, S. Martello and M. Monaci, “Two-dimensional packing problems: A survey”, European Journal of Operational Research, vol. 141, no. 2, pp. 241-252, 2002.
V. Paschos, Paradigms of Combinatorial Optimization: Problems and New Approaches. John Wiley & Sons, 2013.
G. Wascher, H. Haubner and H. Shchumann, “An improved typology of cutting and packing problems”, European Journal of Operational Research, vol. 183, no. 3, pp. 1109-1130, 2007.
E. Coffman, J. Csirik, G. Galambos, S. Martello and D. Vigo, “Bin Packing Approximation Algorithms: Survey and Classification”, in Handbook of Combinatorial Optimization, 2nd ed., P. Pardalos, D. Du and R. Graham (eds): New York, USA: Springer, 2013, pp. 455-531.
M. Alonso, R. Alvarez, J. Tamarit and F. Parreño, “A reactive GRASP algorithm for the container loading problem with load-bearing constraints”, European Journal of Industrial Engineering, vol. 8, no. 5, pp. 669- 694, 2014.
D. Álvarez, F. Parreño, R. Álvarez and F. Parreno, “A grasp algorithm for the container loading problem with multi-drop constraints”, Pesqui. Oper., vol. 35, no. 1, pp. 1-24, 2015.
L. Junqueira, J. Oliveira, M. Carravilla and R. Morabito, “An optimization model for the vehicle routing problem with practical three-dimensional loading constraints”, International Transactions in Operational Research, vol. 20, no. 5, pp. 645-666, 2013.
A. Moura and J. Oliveira, “An integrated approach to vehicle routing and container loading problems”, OR Spectrum, vol. 31, no. 4, pp. 775-800, 2009.
A. Moura, “A multi-objective genetic algorithm for the vehicle routing with time windows and loading problem”, in Intelligent Decision Support, 1st ed., A. Bortfeldt, J. Homberger, H. Kopfer, G. Pankratz and R. Strangmeier (eds). Frankfurt, Germany: Springer, 2008, pp. 187-201.
M. Gendreau, M. Iori, G. Laporte and S. Martello, “A tabu search algorithm for a routing and container loading problem”, Transportation Science, vol. 40, no. 3, pp. 342-350, 2006.
Y. Tao and F. Wang, “A new packing heuristic based algorithm for vehicle routing problem with threedimensional loading constraints”, in Conference on Automation Science and Engineering (CASE), Toronto, Canada, 2010, pp. 972-977.
C. Tarantilis, E. Zachariadis, and C. Kiranoudis, “A hybrid metaheuristic algorithm for the integrated vehicle routing and three-dimensional containerloading problem”, IEEE Transactions on Intelligent Transportation Systems, vol. 10, no. 2, pp. 255-271, 2009.
G. Fuellerer, K. Doerner, R. Hartl and M. Iori, “Metaheuristics for vehicle routing problems with three-dimensional loading constraints”, European Journal of Operational Research, vol. 201, no. 3, pp. 751- 759, 2010.
Q. Ruan, Z. Zhang, L. Miao and H. Shen, “A hybrid approach for the vehicle routing problem with threedimensional loading constraints”, Computers & Operations Research, vol. 40, no. 6, pp. 1579-1589, 2013.
L. Miao, Q. Ruan, K. Woghiren and Q. Ruo, “A hybrid genetic algorithm for the vehicle routing problem with three-dimensional loading constraints”, RAIRO - Operations Research, vol. 46, no. 1, pp. 63-82, 2012.
W. Zhu, H. Qin, A. Lim and L. Wang, “A two-stage tabu search algorithm with enhanced packing heuristics for the 3l-cvrp and m3l-cvrp”, Computers & Operations Research, vol. 39, no. 9, pp. 2178-2195, 2012.
G. Koloch and B. Kaminski, “Nested vs. joint optimization of vehicle routing problems with threedimensional loading constraints”, Engineering Letters, vol. 18, no. 2, pp. 193-198, 2010.
A. Bortfeldt and J. Homberger, “Packing first, routing second - a heuristic for the vehicle routing and loading problem”, Computers & Operations Research, vol. 40, no. 3, pp. 873-885, 2013.
A. Bortfeldt, “A hybrid algorithm for the capacitated vehicle routing problem with three-dimensional loading constraints”, Computers & Operations Research, vol. 39, no. 9, pp. 2248-2257, 2012.
T. Feo and M. Resende, “A probabilistic heuristic for a computationally difficult set covering problem”, Operations Research Letters, vol. 8, no. 2, pp. 67-71, 1989.
M. Resende and C. Ribeiro, “Greedy Randomized Adaptive Search Procedures”, in Handbook of Metaheuristics, 1st ed., F. Glover and G. Kochenberger (eds). Norwell, USA: Kluwer Academic Publishers, 2003, pp. 219-249.
F. Parreño, R. Álvarez, J. Tamarit and J. Oliveira, “Neighborhood structures or the container loading problem: A VNS implementation”, Journal of Heuristics, vol. 16, no. 1, pp. 1-22, 2010.
R. Marti and J. Moreno, “Métodos multiarranque”, Inteligencia Artificial, vol. 7, no. 19, pp. 49-60, 2003.
Y. Tao and F. Wang, “An effective tabu search approach with improved loading algorithms for the 3l-cvrp,” Computers Operations Research, vol. 55, pp. 127-140, 2015.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2016 Revista Facultad de Ingeniería Universidad de Antioquia
This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.
Revista Facultad de Ingeniería, Universidad de Antioquia is licensed under the Creative Commons Attribution BY-NC-SA 4.0 license. https://creativecommons.org/licenses/by-nc-sa/4.0/deed.en
You are free to:
Share — copy and redistribute the material in any medium or format
Adapt — remix, transform, and build upon the material
Under the following terms:
Attribution — You must give appropriate credit, provide a link to the license, and indicate if changes were made. You may do so in any reasonable manner, but not in any way that suggests the licensor endorses you or your use.
NonCommercial — You may not use the material for commercial purposes.
ShareAlike — If you remix, transform, or build upon the material, you must distribute your contributions under the same license as the original.
The material published in the journal can be distributed, copied and exhibited by third parties if the respective credits are given to the journal. No commercial benefit can be obtained and derivative works must be under the same license terms as the original work.
Twitter