Multiple traveling salesman problem with handling times on paths and spiders

Abstract

Dado un conjunto finito de N vértices, el tiempo de viaje entre cada uno de ellos, una cantidad m de vehículos y un punto de origen llamado depósito, en el multiple traveling salesman problem se desea encontrar m rutas que, partiendo desde el depósito, visiten a todos los vértices, a los que llamaremos clientes. En este trabajo tendremos en consideración el tiempo de visita a los clientes, el cual supondremos el mismo para cada uno de ellos. Se estudian dos variantes del problema: la primera es minimizar el máximo tiempo de ruta de los vehículos y, la segunda, es minimizar el tiempo de completación, que corresponde a minimizar el tiempo en que se atiende al último cliente. Se estudió el problema cuando la red de clientes-depósito es un camino, un ciclo y una araña. Para el camino, el ciclo y la araña se encontraron soluciones óptimas estructuradas. Para el camino y el ciclo, algoritmos polinomiales. Para la araña con 2 vehículos se encontró una 3/2-aproximación para el tiempo de ruta y una 5/3-aproximación para el tiempo de completación. Finalmente, para la araña con una cantidad m fija de vehículos, se dedujo una (1 + ε)-aproximación en tiempo N O(m/ε) tanto para el tiempo de completación como para el tiempo de ruta.