Overview

Original Research

A NEW HYBRID APPROACH TO TRAVELLING SALESMAN PROBLEM BY REINFORCEMENT LEARNING AND IMPROVEMENT BY TWO-OPT ALGORITHM

Dr. T BRINDHA 1, and SAURABHEE SAKTHIVEL 2.

Vol 18, No 03 ( 2023 )   |  DOI: 10.17605/OSF.IO/7HYNM   |   Author Affiliation: Associate Professor, Department of Mathematics, PSGR Krishnammal College for Women, Coimbatore, Tamil Nadu, India 1; M.Sc Mathematics, Department of Mathematics, PSGR Krishnammal College for Women, Coimbatore, Tamil Nadu, India 2.   |   Licensing: CC 4.0   |   Pg no: 1910-1919   |   Published on: 30-03-2023

Abstract

Travelling Salesman Problem is a well-known problem in combinatorial optimization theory that is still being extensively studied up to date. Various approaches have been analyzed and developed to find an optimal solution to this problem. This paper focuses on a new hybrid approach to the Travelling Salesman Problem using Reinforcement Learning and its improvement by Two-Opt algorithm. The proposed algorithm has been applied to three real world problems, which are the three South Indian states namely, Tamil Nadu, Kerala and Andhra Pradesh which has 32, 16 and 27 cities respectively. The proposed algorithm is also compared to the classical algorithms, especially the Two- Opt algorithm to analyse and find the best of the two given here.

Keywords

TSP, Hybrid Approach, Reinforcement Learning, Two-Opt, RL and Improvement by Two-Opt