Decision Models for the Knapsack Problem

In this thesis, the effectiveness of various proposed strategies for the accept/reject decision regarding the knapsack problem with items with stochastic returns and capacity requirements are analyzed. The knapsack problem is a problem with a list of items with each its own return and capacity requirements. Such kinds of knapsack problems are common in air cargo revenue management in the booking process for free-sale cargo. The goal is to maximize returns while not exceeding knapsack capacities. The most common strategy is to accept requests whenever their return per capacity unit is at least equal to some threshold value. It is shown that even when setting these threshold values optimally, more complex decision strategies exist that perform better. These strategies include making the threshold value variable over the booking period, dividing the available capacity over several buckets with each its own threshold value and a strategy combining both. The results show that the last strategy combines the benefits of the two individual strategies and significantly outperforms them. However, determining the optimal decision variables for this strategy was found to be a very difficult problem in practice. A dynamic programming algorithm for the accept/reject decision is also proposed which performs better than the best found heuristic solutions in any other strategy in multidimensional cases.