A Heuristic Approach for the Robust Traveling Salesman Problem

The traveling salesman problem (TSP) is widely known as one of the most important NP-hard combinatorial optimization problems. In this study, we consider the robust traveling salesman problem (RTSP) under a min–max regret criterion with interval travel costs. The RTSP aims to find a tour that minimizes the difference between its objective function value and the optimal value when the real scenario is known in advance. We examine four methods, including a Benders-like decomposition method, a branch-and-cut algorithm, a fixed-scenario method, and an iterative dual substitution method. For the iterative dual substitution method, we discuss several possible implementations based on different mathematical models for the classical TSP. We further propose a new heuristic approach which we call the edge generation algorithm. The experimental results show that the proposed edge generation algorithm achieved superior performance compared to that of all of several benchmark methods for all the tested instances.