Resumen:
En la versión online del clásico problema del viajante de comercio (OLTSP) las ciudades a visitar se van conociendo mientras el viajante ejecuta su recorrido. Este problema se modela con un servidor que se desplaza en un espacio métrico para satisfacer requerimientos, teniendo como objetivo terminar su servicio lo antes posible. Los requerimientos se van presentando en distintos puntos del espacio y su existencia sólo es conocida a partir del momento de presentación. Se distinguen dos variantes para OLTSP: en la variante Homing el servidor debe retornar al punto de partida para completar el servicio, mientras que en la variante Nomadic el servicio finaliza al atender todos los requerimientos. Los trabajos anteriores que analizan OLTSP suelen considerar que el espacio es continuo y que el servidor puede cambiar de dirección en cualquier parte del recorrido. A diferencia de ese enfoque, presentamos una versión discreta (DOLTSP) en la que el espacio métrico se representa utilizando un grafo con longitudes asociadas a sus ejes y sólo se le permite al servidor modificar su recorrido cuando está sobre algún vértice. Esta limitación afecta directamente a la capacidad de reacción del servidor y potencia el riesgo asociado a cada decisión. En esta Tesis proponemos diversos algoritmos para ambas variantes de DOLTSP cuando el grafo sobre el que se mueve el servidor es una cadena y medimos el desempeño de cada uno calculando su competitividad. Esta es la forma de análisis de peor caso más difundida para evaluar algoritmos online, y consiste en comparar el costo de las soluciones online contra el de una solución óptima offline, es decir, aquella que podr´ıa obtenerse si se conociera de antemano la secuencia completa de requerimientos. Mostramos que el problema discreto tiene asociadas competitividades más elevadas que el problema continuo y que algunos de los algoritmos que presentamos alcanzan la mejor competitividad posible. Además, hacemos un análisis empírico seleccionando un conjunto significativo de instancias de DOLTSP y midiendo la calidad de las soluciones generadas por cada algoritmo. Mostramos con este análisis que los algoritmos que tienen la mejor competitividad no son los que mejor funcionan en la práctica.
Abstract:
In the online traveling salesman problem (OLTSP), the cities to visit are known while the salesman is traveling. This problem is modeled with a server that moves in a metric space to satisfy requirements, aiming at completing the service as early as possible. Requirements are released at different points of the space and their existence becomes known only after the release time. Two variants are distinguished: in Homing OLTSP the server has to return to the starting point in order to complete its task. In Nomadic OLTSP the service is finished when all requirements are served. Previous studies on OLTSP usually consider a continuous metric space where the server has no restrictions to change its direction. Unlike that approach, we introduce a discrete version (DOLTSP) and represent the metric space using a weighted graph, where the server is allowed to modify its route only if it is on a vertex. This limitation directly affects the capacity of the server to react and increases the risk related to each decision. In this Thesis we propose algorithms for both variants of DOLTSP when the graph is a chain and we measure their performance using competitive analysis, the most widely accepted method for evaluating online algorithms. This worst-case analysis consists of comparing the cost of online solutions against the offline optimal cost, i.e., that of a solution that could be generated if the whole sequence of requirements were known beforehand. We show that the discrete problem has higher competitive ratios than the continuous one and that some of the algorithms we present achieve the best possible competitive ratio. In addition, we perform an empirical analysis generating a significant set of instances for DOLTSP and measuring the quality of the solutions generated by each algorithm. We show that algorithms with the best competitive ratio do not necessarily have the best performance in practice.
Citación:
---------- APA ----------
Aprea, Mauro; Sadovoy, Gustavo. (2006). El problema del viajante de comercio online sobre espacios discretos. (Tesis de Grado. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/seminario_nCOM000297_Aprea
---------- CHICAGO ----------
Aprea, Mauro; Sadovoy, Gustavo. "El problema del viajante de comercio online sobre espacios discretos". Tesis de Grado, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 2006.https://hdl.handle.net/20.500.12110/seminario_nCOM000297_Aprea
Estadísticas:
Descargas mensuales
Total de descargas desde :
https://bibliotecadigital.exactas.uba.ar/download/seminario/seminario_nCOM000297_Aprea.pdf
Distrubución geográfica
