Escudo de la República de Colombia
Sistema Nacional de Biliotecas - Repositorio Institucional Universidad Nacional de Colombia Biblioteca Digital - Repositorio Institucional UN Sistema Nacional de Bibliotecas UN

A relax and cut approach using the multi-commodity flow formulation for the traveling salesman problem

Kawashima, Makswell Seyiti and Rangel, Socorro and Litvinchev, Igor and Infante, Luis (2015) A relax and cut approach using the multi-commodity flow formulation for the traveling salesman problem. DYNA, 82 (191). pp. 42-50. ISSN 2346-2183

Texto completo

[img]
Vista previa
PDF - Versión Publicada
Available under License Creative Commons Attribution Non-commercial No Derivatives.

698kB

URL oficial: https://revistas.unal.edu.co/index.php/dyna/articl...

Resumen

In this paper we explore the multi-commodity flow formulation for the Asymmetric Traveling Salesman Problem (ATSP) to obtain dual bounds. The procedure employed is a variant of a relax and cut procedure proposed in the literature that computes the Lagrangean multipliers associated to the subtour elimination constraints preserving the optimality of the multipliers associated to the assignment constraints. The results obtained by the computational study are encouraging and show that the proposed algorithm generated good dual bounds for the ATSP with a low execution time.

Tipo de documento:Artículo - Article
Palabras clave:traveling salesman problem, relax and cut, Lagrangean relaxation
Temática:6 Tecnología (ciencias aplicadas) / Technology > 62 Ingeniería y operaciones afines / Engineering
Unidad administrativa:Revistas electrónicas UN > Dyna
Código ID:59052
Enviado por : Dirección Nacional de Bibliotecas STECNICO
Enviado el día :31 Oct 2017 17:20
Ultima modificación:27 Noviembre 2017 22:06
Ultima modificación:27 Noviembre 2017 22:06
Exportar:Clic aquí
Estadísticas:Clic aquí
Compartir:

Solamente administradores del repositorio: página de control del ítem

Vicerrectoría de Investigación: Número uno en investigación
Indexado por:
Indexado por Scholar Google WorldCat DRIVER Registry of Open Access Repositories OpenDOAR Metabiblioteca BDCOL OAIster Red de repositorios latinoamericanos DSpace BASE Open archives La referencia Colombiae Open Access Theses and Dissertations Tesis latinoamericanas CLACSO
Este sitio web se ve mejor en Firefox