Metaheuristics applied to vehicle routing. A case study. Part 2: genetic algorithm, compared to a heuristics solution
Metaheurísticas aplicadas al ruteo de vehículos. Un caso de estudio. Parte 2: algoritmo genético, comparación con una solución heurística
DOI:
https://doi.org/10.15446/ing.investig.v27n1.14795Keywords:
vehicle-routing, genetic algorithm, sweep, local search (en)ruteo de vehículos, algoritmo genético, barrido, búsqueda local (es)
Downloads
This paper presents a solution to a vehicle-routing problem by using two different techniques. In the first instance, a genetic algorithm was applied (different experiments were done); later on the cluster first-route second methodology was used via heuristic sweep and local search, respectively. The results of the different techniques were then compared.
Este artículo presenta la solución a un problema de ruteo de vehículos a través de dos técnicas diferentes; en primera instancia se aplica un algoritmo genético y se realizan diferentes experimentos, posteriormente se utiliza la metodología de clusterizar primero y rutear después a través de las heurísticas de barrido y búsqueda local, respectivamente. Los resultados de las diferentes técnicas son comparados.
References
Ahuja, R., Magnanti, T. and Orlin, J., Network flows: theory, algorithms, and applications., Englewood Cliffs, New Jersey: Prentice Hall, 1993.
Anónimo S/F., Network., Disponible en: http://www.cs.tcd.ie/courses/baict/bass/4ict5/Networks2004.pdf. Consultado en Marzo de 2004.
Burke, E., Kendall, G., Newall, J., Hart, E., Ross, P. and Schulenburg, S., Hyper-heuristics: an emerging direction in modern search technology., En: Glover, F. y Kochenberger, G. (Eds.). Handbook of metaheuristics. Kluwer academic publisher, 2003.
Clarke, G. and Wright W., Scheduling of vehicles from a central depot to a number of delivery points., Operations Research, 12, 1964, pp.568-581. DOI: https://doi.org/10.1287/opre.12.4.568
Crainic, T. and Toulouse, M., Parallel strategies for meta-heuristics., En: Glover, F. y Kochen berger, G. (Eds.), Handbook of metaheuristics, Kluwer academic publisher, 2003.
Goldberg, D.E., Genetic algorithms in search, optimization and machine learning., Addison- Wesley, 1989.
LeBlanc, L., Shtub, A., and Anandalingam, A., Formulating and solving production planning problems., En: European Journal of Operational Research, No. 112, 1999. DOI: https://doi.org/10.1016/S0377-2217(97)00394-9
Lin, S., Computer solutions of traveling salesman problem., Bell Systems Tech. J., 44, 1965. DOI: https://doi.org/10.1002/j.1538-7305.1965.tb04146.x
Lourenço, H., Martin, O. and Stützle, T., Iterated local search., En: Glover, F. and Kochenberger, G. (Eds.), Handbook of metaheuristics, Kluwer academic publisher, 2003.
Martí, R. y Moreno, M., Métodos Multiarranque. Inteligencia Artificial., Revista Iberoamericana de Inteligencia Artificial. No.19, 2003, pp. 49-60.
Medaglia, A., Combinatoria para Logística., Coloquio en Optimización Combinatoria Sesión Avanzada, Universidad de los Andes, marzo, 2005.
Melián, B., Moreno, J. y Moreno, M., Metaheurísticas: una visión global. Inteligencia Artificial., Revista Iberoamericana de Inteligencia Artificial, No.19, 2003, pp. 7-28. DOI: https://doi.org/10.4114/ia.v7i19.713
Olivera, A., Heurísticas para Problemas de Ruteo de Vehículos., Instituto de Computación, Facultad de Ingeniería. Universidad de la República, Montevideo, Uruguay. 2004, Disponible en: https://www.fing.edu.uy/inco/pedeciba/bibliote/reptec/TR0408.pdf. Consultado en Febrero de 2005.
Reeves, C., Genetic algorithms., En: Glover, F. and Kochenberger, G. (Ed.), Handbook of metaheuristics, Kluwer academic publisher, 2003.
Torres, J. F., Problemas de Ruteo de Vehículos., En: Modelos de Sistemas Logísticos, Maestría en Ingeniería Industrial, Universidad de los Andes, 2005.
Voudouris, C. and Tsang, E., Guided local search., En: Glover, F. and Kochenberger, G. (Eds.), Handbook of metaheuristics, Kluwer academic publisher, 2003.
Zhou, G., Min, H. and Gen, M., The balanced allocation of customer to multiple distribution centers in the supply chain network: a genetic algorithm approach., En: Computer and Industrial Engineering, No. 43, 2002. DOI: https://doi.org/10.1016/S0360-8352(02)00067-0
How to Cite
APA
ACM
ACS
ABNT
Chicago
Harvard
IEEE
MLA
Turabian
Vancouver
Download Citation
License
Copyright (c) 2007 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.