Un enfoque relax and cut usando una formulación de flujo multiproductos para el problema del agente viajero
Nenhuma Miniatura disponível
Data
2015-01-01
Orientador
Coorientador
Pós-graduação
Curso de graduação
Título da Revista
ISSN da Revista
Título de Volume
Editor
Tipo
Artigo
Direito de acesso
Acesso aberto
Resumo
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.
Descrição
Palavras-chave
Idioma
Inglês
Como citar
DYNA (Colombia), v. 82, n. 191, p. 42-50, 2015.
