Cargo Revenue Management: Bid-Prices for a 0-1 Multi Knapsack Problem
Revenue management is the practice of selecting those customers that generate the maximum revenue from a fixed and perishable capacity. Cargo revenue management differs from the well-known passenger revenue management problem by the fact that its capacity constraint is 2-dimensional, i.e. weight and volume, and that the weight, volume and profit of each booking request are random and continuous variables. This leads to a multi-dimensional on-line knapsack problem. We show that a bid-price acceptance policy is asymptotically optimal if demand and capacity increase proportionally and the bid-prices are set correctly. We provide a heuristic to set the bid-prices based on a greedy algorithm for the multi-knapsack problem proposed by Rinnooy Kan et al. (1993). A test case shows that these bid-prices perform better than the traditional LP-based bid-prices that do not perform well at all for this problem.
|cargo transportation, multi-dimensional knapsack, on-line knapsack, revenue management|
|Optimization Techniques; Programming Models; Dynamic Analysis (jel C61), Business Administration and Business Economics; Marketing; Accounting (jel M), Production Management (jel M11), Transportation Systems (jel R4)|
|ERIM Report Series Research in Management|
|Organisation||Erasmus Research Institute of Management|
Pak, K, & Dekker, R. (2004). Cargo Revenue Management: Bid-Prices for a 0-1 Multi Knapsack Problem (No. ERS-2004-055-LIS). ERIM Report Series Research in Management. Retrieved from http://hdl.handle.net/1765/1449