The effect of the asymmetry of road transportation networks on the traveling salesman problem

The effect of the asymmetry of road transportation networks on the traveling salesman problem

0.00 Avg rating0 Votes
Article ID: iaor201111458
Volume: 39
Issue: 7
Start Page Number: 1566
End Page Number: 1576
Publication Date: Jul 2012
Journal: Computers and Operations Research
Authors: ,
Keywords: vehicle routing & scheduling, combinatorial optimization, programming: travelling salesman
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 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.

Reviews

Required fields are marked *. Your email address will not be published.