Can the Agent with Limited Information Solve Travelling Salesman Problem?

Tomoko Sakiyama and Ikuo Arizono

Complexity, 2017, vol. 2017, 1-6

Abstract:

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.

Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://downloads.hindawi.com/journals/8503/2017/9562125.pdf (application/pdf)
http://downloads.hindawi.com/journals/8503/2017/9562125.xml (text/xml)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:hin:complx:9562125

DOI: 10.1155/2017/9562125

Access Statistics for this article

More articles in Complexity from Hindawi
Bibliographic data for series maintained by Mohamed Abdelhakeem ().