Un Algoritmo GRASP híbrido para el 2eCVRP

Primer acercamiento a la mecánica de contacto en amputados transfemorales unilaterales

Publicado

2017-07-01

Un Algoritmo GRASP híbrido para el 2eCVRP

A hybrid GRASP algorithm for 2eCVRP

Palabras clave:

ruteo de vehículos, dos escalones, metaheurísticas, GRASP, recocido simulado (es)
vehicle routing, two-echelon, metaheuristics, GRASP, simulated annealing (en)

Descargas

Autores/as

Javier Arias-Osorio Universidad Industrial de Santander https://orcid.org/0000-0001-6149-556X
Andrés Fernando Niño-Saénz Universidad Industrial de Santander https://orcid.org/0000-0002-9469-9785

Resumen (es)
Resumen (en)

Avances recientes en la investigación de problemas de ruteo, han abordado extensiones del clásico Problema de Ruteo de Vehículos (VRP), como lo es el Problema de Ruteo de Vehículos de Dos Escalones (2E-CVRP), en el cual se aborda el diseño de rutas en una cadena de suministro de dos escalones. El primero de ellos que conecta la carga desde un depósito central hasta su consolidación en depósitos intermedios denominados satélites, y el segundo que enlaza la carga de los satélites con el cliente final. Para la solución del 2E-CVRP se optó por implementar un híbrido metaheurístico, la primera técnica denominada GRASP se enfoca en la formación de una solución inicial; para dar lugar al segundo método, designado como recocido simulado, en el que por medio de los operadores 2-opt, Or-Opt y Exchange, se intensifica la búsqueda de mejora de la solución inicial. Este algoritmo presenta buenos resultados para casos propuestos de la literatura.

Recent advances in the investigation of routing problems, have allowed to give with extensions of the classic Vehicle Routing Problem (VRP), such as the Two-Echelon Vehicle Routing Problem (2E-CVRP), in which the aim is routes design in two echelon supply chain. The first one that connects the load from a central depot to its consolidation in intermediate deposits called satellites, and the second that links the load of the satellites with the final customer. For the solution of the 2E-CVRP was opted to implement a metaheuristic hybrid, the first technique called GRASP focuses on the formation of an initial solution; to give rise to the second method designated as simulated annealing, in which the inquisition for improvement of the initial solution is intensified by means of the 2-opt, Or-opt and Exchange operators. This algorithm shows goods results for instances of literature.

Descargas

Los datos de descargas todavía no están disponibles.

Citas

Fahimnia, B., Luong, L. and Marian, R. An integrated model for the optimization of a two-echelon supply network. Journal of Arias-Osorio & Niño-Sáenz / Revista DYNA, 84(202), pp. 16-25, September, 2017. 25 Achievements in Materials and Manufacturing Engineering, 31(2), pp. 477-484, 2008.

Perboli, G., Tadei, R. and Vigo, D., The two-echelon capacitated vehicle routing problem: Models and math-based heuristics. Transportation Science, 45(3), pp. 364-380, 2011. DOI: 10.1287/trsc.1110.0368

Gonzales, J., Perboli, G., Tadei R. and Vigo, D., The two-echelon capacitated vehicle routing problem. Technical report DEIS OR.INGCE2007/2(R).

Crainic, T., Mancini, S., Perboli, G. and Tadei, R., Clustering-based heuristics for the two-echelon vehicle routing problem. Technical Report Cirrelt-2008-46.

Crainic, T., Ricciardi, N. and Storchi, G., Models for evaluating and planning city logistics systems. Transportation Science, 43, pp. 432- 454, 2009. DOI: 10.1287/trsc.1090.0279

Crainic, T., Mancini, S., Perboli, G. and Tadei, R., Multi-start heuristics for the two-echelon vehicle routing problem. Evolutionary computation in combinatorial optimization: Lecture notes in Computer Science, 6622, pp.179-190, 2011. DOI: 10.1007/978-3- 642-20364-0_16

Perboli, G. and Tadei, R., New families of valid inequalities for the two-echelon vehicle routing problem. Electronic notes in discrete mathematics, 36(c), pp. 639-646, 2010. DOI: 10.1016/j.endm.2010.05.081

Crainic, T., Sforza, A. and Sterle, C., Location-routing models for two-echelon freight distribution system design. Technical Report Cirrelt-2011-40.

Laporte, G., Location-routing problems, in: Golden, B. and Assad, A., Vehicle routing: Methods and studies, Elsevier Science Publishers, North-Holland: Amsterdam, 1988. pp. 163-198.

Mancini, S., The two-echelon vehicle routing problem. 4or: A Quarterly Journal of Operations Research, 10(4), pp. 391-392, 2012.

Jepsen, M., Spoorendonk, S. and Ropke, S., A branch-and-cut algorithm for the two-echelon capacitated vehicle routing problem. Transportation Science, 47(1), pp. 23-37, 2012. DOI: 10.1287/trsc.1110.0399

Crainic, T., Mancini, S., Perboli, G. and Tadei, R., Impact of generalized travel costs on satellite location in the two-echelon vehicle routing problem. Procedia - Social and Behavioral Sciences, 39, pp. 195-204, 2012. DOI: 10.1016/j.sbspro.2012.03.101

