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

Metaheuristics applied to vehicle routing. A case study. Part 2: genetic algorithm, compared to a heuristics solution

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.

Introducción

El presente artículo es el segundo de una serie de tres que fue iniciada en el número anterior de la presente revista, en este se presentan dos metodologías de solución diferentes al problema de ruteo de vehículos (VRP) que surge de la necesidad que una empresa manufacturera presenta para decidir la localización de una bodega de producto terminado desde la cual satisfacer la demanda de sus clientes  (la descripción del problema y su formulación matemática se encuentran en el primer artículo).

El artículo comienza con una breve descripción bibliográfica de los conceptos de heurística y metaheurística. En    las siguientes líneas los autores presentan el concepto de algoritmo genético, metaheurística ampliamente utilizada en la solución de este tipo de problemas y se ilustra la metodología implementada describiendo de manera detallada los operadores utilizados; adicionalmente se exhiben los resultados obtenidos en los diferentes experimentos realizados. Posteriormente se aborda el problema limitando  el espacio de soluciones a través de la utilización de la técnica de clusterizar primero rutear después  (cluster firts - routen second) (Olivera, 2004), aplicando para ello dos heurísticas: el barrido para clusterizar y la búsqueda local para rutear; igual que en el caso anterior, se registran los resultados.

Finalmente, los autores comparan los resultados logrados por medio de las diferentes técnicas y con base en ello se exponen algunas conclusiones.

Heurísticas y metaheurísticas

El problema de ruteo de vehículos que compete a esta serie de artículos es de naturaleza combinatoria, tal tipo de problemas es formulado generalmente como programas de optimización entera, los cuales a su vez pueden ser reformulados o acotados a través de la exploración de conjuntos de soluciones factibles (Crainic y Toulouse, 2003). Esta exploración se realiza por medio de la enumeración implícita, para lo cual han surgido diferentes métodos tales como el Branch and Bound, Branch and cut, Branch and price; sin embargo, en muchos problemas del "mundo real" dichos métodos fallan por diferentes motivos, entre los que se pueden nombrar los espacios de búsqueda demasiado amplios, o bien, demasiado complejos debido a las restricciones de los problemas (Burke et al., 2003).