The Packing While Traveling Problem

Sergey Polyakovskiy, Frank Neumann

TL;DR

This paper introduces the "Packing While Traveling" (PWT) problem, a novel non-linear knapsack variant where a vehicle collects items with profits and weights along a fixed route, incurring transportation costs that increase with collected weight. The authors develop pre-processing techniques, lower/upper bounds, and exact algorithms (MIP and Branch-Infer-and-Bound) to solve this NP-hard problem, demonstrating their effectiveness on various instance types.

What Problem Does This Paper Address?

The authors tackle a real-world optimization challenge: deciding which items to collect while traveling a fixed route to maximize overall profit. Traditional vehicle routing problems often assume linear transportation costs. However, in reality, factors like vehicle weight (from collected items) directly impact fuel consumption and thus transportation costs, creating a non-linear relationship. This paper formalizes this by introducing the Packing While Traveling (PWT) problem. The core challenge is to balance the profit gained from items against the increased transportation cost incurred by their weight, all within a fixed travel order. They also consider a version where the vehicle's capacity is not a strict constraint (PWT^u).

Methods

The paper proposes several innovative methods:

  • Pre-processing Scheme: A crucial step to reduce problem size by identifying and discarding "unprofitable" items (those whose profit doesn't outweigh their transportation cost increase) and identifying "compulsory" items (those that must be included for an optimal solution). This significantly speeds up subsequent computations.
  • Lower and Upper Bounds: They employ mixed-integer programming (MIP) with piecewise linear approximation to derive lower and upper bounds for the objective function. This is a standard technique for handling non-linearities.
  • Exact Approaches:
    • MIP-based approach: This method uses linearization techniques to transform the non-linear problem into a solvable mixed-integer linear program.
  • Branch-Infer-and-Bound (BIB) Hybrid Approach: This combines constraint programming (CP) with their upper bound procedure. CP is used for domain reduction and inference, while the upper bound helps prune the search tree.
  • Sequencing Constraints: Novel constraints are derived to establish priorities among items, further speeding up the reasoning process within their algorithms.

Datasets

The authors use benchmark instances from Polyakovskiy et al. (2014), which are based on TSPLIB instances augmented with items distributed across cities. They consider different item generation types (uncorrelated, uncorrelated with similar weights, and bounded strongly correlated) and varying vehicle capacities.

Key Insights and Ideas

  • Non-linearity is Key: The paper highlights that real-world transportation costs are often non-linear, making standard linear models insufficient. The PWT problem captures this crucial aspect.
  • Pre-processing is Powerful: The effectiveness of identifying and removing unprofitable items and compulsory items is a significant finding, drastically reducing problem complexity.
  • Hybrid Approaches Shine: Combining CP with MIP-based techniques (like in the BIB approach) offers a powerful way to tackle complex combinatorial problems by leveraging the strengths of both paradigms.
  • Instance Type Matters: The performance of algorithms varies significantly across different instance types (e.g., "b-s-corr" instances are harder for pre-processing). This suggests that problem structure plays a vital role in solution difficulty.

Key Results

  • NP-Hardness: Both constrained (PWT) and unconstrained (PWT^u) versions of the problem are proven to be NP-hard.
  • Pre-processing Efficiency: The pre-processing scheme effectively reduces the number of items and auxiliary variables, leading to significant speedups (e.g., up to ~400 times faster pre-processing for LB100).
  • Approximate Approach (LB100): This method is very fast and provides good quality approximate solutions, offering a strong trade-off between computational time and solution quality. It can solve large instances within reasonable time limits.
  • Exact Approaches (MIP and BIB): These methods can solve small instances to optimality quickly. For larger instances, BIB, especially with sequencing constraints, shows strong performance. The BIB approach, in particular, demonstrates effectiveness in pruning the search space.
  • Instance Hardness: "Uncorr-s-w" type instances are found to be harder for MIP compared to other types, which is an interesting deviation from classical knapsack problem behavior.

Limitations and Future Work

  • Pre-processing for b-s-corr: The pre-processing scheme is less effective for "b-s-corr" type instances, where item profit is close to its weight.
  • Large Instance Complexity: While the approximate approach handles large instances well, exact methods still face significant computational challenges for very large problem sizes.
  • Future Work: The authors suggest generalizing the problem to the Traveling Thief Problem (where city order can be changed) and considering scenarios where cities can be skipped if they offer no benefit. They also mention the possibility of extending the model to incorporate more complex non-linear cost functions, such as those relating fuel consumption to speed and load.

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},
}
Figure