En este artículo se presenta una metaheurística híbrida denominada Genetic Clustering and Tabu Routing, con la cual se soluciona un problema de ruteo de vehículos a través de la metodología de dos fases: clusterizar primero - rutear después. Los resultados son comparados con los obtenidos al aplicar las técnicas metaheurística y heurística, presentadas en la parte 2 de esta serie de artículos, encontrando mejoras promedio del 23% y 9.1% respectivamente.
Introducción
Este, es el tercer artículo de una serie que se inició dos números atrás en esta misma revista (González-Vargas y González, 2006, 2007) y que se ha encargado de abordar el Problema de ruteo de vehículos (VRP), en el marco de la decisión de localización de una empresa manufacturera que tiene como objetivo minimizar la distancia total a recorrer para abastecer a todos sus clientes.
En este artículo se encuentra la descripción de una metaheurística hibrida diseñada para resolver el problema de ruteo en dos fases: primero clusterizar y luego rutear, la técnica propuesta por los autores ha sido denominada Genetic Clustering and Tabu Routing, e intenta responder a la necesidad de lograr una correcta asignación de nodos por vehículo para facilitar de esta forma, el ruteo y por ende alcanzar una baja distancia total a recorrer, tal como se concluyó en el artículo anterior.
Teniendo en cuenta la importancia que representa la metaheurística de Búsqueda Tabú en este artículo y dado que esta temática no había sido expuesta hasta el momento en esta serie de artículos, los autores realizan en las siguientes líneas, una breve descripción de la misma, para posteriormente presentar al lector el algoritmo híbrido desarrollado, exponiendo los operadores utilizados, los experimentos realizados y los resultados obtenidos. El artículo culmina con la presentación de algunas conclusiones y la propuesta de algunos trabajos futuros que pueden ser desarrollados a partir del trabajo presentado.
Una breve introducción a la búsqueda tabú
La búsqueda tabú (Tabu search: TS) es una extensión de los métodos clásicos de búsqueda local, y según Gendreau (2003) es la técnica más efectiva para afrontar problemas combinatorios difíciles. Esta metaheurística fue desarrollada en 1986 por Fred Glover como alternativa para superar los principales problemas a los que se enfrentaban los algoritmos de búsqueda clásicos: el ciclaje, que se evita al implementar la memoria en el algoritmo, y el estancamiento en óptimos locales lo que se supera gracias a la aceptación de soluciones no mejorantes. Según Skorin-Kapov (1990), un desarrollo similar al de Glover, el denominado steepest ascent/mildest descent fue logrado de manera independiente por Hansen en 1986, sin embargo la diferencia básica radica, según Gendrau (2003) en que TS no es una heurística en sí misma, sino una metaheurística que se encarga de guiar y controlar heurísticas internas.
Esta es una versión de prueba de citación de documentos de la Biblioteca Virtual Pro. Puede contener errores. Lo invitamos a consultar los manuales de citación de las respectivas fuentes.
Artículo:
Evaluación de hidrogeles para aplicaciones agroforestales
Guía:
Guía para buenas practicas en el control de la corrosión : corrosión bimetálica
Artículo:
Desarrollos recientes en degradación fotocatalítica ambiental de contaminantes orgánicos : el caso de las nanopartículas de dióxido de titanio una revisión
Artículo:
Evaluación de métodos cualitativos de higiene inversa para control de riesgo químico por exposición
Artículo:
Deshidratación catalítica de etanol a etileno sobre HMOR y HZSM-5 modificada con hierro y cobre
Showroom:
Columna de adsorción de lecho fijo
Artículo:
Implementación de una propuesta de aprendizaje significativo de la cinemática a través de la resolución de problemas
Artículo:
Calidad sanitaria sostenible y satisfacción laboral a través de la cultura organizativa: Enfoques y resultados
Artículo:
Fibras textiles