On the Use of Iterative Problem Solving for the Traveling Salesperson Problem with Changing Time Window Constraints
For researchers and practitioners dealing with sequences of similar TSPTW instances, this work provides evidence that simple iterative initialization can improve solution quality over independent solving.
This paper investigates whether solving related TSPTW tasks sequentially with transfer from previous solutions outperforms solving each independently. Experiments on a multi-task benchmark show that an iterative protocol consistently beats from-scratch in progressive-relaxation settings and is competitive under swap-additive changes, with larger gains on harder instances.
In many real-world settings, problem instances that need to be solved are quite similar, and knowledge from previous optimization runs can potentially be utilized. We explore this for the Traveling Salesperson problem with time windows (TSPTW), which often arises in settings where the travel-time matrix is fixed but time-window constraints change across related tasks. Existing TSPTW studies, however, have not systematically compared solving such task sequences independently with sequential transfer from previously solved tasks. We address this gap using a multi-task benchmark in which each base instance is expanded into five related tasks under two environments: partial time-window expansion and swap-additive time reassignment. We compare a standard from-scratch protocol with an iterative protocol that initializes each task from the best tour of the previous task, using the popular local search approaches LNS, VNS, and LKH-3 under a common penalized-score objective. Our experimental results show that the iterative protocol is consistently superior in the progressive-relaxation setting and generally competitive under swap-additive changes, with improvements increasing on more difficult instances.