Rodríguez Villalobos, A.; Ruiz García, R. (2012). The effect of the asymmetry of road transportation networks on the traveling salesman problem. Computers and Operations Research. 39(7):1566-1576. https://doi.org/10.1016/j.cor.2011.09.005
Por favor, use este identificador para citar o enlazar este ítem: http://hdl.handle.net/10251/37058
Title:
|
The effect of the asymmetry of road transportation networks on the traveling salesman problem
|
Author:
|
Rodríguez Villalobos, Alejandro
Ruiz García, Rubén
|
UPV Unit:
|
Universitat Politècnica de València. Departamento de Organización de Empresas - Departament d'Organització d'Empreses
Universitat Politècnica de València. Departamento de Estadística e Investigación Operativa Aplicadas y Calidad - Departament d'Estadística i Investigació Operativa Aplicades i Qualitat
|
Issued date:
|
|
Abstract:
|
The routing of vehicles on road transportation networks is an area of great importance to transportation planners within scientific literature. This field includes well known and studied problems like traveling salesman ...[+]
The routing of vehicles on road transportation networks is an area of great importance to transportation planners within scientific literature. This field includes well known and studied problems like traveling salesman problems or TSP or the more realistic asymmetric variant or ATSP, whose applications extend to other areas of transport and operations research. This work studies the effect that the asymmetry of road transportation networks, geographical location and territory have over TSP and ATSP methods. We conduct comprehensive experiments in order to assess the effects that these factors have on some of the best known algorithms for the TSP/ATSP. We demonstrate that all these factors have a significant influence in solution time and quality. Furthermore, we show that the solutions obtained with Euclidean matrices and those obtained with real distance matrices differ significantly. © 2011 Elsevier Ltd. All rights reserved.
[-]
|
Subjects:
|
Algorithms
,
Asymmetric traveling salesman problem
,
Asymmetry
,
Geographic information systems
,
Road transportation networks
,
Asymmetric variants
,
Best-known algorithms
,
Distance matrices
,
Euclidean
,
Geographical locations
,
Scientific literature
,
Solution time
,
Transportation planners
,
Work study
,
Motor transportation
,
Roads and streets
,
Traveling salesman problem
|
Copyrigths:
|
Reserva de todos los derechos
|
Source:
|
Computers and Operations Research. (issn:
0305-0548
)
|
DOI:
|
10.1016/j.cor.2011.09.005
|
Publisher:
|
Elsevier
|
Publisher version:
|
http://dx.doi.org/10.1016/j.cor.2011.09.005
|
Project ID:
|
info:eu-repo/grantAgreement/MICINN//DPI2008-03511/ES/SMPA: SECUENCIACION MULTIOBJETIVO PARALELA AVANZADA: AVANCES TEORICOS Y PRACTICOS/
info:eu-repo/grantAgreement/UPV//3147/ES/PPAR - Programación de la producción en entornos altamente restringidos: Nuevos algoritmos y avances computacionales/
info:eu-repo/grantAgreement/Generalitat Valenciana//IMIDIC%2F2009%2F198/ES/OSC: Optimización integral de la cadena de suministro/ /
info:eu-repo/grantAgreement/Generalitat Valenciana//IMIDIC%2F2008%2F137/ES/OSC: Optimización integral de la cadena de suministro/ /
info:eu-repo/grantAgreement/Generalitat Valenciana//IMIDIC%2F2010%2F175/ES/OSC: Optimización integral de la cadena de suministro/ /
|
Thanks:
|
The authors would like to warmly thank Prof. Keld Helsgaun, Prof. Yuichi Nagata, Profs. Boris Goldengorin and Gerold Jager, and especially Prof. Matteo Fischetti, for facilitating the code of their great algorithms. This ...[+]
The authors would like to warmly thank Prof. Keld Helsgaun, Prof. Yuichi Nagata, Profs. Boris Goldengorin and Gerold Jager, and especially Prof. Matteo Fischetti, for facilitating the code of their great algorithms. This work is partially funded by the Spanish Ministry of Science and Innovation, under the project "SMPA Advanced Parallel Multiobjective Sequencing: Practical and Theoretical Advances" with reference DPI2008-03511/DPI. The authors should also thank the IMPIVA-Institute for the Small and Medium Valencian Enterprise, for the project OSC with references IMIDIC/2008/137, IMIDIC/2009/198 and 175 and the Polytechnic University of Valencia, for the project PPAR with reference 3147.
[-]
|
Type:
|
Artículo
|