PaperlayerView exact revision on arXiv

Source-linked AI summary

The Time-Dependent Traveling Salesman Problem with Loose Time Windows

Francisco J. Soulignac

arXiv:2608.26360v1cs.DS

TL;DR

Loose time windows create larger search spaces and motivate extending exact TDTSPTW methods to weakly constrained instances. The paper develops a dynamic-programming framework combining bounded labeling, column generation, ng-memory augmentation, primal bounds, and selective network reduction, substantially improving exact solution capabilities while leaving algorithm selection across tightness regimes open.

  • Problem

    Loose time windows substantially enlarge the search space, motivating methods that extend exact TDTSPTW solution capabilities to weakly constrained instances.

  • Method

    The framework combines dynamic-programming labeling with bounded completion criteria, column generation, ng-memory augmentation, primal heuristics, and completion-bound-based network reduction.

  • Results

    The framework solves all instances with up to 40 customers and a large fraction of 60-customer instances within the time limit, including instances unsolved by previous methods.

  • Takeaways & Limitations

    Dynamic-programming-based methods appear effective for time-dependent routing without time windows and time-independent routing with loose time windows, while stronger ng-relaxations require careful balancing.

  • Takeaways & Limitations

    No single dynamic-programming-based strategy is likely to work uniformly across time-window tightness regimes, and the transition between regimes remains an open question.

Abstract

from arXiv · show

The time-dependent traveling salesman problem with time windows (TDTSPTW) generalizes the well-known traveling salesman problem with time windows by accounting the effects of congestion on travel times. In this paper, we develop an exact framework for the TDTSPTW with a makespan objective that extends the range of instances solvable to optimality under loose time windows while remaining effective across all levels of time-window tightness. Our framework relies on a dynamic-programming labeling algorithm and combines column generation, ng-memory augmentation, and exact search, using completion bounds for state-space sparsification, variable fixing, and exact search pruning. Embedded within a branch-and-price method, the framework solves all instances with up to 45 customers in a benchmark comprising more than 10,000 instances, including all instances without time windows with up to 50 customers.

1 Introduction

Loose time windows create a central challenge for exact TDTSPTW methods because they enlarge the feasible search space, while existing approaches remain limited in weakly constrained regimes. The paper responds with an iterative framework combining column generation, ng-memory augmentation, exact search, and completion-bound-based reductions.

  • Motivation: Loose time windows can matter more than customer count because they substantially enlarge the dynamic-programming search space.This pattern is observed in both TSPTW and TDTSPTW, with time-window width relative to the planning horizon predicting computational effort better than customer count.
  • Motivation: Exact methods remain challenged as TDTSPTW approaches routing without time-window constraints.The weakly constrained end includes deadline-only and no-window variants, where several benchmark instances remain difficult to solve exactly.
  • Motivation: The paper aims to extend the range of weakly constrained TDTSPTW instances that can be solved exactly.This objective directly targets the difficulty associated with loose or absent time-window restrictions.
  • Prior framework: Prior dynamic-programming frameworks use column generation, ng-relaxations, and progressively stronger pricing problems to guide exact solution.The earlier approach obtains dual information, enlarges ng-memories, and eventually performs exact search guided by backward completions.
  • Prior framework: The earlier framework is limited by demanding initial pricing, reused dual information, costly ng-memory enlargement, and fixed sequential phases, especially with loose windows.Loose windows leave many alternative cycles available after individual cycles are forbidden, reducing the payoff from iterative enlargement.
  • Contribution: The proposed framework iteratively lets column generation, ng-memory augmentation, exact search, sparsification, and incumbent improvement guide one another.Each iteration obtains a dual vector, strengthens ng-memories, and runs bounded exact search using completion information.
  • Contribution: An arc-position ng-memory structure uses arc and tour-position information to refine cycle handling under time-dependent travel costs.Position acts as a proxy for departure time, allowing cycles to be processed more selectively before combinatorial growth becomes prohibitive.
  • Results: All benchmark instances with up to 45 customers are solved, including cases where a previous method fails on no-window instances with only 20 customers.The results establish a new state of the art for exact TDTSPTW solution in loose or absent time-window regimes.

2 Problem Formulation and Solution Framework

