Tesis doctoral de Inmaculada Rodríguez Martin
La presente memoria está dedicada al estudio de los problemas del ciclo mediana mcp, consistentes en ubicar en un grafo completo mixto un cilco que visita un determinado vértice, teniendo en cuenta el coste total de establecimiento del ciclo y el costo total de accsibilidad al mismo, definiéndose éste último como la suma de las distancias de los vértices no visitados al ciclo. en primer lugar se revisa la literatura existente sobre problemas bicriterio de localización de estructuas con forma de camino, árbol y ciclo. Además, se proponen formulaciones matemáticas genéricas para este tipo de problemas. en el capítulo 3 presentamos dos versiones de mcp. En la primera, mcp1, el objetivo es encontrar el ciclo que minimiza la suma de los dos tipos de costos (de establecimiento y de accesibilidad). En la segunda, mcp2, el objetivo es encontrar el ciclo con un menor costo de establecimiento entre todos los que tienen el costo total de accesibilidad acotado por un valor dado. Demostramos que los dos problemas son np duros en sentido fuerte y proponemos formulaciones matemáticas para ambos. Así mismo, demostramos que una serie de inecuaciones son válidas a la hora de reforzar la relajación lineal de los modelos matemáticos. el capítulo 4 está dedicado al estudio del poliedro asociado al problema mcp1. Probamos una serie de resutlados que establecen la dimensión de este poliedro y muestran distintos tipos de inecuaciones que definen facetas del mismo. Estos resutlados son utilizados para diseñar los algoritmos de ramificación y corte que se describen en el capítulo 5, y que nos permiten resolver mcp1 y mcp2 de forma exacta. en el capítulo 6 presentamos una nueva técnica metaheurística denominada búsqueda tabú de entorno variable (vnts), y describimos su aplicación para la resolución de los mcp. en capítulo 7 muestra los resultados computacionales obtenidos usando los métodos exactos y heurísticos descritos
Datos académicos de la tesis doctoral «Cycle location problems«
- Título de la tesis: Cycle location problems
- Autor: Inmaculada Rodríguez Martin
- Universidad: La laguna
- Fecha de lectura de la tesis: 12/06/2000
Dirección y tribunal
- Director de la tesis
- Moreno Perez José Andres
- Tribunal
- Presidente del tribunal: Juan Antonio Mesa lópez-colmenar
- leopoldo Acosta sanchez (vocal)
- pedro Larrañaga mugica (vocal)
- dolores Santos peñate (vocal)