Metaheurísticas aplicadas al ruteo de vehículos. Un caso de estudio. Parte 3: Genetic Clustering and Tabu Routing

Metaheuristics applied to vehicle routing. A case study. Part 3: Genetic Clustering and Tabu Routing

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.