On the Use of Iterative Problem Solving for the Traveling Salesperson Problem with Changing Time Window Constraints
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.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Solving the Traveling Salesperson Problem with Precedence Constraints by Deep Reinforcement Learning
This work presents solutions to the Traveling Salesperson Problem with precedence constraints (TSPPC) using Deep Reinforcement Learning (DRL) by adapting recent approaches that work well for regular TSPs. Common to these…
Deep Reinforcement Learningreinforcement-learningReinforcement Learning (RL)Optimising Tours for the Weighted Traveling Salesperson Problem and the Traveling Thief Problem: A Structural Comparison of Solutions
The Traveling Salesperson Problem (TSP) is one of the best-known combinatorial optimisation problems. However, many real-world problems are composed of several interacting components. The Traveling Thief Problem (TTP) ad…
Graph Neural Network Guided Local Search for the Traveling Salesperson Problem
Solutions to the Traveling Salesperson Problem (TSP) have practical applications to processes in transportation, logistics, and automation, yet must be computed with minimal delay to satisfy the real-time nature of the u…
Graph Neural NetworkDancing to the State of the Art? How Candidate Lists Influence LKH for Solving the Traveling Salesperson Problem
Solving the Traveling Salesperson Problem (TSP) remains a persistent challenge, despite its fundamental role in numerous generalized applications in modern contexts. Heuristic solvers address the demand for finding high-…
A weighted-sum method for solving the bi-objective traveling thief problem
Many real-world optimization problems have multiple interacting components. Each of these can be NP-hard and they can be in conflict with each other, i.e., the optimal solution for one component does not necessarily repr…