Revista INGENIERÍA, Vol. 16, No. 2, 2011

DOI:

https://doi.org/10.14483/23448393.3832

Published:

2011-12-18

Issue:

Vol. 16 No. 2 (2011): July - December

Section:

Article

Una Revisión al Estado del Arte del Problema de Ruteo de Vehículos: Evolución Histórica Y Métodos De Solución

State of the art review of the vehicle routing problem: A historic account with solving methods

Authors

  • Linda Bibiana Rocha Medina Universidad Minuto de Dios de Soacha
  • Elsa Cristina González La Rotta Universidad Católica de Colombia
  • Javier Arturo Orjuela Castro Universidad Distrital Francisco José de Caldas

Keywords:

Vehicle Routing Problem, Solution Exact, Heuristics, Meta-heuristics Methods (en).

Keywords:

Problema de Ruteo de Vehículos, Múltiples Viajes, Métodos Exactos, Heurísticas, Metaheurísticas. (es).

Downloads

Abstract Authors Available Metrics References How to Cite

Abstract (es)

Este artículo presenta una revisión bibliográfica acerca de la historia, tipologías y métodos de solución del Problema de Ruteo de Vehículos (VRP). Explica las diferentes variaciones que han surgido, y hace referencia a las categorías básicas de VRP, los métodos de solución propuestos, así como sus tendencias.

Abstract (en)

This paper is a literature review of the history, categories, and solution methods of the vehicle routing problem with multiple trips (Multi-trip VRP). It explains the beginning of the concept of VRP and discusses the different variations that have arisen recently. Solution methods, approaches and tendencies to these variations are described with references to further studies

Author Biographies

Linda Bibiana Rocha Medina, Universidad Minuto de Dios de Soacha

Nació en Bogotá, Colombia. Es Ingeniero Industrial de la Universidad de La Sabana, Chía – Puente del Común, Colombia. Candidata a Título de Maestría en Ingeniería Industrial en la Universidad Distrital Francisco José de Caldas, Bogotá, Colombia. Se desempeñó como Coordinador de Calidad en Almacenes Brisa durante 2,5 años y como consultor Junior de procesos en Novartis de Colombia durante 3 meses. Posteriormente, ejerció el cargo de asesor en la Universidad Distrital Francisco José de Caldas donde participó el proyecto de Documentación e Implementación del Sistema Integrado de Gestión MECI-Calidad. Actualmente se desempeña como docente en el área de Logística en la Universidad Minuto de Dios de Soacha, Colombia.

Elsa Cristina González La Rotta, Universidad Católica de Colombia

Nació en Bogotá, Colombia. Es Ingeniero Industrial de la Universidad Distrital Francisco José de Caldas, Bogotá, Colombia. Candidata a Título de Maestría en Ingeniería Industrial en la Universidad Distrital Francisco José de Caldas, Bogotá, Colombia. Se desempeñó como docente en la Universidad Antonio Nariño durante 5 años. Actualmente se desempeña como profesor en el área de Investigación de Operaciones en la Universidad Católica de Colombia.

Javier Arturo Orjuela Castro, Universidad Distrital Francisco José de Caldas

Nació en Bogotá, Colombia. Es Ingeniero Industrial y Especialista en Ingeniería de Producción de la Universidad Distrital Francisco José de Caldas de Bogotá e Ingeniero de Alimentos. Obtuvo su título de Maestría en Investigación de Operaciones y Estadística en la Universidad Tecnológica de Pereira, Colombia, Estudios de Doctorado en Ingeniería Química, Universidad Nacional, de Bogotá, Colombia. Actualmente se desempeña como docente de tiempo completo en la Universidad Distrital Francisco José de Caldas, adscrito a la Facultad de Ingeniería.

References

Paolo Toth y Daniele Vigo, “The Vehicle Routing Problem”. Society of Industrial and Applied Mathematics (SIAM) monographs on discrete mathematics and applications, Philadelphia, USA, 2002, pp 1-23, 109-149.

