pith. sign in

arxiv: 2604.14745 · v1 · submitted 2026-04-16 · 💻 cs.NE

On the Use of Iterative Problem Solving for the Traveling Salesperson Problem with Changing Time Window Constraints

Hy Nguyen , Thanh Nguyen Pham , Helen Yuliana Angmalisang , Liam Wigney , Frank Neumann This is my paper

Pith reviewed 2026-05-10 09:17 UTC · model grok-4.3

classification 💻 cs.NE
keywords Traveling Salesperson ProblemTime WindowsIterative SolvingLocal SearchWarm StartDynamic ConstraintsBenchmark
0
0 comments X

The pith

Reusing solutions from prior tasks outperforms solving each Traveling Salesperson Problem with Time Windows instance independently when constraints change gradually.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper tests whether solving sequences of similar TSPTW instances can benefit from carrying over tours found on earlier tasks rather than starting fresh each time. It builds a benchmark by deriving five related tasks from each base instance under two change regimes: progressive time-window relaxation and swap-additive reassignment. An iterative protocol that seeds each new task with the best tour from the previous one is compared against independent runs, all using the same local-search solvers and a penalized objective that allows controlled violations. Experiments show the iterative method produces better final solutions under gradual relaxation and remains competitive under swaps, with the advantage growing on harder instances. This matters for real routing applications where time windows evolve but the underlying travel times stay fixed.

Core claim

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.

What carries the argument

The iterative protocol that initializes each new task from the best tour of the immediately preceding task, run under a common penalized-score objective with LNS, VNS, and LKH-3 local search.

If this is right

  • Progressive relaxation of time windows allows the iterative protocol to reach higher-quality tours than independent solving across the tested local-search methods.
  • Gains from iteration become larger as the base instances increase in size or difficulty.
  • Swap-additive time-window changes do not cause consistent degradation when the prior tour is reused.
  • All three local-search approaches (LNS, VNS, LKH-3) show measurable benefit from the warm-start initialization in the progressive-relaxation regime.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same warm-start pattern could be tested on other vehicle-routing problems whose constraints evolve over time while the distance matrix stays fixed.
  • Hybrid methods that combine the iterative protocol with occasional restarts or memory of multiple prior tours might further reduce the performance gap on swap-additive instances.
  • Measuring wall-clock savings rather than only solution quality would clarify whether the iterative protocol also reduces total computation time in practice.

Load-bearing premise

The five tasks generated from each base instance remain similar enough that a tour found on one task remains a useful starting point for the next under the penalized objective.

What would settle it

An experiment in which time-window changes are made sufficiently large or unstructured that reusing the prior tour produces worse final scores than independent solving on a majority of instances would falsify the reported advantage.

Figures

Figures reproduced from arXiv: 2604.14745 by Frank Neumann, Helen Yuliana Angmalisang, Hy Nguyen, Liam Wigney, Thanh Nguyen Pham.

