Un algoritmo para resolver el problema del vendedor viajero con ventanas de tiempo para servicios postales.

Abstract

Esta memoria de título tiene como objetivo estudiar el problema del vendedor viajero con ventanas de tiempo aplicado al caso de los servicios postales, y elaborar una metaheurística para resolver el problema. Este problema es una variante del problema clásico del vendedor viajero que consiste en minimizar el costo de una ruta hamiltoniana con una restricción adicional, que consiste en la existencia de ventanas de tiempo para cada uno de los destinos en la ruta, generándose un aumento en la dificultad en la resolución. Esta dificultad se debe a que al llegar a un destino de forma prematura, se genera un aumento en el costo de la ruta y además, el arribo posterior al cierre de la ventana de tiempo produce una ruta no factible. En los servicios postales por lo general existen dos tipos de entregas, la paquetería y las cartas, para ambos casos la industria busca optimizar las rutas de entrega para reducir los costos operativos y de mano de obra. Además, existen muchos casos en los que el cliente tiene un tiempo acotado para recibir su entrega. Para resolver este problema se propone un algoritmo basado en una búsqueda local iterada. Este algoritmo trabaja con penalizaciones, perturbaciones y búsquedas locales. Los resultados de la metaheurística muestran buenos rendimientos hasta las instancias de 60 nodos.