The framework models time-dependent, FIFO routing with arc-position restrictions and certifies optimality through a master problem, dual bounds, network reduction, ng-memory augmentation, and exact search. Its iterative solver strengthens bounds, improves incumbents, reduces the network, and searches elementary tours until optimality is certified.

  • 2.1 Problem Statement: The framework defines a complete directed transport network with start and end depots, customer vertices, time-dependent travel times, and FIFO arc functions.A tour is an elementary path from the start depot to the end depot visiting every customer exactly once.
  • 2.1 Problem Statement: Time windows and ng-memories are attached to arc-position states, constraining traversal times and excluding repeated vertices from cycles.This representation associates each arc-position pair with a time window and memory set rather than assigning them only to vertices.
  • 2.1 Problem Statement: Earliest arrival is computed recursively with waiting, and an ng-feasible path must satisfy both memory and arc-position time-window constraints.The makespan equals the final earliest arrival for an ng-feasible path and T + 1 otherwise.
  • 2.1 Problem Statement: The TDTSPTW seeks an ng-feasible elementary tour of minimum makespan, while ng-memory defines relaxations rather than the underlying optimization problem.Every elementary tour is ng-feasible, so the memory structure supports relaxation and search without changing the elementary-tour definition.
  • 2.2 Certification of Optimality: Optimality certification searches for improving ng-feasible tours and uses a master problem whose infeasibility proves that no improving elementary tour exists.The same mechanism can certify infeasibility when the incumbent is an artificial tour with makespan T + 1.
  • 2.3 The σ-TDTSPTW: The σ-TDTSPTW minimizes reduced cost using vertex benefits σ, typically obtained from master-problem dual variables.When σ is dual feasible, the objective value δ equals a tour's reduced cost.
  • 2.3 The σ-TDTSPTW: The σ-bound is a lower bound on every elementary tour's makespan, and a bound at least as large as the incumbent certifies optimality.This bound supplies the central certificate used to terminate the framework.
  • 2.4 Overview of the framework: Each solver iteration increases the σ-bound, improves the incumbent, reduces the network, augments ng-memories, and performs exact search with completion bounds.The solver starts from an artificial incumbent and returns an optimal elementary tour or the artificial tour when no elementary tour exists.

3 Solving a σ-TDTSPTW

The paper solves σ-TDTSPTW pricing problems with forward and backward dynamic-programming labeling, ng-memory feasibility, dominance, and completion-bound pruning. These mechanisms support state-space sparsification and optimality certification while generating tours for column generation and ng-memory augmentation.

  • Forward labeling: Forward labels represent ng-feasible paths and store position, last vertex, makespan, profit, and memory in O(1) words.Extensions evaluate piecewise-linear travel times in O(1) time using arc-specific lookup tables.
  • Forward labeling: Dominance removes labels without affecting optimality when position, endpoint, makespan, profit, and memory inclusion satisfy Rule 1.Complete tours are exempt from dominance so they can enrich the master problem and ng-memories.
  • Forward labeling: Heuristic relax-all and relax-ng variants accelerate early pricing by weakening dominance, but their lb estimate is not guaranteed valid.Relax-all retains only profit comparison, while relax-ng also removes memory inclusion.
  • Backward labeling: Backward labeling fixes the target arrival time to incumbent makespan δ(r∗), avoiding an additional state variable while retaining information for pruning and fixing.Backward labels use latest-departure travel times and define bng-feasible suffixes analogously to forward paths.
  • Bounded labeling: Completion bounds discard forward labels that cannot combine with backward labels into a tour improving the incumbent, thereby certifying optimality when no improving tour remains.Compatibility requires matching positions and vertices, disjoint memories, and consistent forward and backward times.

4 Column generation

Column generation alternates restricted-master dual optimization with labeling-based pricing, progressively tightening the working network through staged sparsification. A primal heuristic improves incumbents and strengthens completion bounds, while retained columns and memory cleaning preserve useful information and reduce later effort.

  • Sparsification: Non-dominated pricing labels sparsify a working network, restricting subsequent pricing problems to tours considered more promising.Each phase resets the working network and tightens it until the σ-bound meets a stopping criterion controlled by κS.
  • Stages: The procedure uses consecutive stages that move from relax-all without sparsification through relax-ng and exact labeling with progressively stronger sparsification.Threshold ρ increases across the relaxed and exact stages before the final exact stage.
  • Procedure: Each column-generation iteration solves the restricted master, prices tours using the current labeling stage, adds negative reduced-cost tours, and updates the incumbent.The procedure outputs a dual vector σ and non-dominated forward labels after the final stage.
  • Primal heuristic: The primal heuristic tightens completion bounds through improved incumbents, reducing the labeling search space under a limited time budget.It is applied selectively to tours in the restricted master because processing every tour may be computationally prohibitive.
  • Additional acceleration: Retaining selected columns, shrinking time windows, backward tightening, and ng-memory cleaning preserve dual information and reduce dominance-comparison overhead.Artificially penalized ng-infeasible columns can still provide useful early dual information after memory augmentation.

5 Ng-memory augmentation (MA)