Figure 1
Figure 1. Figure 1: Summary of Mann-Whitney U test outcomes for the partial time-window expansion setting across Tasks [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Mean feasibility success rate for the partial time-window expansion setting. only. Entries shown as “–” indicate that no successful run was obtained for that task-instance combination, and hence these quantities are undefined. The Stat column summarizes the Mann–Whitney U outcome: (+) means iterative is significantly better, (-) means iterative is significantly worse, and (*) means no statistically signifi… view at source ↗
Figure 3
Figure 3. Figure 3: Summary of Mann-Whitney U test outcomes for the swap-additive time-window setting across Tasks [PITH_FULL_IMAGE:figures/full_fig_p008_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Mean feasibility success rate for the swap-additive time-window setting [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript presents an empirical comparison of solving sequences of related TSPTW instances independently versus using an iterative protocol that warm-starts each new task from the best tour of the prior task. It constructs a multi-task benchmark by expanding base instances into five related tasks under two change models (partial time-window expansion and swap-additive reassignment), evaluates LNS, VNS, and LKH-3 under a shared penalized objective, and reports that the iterative protocol is consistently superior in the progressive-relaxation setting, competitive under swap-additive changes, and yields larger gains on harder instances.

Significance. If the results hold under closer scrutiny, the work supplies useful evidence that solution reuse can accelerate local search in gradually changing TSPTW settings common to logistics. The choice of three standard solvers and a uniform penalized objective enables direct, apples-to-apples comparison and is a methodological strength. The main caveat is that the observed advantages rest on an untested assumption of sufficient task similarity; quantifying that similarity would materially increase the practical value of the findings.

major comments (2)
  1. [Benchmark generation procedure] Benchmark generation procedure: the five tasks derived from each base instance are described as 'related' but no quantitative similarity metrics are supplied (e.g., average initial penalized cost of the carried-over tour on the new instance, fraction of violated windows, or tour-edit distance). This omission is load-bearing for the central claim that the iterative protocol benefits from warm-starting under the penalized objective.
  2. [Experimental results section] Experimental results section: directional superiority is reported across solvers and environments, yet no statistical tests (paired t-tests, Wilcoxon signed-rank, or confidence intervals) or details on the number of independent runs per instance are provided. Without these, it is difficult to judge whether the claimed increase in improvement on harder instances is reliable.
minor comments (1)
  1. The manuscript would benefit from an explicit statement of the penalized objective function (including the exact penalty coefficients) and the precise parameter settings used for LNS, VNS, and LKH-3 so that the experiments can be reproduced.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We are grateful to the referee for their thoughtful comments and for recognizing the potential utility of our work in logistics settings. We address the major comments below and will incorporate the suggested improvements in the revised manuscript.

read point-by-point responses

  1. Referee: [Benchmark generation procedure] Benchmark generation procedure: the five tasks derived from each base instance are described as 'related' but no quantitative similarity metrics are supplied (e.g., average initial penalized cost of the carried-over tour on the new instance, fraction of violated windows, or tour-edit distance). This omission is load-bearing for the central claim that the iterative protocol benefits from warm-starting under the penalized objective.

    Authors: We agree that the lack of quantitative similarity metrics weakens the support for our central claim. In the revised manuscript, we will include such metrics, including the average initial penalized cost of the carried-over tour, the fraction of violated time windows, and tour-edit distances for the sequences of tasks under both change models. This will help quantify the task similarity and better justify the benefits of the iterative protocol. revision: yes

  2. Referee: [Experimental results section] Experimental results section: directional superiority is reported across solvers and environments, yet no statistical tests (paired t-tests, Wilcoxon signed-rank, or confidence intervals) or details on the number of independent runs per instance are provided. Without these, it is difficult to judge whether the claimed increase in improvement on harder instances is reliable.

    Authors: We concur that statistical tests and details on experimental runs are necessary to establish the reliability of the results. We will revise the experimental results section to specify the number of independent runs per instance and to include statistical tests such as the Wilcoxon signed-rank test for paired comparisons between the independent and iterative protocols, along with confidence intervals. This will allow readers to assess the significance of the observed improvements, especially on harder instances. revision: yes

Circularity Check

0 steps flagged

No circularity: pure empirical protocol comparison

full rationale

The paper is an empirical study that generates sequences of related TSPTW instances under two change models and directly compares a from-scratch solving protocol against an iterative warm-start protocol using LNS, VNS, and LKH-3. No mathematical derivation, fitted parameter, or ansatz is presented as a prediction; the central claims rest on tabulated experimental outcomes (solution quality and runtime) across the generated benchmark. No self-citation is invoked to establish uniqueness or to forbid alternatives, and no quantity is defined in terms of itself. The similarity assumption underlying warm-start utility is an experimental design choice whose validity is left to the reported performance deltas rather than being enforced by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the domain assumption that local-search heuristics benefit from warm starts when problem instances are related through the described time-window modifications.

axioms (1)
  • domain assumption Local search methods (LNS, VNS, LKH-3) can be effectively warm-started with a feasible or near-feasible tour from a related prior instance under a penalized objective.
    This is the core premise enabling the iterative protocol.

pith-pipeline@v0.9.0 · 5498 in / 1186 out tokens · 50356 ms · 2026-05-10T09:17:50.866706+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 21 canonical work pages

  1. [1]

    New heuristic techniques for solving the multi-objective travelling salesman problem

    Ali Abbas Numman, Bayda Atiya Kalaf, Elena Cristina Rada, Maya Julian, Auday Shaban, Kareem Jasim, and Chafic Salamé. New heuristic techniques for solving the multi-objective travelling salesman problem. InAIP conference proceedings, volume 3486, Melville, 2026. American Institute of Physics

    work page 2026

  2. [2]

    Comparative analysis of enhanced metaheuristics for the colored traveling salesman problem

    Karuna Panwar. Comparative analysis of enhanced metaheuristics for the colored traveling salesman problem. Evol. Intell., 19(1):30, 2026

    work page 2026

  3. [3]

    Single- and multi-objective evolutionary algorithms for the knapsack problem with dynamically changing constraints.Theor

    Vahid Roostapour, Aneta Neumann, and Frank Neumann. Single- and multi-objective evolutionary algorithms for the knapsack problem with dynamically changing constraints.Theor . Comput. Sci., 924:129–147, 2022

    work page 2022

  4. [4]

    A matheuristic for the traveling salesman problem with positional consistency constraints.International Transactions in Operational Research, 2025

    Luís Gouveia, Ana Paias, and Mafalda Ponte. A matheuristic for the traveling salesman problem with positional consistency constraints.International Transactions in Operational Research, 2025

    work page 2025

  5. [5]

    The hybrid electric vehicle - traveling salesman problem with time windows.Eur

    Christian Doppstadt, Achim Koberstein, and Daniele Vigo. The hybrid electric vehicle - traveling salesman problem with time windows.Eur . J. Oper . Res., 284(2):675–692, 2020

    work page 2020

  6. [6]

    Yvan Dumas, Jacques Desrosiers, Éric Gélinas, and Marius M. Solomon. An optimal algorithm for the traveling salesman problem with time windows.Oper . Res., 43(2):367–371, 1995

    work page 1995

  7. [7]

    Ohlmann, and Barrett W

    Manuel López-Ibáñez, Christian Blum, Jeffrey W. Ohlmann, and Barrett W. Thomas. The travelling salesman problem with time windows: Adapting algorithms from travel-time to makespan optimization.Appl. Soft Comput., 13(9):3806–3815, 2013

    work page 2013

  8. [8]

    Using constraint programming and local search methods to solve vehicle routing problems

    Paul Shaw. Using constraint programming and local search methods to solve vehicle routing problems. In Michael J. Maher and Jean-Francois Puget, editors,Principles and Practice of Constraint Programming - CP98, 4th International Conference, Pisa, Italy, October 26-30, 1998, Proceedings, Lecture Notes in Computer Science, pages 417–431. Springer, 1998

    work page 1998

  9. [9]

    A general VNS heuristic for the traveling salesman problem with time windows.Discret

    Rodrigo Ferreira da Silva and Sebastián Urrutia. A general VNS heuristic for the traveling salesman problem with time windows.Discret. Optim., 7(4):203–211, 2010

    work page 2010

  10. [10]

    An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems

    Keld Helsgaun. An extension of the Lin-Kernighan-Helsgaun TSP solver for constrained traveling salesman and vehicle routing problems. Technical Report Technical Report, Roskilde University, Roskilde, Denmark, 2017

    work page 2017

  11. [11]

    Effective handling of dynamic time windows and its application to solving the dial-a-ride problem.Transp

    Timo Gschwind and Stefan Irnich. Effective handling of dynamic time windows and its application to solving the dial-a-ride problem.Transp. Sci., 49(2):335–354, 2015

    work page 2015

  12. [12]

    Kai Qin, Maoguo Gong, and Deyun Zhou

    Xiaolong Zheng, A. Kai Qin, Maoguo Gong, and Deyun Zhou. Self-regulated evolutionary multitask optimization. IEEE Trans. Evol. Comput., 24(1):16–28, 2020

    work page 2020

  13. [13]

    Insights on transfer optimization: Because experience is the best teacher.IEEE Trans

    Abhishek Gupta, Yew-Soon Ong, and Liang Feng. Insights on transfer optimization: Because experience is the best teacher.IEEE Trans. Emerg. Top. Comput. Intell., 2(1):51–64, 2018

    work page 2018

  14. [14]

    Ray Lim, Yew-Soon Ong, Phan Thi Hong Hanh, Abhishek Gupta, and Nengsheng Allan Zhang. Can route planning be smarter with transfer optimization? In Manuel López-Ibáñez, Anne Auger, and Thomas Stützle, editors,Proceedings of the Genetic and Evolutionary Computation Conference Companion, GECCO 2019, Prague, Czech Republic, July 13-17, 2019, pages 318–319. ACM, 2019

    work page 2019

  15. [15]

    On the use of matching algorithms to transfer solutions for the travelling salesperson problem

    Liam Wigney, Aneta Neumann, Yew-Soon Ong, and Frank Neumann. On the use of matching algorithms to transfer solutions for the travelling salesperson problem. In Bogdan Filipic, editor,Proceedings of the Genetic and Evolutionary Computation Conference, GECCO 2025, NH Malaga Hotel, Malaga, Spain, July 14-18, 2025, pages 845–853. ACM, 2025

    work page 2025

  16. [16]

    Enhanced evolution of parallel algorithm portfolio for vehicle routing problem via transfer optimization.IEEE Transactions on Evolutionary Computation, pages 1–1, 2025

    Tong Guo, Yi Mei, Mengjie Zhang, Ke Tang, Kaiquan Cai, and Wenbo Du. Enhanced evolution of parallel algorithm portfolio for vehicle routing problem via transfer optimization.IEEE Transactions on Evolutionary Computation, pages 1–1, 2025

    work page 2025

  17. [17]

    Evolutionary multitask optimization with adaptive knowledge transfer

    Hao Xu, Alex Kai Qin, and Siyu Xia. Evolutionary multitask optimization with adaptive knowledge transfer. IEEE Trans. Evol. Comput., 26(2):290–303, 2022

    work page 2022

  18. [18]

    Evolving scheduling heuristics via genetic programming with feature selection in dynamic flexible job-shop scheduling.IEEE Trans

    Fangfang Zhang, Yi Mei, Su Nguyen, and Mengjie Zhang. Evolving scheduling heuristics via genetic programming with feature selection in dynamic flexible job-shop scheduling.IEEE Trans. Cybern., 51(4):1797–1811, 2021

    work page 2021

  19. [19]

    Spatial-temporal knowledge transfer for dynamic constrained multiobjective optimization.IEEE Trans

    Zhenzhong Wang, Dejun Xu, Min Jiang, and Kay Chen Tan. Spatial-temporal knowledge transfer for dynamic constrained multiobjective optimization.IEEE Trans. Evol. Comput., 29(5):1990–2003, 2025

    work page 1990

  20. [20]

    Dynamic auxiliary task-based evolutionary multitasking for constrained multiobjective optimization.IEEE Trans

    Kangjia Qiao, Kunjie Yu, Boyang Qu, Jing Liang, Hui Song, Caitong Yue, Hongyu Lin, and Kay Chen Tan. Dynamic auxiliary task-based evolutionary multitasking for constrained multiobjective optimization.IEEE Trans. Evol. Comput., 27(3):642–656, 2023. 15 APREPRINT- APRIL17, 2026

    work page 2023

  21. [21]

    A two-commodity flow formulation for the traveling salesman and the makespan problems with time windows.Networks, 23(7):631– 640, 1993

    André Langevin, Martin Desrochers, Jacques Desrosiers, Sylvie Gélinas, and François Soumis. A two-commodity flow formulation for the traveling salesman and the makespan problems with time windows.Networks, 23(7):631– 640, 1993. 16

    work page 1993