Decoupled Training Neural Solver for Dynamic Traveling Salesman Problem

Abstract

Deep reinforcement learning (DRL) methods have achieved remarkable success in solving static traveling salesman problems (TSP). However, dynamic TSP (DTSP), with the random appearance of new customers over time, introduces additional complexities that challenge DRL methods by the difficulty of obtaining optimized routing policy which lead to sub-optimal results and reduced training efficiency. To address these issues, we propose a decoupled training neural solver (DTNS) based on the encoder-decoder architecture, which is a novel approach that decouples the optimization of encoder and decoder, enhancing the model's ability to handle dynamic changes. Our method involves training under an Fore-Reveal condition first where the information of all customers nodes are known in advance to obtain optimized encoder and initialization for decoder and then fine-tuning the decoder in dynamic scenarios where dynamic customers are revealed over time. This training paradigm results in a flexible and globally optimized routing policy. Experimental results demonstrate that DTNS efficiently adapts to new customer requests in dynamic scenario, outperforming existing methods in dynamic routing environments.