A new multiagent reinforcement learning algorithm to solve the symmetric traveling salesman problem

Subtitle:

Article type: Research Article

Authors: Alipour, Mir Mohammad^* | Razavi, Seyed Naser

Affiliations: Department of Computer Engineering, Faculty of Electrical and Computer Engineering, University of Tabriz, Tabriz, Iran

Correspondence: [*] Corresponding author: Mir Mohammad Alipour, Department of Computer Engineering, Faculty of Electrical and Computer Engineering, University of Tabriz, Tabriz, Iran. Tel.: +98 912 3956383; Fax: +98 41 36388557; E-mail:mohammad.alipour@tabrizu.ac.ir

Abstract: Travelling salesman problem (TSP) looks simple, however it is an important combinatorial problem. Its computational intractability has attracted a number of heuristic approaches to generate satisfactory, if not optimal solutions. In this paper, we present a new algorithm for the Symmetric TSP using Multiagent Reinforcement Learning (MARL) approach. Each agent in the multiagent system is an autonomous entity with personal declarative memory and behavioral components which are used to tour construction and then constructed tour of each agent is improved by 2-opt local search heuristic as tour improvement heuristic in order to reach optimal or near-optimal solutions in a reasonable time. The experiments in this paper are performed using the 29 datasets obtained from the TSPLIB. Also, the experimental results of the proposed method are compared with some well-known methods in the field. Our experimental results indicate that the proposed approach has a good performance with respect to the quality of the solution and the speed of computation.

Keywords: Traveling salesman problem (TSP), multiagent reinforcement learning (MARL), 2-opt local search heuristic

DOI: 10.3233/MGS-150232

Journal: Multiagent and Grid Systems, vol. 11, no. 2, pp. 107-119, 2015