Presentación | Participantes | Bibliografía (DML-E) | Bibliografía adicional | Enlaces de interés | Otros proyectos DML | Ayuda  
INICIO | 16 de abril de 2024
  

La combinatoria poliédrica y el problema del viajante. Aplicación al caso de ciento tres ciudades españolas.

Título inglés Polyhedral combinatorics and the travelling salesman problem: application to the case of hundred and three Spanish towns.
Título español La combinatoria poliédrica y el problema del viajante. Aplicación al caso de ciento tres ciudades españolas.
Autor/es Alvarez Valdés, Ramón ; Corberán Salvador, Angel ; Tamarit Goerlich, José Manuel
Organización Dep. Estad. Invest. Oper. Fac. Mat. Univ. Valencia, Valencia, España
Revista 0210-8054
Publicación 1985, 9 (3): 199-213, 16 Ref.
Tipo de documento articulo
Idioma Español
Resumen español El trabajo resume los resultados de la aplicación de la Combinatoria Poliédrica al Problema del Viajante (TSP): definición del poliedro, dimensión, desigualdades válidas, facetas. Estos resultados se aplican al caso concreto de encontrar el circuito para el TSP de coste mínimo que recorre ciento tres ciudades españolas.
Se trata de un proceso interactivo en el que, para cada solución de la relajación lineal del problema, obtenida mediante la aplicación de un código comercial de Programación lineal, se identifican las restricciones violadas y se incorporan manualmente al problema relajado en la iteración siguiente. En nuestro caso, la séptima resolución del problema lineal, al que se habían incorporado 68 nuevas restricciones, proporcionó la solución óptima.
Clasificación UNESCO 120709
Palabras clave español Programación lineal ; Problemas combinatorios ; Problema del viajante ; Algoritmos ; Corte
Código MathReviews MR0891854
Icono pdf Acceso al artículo completo
Equipo DML-E
Instituto de Ciencias Matemáticas (ICMAT - CSIC)
rmm()icmat.es