Tratamiento eficiente del problema del reparador viajero con ventanas de tiempo
Oscar Yani Miguel Pilar
|
Texto completo de la Tesis 
Video del evento 
Resumen
El problema del reparador viajero con ventanas de tiempo (TRPTW por sus siglas en inglés: Traveling Repairman Problem with Time Windows) es un problema de calendarización de tareas, el cual es importante estudiar debido a su vasta aplicación en áreas como manufactura, logística, transportación o turismo. Este problema surge al agregar restricciones de tiempo al problema del agente viajero. En este trabajo se estudia el caso especial de TRPTW en el cual las ventanas de tiempo de las tareas son de longitud unitaria. Se presentan algunos problemas relacionados y se analizan experimentalmente dos algoritmos de la literatura que ofrecen soluciones aproximadas para TRPTW. Además, se propone un enfoque de programación lineal entera para resolver TRPTW en el mismo caso (ventanas de tiempo unitarias). Se expone un análisis experimental de este enfoque de programación lineal entera. El modelo se extiende para soportar el caso en que las ventanas de tiempo tienen longitud arbitraria. Las implementaciones de esta tesis conforman una plataforma computacional que resuelve instancias de TRPTW. La plataforma implementa dos algoritmos de aproximación de la literatura así como el enfoque de programación lineal entera que hemos propuesto.
Abstract
The Traveling Repairman Problem with Time Windows (TRPTW) is a task scheduling problem that has become important due to its wide application in areas such as manufacturing, logistics, transportation, or tourism. This problem arises when adding time restrictions to the traveling salesman problem. In this work, we study the special case of TRPTW in which time windows have unit length. We introduce some related problems and analyze two very well known algorithms to approximate TRPTW. A new integer linear programming approach to solve TRPTW in this special case (unit time windows) is proposed. An experimental analysis of this integer linear programming approach is exposed. Later, this approach is extended to support the case of TRPTW with time windows for arbitrary length. Our implementations establish a computational platform to solve instances of TRPTW. They include the two algorithms analyzed as well as our new integer linear approach.
