Shift‐and‐merge technique for the DP solution of the time‐constrained backpacker problem

We formulate the time‐constrained backpacker problem as an extension of the classical knapsack problem (KP), where a ‘backpacker’ travels from a origin to a destination on a directed acyclic graph, and collects items en route within the capacity of his knapsack and within a fixed time limit. We present a dynamic programming (DP) algorithm to solve this problem to optimality, and a ‘shift‐and‐merge’ DP algorithm to solve larger instances. The latter is an extension of the list‐type DP, which has been successful for one‐dimensional KPs, to the two‐dimensional case. Computational experiments on a series of instances demonstrate advantage of the shift‐and‐merge technique over commercial MIP solvers.