M. L. Balinzki y R. E. Quandt, “On an Integer Program for a Delivery Problem”, Operational Research, Vol. 12, No. 2, 1964, pp 300-304. Mencionado por Prawda, J. (2002)

W. W. Garvin, H. W. Crandall, J.B. John y R. A. Spellman, “Aplications of Linear Programming in the Oil Industry”, Management Science, Vol. 3, 1957, pp 407. Mencionado por Prawda, J. (2002)

Alfredo Olivera, “Heurísticas para problemas de ruteo de vehículos”, reporte de investigación, Instituto de Computación – Facultad de Ingeniería, Universidad de la República, Montevideo, Uruguay, 2004, disponible en http://www.fing.edu.uy/inco/pedeciba/bibliote/reptec/TR0408.pdf.

Bruce Golden, S. Raghavan y Edward Wasil, “The vehicle routing problem: latest advances and new challenges”. Springer, New York, 2008, pp 3-122.

Leonora Bianchi, Mauro Birattari, Marco Chiarandini, Max Manfrin y Monaldo Mastrolilli, “Metaheuristics for the Vehicle Routing Problem with Stochastic Demands”, Lecture Notes in Computer Science, Vol 3242, 2004, pp 450-460.

The VRP Web, Collaboration between AUREN and the Languages and Computation Sciences department of the University of Málaga by Bernabé Dorronsoro Díaz, última actualización: marzo de 2007, consultada en abril de 2010, disponible en http://neo.lcc.uma.es/radi-aeb/WebVRP/.

Jorge Hernán Restrepo, Pedro Daniel Medina y Eduardo Arturo Cruz, “Un problema logístico de programación de vehículos con ventanas de tiempo”, Scientia et Technica – Universidad Tecnológica de Pereira, Vol. 14, No 39, 2008.

N. Suthikarnnarunai y E. Olinick, “Improving transportation services for the University of the Thai Chamber of Commerce: A case study on solving the mixed-fleet vehicle routing problem with split deliveries”, Transacctions on engineering tecnologies, Vol. 1, Special edition of the international MultiConference of Engineers and Computer Scientist, 2009.

Ulrich Derigs y Thomas Döhmer, “Indirect search for the vehicle routing problem with pickup and delivery and time windows”, OR Spectrum, Vol. 30, No. 1,2006, pp 149-165.

G. Gutierres Jarpa, V. Marianov y C. Obrecue, “A single Vehicle routing problem with fixed delivery and optional collection”, IIE Transactions, Vol. 41, 2009, pp 1067-1079.

Bernhard Fleischmann, Martin Gietz y Stefan Gnutzmann, “Time-varying travel times in vehicle routing”, Transportation science, Vol. 38, No. 2, 2003, pp. 160–173.

Nabila Azi, Michel Gendreau y Jean-Yves Potvin, “An exact algorithm for a vehicle routing problem with time windows and multiple use of vehicles”, European Journal of Operational Research, Vol. 202, No. 3, 2010, pp 756-763.

María Battarraa, M. Monaci y Daniele Vigo, “An adaptive guidance approach for the heuristic solution of a minimum multiple trip vehicle routing problem”, Computers & Operations Research, Vol. 36, 2009, pp 3041-3050.

D.J. Guan y Xuding Zhu, “Multiple capacity vehicle routing on paths”, Siam J. Discrete math, Vol. 11, No. 4, 1998, pp 590-602.

K.C. Tan, C.Y. Cheong y C.K. Goh, “Solving multiobjective vehicle routing problem with stochastic demand via evolutionary computation”, European Journal of Operational Research, Vol. 177, 2006, pp 813–839.

Dusan Teodorovic y Panta Lucic, “The fuzzy ant system for the vehicle routing problem when demand at nodes is uncertain”, International Journal of Computational Intelligence and Applications, Vol. 16, No. 5, 2006, pp 751-770.

