A relax and cut approach using the multi-commodity flow formulation for the traveling salesman problem
En este artículo nosotros exploramos una formulación de flujo multiproductos para el Problema del Agente Viajero Asimétrico (ATSP) en la obtención de cotas duales de este problema. El procedimiento empleado es una variante del método relax and cut propuesto en la literatura que computa los multiplic...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
2015
|
| Online Access: | http://eprints.uanl.mx/14989/1/156.pdf |
| _version_ | 1824414214571163648 |
|---|---|
| author | Kawashima, Makswell Seyiti Rangel, Socorro Litvinchev, Igor Infante, Luis |
| author_facet | Kawashima, Makswell Seyiti Rangel, Socorro Litvinchev, Igor Infante, Luis |
| author_sort | Kawashima, Makswell Seyiti |
| collection | Repositorio Institucional |
| description | En este artículo nosotros exploramos una formulación de flujo multiproductos para el Problema del Agente Viajero Asimétrico (ATSP) en la obtención de cotas duales de este problema. El procedimiento empleado es una variante del método relax and cut propuesto en la literatura que computa los multiplicadores lagrangianos asociados a las restricciones de eliminación de subrutas preservando la optimalidad de los multiplicadores asociados a las restricciones de asignación. Los resultados obtenidos con la experimentación computacional son alentadores y muestran que el algoritmo propuesto genera buenas cotas duales con un tiempo de ejecución bajo.
ABSTRACT
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. |
| format | Article |
| id | eprints-14989 |
| institution | UANL |
| language | English |
| publishDate | 2015 |
| record_format | eprints |
| spelling | eprints-149892019-05-27T15:37:37Z http://eprints.uanl.mx/14989/ A relax and cut approach using the multi-commodity flow formulation for the traveling salesman problem Kawashima, Makswell Seyiti Rangel, Socorro Litvinchev, Igor Infante, Luis En este artículo nosotros exploramos una formulación de flujo multiproductos para el Problema del Agente Viajero Asimétrico (ATSP) en la obtención de cotas duales de este problema. El procedimiento empleado es una variante del método relax and cut propuesto en la literatura que computa los multiplicadores lagrangianos asociados a las restricciones de eliminación de subrutas preservando la optimalidad de los multiplicadores asociados a las restricciones de asignación. Los resultados obtenidos con la experimentación computacional son alentadores y muestran que el algoritmo propuesto genera buenas cotas duales con un tiempo de ejecución bajo. ABSTRACT 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. 2015 Article PeerReviewed text en cc_by_nc_nd http://eprints.uanl.mx/14989/1/156.pdf http://eprints.uanl.mx/14989/1.haspreviewThumbnailVersion/156.pdf Kawashima, Makswell Seyiti y Rangel, Socorro y Litvinchev, Igor y 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 0012-7353 http://doi.org/10.15446/dyna.v82n191.51144 doi:10.15446/dyna.v82n191.51144 |
| spellingShingle | Kawashima, Makswell Seyiti Rangel, Socorro Litvinchev, Igor Infante, Luis A relax and cut approach using the multi-commodity flow formulation for the traveling salesman problem |
| thumbnail | https://rediab.uanl.mx/themes/sandal5/images/online.png |
| title | A relax and cut approach using the multi-commodity flow formulation for the traveling salesman problem |
| title_full | A relax and cut approach using the multi-commodity flow formulation for the traveling salesman problem |
| title_fullStr | A relax and cut approach using the multi-commodity flow formulation for the traveling salesman problem |
| title_full_unstemmed | A relax and cut approach using the multi-commodity flow formulation for the traveling salesman problem |
| title_short | A relax and cut approach using the multi-commodity flow formulation for the traveling salesman problem |
| title_sort | relax and cut approach using the multi commodity flow formulation for the traveling salesman problem |
| url | http://eprints.uanl.mx/14989/1/156.pdf |
| work_keys_str_mv | AT kawashimamakswellseyiti arelaxandcutapproachusingthemulticommodityflowformulationforthetravelingsalesmanproblem AT rangelsocorro arelaxandcutapproachusingthemulticommodityflowformulationforthetravelingsalesmanproblem AT litvinchevigor arelaxandcutapproachusingthemulticommodityflowformulationforthetravelingsalesmanproblem AT infanteluis arelaxandcutapproachusingthemulticommodityflowformulationforthetravelingsalesmanproblem AT kawashimamakswellseyiti relaxandcutapproachusingthemulticommodityflowformulationforthetravelingsalesmanproblem AT rangelsocorro relaxandcutapproachusingthemulticommodityflowformulationforthetravelingsalesmanproblem AT litvinchevigor relaxandcutapproachusingthemulticommodityflowformulationforthetravelingsalesmanproblem AT infanteluis relaxandcutapproachusingthemulticommodityflowformulationforthetravelingsalesmanproblem |