untitled

Enfoques de programación entera para el Problema del Viajante de Comercio con costos en función del tiempo


Integer programming approaches to the Time Dependent Travelling Salesman Problem

Miranda Bront, Juan José

Director(a):
Méndez Díaz, Isabel - Zabala, Paula
 
Institución otorgante:
Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Fecha:
2012
Tipo de documento: 
Tesis Doctoral
 
Formato:
text; pdf
Idioma:
Inglés
Temas:
Computación / Optimización Combinatoria - PROBLEMA DEL VIAJANTE DE COMERCIO DEPENDIENTE DEL TIEMPO - OPTIMIZACION COMBINATORIA - PROGRAMACION LINEAL ENTERA MIXTA - ALGORITMOS BRANCH AND CUT - DESIGUALDADES VALIDAS - VENTANAS DE TIEMPO - CAMINOS INFACTIBLES
Descripción:
El Problema del Viajante de Comercio Dependiente del Tiempo (PVCDT) es una generalización del clásico Problema del Viajante de Comercio (PVC) en el cual se busca un circuito de costo mínimo que recorra todos los clientes, donde los tiempos (o costos) de viaje entre ellos no son constantes y pueden variar dependiendo de diversos factores. Una de las motivaciones para considerar la dependencia del tiempo es que nos permite tener una mejor aproximación a muchas aplicaciones de la vida real, dentro de la industria y en el sector de servicios. En la literatura relacionada, existen distintas versiones del PVCDT que consideran que las variaciones se producen por diversos motivos y sobre distintos parámetros. Algunas de ellas estipulan que las variaciones se producen sobre los tiempos (y/o costos) de viaje mientras que otras asumen que las variaciones se producen sobre la velocidad de viaje. Más aún, para el primer caso, una variante asume que el tiempo de viaje depende de la posición del arco en el circuito mientras que otra asume que depende del instante en el que se comienza a atravesar el arco. Al igual que el PVC, el PVCDT pertence a la clase NP-Difícil y por lo tanto no se conoce un algoritmo que encuentre una solución en tiempo polinomial. En esta tesis abordamos dos de las variantes antes mencionadas mediante la formulación de modelos de Programación Lineal Entera. Para cada formulación, realizamos un estudio teórico enfocado en derivar familias de desigualdades válidas que exploten las características particulares del problema. En particular, para una de las variantes, demostramos que varias de ellas definen facetas del poliedro. Desde el punto de vista práctico, para las variantes consideradas desarrollamos algoritmos exactos de tipo Branch and Cut que incorporan estas familias de desigualdades válidas y los evaluamos considerando instancias propuestas en la literatura, obteniendo buenos resultados que muestran que ambos enfoques son factibles para ser utilizados en la práctica.
Identificador:
http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_5113_MirandaBront
Identificador único:
http://repositoriouba.sisbi.uba.ar/h/4350
Derechos:
info:eu-repo/semantics/openAccess
http://creativecommons.org/licenses/by-nc-nd/2.5/ar/
Licencia de uso:
Licencia Creative Commons


Cita bibliográfica:

Miranda Bront, Juan José  (2012).     Enfoques de programación entera para el Problema del Viajante de Comercio con costos en función del tiempo.  (Tesis Doctoral).    Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires.    [consultado:  ] Disponible en el Repositorio Digital Institucional de la Universidad de Buenos Aires:  <http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_5113_MirandaBront>