Gilbert Laporte, Francois Louveaux y Hélène Mercure, “The vehicle routing problem with stochastic travel times”, Transportation Science, Vol. 26, No.3, 2001, pp 161-170.

Pierre Hansen, Nenad Mladenovic y José Andrés Moreno. “Búsqueda de Entorno Variable”, Inteligencia Artificial – Revista Iberoamericana de Inteligencia Artificial, Vol. 7, No. 19, 2003, pp 77-92, disponible en http://www.redalyc.org/src/inicio/ArtPdfRed.jsp?iCve=92571905 .

Dionisio Pérez Brito, José Andrés Moreno Pérez y Carlos Gustavo García González, “Búsqueda por entornos variables: Desarrollo y Aplicaciones en localización” En: Avances en localización de servicios y sus aplicaciones por Blas Pelegrín Pelegrín. 1ª Edición, Servicio de publicaciones – Universidad de Murcia, Murcia, España, 2004, pp 349-374.

Gilbert Laporte, “The Vehicle Routing Problem: An overview of exact and approximate algorithms”, European Journal of Operational Research, Vol. 59, 1991, pp 345-358.

Víctor Yepes Piqueras, “Optimización heurística económica aplicada a las redes de transporte del tipo VRPTW”, tesis doctoral, Departamento de Ingeniería de la Construcción y Proyectos de Ingeniería Civil, Escuela Técnica Superior de Ingenieros de Caminos Canales y Puertos – Universidad Politécnica de Valencia, Valencia, España, 2002.

Alexander Ayala Rodríguez y Edgar González Butrón, “Asignación de rutas de vehículos para un sistema de recolección de residuos sólidos en la acera”, Revista de Ingeniería - Universidad de Los Andes, No. 13, 2001, pp 5-11.

Eduardo Arturo Cruz, Jorge Hernán Restrepo y Pedro Daniel Medina, “Un problema logístico de ruteo de vehículos y una solución con solver Excel”, Scientia et Technica – Universidad Tecnológica de Pereira, Vol. 13, No. 37, 2007, pp 369-372.

Dongjoo Park, Laurence Rilett y Changho Chol, “A class of multicriteria shortest path problems for real-time in-vehicle routing”, Canadian Journal of Civil Engineering, Vol. 34, No. 9, 2007, pp 1096-1109.

Jorge Hernán Restrepo y Pedro Daniel Medina, “Un problema logístico de ruteo de vehículos y una solución con la heurística R”, Scientia et Technica – Universidad Tecnológica de Pereira, Vol. 14, No 39, 2007, pp 229-234.

R. J. Petch y S. Salhi, “A multi-phase constructive heuristic for the vehicle routing problem with multiple trips”, Discrete Applied Mathematics, Vol. 133, 2003, pp 69 – 92.

José Fidel Torres Delgado y Edgar González Butrón, “Un caso real en Colombia de aplicación de heurísticas en el problema de programación de rutas para helicópteros”, XI Congreso Latino Iberoamericano de Investigación de Operaciones – Universidad de Concepción, Concepción, Chile, 2006.

Francisco Baptista Pereira y Jorge Tavares, “Bio-inspired algorithms for the vehicle routing problem”. Vol. 161, Springer, Varsovia, Polonia, 2009, pp 55-130.

Wee-Kit Ho, Juay Chin Ang y Andrew Lim, “A hybrid search algorithm for the vehicle routing problem with time windows”, International Journal on Artificial Intelligence Tools, Vol. 10, N0.3, 2001, pp 431-449.

Gilbert Laporte, Michel Gendreau y Alain Hertz, “An aproximation algorithm for the traveling salesman problem with time windows”, Institute for Operation Research and de Management Science – Operations Research, Vol. 45, No. 4, 1998, pp 639-641.

