Shift-and-merge technique for the DP solution of the time-constrained backpacker problem |
| |
Authors: | Byungjun You Takeo Yamada |
| |
Affiliation: | Department of Computer Science, The National Defense Academy, Yokosuka, Kanagawa 239-8686, Japan |
| |
Abstract: | 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. |
| |
Keywords: | Two-dimensional 0-1 knapsack problem Dynamic programming Combinatorial optimization |
本文献已被 ScienceDirect 等数据库收录! |
|