Aplicación de la Metaheurística de Recocido Simulado a un Problema de Ruteo Dinámico de Vehículos con Ventanas de Tiempo-Edición Única

Abstract

Este trabajo de tesis estudia el problema de Ruteo Dinámico de Vehículos con Ventanas de Tiempo, conocido por sus siglas en inglés como DVRPTW, así como la realización de una plataforma la cual hace posible la aplicación de la metaheurística de recocido simulado para su solución. La versión estática de este problema, donde las demandas de los clientes se conocen por anticipado, se le considera como NP, ya que sólo es posible obtener una solución óptima en instancias de problemas relativamente pequeñas, o por lo menos en un tiempo razonable y con recursos computacionales convencionales, por lo que el uso de heurísticas para su solución se le considera la manera más adecuada de tratar dichos problemas.Se desarrolla una plataforma que pueda manejar eventos generados por los clientes los cuales no se tenían considerados. Primeramente se define el problema estático,presentando diferentes enfoques de solución que se han tratado en la literatura. Después se hace la introducción de la versión dinámica, donde se muestra que es una extensión del problema estático. Por último se explica nuestra plataforma de solución, y se hacen experimentos aplicándolos a una versión extendida de las instancias de Solomon basados en los problemas R1, los cuales tienen una ventana de tiempo angosta. La plataforma demuestra ser una manera efectiva de distribuir las demandas de los clientes en la flota de vehículos, cumpliendo con sus respectivas ventanas de tiempo, y a la vez minimizando el uso de vehículos y la distancia total recorrida.