Claudio Andrés Contardo Vera, “Formulación y solución de un problema de ruteo de vehículos con demanda variable en tiempo real, trasbordos y ventanas de tiempo”, Memoria para optar al título de ingeniero civil matemático, Departamento de Ingeniería Matemática, Universidad de Chile, Santiago de Chile, Chile, 2005.

Gilbert Laporte, Jacques Reanud y Fayez Boctor, “An improved petal heuristic for the vheicle routeing problem”, The Journal of the Operational Research Society, Vol. 47, No. 2, 1996, pp. 329- 336.

Jean-Francois Cordeau, Michel Gendreau, Gilbert Laporte, Jean-Yves Potvin y Frédéric Semet, “A guide to vehicle routing heuristics”, The Journal of the Operational Research Society, Vol. 53, No. 5, 2002, pp 512- 522.

Olli Bräysy y Wout Dullaert, “A fast evolutionary metaheuristic for the VRP with time windows”, International Journal on Artificial Intelligence Tools, Vol. 12, 2003, pp 153-172.

Eric Crespo, Rafael Martí y Joaquín Pacheco, “Procedimientos Metaheurísticos en Economía y Empresa”, Revista Electrónica de Comunicaciones y trabajos de ASEPUMA, 1ª Edición, Tirant lo Blanch, Valencia, España, 2007.

Guillermo González Vagas y Felipe González Aristizábal, “Metaheurísticas aplicadas al ruteo de vehículos. Parte 1: formulación del problema”, Revista de Ingeniería e Investigación – Universidad Nacional de Colombia, Vol. 26, No.3, 2006, pp 149-156.

Guillermo González Vagas y Felipe González Aristizábal, “Metaheurísticas aplicadas al ruteo de vehículos. Parte 2: algoritmo genético, comparación con una solución heurística”, Revista de Ingeniería e Investigación – Universidad Nacional de Colombia, Vol. 27, No.1, 2007, pp 149-157.

Guillermo González Vagas y Felipe González Aristizábal, “Metaheurísticas aplicadas al ruteo de vehículos. Parte 3: Genetic Clustering and Tabu Routing”, Revista de Ingeniería e Investigación – Universidad Nacional de Colombia, Vol. 27, No.2, 2007, pp 106-113.

George Mourkousis, Matew Protonotarios y Theodora Varvarigou, “Application of genetic algorithm to a large-scale multiple-constraint vehicle routing problem”, International Journal of Computational Intelligence and Applications, Vol. 3, No. 1, 2003, pp 1-21.

R. J. Petch y S. Salhi, “A GA Based Heuristic for the Vehicle Routing Problem with Multiple Trips”, Journal of Mathematical Modelling and Algorithms, Vol. 6, No. 4, 2007, pp 591-613

Olatz Arbelaitz y Clemente Rodríguez, “Comparison of systems based on evolutionary search and simulated annealing to solve VRPTW problem”, International Journal of Computational Intelligence and Applications, Vol. 4, 2004, pp 27-39.

Karl Doerner et all. “Savings Ants for the Vehicle Routing Problem”, Lecture Notes in Computer Science – Applications of Evolutionary Computing, Vol. 2279, 2001, pp 73-109.

D.K Gupta. “Tabu search for vehicle routing problem”, Intern. J. Computer Math, Vol. 79, No. 6, 2002, pp 693-701.

Gilbert Laporte, Alain Hertz y Michel Mittaz, “A tabu search heuristic for the capacited arc routing problem”, Institute for Operation Research and de Management Science – Operations Research, Vol. 48, No. 1, 2000, pp 129-135.

Alfredo Olivera y Omar Viera. “Adaptive memory programming for the Vehicle routing problem with multiple trips”, Computers and Operation Research, Vol. 34, 2007, pp 28–47.

Ahmet Sen y Kerem Bülbül, “A survey on multi trip vehicle routing problem”, VI International Logistics and Supply Chain Congress, Turkiye, 2008.

