New Heuristic Approaches for the Min–Max Regret Traveling Salesman Problem

The traveling salesman problem (TSP) is widely known as one of the most important NP-hard combinatorial optimization problems. In this paper, we consider the min–max regret traveling salesman problem (MMR-TSP) with interval travel costs. The MMR-TSP aims to find a tour that minimizes the difference between its objective function value and the optimal value of the case in which the real scenario is known in advance. We examine five methods: a Benders-like decomposition method, a branch-and-cut algorithm, a fixed-scenario method, an iterated dual substitution method, and a gravitational search algorithm. For the iterated 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 core selection algorithm. The experimental results show that the proposed core selection algorithm achieved superior performance compared to all other methods we examined for benchmark instances up to 80 cities. Furthermore, for the instances with 1000 cites, our new algorithm obtained high-quality solutions with an average optimality gap of 2.7%, whereas existing methods failed to obtain feasible solutions or only obtained solutions with an average optimality gap above 100%.