HH-VRP: Una hiperheurística que resuelve el problema de la asignación dinámica de rutas a vehículos

Tesis (Magister en Ciencias de la Ingeniería Informática) -- Prof. guía: María Cristina Riff Rojas, prof. corref.: Carlos Castro Valdebenito

h. 197 - 203

[Resumen del autor]

En esta tesis de magíster se presenta un enfoque basado en hiperheurísticas para resolver dos ti<U+00AD>pos de problemas: asignación de rutas a vehículos (VRP) y asignación dinámica de rutas a vehículos (DVRP). Las hiperheurísticas, que se han introducido y aplicado exitosamente en diferentes problemas, son básicamente (meta) heurísticas que eligen (meta) heurísticas (Burke, 2003). En los marcos diseñados, se utilizan heurísticas sencillas, pero eficientes, que han sido propuestas en el estado del arte del problema. La investigación tiene por objetivo evaluar si las hiperheurísticas pueden ser un buen método para resolver problemas de asignación de rutas a vehículos. La evaluación considera dos criterios: la calidad de la solución encontrada y el desempeño del algoritmo. Para resolver el problema de asignación de rutas a vehículos, se presenta un diseño de hiper<U+00AD>heurísticas basado en algoritmos evolutivos. En este enfoque, se utilizan dos mecanismos para sintonizar parámetros: sintonización estándar y sintonización mediante REVAC (Nannen and Eiben, 2007); este último ha sido propuesto recientemente para calibrar parámetros. El diseño anterior es extendido y adaptado para el problema de asignación dinámica de rutas a vehículos. Este nuevo enfoque, también basado en algoritmos evolutivos, enfrenta y resuelve el dinamismo del problema a través de la resolución parcial de varios problemas estáticos que se actualizan y cambian a lo largo del tiempo (Kilby et al, 1998). A diferencia del enfoque anterior, el marco dinámico incorpora un mecanismo interno más sencillo para controlar, de forma dinámica, el uso de las heurísticas. El desempeño de los marcos se evalúa y compara con las instancias estándares de Christofides (Chris-tofides et al., 1979), Taillard (Taillard, 1993; Rochat and Taillard, 1995) y Fisher (Fisher, 1994), para el caso estático, y con las instancias de Kilby (Kilby et al., 1998) en el caso dinámico. Los resultados obtenidos por los marcos basados en hiperheurísticas son muy alentadores, ya que son capaces de mejorar los resultados conseguidos por las heurísticas de bajo nivel y por algunas técnicas especializadas para el problema. Específicamente, el marco dinámico fue capaz de lograr resultados muy competitivos que superaron a la mayoría de las técnicas del estado del arte. El éxito de la técnica, en ambos problemas, se atribuye a la simplicidad y a la capacidad de adaptación de la hiperheurística para buscar distintas secuencias de heurísticas que permiten enfrentar tanto el dinamismo como los cambios de estado que presenta el problema. Por lo tanto, se concluye que la colaboración entre heurísticas es una buena vía para resolver problemas de asignación de rutas a vehículos.

2