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

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.