💻 computer science

The Traveling Thief Problem with Time Windows: Benchmarks and Heuristics

This paper introduces the Traveling Thief Problem with Time Windows (TTP-TW), a new variant relevant to real-world scenarios where goods can only be collected within specific intervals, and proposes a novel heuristic algorithm that outperforms adapted existing methods on newly created benchmark instances.

Original authors: Helen Yuliana Angmalisang, Frank Neumann

Published 2026-04-09

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Helen Yuliana Angmalisang, Frank Neumann

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a thief (let's call him "The Traveling Thief") who has just broken into a city full of houses. Your goal is simple: steal as much valuable stuff as possible and get out with a high profit.

But this isn't a normal heist. This paper introduces a much more complicated version of the game with three major twists:

The Heavy Backpack: You have a backpack with a weight limit. The heavier your backpack gets, the slower you walk.
The Time Windows: You can't just walk into any house whenever you want. Each house has a specific "opening time" (like a shop that only opens between 9:00 AM and 10:00 AM). If you arrive too early, you have to wait outside. If you arrive too late, the door is locked, and you get a penalty (or the whole plan fails).
The Rental Fee: You are renting the backpack by the hour. The longer your trip takes (because you are walking slowly or waiting for doors to open), the more money you lose.

The Problem:
The thief needs to figure out two things at the same time:

The Route: Which order should I visit the houses to minimize travel time?
The Loot: Which items should I steal? (Stealing a heavy TV might slow you down so much that you miss the next house's opening time, costing you more in rental fees than the TV is worth).

This is the Traveling Thief Problem with Time Windows (TTPTW). It's a nightmare for computers because changing your route changes your speed, which changes your arrival time, which might make you miss a door, which changes which items you can steal. It's a giant, tangled web of cause-and-effect.

The Old Ways (And Why They Failed)

The researchers tried using existing "smart thief" algorithms (like S4, S5, C5) and "smart route" algorithms (like LKH-3).

The Route Algorithms: These are great at finding the shortest path, but they don't care about the backpack weight or the time windows. They often send the thief to a house at 8:55 AM when the door doesn't open until 9:00 AM, or they send him there so late he misses it entirely.
The Thief Algorithms: These are good at picking items, but they assume the thief can go anywhere anytime. When you add strict time windows, these algorithms get stuck. They try to solve the puzzle, but the "feasible" area (where a solution actually works) becomes so tiny that they can't find it.

The Result: In many test cases, the old algorithms found zero working solutions. They were like a GPS that tells you to drive through a wall because it doesn't know the wall is there.

The New Solution: The "Dual Search" Algorithm (DSEA)

The authors created a new algorithm called DSEA (Dual Search Evolutionary Algorithm). Think of this as a super-smart thief coach who uses a two-pronged approach:

The "Smart Start" (Tour Initialization):
Instead of guessing a random route, the coach uses a special trick to build the first route. It looks at the time windows and the speed limits to create a path that is likely to work right from the start. It's like checking the traffic and store hours before you even leave the house, rather than just driving and hoping for the best.
The "Dual Search" (Two Types of Tweaks):
Once the coach has a starting plan, it tries to improve it using two different strategies simultaneously:
- The "Swap" Strategy: It swaps the order of two houses in the route to see if that saves time.
- The "Insert" Strategy: It moves a house to a different spot in the route.
The genius of DSEA is that it doesn't just fix the route; it constantly re-evaluates what to steal based on the new route. It's a continuous loop of: Change the path -> Recalculate the speed -> Check the time windows -> Adjust the loot.

The Experiments: Testing the Thief

The researchers created a new set of "heist scenarios" (benchmarks) with different levels of difficulty:

Loose Time Windows: Shops are open most of the day. (Easy mode).
Tight Time Windows: Shops are only open for 10 minutes. (Hard mode).
Different City Sizes: From small towns (51 houses) to massive metropolises (1,000 houses).

The Results:

The Old Guard: The old algorithms (S4, S5, LKH-3) mostly failed. They couldn't find a single valid plan in many of the tight scenarios. They were like a thief who keeps getting locked out.
The New Coach (DSEA): The new algorithm found valid solutions almost every time.
- DSEA1 (The "No-Clutter" Version): Interestingly, the best version of the new algorithm was the one that didn't try to constantly "fix" the loot list after every tiny change. It focused on exploring new routes and only decided on the final loot at the very end. It was like a thief who focuses on the path first and grabs whatever fits at the end, rather than constantly dropping and picking up items while walking.
- DSEA3 (The "Integrator"): This version was better for very specific, tricky scenarios where the loot and the route were tightly linked, but generally, the simpler approach won.

The Big Takeaway

This paper solves a real-world problem. Imagine emergency services (ambulances that must arrive within a specific time window) or food delivery (drivers who must pick up food at a restaurant and drop it off at a customer's house within a specific time, while managing the weight of the food).

The authors showed that to solve these complex, real-world puzzles, you can't just use old tools. You need a new approach that understands that route, weight, and time are all connected. Their new "Dual Search" method is like giving the thief a smartwatch, a map, and a calculator all in one, allowing him to navigate the tightest time windows and heaviest backpacks to make the most profit.

In short: They took a problem that was too hard for old computers to solve, built a new "smart thief" algorithm, and proved it can find solutions where everyone else was stuck staring at a locked door.

1. Problem Definition

The paper addresses the Traveling Thief Problem with Time Windows (TTPTW), a complex multi-component optimization problem that combines the Traveling Salesperson Problem (TSP) and the Knapsack Problem (KP) under strict temporal constraints.

Core Components:
- Routing: A thief must visit a set of cities starting and ending at city 1.
- Packing: At each city, the thief can choose to steal items (profit $p_j$ , weight $w_j$ ) subject to a knapsack capacity $W$ .
- Interdependence: The thief's travel speed is not constant; it decreases as the knapsack weight increases. This creates a feedback loop where packing decisions affect travel time, which in turn affects the feasibility of visiting subsequent cities.
- Time Windows (TW): Each city $i$ $i$ has a time window $[L_i, U_i]$ $[L_{i}, U_{i}]$ . The thief must arrive within this window.
  - If arrival is early ( $t < L_i$ ), the thief waits.
  - If arrival is late ( $t > U_i$ ), the solution is infeasible (hard constraint).
Objective: Maximize total profit minus the rental cost of the knapsack (which is charged per unit of time). The rental cost is heavily influenced by the total trip duration, which is affected by both the route and the cumulative weight carried.
Challenge: The addition of time windows drastically narrows the feasible search space. A route that is optimal for TSP may be infeasible for TTPTW due to waiting times or speed reductions caused by heavy loads.

2. Methodology

2.1 Benchmark Generation

The authors created a new set of benchmark instances based on existing TTP benchmarks (Polyakovskiy et al., 2014).

Time Window Generation: Windows were generated using a method similar to Dumas et al. (1995), controlling tightness via a parameter $l \in \{100, 1000, -100, -1000\}$ $l \in {100, 1000, - 100, - 1000}$ .
- Positive $l$ allows for some flexibility.
- Negative $l$ creates very tight windows, simulating real-world scenarios like emergency services.
Instance Types:
- Type A: Time windows are generated based on the optimal TSP route (easier to find feasible solutions).
- Type B: Time windows are generated based on random tours (harder, simulating real-world unpredictability).
Scale: Instances range from 51 to 1000 cities with varying item counts and knapsack correlations.

2.2 Adaptation of Existing Algorithms

The authors first attempted to adapt state-of-the-art algorithms for TTP (S4, S5, C5) and TSPTW (LKH-3, VSR-LKH-3) to TTPTW.

Adaptation: They incorporated time window violation checks and used a constraint-objective separation technique (Deb, 2000) to handle infeasibility.
Result: As shown in Table 1, these adapted algorithms performed poorly, often failing to find any feasible solution (0% feasible rate) on instances with tight time windows or large city counts. This highlighted the need for a specialized approach.

2.3 Proposed Algorithm: Dual Search Evolutionary Algorithm (DSEA)

To address the failures of existing methods, the authors proposed DSEA, an evolutionary algorithm designed specifically for TTPTW.

Key Components:
1. Novel Tour Initialization: Instead of using the standard Chained Lin-Kernighan (CLK) heuristic (which seeks the shortest path but ignores time windows), DSEA uses a scoring-based nearest neighbor approach.
  - It calculates a score for unvisited cities based on travel time and time window satisfaction.
  - It prioritizes cities that can be reached on time and penalizes those that would cause late arrivals.
  - This ensures the initial solution is likely feasible, a critical step given the narrow feasible space.
2. Dual Search Operators: DSEA employs two complementary operators in a single run:
  - 2-opt based (Topo/ITP): Reverses subtours to optimize the route.
  - Insertion based (Rain/IIP): Inserts cities into different positions.
  - The combination prevents the algorithm from getting stuck in local optima.
3. Packing Plan Repair: The paper investigates three variants of DSEA regarding how they handle the packing plan:
  - DSEA1: No explicit repair; generates the packing plan only at the end of the main loop.
  - DSEA2: Uses "Repack," a modified algorithm that removes heavy, low-profit items if they cause delays, then refills.
  - DSEA3: Integrates repair with the optimizer, updating the packing plan incrementally as the tour changes.

3. Key Contributions

Problem Formulation: First formal definition and investigation of the TTP with hard time window constraints (TTPTW).
New Benchmarks: Introduction of a comprehensive suite of TTPTW instances with varying time window tightness and instance types (A and B).
Algorithmic Innovation:
- Development of DSEA, which outperforms adapted state-of-the-art methods.
- Proposal of a time-window-aware tour initialization algorithm that significantly improves the feasibility of starting solutions.
Empirical Analysis: A rigorous comparison of packing plan repair strategies, revealing that not repairing the packing plan during the search (DSEA1) often yields better results than complex repair mechanisms, as it allows for more extensive tour exploration.

4. Experimental Results

The algorithms were evaluated over 30 independent runs with a stopping criterion of 1,000,000 Function Evaluations (FE).

Feasibility:
- Standard adapted algorithms (S4, S5, C5, LKH-3) achieved 0% feasible rates on many difficult instances (e.g., 225-A, 575-A).
- DSEA achieved high feasible rates (often 100%) across almost all instances, including those with very tight time windows.
Performance Comparison:
- DSEA1 (No Repair) emerged as the best variant overall, achieving the highest mean objective values in most instances. The authors attribute this to the fact that repair mechanisms consume computational resources that could be better spent exploring new tours.
- DSEA3 (Integrated Repair) performed well on specific small, strongly correlated instances but was generally outperformed by DSEA1.
- DSEA2 (Repack) performed the worst, likely due to the high computational cost of the repacking process.
Impact of Initialization: Applying the new tour initialization to existing algorithms (S4-Initial, S5-Initial) improved their feasible rates significantly compared to their non-initialized versions, but they still could not match the solution quality of DSEA.

5. Significance

Real-World Applicability: The TTPTW models critical real-world scenarios such as emergency response, home health care, and waste management, where both routing and resource selection are interdependent and time-critical.
Methodological Insight: The study demonstrates that for highly constrained multi-component problems, feasibility-driven initialization is more critical than complex repair mechanisms during the search process.
Future Work: The paper establishes a new benchmark and a strong baseline (DSEA) for future research in constrained multi-component optimization problems.

In conclusion, the paper successfully identifies that standard TTP and TSPTW heuristics fail under the combined pressure of speed-weight interdependence and time windows. The proposed DSEA, particularly the DSEA1 variant with its specialized initialization and lack of intermediate repair, provides a robust and superior solution for this challenging problem class.