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:
Remoción de colorantes sintéticos mediante el proceso Fenton heterogéneo usando Fe2O3 soportado en carbón activado obtenido a partir de residuos de rosas
Video:
Teoría de la combustión y aplicaciones en dinámica de fluidos computacional (Pitsch). Día 1, parte 2
Memoria:
Evaluación de los líquidos iónicos como disolventes a escala de proceso: Contribuciones de la simulación de procesos a la investigación fundamental
Artículo:
Resistividad eléctrica y Efecto Hall en películas delgadas de ZnO depositadas por evaporación reactiva
Artículo:
Conversión de CO2 mediante catálisis homogénea redox estimulada por luz visible
Artículo:
Creación de empresas y estrategia : reflexiones desde el enfoque de recursos
Artículo:
La gestión de las relaciones con los clientes como característica de la alta rentabilidad empresarial
Artículo:
Los web services como herramienta generadora de valor en las organizaciones
Libro:
Ergonomía en los sistemas de trabajo