The Packing While Traveling Problem

Sergey Polyakovskiy, Frank Neumann

Abstract

This research addresses the Packing While Traveling (PWT) problem, a non-linear variation of the classic knapsack problem where the act of collecting items increases transportation costs by reducing vehicle velocity. The authors demonstrate that PWT is NP-hard even in the absence of capacity constraints. To solve this, the paper introduces a suite of high-performance exact and approximate solvers that integrate Mixed-Integer Programming (MIP) with Constraint Programming (CP). Experimental results show that these methods can handle massive instances with over 850,000 items, providing a robust framework for real-world logistics optimization where weight significantly impacts fuel consumption and travel time.

Introduction

In traditional logistics and routing models, transportation costs are typically assumed to be linear. However, physical reality dictates that a heavily loaded vehicle consumes more fuel and moves slower than an empty one. The Packing While Traveling (PWT) problem formalizes this reality. In this scenario, a vehicle follows a fixed route through a series of cities, each containing items with specific profits and weights. The objective is to select a subset of items that maximizes "total gain"—defined as the total profit minus the cost of the additional time and fuel spent hauling the extra weight.

Because the vehicle's velocity decreases linearly as weight increases, the travel time (distance divided by velocity) becomes a non-linear function. This non-linearity makes PWT significantly more complex than the standard knapsack problem, necessitating specialized algorithmic approaches.

Problem Complexity and Formalization

The authors prove that the unconstrained version of PWT (where the vehicle has infinite capacity) is NP-hard. This proof is established by reducing the Subset Sum Problem to PWT, demonstrating that even without physical limits, the trade-off between item profit and travel cost creates a computationally difficult search space.

A critical factor in the problem's difficulty is the Rent Rate ($R$), which represents the cost per unit of time. When $R$ is low, the problem approximates a standard knapsack problem; when $R$ is high, the weight penalties dominate, requiring a more selective strategy to maintain profitability.

Methodology

The paper proposes a multi-stage approach to solve the PWT problem efficiently:

1. Pre-processing and Pruning

The authors developed a scheme to identify "compulsory" items—those so profitable they should always be picked—and "unprofitable" items—those that never cover their own transport costs. By identifying these items early, the search space is significantly pruned before optimization begins. For uncorrelated items, this stage can discard over 30% of the items immediately.

2. Piecewise Linear Approximation

To handle the non-linear objective function (specifically the $1/v$ term for time), the authors utilize a piecewise linear approximation. By using straight-line segments to approximate the curve, they create tight lower and upper bounds within a Mixed-Integer Programming (MIP) framework, allowing for faster convergence.

3. Exact and Hybrid Solvers

  • MIP-based Solver: This uses linearization techniques to transform the non-linear problem into a standard linear mixed-integer program.
  • Branch-Infer-and-Bound (BIB): This hybrid approach combines Constraint Programming (CP) with the MIP-derived upper bounds. It employs "sequencing constraints" to deduce which items must be picked before others based on their profit-to-weight-impact ratio, effectively pruning large branches of the search tree.

Experimental Evaluation

The researchers evaluated their algorithms using a benchmark set (Set $B$) derived from classic Traveling Salesperson Problem (TSP) and Knapsack Problem (KP) instances. The testing included small instances (51 to 101 cities, up to 1,000 items) and massive instances (up to 85,900 cities and 860,000 items). They tested three item generation types: uncorrelated, uncorrelated with similar weights, and bounded strongly correlated (where profit is closely tied to weight).

Key Results

  • Optimality and Accuracy: The exact solvers successfully found optimal solutions for all small-scale test instances. For larger instances, the approximate model (LB100) proved incredibly accurate, often reaching a solution quality ratio ($ ho$) of 1.0 (optimal) while running in a fraction of the time.
  • Scalability: The approximate approach mastered massive instances with over 850,000 items in under four hours on a computational cluster, demonstrating practical utility for large-scale industrial logistics.
  • Computational Speedup: Utilizing sequencing constraints in the pre-processing stage for large unconstrained instances resulted in speedups of up to 400x.

Discussion and Future Work

While the solvers are highly effective for uncorrelated items, the authors acknowledge limitations regarding "strongly correlated" items. In these cases, where an item's profit is very close to its weight, the "gain" is marginal, making it difficult for pre-processing and sequencing constraints to trigger effectively.

Future research directions include:

  • The Traveling Thief Problem (TTP): Generalizing the model to cases where the route is not fixed, combining TSP and PWT.
  • Dynamic Routing: Modifying the model to allow the vehicle to skip cities entirely if the items available do not justify the travel cost.
  • Pickup and Delivery: Extending the non-linear cost model to scenarios where items are both picked up and dropped off at various points along the route.

Summary updated

Abstract

This paper introduces the Packing While Traveling problem as a new non-linear knapsack problem. Given are a set of cities that have a set of items of distinct profits and weights and a vehicle that may collect the items when visiting all the cities in a fixed order. Each selected item contributes its profit, but produces a transportation cost relative to its weight. The problem asks to find a subset of the items such that the total gain is maximized. We investigate constrained and unconstrained versions of the problem and show that both are NP-hard. We propose a pre-processing scheme that decreases the size of instances making them easier for computation. We provide lower and upper bounds based on mixed-integer programming (MIP) adopting the ideas of piecewise linear approximation. Furthermore, we introduce two exact approaches: one is based on MIP employing linearization technique, and another is a branch-infer-and-bound (BIB) hybrid approach that compounds the upper bound procedure with a constraint programming model strengthened with customized constraints. Our experimental results show the effectiveness of our exact and approximate solutions in terms of solution quality and computational time.
BibTeX
@article{polyakovskiy2017packing,
  author = {Sergey Polyakovskiy and Frank Neumann},
  title = {{The Packing While Traveling Problem}},
  journal = {Eur. J. Oper. Res.},
  year = {2017},
  url = {https://openreview.net/forum?id=-XkILzcAF7i},
}

Loading related content...

Figure