Ng-memory augmentation forbids undesirable cycles in an arc-position-specific manner, then alternates bounded labeling and cycle forbidding to strengthen the pricing relaxation. Its repeated iterations can reduce the bound gap enough for exact search to terminate before expensive pricing resumes.

  • Cycle forbidding: Cycle forbidding inserts cycle-start vertices into arc-position memories, removing all tours that traverse each selected inclusion-minimal cycle.Arc-position states make the elimination selective because feasibility and completion times depend on position.
  • Augmentation procedure: Augmentation alternates forward and backward bounded labeling with cycle forbidding while keeping the dual vector σ fixed.It selects low-δ tours, forbids their cycles, switches direction, and updates the gap threshold.
  • Computational trade-off: Several augmentation iterations can substantially enlarge ng-memories and make subsequent pricing problems expensive.This overhead typically arises when the lower-bound gap is small and bounded labeling is computationally efficient.
  • Horizon dependence: Backward labeling is performed for the current horizon before incumbent updates because tighter horizons can change which backward labels are dominated.Backward labels generated under the current horizon therefore cannot be safely reused for completion bounds under a tighter horizon.

6 Exact search

Exact search progressively tests candidate makespan thresholds between the lower bound and incumbent, using bounded backward and forward labeling to compute completion bounds. If an elementary tour is found at a threshold, the best such tour is optimal; otherwise that threshold is ruled out.

  • Threshold search: Exact search tests candidate thresholds lb < t0 < . . . < tk = δ(r∗) to reduce the gap between the lower bound and incumbent.Backward bounded labeling enumerates only elementary paths using forward labels from ng-memory augmentation.
  • Threshold search: If backward enumeration generates a tour, an elementary tour with makespan at most ti exists; forward enumeration then searches the same horizon to termination.Forward labeling uses backward labels to compute completion bounds.
  • Optimality certification: When forward enumeration generates an elementary tour, the minimum-δ tour is optimal; otherwise no elementary tour with makespan strictly below the tested threshold exists.Backward enumeration precedes forward enumeration because backward labels depend on their planning horizon.

7 Experimental results

The experiments evaluate B&P across time-window regimes and ablate sparsification and the primal heuristic. B&P is strongest on loose and absent time-window instances, while Fon23 remains faster in tight regimes.

  • Experimental setup: Experiments compare B&P with Ler22 and Fon23 across no, loose, moderate, and tight time windows under a one-hour limit.Instances are organized primarily by customer count and time-window width.
  • No time windows: B&P is about two orders of magnitude faster than Ler22 on commonly solved instances without time windows and solves substantially larger instances.On Rif20[T ], B&P solves most instances with up to 60 customers.
  • Loose and moderate time windows: B&P solves all instances with n ≤40 and most instances with n ∈{50, 60} under loose and moderate time windows, with a larger advantage over Fon23 for β ∈{0, 0.25}.For β = 0.5, B&P remains competitive with and overall slightly faster than Fon23.
  • Ablation studies: Sparsification reduces first-iteration time by roughly one-fourth to one-half, with most savings coming from column generation.It also substantially reduces the final gap when the primal heuristic is disabled, although the proposed interpretation is explicitly speculative.
  • Ablation studies: The primal heuristic usually yields smaller gaps and fewer arc-position states, while sparsification makes B&P faster than NoSP through savings in pricing, sparsification, and variable fixing.NoSP requires about 1.8 times the loose-window and 2.2 times the no-window time on half of the shared solved instances, with maxima of 4.5 and 5.2.

8 Conclusions

The paper presents an exact framework that extends dynamic-programming-based solution capabilities to loose or absent time windows. Its effectiveness depends on balancing stronger completion bounds against the computational effort and state-space growth needed to obtain them.

  • 8 Conclusions: The framework extends exact dynamic-programming methods to TDTSPTW instances with loose or absent time windows.It substantially improves upon Lera-Romero et al. (2022), solving all instances with up to 40 customers and many with 60 customers within the time limit.
  • 8 Conclusions: Dynamic programming appears particularly advantageous for time-dependent routing without time windows and time-independent routing with loose time windows.
  • 8 Conclusions: No single dynamic-programming strategy is uniformly effective across all time-window tightness regimes.Direct exact-search methods benefit from tight windows, whereas column generation and ng-relaxations become more worthwhile as windows loosen.
  • 8 Conclusions: The framework balances σ-bound strength against the computational effort required to obtain it.Column generation and ng-memory augmentation improve the σ-bound, while primal improvements and selective arc-position network reduction help prevent stronger ng-relaxations from causing prohibitive pricing-state growth.

Declaration of generative AI and AI-assisted technologies in the manuscript preparation process

