Solving Quadratic Traveling Salesman Problem with Deep Reinforcement Learning

There are many combinatorial optimization problems derived from the classic traveling salesman problem (TSP). The quadratic traveling salesman problem (QTSP) is one of them. It needs to consider the relationship between three successive nodes rather than two successive nodes. In literature, there are exact methods based on integer programming and approximate methods based on heuristics for solving QTSP. In this paper, we try to adopt deep reinforcement learning to tackle QTSP. We consider two classic QTSPs studied in the previous literature, namely the angular-metric TSP and the angular-distance-metric TSP. Both of them consider the turning angle for each node, and the angular-distance-metric TSP further considers the total traveling distance in the original TSP. The experimental results show that our method is superior to some typical heuristic methods in terms of solution quality, and better than the exact methods in terms of time.

I. Introduction

As a typical NP-hard combinatorial optimization problem, the traveling salesman problem (TSP) has been widely studied and achieved remarkable results [1]–[3]. Many variants of the classic TSP have also been investigated. The quadratic traveling salesman problem (QTSP) is one of them. It is inspired by the problem of finding the optimal Permuted Markov (PM) model [4] and the optimal Permuted Variable Length Markov (PVLM) model [5] for a given set of DNA sequences. This problem is important in bioinformatics and genome research for the recognition of transcription factor binding sites and splice sites.