A relax and cut approach using the multi-commodity flow formulation for the traveling salesman problem
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 eli...
- Autores:
-
Kawashima, Makswell Seyiti
Rangel, Socorro
Litvinchev, Igor
Infante, Luis
- Tipo de recurso:
- Article of journal
- Fecha de publicación:
- 2015
- Institución:
- Universidad Nacional de Colombia
- Repositorio:
- Universidad Nacional de Colombia
- Idioma:
- spa
- OAI Identifier:
- oai:repositorio.unal.edu.co:unal/60720
- Acceso en línea:
- https://repositorio.unal.edu.co/handle/unal/60720
http://bdigital.unal.edu.co/59052/
- Palabra clave:
- 62 Ingeniería y operaciones afines / Engineering
traveling salesman problem
relax and cut
Lagrangean relaxation
- Rights
- openAccess
- License
- Atribución-NoComercial 4.0 Internacional
| Summary: | 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. |
|---|