Hiperheurísticas a través de programación genética para la resolución de problemas de ruteo de vehículos-Edición Única

Abstract

El problema de ruteo de vehículos, o VRP por sus siglas en inglés, (Vehicle Routing Problem) puede ser descrito en su forma más sencilla como una flota de vehículos con capacidades uniformes que tiene que satisfacer la demanda de un grupo de clientes a través de un conjunto de rutas que empiezan y terminan en un almacén común y que representan el menor costo posible. Como consecuencia de los altos niveles actuales de congestión vehicular, de los fuertes consumos de energía de los vehículos de carga, así como del impacto negativo que ´estos últimos tienen en el medio ambiente, en los últimos años ha aumentado el interés de desarrollar técnicas de optimización que sean eficientes en la resolución de una gran variedad de problemas VRP. Sin embargo, debido a la naturaleza NP-difícil del VRP, no es factible resolver instancias de tamaño grande utilizando técnicas exactas sino que la mayoría de los algoritmos de solución para este problema están basados en el uso de heurísticas y metaheurísticas. Estas últimas técnicas no han sido del todo exitosas ya que las heurísticas entregan frecuentemente resultados de baja calidad; mientras que las metaheurísticas requieren mucho tiempo de cómputo, así como un alto nivel de especialización en grupos de instancias para la obtención de buenos resultados. Este trabajo de tesis aborda el problema de VRP con vehículos de capacidad fija utilizando para su resolución un nuevo enfoque basado en un algoritmo de hiperheurísticas con programación genética como mecanismo de aprendizaje teniendo un conjunto de terminales formada por heurísticas de mejora y un conjunto de funciones compuesto por ciclos, condicionales y operadores auxiliares. La propuesta para el uso de este algoritmo se basa en que el concepto de hiperheurísticas ha dado buenos resultados en otro tipo de problemas como problemas de horario y de empaquetamiento. Por otra parte, en que la programación genética es una técnica que puede dar mayor expresividad a la administración de las heurísticas simples que solamente el manejar para éstas un arreglo en forma de cadena o tira. El uso del algoritmo propuesto obtuvo de manera consistente resultados bastante cercanos al mejor valor reportado, encontrando para dos instancias el valor óptimo conocido. Otra de las ventajas que se observaron en esta técnica fueron los cortos tiempos de cómputo, la repetibilidad y el grado de abstracción de la plataforma propuesta ya que generalizar su uso a otro tipo de problemas VRP no implicaría mucho tiempo de desarrollo. De lo anterior se prueba la hipótesis planteada y se abre un nuevo camino de investigación para atacar problema de optimización de tipo NP-completos.