Un enfoque exacto para el problema del vendedor viajero con tiempos de trabajo.
| dc.contributor.advisor | Contreras Bolton, Carlos | es |
| dc.contributor.author | Gutiérrez Aguirre, Pablo Javier | es |
| dc.date.accessioned | 2024-12-17T12:59:01Z | |
| dc.date.available | 2024-12-17T12:59:01Z | |
| dc.date.issued | 2024 | |
| dc.description | Tesis presentada para optar al Grado académico de Magíster en Ingeniería Industrial | es |
| dc.description.abstract | El problema del vendedor viajero con tiempos de trabajo (TSPJ) es una variante del problema clásico del vendedor viajero. En el TSPJ, el viajero visita un conjunto de vértices, asegurando una visita a cada uno de ellos mientras inicia un trabajo. El tiempo de cada trabajo depende del vértice donde se realiza. Una vez iniciado, el viajero se desplaza al siguiente vértice, y el trabajo continúa de forma autónoma. El objetivo es minimizar el tiempo máximo de finalización, también conocido como makespan. Sin embargo, dado que el problema es NP-hard, los modelos de programación lineal entera mixta (MILP) existentes no pueden resolver eficientemente instancias grandes. Por tanto, se mejora el modelo de MILP existente y se propone un nuevo modelo de MILP para el TSPJ, que se mejora mediante el cálculo de cotas inferiores y superiores válidas. Además, se propone reforzar las formulaciones de tamaño exponencial que incorporan explícitamente restricciones de eliminación de subtour, desigualdades de blossom y desigualdades válidas. Se desarrollan también dos algoritmos exactos de branch-and-cut (B&C) basados en el modelo existente mejorado (BCEM) y en el nuevo modelo (BCNM). Los algoritmos propuestos se prueban en instancias de referencia de la literatura, cuatro conjuntos de instancias cuyos tamaños oscilan entre 17 y 1200 vértices. Los resultados computacionales muestran que los algoritmos propuestos de B&C superan a los modelos de MILP del estado del arte en todos los conjuntos de instancias. Los algoritmos propuestos fueron capaces de encontrar 50 y tres nuevas mejores soluciones conocidas, respectivamente. Dado que ninguna formulación alcanza la optimalidad dentro del límite de tiempo dado para instancias medianas y grandes, se propone un nuevo conjunto de instancias que van de 100 a 390 vértices para evaluar más a fondo los límites de rendimiento. Los algoritmos propuestos obtienen mejores resultados, sobre todo en términos de valores de brecha de optimalidad y tiempos computacional de cálculo, resolviendo de forma óptima instancias de hasta 380 vértices. | es |
| dc.description.abstract | The traveling salesman problem with job-times (TSPJ) is a variant of the classic traveling salesman problem. In the TSPJ, the traveler visits a set of vertices, ensuring one visit to each of them while he initiates a job. The time of each job depends on the vertex where it is performed. Once started, the traveler moves to the next vertex, and the job continues autonomously. The aim is to minimize the maximum completion time, also known as the makespan. However, since the problem is NP-hard, the existing mixed integer linear programming (MILP) models cannot efficiently solve large instances. Therefore, we improve the existing MILP model and propose a new MILP model for the TSPJ, which is improved by the computation of valid lower and upper bounds. Moreover, we propose strengthened exponential-size formulations that explicitly incorporate subtour elimination constraints, blossom inequalities, and additional valid inequalities. We also develop two exact branch-and-cut (B&C) algorithms based on the improved existing (BCEM) and new model (BCNM). The B&C algorithms are tested on benchmark instances from the literature, four sets of instances ranging in size from 17 to 1200 vertices. The computational results show that proposed B&C algorithms outperform the state-of-the-art MILPs in all sets of instances. The BCEM and BCNM were able to find 50 and three new best known solutions, respectively. Since no formulation achieves optimality within the given time limit for medium and large instances, we propose a new set of instances ranging from 100 to 390 vertices to assess performance limits further. The proposed algorithms obtain better performance particularly in terms of gap values and computing times, optimally solving instances up to 380 vertices. | en |
| dc.description.campus | Concepción | es |
| dc.description.departamento | Departamento de Ingeniería Industrial | es |
| dc.description.facultad | Facultad de Ingeniería | es |
| dc.description.sponsorship | ANID, Proyecto FONDECYT INICIACIÓN 11241132 | es |
| dc.identifier.uri | https://repositorio.udec.cl/handle/11594/12239 | |
| dc.language.iso | en | en |
| dc.publisher | Universidad de Concepción | es |
| dc.rights | CC BY-NC-ND 4.0 DEED Attribution-NonCommercial-NoDerivs 4.0 International | en |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/4.0/ | |
| dc.subject | Investigación operacional | es |
| dc.subject | Logística | es |
| dc.subject | Planificación | es |
| dc.title | Un enfoque exacto para el problema del vendedor viajero con tiempos de trabajo. | es |
| dc.type | Thesis | en |