Eric D.Taillard, Gilbert Laporte y Michel Gendreau, “Vehicle routeing with multiple use of Vehicles”, The Journal of the Operational Research Society, Vol. 47, No. 8, 1996, pp 1065- 1070

José Brandao y Alan Mercer. “A tabu search algorithm for the multi-trip vehicle routing and scheduling problem”, European Journal of Operational Research, Vol. 100, No. 1, 1997, pp 180-191

Christian Prins, “Efficient heuristics for the heterogeneous fleet multitrip VRP with application to a large-scale real case”, Journal of Mathematical Modelling and Algorithms, Vol 1, 2002, pp 135-150.

F. Alonso, M. J. Álvarez y J.E. Beasley, “A Tabu Search Algorithm for the periodic vehicle routing problem with multiple vehicle trips and accessibility restrictions”, Journal of the Operational Research Society, Vol 59, 2008, pp 963-976.

Nabila Azi, Michel Gendreau y Jean-Yves Potvin, “An adaptive large neighborhood search for a vehicle routing problem with multiple trips”, Centre interuniversitaire de recherche sur les réseaux d’enterprise, la logistique et le transport (CIRRELT), Quebec, Canadá, 2010

Gerardo Berbeglia, Jean-Francois Cordeau y Gilbert Laporte, “Dynamic pickup and delivery problems” European Journal of Operational Research, Vol. 202, 2009, pp 8-15.

Roberto Baldacce, Aristide Mingozzi y Roberto Roberti, “Recent exact algoritms for solving the vehicle routing problem under capacity and time windows constraints”, European Journal of Operational Research, Vol. 218, 2011, pp 1-6.

Michel Gendreau, “Recent advances in stochastic vehicle routing”, SPBO 42° Bento Golcalves, 2010.

Hillier Frederick, Lieberman Gerald, “Introducción a la Investigación de Operaciones”, Mc Graw Hill, novena edición, 2010.

José Álvaro Rengifo Campo, M. Gulnara Baldoquin de la Peña y John Wilmer Escobar, “Diseño de un modelo matemático para el despacho de vehículos de emergencias médicas en Colombia”, XVI Latin-Ibero-American Conference on Operation Research / XLIV Brazilian Symposium on Operation Research (XVI CLAIO / XVIV SPBO), ponencia No. 101157, Rio de Janeiro, Brazil, 2011

Javier Arias-Osorio, Carlos Eduardo Díaz Bohórquez y Henry Lamos Díaz, “Sistema de soporte a decisiones para el diseño de rutas escolares en Coomunclaver Ltda”, XVI Latin-Ibero-American Conference on Operation Research / XLIV Brazilian Symposium on Operation Research (XVI CLAIO / XVIV SPBO), ponencia No. 102217, Rio de Janeiro, Brazil, 2011

W. J. Guerrero, C. Prodhon, N. Velasco y C. A. Amaya, “Hybrid heuristic for the inventory location-routing problem”, XVI Latin-Ibero-American Conference on Operation Research / XLIV Brazilian Symposium on Operation Research (XVI CLAIO / XVIV SPBO), session especial No. 105451, Rio de Janeiro, Brazil, 2011

Elsa Cristina González La Rotta y Javier Arturo Orjuela Castro, “Vehicle routing problem with random components for the collection of perishable products”, XVI Latin-Ibero-American Conference on Operation Research / XLIV Brazilian Symposium on Operation Research, (XVI CLAIO / XVIV SPBO), poster No. 105405, Rio de Janeiro, Brazil, 2011

How to Cite

APA

Rocha Medina, L. B., González La Rotta, E. C., and Orjuela Castro, J. A. (2011). Una Revisión al Estado del Arte del Problema de Ruteo de Vehículos: Evolución Histórica Y Métodos De Solución. Ingeniería, 16(2), 35–55. https://doi.org/10.14483/23448393.3832