The author used ChatGPT to assist with manuscript editing, refinement, and presentation of methodological and experimental material. The author states that the underlying scientific content, decisions, results, and interpretations remained their own.

  • Declaration of generative AI and AI-assisted technologies in the manuscript preparation process: ChatGPT assisted with sentence structure, organization, clarity, and scientific writing in English.
  • Declaration of generative AI and AI-assisted technologies in the manuscript preparation process: ChatGPT also assisted with presenting methodological details and experimental results.
  • Declaration of generative AI and AI-assisted technologies in the manuscript preparation process: The author provided the underlying scientific content, methodological decisions, experimental results, and interpretations.

A Primal heuristic

The primal heuristic converts potentially non-elementary tours into improved elementary tours through repair, destroy-and-repair, and local search procedures. Its insertion decisions prioritize time-window feasibility before completion time.

  • A Primal heuristic: The heuristic generates improved elementary tours from potentially non-elementary tours obtained during solution.It combines elementary conversion, destroy-and-repair, and local search using swap, 2-opt, and shift moves.
  • A Primal heuristic: Repeated visits are removed, missing customers are greedily reinserted, and destroy-and-repair repeatedly removes and reinserts consecutive customers.
  • A Primal heuristic: Insertions are evaluated first by total time-window violation and then by completion time.

B Ng-memory cleaning

The clean-ng method reconstructs the ng-memory structure while preserving which tours are ng-infeasible. It removes memory restrictions only when position-expanded feasibility analysis shows they are unnecessary.

  • B Ng-memory cleaning: For each customer z, the method builds a position-expanded digraph with vertices v_p and arcs selected according to the existing memory structure.M-infeasible tours visiting z at two positions correspond to paths between the corresponding layers.
  • B Ng-memory cleaning: Earliest arrivals and latest feasible departures determine whether feasible paths can traverse each candidate arc-position combination.These quantities are computed for every pair of layers using time-dependent Dijkstra’s algorithm.
  • B Ng-memory cleaning: A memory entry is retained exactly when the position-expanded graph contains a feasible path traversing its associated arc.The associated position-expanded vertices carry arc-position time windows [a(v_p), b(v,p)].
  • B Ng-memory cleaning: Clean-ng removes unnecessary memory restrictions while preserving the ng-feasibility status of all tours.This enables additional label dominances, especially after variable fixing or sparsification and time-window shrinking.

C Algorithm Configuration

The algorithm configuration combines staged column generation, completion-bound sparsification, variable fixing, ng-memory augmentation, exact search, and primal heuristics within a time-limited branch-and-bound framework.

  • Branching and Solver: Branch-and-bound uses best-bound search, evaluates n/2 fractional arcs, and retains up to min{3, k} candidates for restricted column generation.The solver also stops when successive σ-bound gap reductions satisfy specified thresholds, limiting work under the one-hour budget.
  • Column Generation: Column generation begins with relax-all labeling and continues through four relax-ng stages with relaxed stabilization.The root-node configuration seeks strong completion bounds early to support variable fixing and avoid repeated pricing.
  • Sparsification: The sparsification threshold ρ interpolates between the best reduced cost and δ(r∗), while its max term protects early stages from excessive arc removal.Here, r is the tour minimizing δ before sparsification.
  • Sparsification: The σ-bound parameter q′ controls sparsification frequency by requiring lb to close a fraction q′ of the gap to max{d∗, δ(r∗)}.At least ι = 5 pricing iterations occur between sparsification applications, and d∗ may lie above or below δ(r∗) depending on the stage.
  • Ng-memory Augmentation: Ng-memory initialization uses each vertex’s five closest customers, while augmentation initially performs at least four pricing solves in each direction.Later forward pricing continues only when the σ-bound improvement meets the κ threshold.
  • Exact Search: Exact search tests four equally spaced thresholds, each with a budget of max{10^6, k} non-discarded labels.The value k is the number of non-dominated labels in the preceding pricing problem.
  • Primal Heuristic: The primal heuristic allows n/2 non-improving iterations, removes a uniformly chosen subsequence of ⌊n/20⌋ to ⌊n/10⌋ customers, and uses first-improvement local search.Its time budget is t/5 after each column-generation phase and after each forward pricing problem.

D Extended Experimental Results

The extended-results tables aggregate missing benchmark outcomes for the TDTSP and for TDTSPTW instances across loose, moderate, and tight time windows.

  • Extended Results: Tables 7–9 aggregate results for benchmark instances considered in the main text but not reported there.
  • TDTSP: Table 7 reports missing results for benchmark instances of the TDTSP without time windows.
  • Loose and Moderate Time Windows: Table 8 reports missing results for TDTSPTW instances with loose and moderate time windows.
  • Tight Time Windows: Table 9 reports missing results for TDTSPTW instances with tight time windows.
Loading 2608.26360v1…