Neural Model Embedded Heuristics for Robust Traveling Salesman Problem with Interval Uncertainty

We explore the robust traveling salesman problem (RTSP) with interval uncertainty under the min-max regret criterion, which enhances the classic traveling salesman problem (TSP) by focusing on robustness. Our aim is to develop a conservative solution that minimizes the maximum deviation from the optimal routing time in the worst-case scenario. To achieve this, we integrate neural models into heuristic approaches, capitalizing on recent advancements in neural techniques. Specifically, we incorporate a pre-trained neural model into the tabu search framework, using it to refine the evaluation function. This novel integration streamlines the solution improvement process. Our experimental results underscore the effectiveness of this approach, showing that it handles various scales of the robust traveling salesman problem more efficiently and in less time compared to traditional heuristic methods.