In this thesis, we develop decomposition-based approximate dynamic programming methods for problems in capacity allocation and network revenue management. Noting that the dynamic programming formulation of these problems suffers from the “curse of dimensionality”, we demonstrate that a set of single-dimensional dynamic problems can be employed to provide approximate solutions to the original dynamic program. We show that the proposed approximations have two important characteristics: First, they provide relatively tight performance bounds on the optimal value of the stochastic optimization problem under consideration. Second, they give rise to policies that on average perform significantly better than a variety of benchmark methods found in the literature. We begin by focusing on network revenue management problems. We assume a profit maximizing airline operating a network of flight legs and processing itinerary requests arriving randomly over time. We consider several variants of the basic model and for each show that the dynamic programming formulation can be decomposed by flight legs into a set of single-leg revenue management problems. Furthermore, we demonstrate that the appropriate decomposition method gives rise to an upper bound on the optimal total expected revenue and that this upper bound is tighter than the upper bound provided by a deterministic linear program known from the literature. Finally, computational experiments show that the pol- icy based on the suggested value function approximation performs significantly better than a set of standard benchmark methods. In addition to network revenue management applications, we also consider a capacity allocation problem with a fixed amount of daily processing capacity. Here, the decision maker tries to minimize the cost of scheduling a set of jobs arriving randomly over time to be processed within a given planning horizon. The scheduling (holding) cost of a given job depends on its priority level and the length of its scheduled waiting period. In this setting, the decomposition approach that we suggest decomposes the problem by booking days. In particular, we replace the original dynamic program with a sequence of single-dimensional dynamic programs, each of which is concerned with capacity limitations on one particular booking day only. We show that our approach provides tight lower bounds on the minimum total expected holding cost. Furthermore, it gives rise to a scheduling policy that on average performs better than a variety of benchmark methods known from the literature.
展开▼
