Published
Metaheuristics applied to vehicle routing. A case study. Part 1: formulating the problem
Metaheurísticas aplicadas al ruteo de vehículos. Un caso de estudio. Parte 1: formulación del problema
DOI:
https://doi.org/10.15446/ing.investig.v26n3.14768Keywords:
distribution, vehicle routing problem, mathematical formulation (en)distribución, ruteo de vehículos, formulación matemática (es)
Downloads
This paper deals with VRP (vehicle routing problem) mathematical formulation and presents some methodologies used by different authors to solve VRP variation. This paper is presented as the springboard for introducing future papers about a manufacturing company’s location decisions based on the total distance traveled to distribute its product.
En este artículo se presentan la formulación matemática del problema de ruteo de vehículos (VRP) y una serie de metodologías utilizadas por diferentes autores para resolver sus variaciones. Se presenta con el propósito de introducir al lector a una serie de artículos referentes a la decisión de localización de una empresa manufacturera tomando como criterio de selección la distancia total a recorrer para distribuir su producto.
References
Ahuja, R., Magnanti, T. and Orlin, J., Network flows: theory, algorithms, and applications., Englewood Cliffs, New Jersey: Prentice Hall, 1993.
Anónimo., Network. s/f., Disponible en: http://www.cs.tcd.ie/courses/baict/bass/4ict5/Networks2004.pdf. Consultado en Marzo de 2004.
Applegate, D., Cook, W., Dash, S. and Rohe, A., Solution of a Min-Max Vehicle Routing Problem. August 15, 2001. Disponible en: http://www.research.ibm.com/people/s/sanjeebd/reports/newsboys.pdf. Consultado en Febrero de 2005.
Archetti, C., Mansini, R. and Speranza, M.G., The Split Delivery Vehicle Routing Problem with Small Capacity, November 7, 2001, Disponible en: http://fausto.eco.unibs.it/~www_mequ/ricerca/quaderni/201.pdf. Consultado en: Febrero de 2005.
Ballou, R. H., Business Logistics Management., Prentice-Hall, New Jersey, 4° edición, 1998, pp. 3-28, 481-592.
Baran, B. and Schaerer, M. A., Multiobjective Ant Colony System for Vehicle Routing Problem with Time Windows., Proceedings of the 21st IASTED International Conference APPLIED INFORMATICS, Innsbruck, Austria, 2003.
Barchett D. and Campion, E., Mix fleet vehicle routing problem — An application of Tabu search in the grocery delivery industry; 2002., Disponible en: http://www.mang.canterbury.ac.nz/courseinfo/msci/msci480/WebPage.htm, Consultado en: Febrero de 2005.
Bianchi, L., Metaheuristics for the Vehicle Routing Problem with Stochastic Demands; S/F., Disponible en: http://www.idsia.ch/idsiareport/IDSIA-06-04.pdf, Consultado en: Febrero de 2005.
Bramel, J. and Simchi-Levi, D., A location based heuristic for general routing problems., Operations Research, Vol. 43, 1995, pp. 649-660.
Bräysy, O., Genetic Algorithms for the Vehicle Routing Problem with Time Windows. 2001., Disponible en: osiris.tuwien.ac.at/~wgarn/VehicleRouting/Braysy.pdf, Consultado en: Febrero de 2005.
Charlotte, J. andy Goetschalckx, M., The vehicle routing problem with backhauls: properties and solution algorithms. Scholl of industrial and systems engineering - Georgia institute of technology., Copyright 1992 — 1998. Disponible en: http://www.isye.gatech.edu/people/taculty/Marc_Goetschalckx/cali/Lineback/Vehicle%20Routing%20Problem%20with%20Backhauls.pdf, Consultado en Febrero de 2005.
Dethloff, J., Relation between vehicle routing problems: an insertion heuristic for the vehicle routing problem with simultaneous delivery and pick-up applied to the vehicle routing problem with backhauls., Journal of the Operational Research Society, 2002, Consultado en: Febrero de 2005.
Fisher, M., and Jaikumur, R., A generalized assignment heuristic for the vehicle routing problem., Networks 11, 1981, pp.109-124.
Francis, P, Smilowitz, K. and Tzur, M., The period vehicle routing problem with service choice; 2004., Disponible en: http://www.iems.northwestern.edu/images/PDF/WP_04_005.pdf, Consultado en: Febrero 2005.
Gambardella, L.M., Taillard, E. and Agazzi, G., MACS-VRPTW: A Multiple Ant Colony System for Vehicle Routing Problems with Time Windows., New Ideas in Optimization, Disponible en: http://www.idsia.ch. Consultado en: Febrero 2005, McGraw-Hill, 1999.
García, A., Optimización de rutas, seguridad en el transporte y sistemas GIS. 2000., Disponible en: http://www.imac.unavarra.es/SEMAOL/Ponencias/04_ Alejandro G_del_Valle.pdf, Consultado en: Febrero de 2005.
Gendreau, M., Hertz, A. and Laporte, G., A tabu search heuristic for the vehicle routing problem., Management Science 40, 1994, pp. 1276-1290.
Gendreau, M., Hertz, A., Laporte, G. and Stan, M.., A generalized insertion heuristic for the traveling salesman problem with time windows., Operations Research, Vol. 43, 1998, pp. 330-335.
Guerrero, L., y Osorio, L., La localización de instalaciones como decisión estratégica de la logística: un acercamiento al estado del arte., Trabajo de grado ingeniería industrial, Universidad Nacional de Colombia, Manizales, Marzo, 2003.
Halse, K., Modeling and Solving Complex Vehicle Routing Problems., PhD Thesis, Institute of Mathematical Statistics and Operations Research, Technical University of Denmark, Lyngby, 1992.
Hermosilla, A. y Barán, B., Comparación de un sistema de colonias de hormigas y una estrategia evolutiva para un Problema Multiobjetivo de Ruteo de Vehículos con Ventanas de Tiempo. s/f., Disponible en: http://www.cnc.una.py/invest/paper2/augCLEI.pdf. Consultado en: Febrero de 2005.
Hurkens, C., WHIZZKIDS ‘96 1997., Disponible en: http://www.win.tue.nl/whizzkids/1996/, Consultado en: Febrero de 2005.
Laporte, G., The vehicle routing problem: an overview of exact and approximate algorithms., European Journal of Operational Research, 59, 1992, pp. 345-358.
Lee, Ch., Epelman, M., Chelsea, C. and Bozer Y., A Shortest Path Approach to the Multiple-Vehicle Routing Problem with Split Pick-Ups, 2002., Disponible en: http://osiris.tuwien.ac.at/~wgarn/VehicleRouting/myrpsp_ts.pdft, Consultado en: Febrero de 2005.
Liu, F and Shen, S., A Method for Vehicle Routing Problem with Multiple Vehicle Types and Time Windows. 1999., Disponible en: http://nrstic.gov.tw/ejournal/ProceedingA/v23n4/526-536.pdf. Consultado en: Febrero de 2005, Proc. Natl. Sci. Counc. ROC(A), Vol. 23, No. 4, 1999.
Louis, S., Yin, X. and Yuan, Z., Multiple Vehicle Routing with Time Windows Using Genetic Algorithms., Memorias de Proceedings of the Congress of Evolutionary Computation, 1999, pp. 1804-1808.
Machado, P, Tavares, J., Pereira, F and Costa, E., Vehicle Routing Problem: Doing it the Evolutionary Way. 2000., Disponible en: http://osiris.tuwien.ac.at/~wgarn/VehicleRouting/GECCO02_VRPCoEvo.pdf. Consultado en: Febrero de 2005.
Machado, P, Pereira, F, Tavares, J. and Costa, E., GVR: a New Genetic Representation for the Vehicle Routing Problem. 2002., Disponible en: http://neo.lcc.uma.es/radiaeb/WebVRP/data/articles/vrp_aics2002.pdf, Consultado en: Febrero de 2005.
Machado, P, Tavares, J., Pereira, F and Costa, E., Crossover and Diversity: A Study about GVR. 2003 (a)., Memorias de Proceedings of the Analysis and Design of Representations and Operators (ADoRo’2003) a bird-of-a-feather workshop at the 2003 Genetic and Evolutionary Computation Conference (GECCO-2003), Chicago, Illinois, USA, 12-16 July, 2003. Disponible en: http://cisuc.dei.uc.pt/ecos /view_pub.php2id_p=65. Consultado en: Febrero de 2005.
Machado, P, Tavares, J., Pereira, F and Costa, E., On the Influence of GVR in Vehicle Routing. 2003 (b)., Memorias de Proceedings of the 2003 ACM Symposium On Applied Computing (SAC 2003) - Evolutionary Computation and Optimization Track, pp.753-758, Melbourne, Florida, USA, 9-13 March, 2003. Disponible en: http://cisuc.dei.uc.pt/ecos/view_pub.php?id_p=65. Consultado en: Febrero de 2005
Medaglia, A., Combinatoria para Logística., Coloquio en Optimización Combinatoria Sesión Avanzada, Universidad de los Andes, marzo de 2005.
Min, H., The Multiple Vehicle Routing Problem with Simultaneous Delivery and Pick-Up Points., Transportation Research, vol.23-A, 1989, pp. 377-386.
Olivera, A., Heurísticas para Problemas de Ruteo de Vehículos., Instituto de Computación, Facultad de Ingeniería. Universidad de la Republica, Montevideo, Uruguay. 2004. Disponible en: http://www.fing.edu.uy/inco/pedeciba/bibliote/reptec/TRO408.pdf. Consultado en Febrero de 2005.
Rego, C., Node Ejection Chains for the Vehicle Routing Problem: Sequential and Parallel Algorithms. (s/f)., Disponible en: http://hces.bus.olemiss.edu/reports/hces0201.pdf. Consultado en: febrero de 2005.
Restori M., An Application of VRP Algorithms with Original Modifications. s/f., Disponible en: http://eal.asu.edu/Papers%5CMel_VRP_studentTech.pdf, Consultado en: Febrero 2005
Shaw, P, Using Constraint Programming and Local Search Methods to Solve Vehicle Routing Problems., Memorias de Proceedings of the Fourth International Conference on Principles and Practice of Constraint Programming (CP '98), M. Maher and J. Puget (eds.), 1998, pp. 417-431.
Schroeder, R., Administración de operaciones, toma de decisiones en la función de operaciones., 3°. Ed., Editorial Mc Graw Hill, México, 1992.
Tansini, L., Urquhart, M. and Viera, O., Comparing assignment algorithms for the Multi-Depot VRP; s/f; Diponible en: http://www.fing.edu.uy/inco/pedeciba/bibliote/reptec/TRO108.pdf. Consultado en: Febrero 2005
Taha, H., Investigación de Operaciones., 5°. Edición, alfaomega, Grupo Editor México, 1995.
Thompson, P and Orlin, J., The Theory of Cyclic Transfers. 1989., Disponible en: http://web.mit.edu/jorlin/www/oldpapersfolder/cyclic_tranfers.pdf. Consultado en Febrero de 2005.
Toth, P and Vigo, D., An Overview of Vehicle Routing Problems., Monographs on Discrete Mathematics and Applications. In: The Vehicle Routing Problem. SIAM, 2000, pp. 1-26.
Vacic, V., Vehicle Routing Problem with Time Windows; 2002., Disponible en: http://www.bridgeport.edu/sed/projects/cs399/vacic/vrptw.html. Consultado en: Febrero 2005
Volkan, A., A GA Based Meta-Heuristic for the Capacitated Vehicle Routing Problem with Simultaneous Pick-up and Deliveries. 2005., Disponible en: http://www.msie.sabanciuniv.edu/thesis/arif_volkan_vural.ppt. Consultado en: Marzo 2005
Wendt, O. and König, W., Cooperative Simulated Annealing: How much cooperation is enough?. s/t., Disponible en: http://www.wiiw.de/publikationen/Cooperative SimulatedAnnealing48.pdf. Consultado en: Febrero de 2005
Zhu, K., A new genetic algorithm for VRPTW., Presented at IC-Al 2000, Las Vegas, USA, 2000.
Dimensions
PlumX
Article abstract page views
Downloads
How to Cite
License
Copyright (c) 2006 Guillermo González Vargas, Felipe González Aristizábal
This work is licensed under a Creative Commons Attribution 4.0 International License.
The authors or holders of the copyright for each article hereby confer exclusive, limited and free authorization on the Universidad Nacional de Colombia's journal Ingeniería e Investigación concerning the aforementioned article which, once it has been evaluated and approved, will be submitted for publication, in line with the following items:
1. The version which has been corrected according to the evaluators' suggestions will be remitted and it will be made clear whether the aforementioned article is an unedited document regarding which the rights to be authorized are held and total responsibility will be assumed by the authors for the content of the work being submitted to Ingeniería e Investigación, the Universidad Nacional de Colombia and third-parties;
2. The authorization conferred on the journal will come into force from the date on which it is included in the respective volume and issue of Ingeniería e Investigación in the Open Journal Systems and on the journal's main page (https://revistas.unal.edu.co/index.php/ingeinv), as well as in different databases and indices in which the publication is indexed;
3. The authors authorize the Universidad Nacional de Colombia's journal Ingeniería e Investigación to publish the document in whatever required format (printed, digital, electronic or whatsoever known or yet to be discovered form) and authorize Ingeniería e Investigación to include the work in any indices and/or search engines deemed necessary for promoting its diffusion;
4. The authors accept that such authorization is given free of charge and they, therefore, waive any right to receive remuneration from the publication, distribution, public communication and any use whatsoever referred to in the terms of this authorization.