Hemmelmayr, V., Cordeau, J. and Crainic, T., An adaptive large neighborhood search heuristic for two-echelon vehicle routing problems arising in city logistics. Computers & Operations Research, 39(12), pp. 3215-3228, 2012. DOI: 10.1016/j.cor.2012.04.007

Santos, F., Da cunha, A. and Mateus, G., Branch-and-price algorithms for the two-echelon capacitated vehicle routing problem. Optimization Letters, 7(7), pp. 1537-1547, 2012. DOI: 10.1007/s11590-012-0568-3

Baldacci, R., Mingozzi A., Roberti, R. and Calvo, R., An exact algorithm for the two-echelon capacitated vehicle routing problem. Operations Research, 61(2), pp. 298-314, 2013. DOI: 10.1287/opre.1120.1153

Crainic, T., Mancini, S., Perboli, G. and Tadei, R., Grasp with path relinking for the two-echelon vehicle routing problem. Advances in metaheuristics: Operations research/computer science interfaces series, 53, pp. 113-125, 2013. DOI: 10.1007/978-1-4614-6322-1_7

Zeng, Z., Xu, W. and Xu, Z., A two-phase hybrid heuristic for the two-echelon vehicle routing problem. Chinese Automation Congress (CAC), pp. 625-630, 2013. DOI: 10.1109/CAC.2013.6775811

Cuda, R., Guastaroba, G. and Speranza, M., A survey on two-echelon routing problems. Computers and Operations Research, 55, pp. 185- 199, 2014. DOI: 10.1016/j.cor.2014.06.008

Jiang, H., An hybrid heuristic algorithm for the two-echelon vehicle routing problem. Information Science and Control Engineering, 1, pp. 1-5, 2014.

Soysal, M., Bloemhof, J. and Bektas, T., The time-dependent twoechelon capacitated vehicle routing problem with environmental considerations. International Journal of Production Economics, 164, pp. 366-378, 2014. DOI: 10.1016/j.ijpe.2014.11.016

Grangier, P., Gendreau, M., Lehuédé F. and Rousseau, L., An adaptive large neighborhood search for the two-echelon multiple-trip vehicle routing problem with satellite synchronization. European Journal of Operational Research, 254(1), pp. 80-91, 2016. DOI: 10.1016/j.ejor.2016.03.040

Prins, C., A simple and effective evolutionary algorithm for the vehicle routing problem. Computers & Operations Research, 31, pp. 1985-2002, 2004. DOI: 10.1016/S0305-0548(03)00158-8

Nguyen, V., Prins, C. and Prodhon, C., Solving the two-echelon location routing problem by a grasp reinforced by a learning process and path relinking. European Journal of Operational Research, 216(1), pp. 113-126, 2012. DOI: 10.1016/j.ejor.2011.07.030

Avner, S., Introducción a la metalurgia física. 2° ed. México: Mc graw Hill. 1995.

Festa, P. and Resende, M., Hybrid grasp heuristics, in: Abraham, A., et al. Foundations of Computational Intelligence, vol. 3, 2009. pp. 75- 100. DOI: 10.1007/978-3-642-01085-9_4

Glover, F. and Kochenberger, G., Handbook of metaheuristics. 1° ed. New York: Kluwer academic publishers. 2003.

Ahuja, R., Ergun, O., Orlin, J. and Punnen, A., A survey of very largescale neighborhood search techniques. Discrete Applied Mathematics, 123, pp. 75-102, 2002. DOI: 10.1016/S0166- 218X(01)00338-9

Chen, P., Huang, H. and Dong, X., Iterated variable neighborhood descent algorithm for the capacitated vehicle routing problem. Expert Systems with Applications, 37, pp. 1620-1627, 2010. DOI: 10.1016/j.eswa.2009.06.047

Potvin, J. and Rousseau, J., An exchange heuristic for routeing problems with time windows. Journal of the Operational Research Society, 46, pp. 1433-1446, 1995. DOI: 10.1057/jors.1995.204

Braysy, O. and Gendreau, M., Vehicle routing problem with time windows, Part I: Route construction and local search algorithms. Transportation Science, 39(1), pp. 104-118, 2005. DOI: 10.1287/trsc.1030.0057, 10.1287/trsc.1030.0056

Gonzales, J., The N-echelon location routing problem: Concepts and methods for tactical and operational planning. Technical report halshs-00422492v2.

Licencia

Derechos de autor 2017 DYNA

Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-SinDerivadas 4.0.

El autor o autores de un artículo aceptado para publicación en cualquiera de las revistas editadas por la facultad de Minas cederán la totalidad de los derechos patrimoniales a la Universidad Nacional de Colombia de manera gratuita, dentro de los cuáles se incluyen: el derecho a editar, publicar, reproducir y distribuir tanto en medios impresos como digitales, además de incluir en artículo en índices internacionales y/o bases de datos, de igual manera, se faculta a la editorial para utilizar las imágenes, tablas y/o cualquier material gráfico presentado en el artículo para el diseño de carátulas o posters de la misma revista.