ACM

[1]
Rocha Medina, L.B. et al. 2011. Una Revisión al Estado del Arte del Problema de Ruteo de Vehículos: Evolución Histórica Y Métodos De Solución. Ingeniería. 16, 2 (Dec. 2011), 35–55. DOI:https://doi.org/10.14483/23448393.3832.

ACS

(1)
Rocha Medina, L. B.; González La Rotta, E. C.; Orjuela Castro, J. A. Una Revisión al Estado del Arte del Problema de Ruteo de Vehículos: Evolución Histórica Y Métodos De Solución. Ing. 2011, 16, 35-55.

ABNT

ROCHA MEDINA, Linda Bibiana; GONZÁLEZ LA ROTTA, Elsa Cristina; ORJUELA CASTRO, Javier Arturo. Una Revisión al Estado del Arte del Problema de Ruteo de Vehículos: Evolución Histórica Y Métodos De Solución. Ingeniería, [S. l.], v. 16, n. 2, p. 35–55, 2011. DOI: 10.14483/23448393.3832. Disponível em: https://revistas.udistrital.edu.co/index.php/reving/article/view/3832. Acesso em: 8 nov. 2024.

Chicago

Rocha Medina, Linda Bibiana, Elsa Cristina González La Rotta, and Javier Arturo Orjuela Castro. 2011. “Una Revisión al Estado del Arte del Problema de Ruteo de Vehículos: Evolución Histórica Y Métodos De Solución”. Ingeniería 16 (2):35-55. https://doi.org/10.14483/23448393.3832.

Harvard

Rocha Medina, L. B., González La Rotta, E. C. and Orjuela Castro, J. A. (2011) “Una Revisión al Estado del Arte del Problema de Ruteo de Vehículos: Evolución Histórica Y Métodos De Solución”, Ingeniería, 16(2), pp. 35–55. doi: 10.14483/23448393.3832.

IEEE

[1]
L. B. Rocha Medina, E. C. González La Rotta, and J. A. Orjuela Castro, “Una Revisión al Estado del Arte del Problema de Ruteo de Vehículos: Evolución Histórica Y Métodos De Solución”, Ing., vol. 16, no. 2, pp. 35–55, Dec. 2011.

MLA

Rocha Medina, Linda Bibiana, et al. “Una Revisión al Estado del Arte del Problema de Ruteo de Vehículos: Evolución Histórica Y Métodos De Solución”. Ingeniería, vol. 16, no. 2, Dec. 2011, pp. 35-55, doi:10.14483/23448393.3832.

Turabian

Rocha Medina, Linda Bibiana, Elsa Cristina González La Rotta, and Javier Arturo Orjuela Castro. “Una Revisión al Estado del Arte del Problema de Ruteo de Vehículos: Evolución Histórica Y Métodos De Solución”. Ingeniería 16, no. 2 (December 18, 2011): 35–55. Accessed November 8, 2024. https://revistas.udistrital.edu.co/index.php/reving/article/view/3832.

Vancouver

1.
Rocha Medina LB, González La Rotta EC, Orjuela Castro JA. Una Revisión al Estado del Arte del Problema de Ruteo de Vehículos: Evolución Histórica Y Métodos De Solución. Ing. [Internet]. 2011 Dec. 18 [cited 2024 Nov. 8];16(2):35-5. Available from: https://revistas.udistrital.edu.co/index.php/reving/article/view/3832

Download Citation

Visitas

3075

Dimensions


PlumX


Downloads

Download data is not yet available.

License

From the edition of the V23N3 of year 2018 forward, the Creative Commons License "Attribution-Non-Commercial - No Derivative Works " is changed to the following:

Attribution - Non-Commercial - Share the same: this license allows others to distribute, remix, retouch, and create from your work in a non-commercial way, as long as they give you credit and license their new creations under the same conditions.

Most read articles by the same author(s)