Un algoritmo híbrido para el problema de ruteo de vehículos con restricciones de carga de tridimensional
DOI:
https://doi.org/10.17533/udea.redin.n78a02Palabras clave:
problema de enrutamiento de vehículos, matheurísticas, branch-and-cut, empaquetamientoResumen
En este artículo se presenta un algoritmo híbrido para resolver el problema de ruteo de vehículos con restricciones de capacidad y restricciones prácticas de empaquetamiento tridimensional, este problema en la literatura es conocido como 3L-CVRP (Capacitated Vehicle Routing Problem and Container Loading Problem). La metodología de solución propuesta en este trabajo consiste de dos fases. La primera utiliza un procedimiento de optimización basado en cortes para el Problema de Rutas de Vehículos Capacitados (CVRP). La segunda valida las soluciones de la fase anterior a través de un algoritmo GRASP (Greedy Randomized Adaptive Search Procedure), el cual evalúa las restricciones de empaquetamiento de cada una de las rutas. Para el algoritmo híbrido se utiliza la relajación del modelo clásico de dos subíndices para el problema de ruteo de vehículos. En particular diferentes tipos de cortes son adicionados: eliminación de subtours, cortes debido a las restricciones de capacidad y cortes para restricciones de empaquetamiento. El algoritmo propuesto ha sido comparado con los algoritmos más eficaces para el 3L-CVRP en el conjunto clásico de instancias presentadas en la literatura. Los resultados computacionales muestran que el método propuesto es capaz de obtener buenos resultados perfeccionando algunas de las mejores soluciones conocidas propuestas en la literatura.
Descargas
Citas
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.
Descargas
Publicado
Cómo citar
Número
Sección
Licencia
Derechos de autor 2016 Revista Facultad de Ingeniería Universidad de Antioquia
Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-CompartirIgual 4.0.
Los artículos disponibles en la Revista Facultad de Ingeniería, Universidad de Antioquia están bajo la licencia Creative Commons Attribution BY-NC-SA 4.0.
Eres libre de:
Compartir — copiar y redistribuir el material en cualquier medio o formato
Adaptar : remezclar, transformar y construir sobre el material.
Bajo los siguientes términos:
Reconocimiento : debe otorgar el crédito correspondiente , proporcionar un enlace a la licencia e indicar si se realizaron cambios . Puede hacerlo de cualquier manera razonable, pero no de ninguna manera que sugiera que el licenciante lo respalda a usted o su uso.
No comercial : no puede utilizar el material con fines comerciales .
Compartir igual : si remezcla, transforma o construye a partir del material, debe distribuir sus contribuciones bajo la misma licencia que el original.
El material publicado por la revista puede ser distribuido, copiado y exhibido por terceros si se dan los respectivos créditos a la revista, sin ningún costo. No se puede obtener ningún beneficio comercial y las obras derivadas tienen que estar bajo los mismos términos de licencia que el trabajo original.
Twitter