![](/images/graphics-bg.png)
Can the Agent with Limited Information Solve Travelling Salesman Problem?
Joint Authors
Source
Issue
Vol. 2017, Issue 2017 (31 Dec. 2017), pp.1-6, 6 p.
Publisher
Hindawi Publishing Corporation
Publication Date
2017-04-11
Country of Publication
Egypt
No. of Pages
6
Main Subjects
Abstract EN
Here, we develop new heuristic algorithm for solving TSP (Travelling Salesman Problem).
In our proposed algorithm, the agent cannot estimate tour lengths but detect only a few neighbor sites.
Under the circumstances, the agent occasionally ignores the NN method (choosing the nearest site from current site) and chooses the other site far from current site.
It is dependent on relative distances between the nearest site and the other site.
Our algorithm performs well in symmetric TSP and asymmetric TSP (time-dependent TSP) conditions compared with the NN algorithm using some TSP benchmark datasets from the TSPLIB.
Here, symmetric TSP means common TSP, where costs between sites are symmetric and time-homogeneous.
On the other hand, asymmetric TSP means TSP where costs between sites are time-inhomogeneous.
Furthermore, the agent exhibits critical properties in some benchmark data.
These results suggest that the agent performs adaptive travel using limited information.
Our results might be applicable to nonclairvoyant optimization problems.
American Psychological Association (APA)
Sakiyama, Tomoko& Arizono, Ikuo. 2017. Can the Agent with Limited Information Solve Travelling Salesman Problem?. Complexity،Vol. 2017, no. 2017, pp.1-6.
https://search.emarefa.net/detail/BIM-1143741
Modern Language Association (MLA)
Sakiyama, Tomoko& Arizono, Ikuo. Can the Agent with Limited Information Solve Travelling Salesman Problem?. Complexity No. 2017 (2017), pp.1-6.
https://search.emarefa.net/detail/BIM-1143741
American Medical Association (AMA)
Sakiyama, Tomoko& Arizono, Ikuo. Can the Agent with Limited Information Solve Travelling Salesman Problem?. Complexity. 2017. Vol. 2017, no. 2017, pp.1-6.
https://search.emarefa.net/detail/BIM-1143741
Data Type
Journal Articles
Language
English
Notes
Includes bibliographical references
Record ID
BIM-1143741