  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.

Data Structures and Algorithms