A Fully Polynomial Time Approximation Scheme for Packing While Traveling

Frank Neumann, Sergey Polyakovskiy, Martin Skutella, Leen Stougie, Junhua Wu

Abstract

Understanding the interactions between different combinatorial optimization problems in real-world applications is a challenging task. Recently, the traveling thief problem (TTP), as a combination of the classical traveling salesperson problem and the knapsack problem, has been introduced to study these interactions in a systematic way. We investigate the underlying non-linear packing while traveling (PWT) problem of the TTP where items have to be selected along a fixed route. We give an exact dynamic programming approach for this problem and a fully polynomial time approximation scheme (FPTAS) when maximizing the benefit that can be gained over the baseline travel cost. Our experimental investigations show that our new approaches outperform current state-of-the-art approaches on a wide range of benchmark instances.

Introduction

The Packing While Traveling (PWT) problem represents a critical sub-component of the Traveling Thief Problem (TTP), a multi-component optimization challenge that merges the Traveling Salesperson Problem (TSP) with the Knapsack Problem (KP). While the TSP focuses on route efficiency and the KP on item value, the PWT introduces a realistic, non-linear dependency: as a vehicle collects items, its weight increases, which in turn reduces its speed and increases the operational cost of travel.

In this study, we address the PWT on a fixed route. The objective is to select a subset of items from various cities along the path to maximize total profit minus the weight-dependent travel costs. This problem is inherently difficult because the objective function can yield negative values if travel costs outweigh item profits, complicating standard approximation techniques.

Algorithmic Framework

1. Exact Dynamic Programming (DP)

We propose a dynamic programming approach that processes items sequentially according to their position on the fixed route. The algorithm constructs a state table where each entry represents the maximum benefit achievable for a specific total weight. By utilizing the order of cities, the DP effectively captures the cumulative impact of weight on the remaining travel segments. While this approach runs in pseudo-polynomial time—dependent on the total weight capacity—it provides an exact solution that serves as a benchmark for efficiency.

2. Fully Polynomial Time Approximation Scheme (FPTAS)

To address larger instances where exact DP becomes computationally expensive, we developed the first FPTAS for the PWT. The primary challenge was the potential for negative objective values, which typically invalidates standard approximation ratios. We overcame this by redefining the objective to maximize the gain over the baseline travel cost (the cost of traversing the route with an empty vehicle).

By rounding profit values and applying dominance relations to prune the DP table, the FPTAS guarantees a solution within $(1 - \epsilon)$ of the optimum. This ensures the algorithm remains efficient, with a runtime polynomial to both the input size and $1/\epsilon$.

Theoretical Insights

  • The Baseline Shift: Shifting the objective function to $B'(x) = B(x) - B(\emptyset)$ ensures the target value is always non-negative. This mathematical pivot allows for the application of approximation theory to a problem that was previously considered "tricky" to bound.
  • Convexity and Monotonicity: The FPTAS leverages the property that travel time per unit distance is a monotonically increasing and convex function of weight. This ensures that errors introduced by rounding do not compound exponentially as the vehicle progresses along the route.
  • Dominance Pruning: Efficiency is maintained by storing only "non-dominated" states. If two item sets result in the same rounded profit, the algorithm only retains the set with the lower weight, significantly reducing the search space.

Experimental Evaluation

Datasets

We evaluated our algorithms using the standard TTP benchmark set, including the eil101 instances (101 cities with various item correlations). Additionally, we introduced Large Range Instances with profit and weight values up to $10^7$ to test the scalability of the DP and FPTAS under extreme conditions.

Key Results

  • Computational Speedup: The DP approach demonstrated a massive performance advantage over existing Mixed Integer Programming (MIP) solvers. In a benchmark instance with 1,000 items, the previous state-of-the-art required 35 minutes to solve, whereas our DP approach reached the solution in just 15 seconds.
  • Scalability: On the new Large Range instances, where traditional exact methods often timed out or failed, both the DP and FPTAS provided solutions within seconds or minutes.
  • High Fidelity: Even with a generous error tolerance (large $\epsilon$), the FPTAS frequently identified the true optimal solution. It maintained 100% accuracy on many standard benchmarks while operating significantly faster than approximate MIP alternatives.

Conclusion

This research provides a robust foundation for solving the Packing While Traveling problem efficiently. By introducing an exact DP and a provably efficient FPTAS, we have significantly improved the state-of-the-art for this non-linear optimization problem. Future work involves integrating this PWT solver as a sub-routine within meta-heuristic frameworks to tackle the full Traveling Thief Problem, where both the route and the packing plan must be optimized simultaneously.

Summary updated

Abstract

Understanding the interactions between different combinatorial optimisation problems in real-world applications is a challenging task. Recently, the traveling thief problem (TTP), as a combination of the classical traveling salesperson problem and the knapsack problem, has been introduced to study these interactions in a systematic way. We investigate the underlying non-linear packing while traveling (PWT) problem of the TTP where items have to be selected along a fixed route. We give an exact dynamic programming approach for this problem and a fully polynomial time approximation scheme (FPTAS) when maximising the benefit that can be gained over the baseline travel cost. Our experimental investigations show that our new approaches outperform current state-of-the-art approaches on a wide range of benchmark instances.
BibTeX
@inproceedings{neumann2018fully,
  author = {Frank Neumann and Sergey Polyakovskiy and Martin Skutella and Leen Stougie and Junhua Wu},
  title = {{A Fully Polynomial Time Approximation Scheme for Packing While Traveling}},
  booktitle = {ALGOCLOUD},
  year = {2018},
  doi = {10.1007/978-3-030-19759-9\_5},
}
Figure