A Fully Polynomial Time Approximation Scheme for Packing While Traveling

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

TL;DR

This paper introduces the first Fully Polynomial Time Approximation Scheme (FPTAS) for the "Packing While Traveling" (PWT) problem—a complex scenario where a vehicle's travel cost increases as it picks up items along a fixed route. The authors provide an exact dynamic programming approach and a provably efficient approximation that outperforms previous state-of-the-art integer programming methods in both speed and scalability.

What Problem Does This Paper Address?

The authors tackle the Packing While Traveling (PWT) problem, which is a core component of the more famous Traveling Thief Problem (TTP).

In a standard Knapsack Problem, you pick items to maximize profit without exceeding a weight limit. In a Traveling Salesperson Problem, you find the shortest route. PWT combines these with a realistic twist: the heavier the vehicle gets, the slower it moves and the more it costs to operate.

Specifically, the PWT assumes the route is already fixed, but the "thief" must decide which items to pick up at various cities to maximize total profit minus the weight-dependent travel costs. Because the cost function is non-linear and the objective value can actually be negative (if travel costs exceed item profits), the problem is not just NP-hard to solve, but also mathematically "tricky" to approximate.

Methods

The researchers developed two primary algorithmic contributions:

  1. Exact Dynamic Programming (DP): They designed a DP approach that processes items in the order they appear on the route. It builds a table where each entry represents the maximum benefit for a specific total weight. While this runs in pseudo-polynomial time (dependent on the total weight capacity), it serves as the foundation for their approximation.
  2. FPTAS (Fully Polynomial Time Approximation Scheme): To handle larger instances where exact DP is too slow, they created an FPTAS. Since the original objective function can be negative (making standard approximation ratios meaningless), they redefined the goal: maximize the gain over the baseline travel cost (the cost of traveling the route empty). By rounding the profit values and using dominance relations to prune the DP table, they guaranteed a solution within $(1 - \epsilon)$ of the optimum in time polynomial to the input size and $1/\epsilon$.

Datasets

The algorithms were evaluated using the standard TTP benchmark set, specifically:

  • eil101 instances: A family of problems based on 101 cities with various item types (uncorrelated, uncorrelated with similar weights, and bounded strongly correlated).
  • Large Range Instances: The authors generated new, more difficult versions of these benchmarks with significantly larger profit and weight ranges (up to $10^7$) to test the limits of the DP and FPTAS.

Key Insights and Ideas

  • The "Baseline" Shift: A major hurdle was that the objective function $B(x)$ can be negative. Standard approximation theory doesn't play well with functions that cross zero. The authors' "aha moment" was shifting the objective to $B'(x) = B(x) - B(\emptyset)$. This represents the added value of picking items, which is always non-negative, allowing for a valid FPTAS.
  • Convexity is Key: The FPTAS relies on the fact that travel time per unit distance is a monotonically increasing and convex function of weight. This mathematical property ensures that the rounding errors in the FPTAS don't compound uncontrollably.
  • Dominance Pruning: To keep the DP efficient, they only store "non-dominated" entries—meaning if two sets of items have the same rounded profit, they only keep the one that weighs less.

Key Results

  • Speedup: The DP approach was dramatically faster than previous methods like Mixed Integer Programming (MIP). For example, on one 1,000-item instance, the previous state-of-the-art took 35 minutes, while the new DP approach took only 15 seconds.
  • Scalability: On "Large Range" instances where previous exact methods failed or took hours, the DP and FPTAS provided solutions in seconds or minutes.
  • Accuracy: Even with a relatively large $\epsilon$ (error tolerance), the FPTAS often found the true optimal solution or something extremely close to it, maintaining 100% accuracy on many standard benchmarks while running much faster than approximate MIP solvers.

Limitations and Future Work

  • Fixed Route Constraint: The biggest limitation is that this paper assumes the route is already decided. In the full Traveling Thief Problem, the route and the packing plan must be optimized simultaneously, which is significantly more complex.
  • Weight Dependency: The current DP table size depends on the number of possible weights (or rounded profit values). If the capacity $W$ is astronomical and profits are highly varied, even the DP might struggle without the FPTAS rounding.
  • Future Directions: The authors suggest that this PWT solver could be integrated as a "sub-routine" into larger meta-heuristic solvers for the full TTP, potentially leading to a new state-of-the-art for the combined routing and packing problem.

Summary updated

Abstract

Understanding the interaction between different combinatorial optimization problems is a challenging task of high relevance for numerous real-world applications including modern computer and memory architectures as well as high performance computing. 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 Problem (PWTP) 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.
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},
}

Loading related content...

Figure