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...

Full description

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
id UNACIONAL2_de3bb1d58499eb197b63a151405af9cf
oai_identifier_str oai:repositorio.unal.edu.co:unal/60720
network_acronym_str UNACIONAL2
network_name_str Universidad Nacional de Colombia
repository_id_str
spelling Atribución-NoComercial 4.0 InternacionalDerechos reservados - Universidad Nacional de Colombiahttp://creativecommons.org/licenses/by-nc/4.0/info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2Kawashima, Makswell Seyitia84467e9-0fc3-4b76-bae3-024cce1826bc300Rangel, Socorro3619240a-aaab-4aaa-8d18-0b1e4a3999f0300Litvinchev, Igor2fe66fc8-1c06-4c4c-8bf6-907ff6c53370300Infante, Luis41fd3a97-5aec-4234-a247-8ec65d96c9b33002019-07-02T18:57:38Z2019-07-02T18:57:38Z2015-05-01ISSN: 2346-2183https://repositorio.unal.edu.co/handle/unal/60720http://bdigital.unal.edu.co/59052/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.application/pdfspaUniversidad Nacional de Colombia (Sede Medellín). Facultad de Minas.https://revistas.unal.edu.co/index.php/dyna/article/view/51144Universidad Nacional de Colombia Revistas electrónicas UN DynaDynaKawashima, 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-218362 Ingeniería y operaciones afines / Engineeringtraveling salesman problemrelax and cutLagrangean relaxationA relax and cut approach using the multi-commodity flow formulation for the traveling salesman problemArtículo de revistainfo:eu-repo/semantics/articleinfo:eu-repo/semantics/publishedVersionhttp://purl.org/coar/resource_type/c_6501http://purl.org/coar/resource_type/c_2df8fbb1http://purl.org/coar/version/c_970fb48d4fbd8a85Texthttp://purl.org/redcol/resource_type/ARTORIGINAL51144-250826-1-PB.pdfapplication/pdf698818https://repositorio.unal.edu.co/bitstream/unal/60720/1/51144-250826-1-PB.pdfcfa1d0af70e1e29b0c4a42640a7d662cMD51THUMBNAIL51144-250826-1-PB.pdf.jpg51144-250826-1-PB.pdf.jpgGenerated Thumbnailimage/jpeg9171https://repositorio.unal.edu.co/bitstream/unal/60720/2/51144-250826-1-PB.pdf.jpg6df29df50da0f05202f9bc95dc045e5aMD52unal/60720oai:repositorio.unal.edu.co:unal/607202024-04-14 23:11:43.432Repositorio Institucional Universidad Nacional de Colombiarepositorio_nal@unal.edu.co
dc.title.spa.fl_str_mv A relax and cut approach using the multi-commodity flow formulation for the traveling salesman problem
title A relax and cut approach using the multi-commodity flow formulation for the traveling salesman problem
spellingShingle A relax and cut approach using the multi-commodity flow formulation for the traveling salesman problem
62 Ingeniería y operaciones afines / Engineering
traveling salesman problem
relax and cut
Lagrangean relaxation
title_short 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_sort A relax and cut approach using the multi-commodity flow formulation for the traveling salesman problem
dc.creator.fl_str_mv Kawashima, Makswell Seyiti
Rangel, Socorro
Litvinchev, Igor
Infante, Luis
dc.contributor.author.spa.fl_str_mv Kawashima, Makswell Seyiti
Rangel, Socorro
Litvinchev, Igor
Infante, Luis
dc.subject.ddc.spa.fl_str_mv 62 Ingeniería y operaciones afines / Engineering
topic 62 Ingeniería y operaciones afines / Engineering
traveling salesman problem
relax and cut
Lagrangean relaxation
dc.subject.proposal.spa.fl_str_mv traveling salesman problem
relax and cut
Lagrangean relaxation
description 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.
publishDate 2015
dc.date.issued.spa.fl_str_mv 2015-05-01
dc.date.accessioned.spa.fl_str_mv 2019-07-02T18:57:38Z
dc.date.available.spa.fl_str_mv 2019-07-02T18:57:38Z
dc.type.spa.fl_str_mv Artículo de revista
dc.type.coar.fl_str_mv http://purl.org/coar/resource_type/c_2df8fbb1
dc.type.driver.spa.fl_str_mv info:eu-repo/semantics/article
dc.type.version.spa.fl_str_mv info:eu-repo/semantics/publishedVersion
dc.type.coar.spa.fl_str_mv http://purl.org/coar/resource_type/c_6501
dc.type.coarversion.spa.fl_str_mv http://purl.org/coar/version/c_970fb48d4fbd8a85
dc.type.content.spa.fl_str_mv Text
dc.type.redcol.spa.fl_str_mv http://purl.org/redcol/resource_type/ART
format http://purl.org/coar/resource_type/c_6501
status_str publishedVersion
dc.identifier.issn.spa.fl_str_mv ISSN: 2346-2183
dc.identifier.uri.none.fl_str_mv https://repositorio.unal.edu.co/handle/unal/60720
dc.identifier.eprints.spa.fl_str_mv http://bdigital.unal.edu.co/59052/
identifier_str_mv ISSN: 2346-2183
url https://repositorio.unal.edu.co/handle/unal/60720
http://bdigital.unal.edu.co/59052/
dc.language.iso.spa.fl_str_mv spa
language spa
dc.relation.spa.fl_str_mv https://revistas.unal.edu.co/index.php/dyna/article/view/51144
dc.relation.ispartof.spa.fl_str_mv Universidad Nacional de Colombia Revistas electrónicas UN Dyna
Dyna
dc.relation.references.spa.fl_str_mv 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
dc.rights.spa.fl_str_mv Derechos reservados - Universidad Nacional de Colombia
dc.rights.coar.fl_str_mv http://purl.org/coar/access_right/c_abf2
dc.rights.license.spa.fl_str_mv Atribución-NoComercial 4.0 Internacional
dc.rights.uri.spa.fl_str_mv http://creativecommons.org/licenses/by-nc/4.0/
dc.rights.accessrights.spa.fl_str_mv info:eu-repo/semantics/openAccess
rights_invalid_str_mv Atribución-NoComercial 4.0 Internacional
Derechos reservados - Universidad Nacional de Colombia
http://creativecommons.org/licenses/by-nc/4.0/
http://purl.org/coar/access_right/c_abf2
eu_rights_str_mv openAccess
dc.format.mimetype.spa.fl_str_mv application/pdf
dc.publisher.spa.fl_str_mv Universidad Nacional de Colombia (Sede Medellín). Facultad de Minas.
institution Universidad Nacional de Colombia
bitstream.url.fl_str_mv https://repositorio.unal.edu.co/bitstream/unal/60720/1/51144-250826-1-PB.pdf
https://repositorio.unal.edu.co/bitstream/unal/60720/2/51144-250826-1-PB.pdf.jpg
bitstream.checksum.fl_str_mv cfa1d0af70e1e29b0c4a42640a7d662c
6df29df50da0f05202f9bc95dc045e5a
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
repository.name.fl_str_mv Repositorio Institucional Universidad Nacional de Colombia
repository.mail.fl_str_mv repositorio_nal@unal.edu.co
_version_ 1814090243406561280

Publicaciones similares