Enfoques de programación entera para el problema del viajante de comercio con costos en función del tiempo

Mostrar todas las versiones(3)

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 v...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Miranda Bront, Juan José
Formato: Tesis Doctoral
Lenguaje:Inglés
Publicado: 2012
Materias:
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
TIME DEPENDENT TRAVELLING SALESMAN PROBLEM
COMBINATORIAL OPTIMIZATION
MIXED INTEGER LINEAR PROGRAMMING
BRANCH AND CUT ALGORITHM
VALID INEQUALITIES
TIME WINDOWS
INFEASIBLE PATHS
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n5113_MirandaBront
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:tesis_n5113_MirandaBront
record_format dspace
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Inglés
orig_language_str_mv Inglés
topic 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
TIME DEPENDENT TRAVELLING SALESMAN PROBLEM
COMBINATORIAL OPTIMIZATION
MIXED INTEGER LINEAR PROGRAMMING
BRANCH AND CUT ALGORITHM
VALID INEQUALITIES
TIME WINDOWS
INFEASIBLE PATHS
spellingShingle 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
TIME DEPENDENT TRAVELLING SALESMAN PROBLEM
COMBINATORIAL OPTIMIZATION
MIXED INTEGER LINEAR PROGRAMMING
BRANCH AND CUT ALGORITHM
VALID INEQUALITIES
TIME WINDOWS
INFEASIBLE PATHS
Miranda Bront, Juan José
Enfoques de programación entera para el problema del viajante de comercio con costos en función del tiempo
topic_facet 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
TIME DEPENDENT TRAVELLING SALESMAN PROBLEM
COMBINATORIAL OPTIMIZATION
MIXED INTEGER LINEAR PROGRAMMING
BRANCH AND CUT ALGORITHM
VALID INEQUALITIES
TIME WINDOWS
INFEASIBLE PATHS
description 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.
format Tesis Doctoral
author Miranda Bront, Juan José
author_facet Miranda Bront, Juan José
author_sort Miranda Bront, Juan José
title Enfoques de programación entera para el problema del viajante de comercio con costos en función del tiempo
title_short Enfoques de programación entera para el problema del viajante de comercio con costos en función del tiempo
title_full Enfoques de programación entera para el problema del viajante de comercio con costos en función del tiempo
title_fullStr Enfoques de programación entera para el problema del viajante de comercio con costos en función del tiempo
title_full_unstemmed Enfoques de programación entera para el problema del viajante de comercio con costos en función del tiempo
title_sort enfoques de programación entera para el problema del viajante de comercio con costos en función del tiempo
publishDate 2012
url https://hdl.handle.net/20.500.12110/tesis_n5113_MirandaBront
work_keys_str_mv AT mirandabrontjuanjose enfoquesdeprogramacionenteraparaelproblemadelviajantedecomercioconcostosenfunciondeltiempo
AT mirandabrontjuanjose integerprogrammingapproachestothetimedependenttravellingsalesmanproblem
_version_ 1807320359519649792
spelling todo:tesis_n5113_MirandaBront2023-10-03T12:53:50Z 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é 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 TIME DEPENDENT TRAVELLING SALESMAN PROBLEM COMBINATORIAL OPTIMIZATION MIXED INTEGER LINEAR PROGRAMMING BRANCH AND CUT ALGORITHM VALID INEQUALITIES TIME WINDOWS INFEASIBLE PATHS 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. The Time Dependent Travelling Salesman Problem (TDTSP) is a generalization of the well known Travelling Salesman Problem (TSP) in which we look for a minimum cost tour that visits each client exactly once where the travel times (or costs) among them are not assumed to be constant and may vary depending on many different factors. The motivation to consider the time dependence factor is that it enables to have better approximations to many problems from practice, mainly from the industry and the service sector. In the related literature there are different versions of the TDTSP that consider that variations occur for different reasons and over distinct parameters. For example, some of them consider that variations affect travel times (and/or costs) while others assume that variations influence travel speeds. Moreover, in the first case, one version assumes that the travel time depends on the position of the arc in the tour while another one assumes that it depends on the particular starting instant for travelling the arc. As well as the TSP, the TDTSP belongs to the class NP-Hard and therefore it is not known an algorithm that solves it in polynomial time. In this thesis we approach two of the versions mentioned above by means of Integer Linear Programming formulations. For each formulation, we perform a theoretical study focused on deriving families of valid inequalities that exploit the particular characteristics of the problem. In particular, for one of the variants, we prove that some of them are facet defining. From a practical standpoint, for the versions considered we develop exact Branch and Cut algorithms that incorporate these families of valid inequalities and we evaluate them on instances from the related literature, obtaining good computational results that show that both approaches are feasible to be used in practice. Fil: Miranda Bront, Juan José. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2012 Tesis Doctoral PDF Inglés info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/tesis_n5113_MirandaBront

Ejemplares similares