Formulaciones y algoritmos exactos para el problema del vendedor viajero asimétrico selectivo con múltiples visitas.
| dc.contributor.advisor | Aguayo Bustos, Maichel Miguel | es |
| dc.contributor.author | Slater Carrasco, José Manuel | es |
| dc.date.accessioned | 2021-07-01T20:15:15Z | |
| dc.date.accessioned | 2024-08-28T20:12:20Z | |
| dc.date.available | 2021-07-01T20:15:15Z | |
| dc.date.available | 2024-08-28T20:12:20Z | |
| dc.date.issued | 2018 | |
| dc.description | Tesis Para optar al grado de Magíster en Ingeniería Industrial. | es |
| dc.description.abstract | Este trabajo, aborda una extensión del problema vendedor viajero asimétrico (ATSP), denominado problema del vendedor viajero selectivo asimétrico con múltiples visitas (SHMATSP). El objetivo en este problema es encontrar un tour que comience y termine en el nodo inicial, que maximice el beneficio obtenido por la visita de nodos, sujeto a la restricción de distancia máxima permitida y la posibilidad de visitar algunos nodos más de una vez. Para capturar el S-HMATSP se proponen tres modelos de programación lineal entera, uno de tamaño polinomial y dos de tamaño exponencial. Para resolver el S-HMATSP, se diseñan dos tipos de algoritmos exactos, un método secuencial de cutting planes y otro paralelo de Branch-and-Cut, ambos algoritmos resuelven relajaciones del problema y agregan cortes para eliminar subtours desde soluciones enteras. En instancias que involucran entre 300 y 1001 nodos, los algoritmos propuestos muestran una clara superioridad sobre los métodos de descomposición de Benders y Branch-and-Cut disponibles en CPLEX. | es |
| dc.description.departamento | Departamento de Ingeniería Industrial. | es |
| dc.description.facultad | Departamento de Ingeniería Industrial | es |
| dc.identifier.uri | https://repositorio.udec.cl/handle/11594/6640 | |
| dc.language.iso | spa | es |
| dc.publisher | Universidad de Concepción. | es |
| dc.rights | Creative Commoms CC BY NC ND 4.0 internacional (Atribución-NoComercial-SinDerivadas 4.0 Internacional) | |
| dc.rights.uri | https://creativecommons.org/licenses/by-nc-nd/4.0/deed.es | |
| dc.source.uri | https://go.openathens.net/redirector/udec.cl?url=http://tesisencap.udec.cl/concepcion/slater_c_j/index.html | |
| dc.subject | Problema de Vendedor Viajero | es |
| dc.subject | Optimización Combinatoria | es |
| dc.subject | Programación Heurística | es |
| dc.subject | Algoritmos | es |
| dc.title | Formulaciones y algoritmos exactos para el problema del vendedor viajero asimétrico selectivo con múltiples visitas. | es |
| dc.type | Tesis | es |