Home | Business News | Browse by Publication | O | Operations Research

Using Lagrangian relaxation to compute capacity-dependent bid prices in network revenue management.

Article Excerpt
We propose a new method to compute bid prices in network revenue management problems. The novel aspect of our method is that it explicitly considers the temporal dynamics of the arrivals of the itinerary requests and generates bid prices that depend on the remaining leg capacities. Our method is based on relaxing certain constraints that link the decisions for different flight legs by associating Lagrange multipliers with them. In this case, the network revenue management problem decomposes by the flight legs, and we can concentrate on one flight leg at a time. When compared with the so-called deterministic linear program, we show that our method provides a tighter upper bound on the optimal objective value of the network revenue management problem. Computational experiments indicate that the bid prices obtained by our method perform significantly better than the ones obtained by standard benchmark methods.

Subject classifications: dynamic programming/optimal control: applications; probability: stochastic model applications.

Area of review: Revenue Management.

History: Received April 2006; revisions received March 2007, November 2007; accepted April 2008. Published online in Articles in Advance February 9, 2009.

**********

The idea of bid prices forms a powerful tool for solving network revenue management problems. This idea associates a bid price with each flight leg that captures the opportunity cost of a unit of capacity. An itinerary request is accepted only if there is enough capacity and the revenue from the itinerary request exceeds the sum of the bid prices associated with the flight legs that are in the requested itinerary; see Williamson (1992) and Talluri and van Ryzin (1998). One of the traditional approaches in the literature for computing bid prices involves solving a deterministic linear program. However, this linear program tends to be somewhat crude in the sense that it only uses the expected numbers of the itinerary requests that are to arrive until the time of departure and does not incorporate the probability distributions or temporal dynamics of the arrivals of the itinerary requests.

In this paper, we propose a new method to compute bid prices in network revenue management problems. Our method is motivated by the following intuitive observation. The network revenue management problem is difficult because if we accept an itinerary request, then we have to consume the capacity on every flight leg that is in the requested itinerary. We relax this requirement by using Lagrangian relaxation. In particular, we allow ourselves to individually accept or reject the flight legs that are in a requested itinerary. When we allow such "partially accepted" itineraries, the problem decomposes by the flight legs and we can concentrate on one flight leg at a time. This approach provides a method to compute bid prices that explicitly considers the temporal dynamics of the arrivals of the itinerary requests. Furthermore, the bid prices computed in this manner depend on the remaining leg capacities, which is a feature lacking in the existing methods.

Our work builds on previous research. Hawkins (2003) and Adelman and Mersereau (2008) develop a Lagrangian relaxation method for what they call weakly coupled dynamic programs. In these dynamic programs, the evolutions of the different components of the state variable are affected by different types of decisions, and these different types of decisions interact through a set of linking constraints. The authors propose relaxing the linking constraints by associating Lagrange multipliers with them. In this paper, we show that the network revenue management problem can be viewed as a weakly coupled dynamic program. In addition, the Lagrangian relaxation method in Hawkins (2003) and Adelman and Mersereau (2008) runs into computational difficulties when applied to the network revenue management problem. Specifically, this method requires finding a good set of Lagrange multipliers by minimizing the so-called dual function and the dual function may involve thousands of dimensions. We show that it is indeed possible to minimize the dual function efficiently by using standard subgradient optimization.

Network revenue management is an active area of research. The idea of bid prices dates back to Simpson (1989) and Williamson (1992), where the authors use the deterministic linear program mentioned above to compute bid prices. Talluri and van Ryzin (1998) give a careful analysis of the policies that are based on bid prices and point out that the idea of bid prices is equivalent to using linear value function approximations in the dynamic programming formulation of the network revenue management problem. Talluri and van Ryzin (1999) propose a randomized version of the deterministic linear program that uses actual samples of the itinerary requests that are to arrive until the time of departure. Their goal is to remedy the fact that the deterministic linear program only uses the expected numbers of the itinerary requests. Phillips (2005) describes a sequential estimation procedure to compute bid prices. This procedure builds on the popular expected marginal seat revenue heuristic of Belobaba (1987) and addresses the probabilistic nature of the itinerary requests. Bertsimas and Popescu (2003) propose a method that captures the total opportunity cost of the leg capacities consumed by an itinerary request more accurately. Their method essentially uses nonseparable and concave value function approximations. Adelman (2007) computes bid prices by using the linear programming representation of the dynamic programming formulation of the network revenue management problem. His approach explicitly considers the temporal dynamics of the arrivals of the itinerary requests, but does not generate bid prices that depend on the remaining leg capacities. Computational experiments indicate that the bid prices obtained by the methods proposed by Talluri and van Ryzin (1999), Bertsimas and Popescu (2003), and Adelman (2007) tend to perform better than the ones obtained by the deterministic linear program. Finally, other methods, besides bid prices, have been proposed for solving network revenue management problems. We do not go into the details of these methods and refer the reader to Talluri and van Ryzin (2004) for a comprehensive coverage of the network revenue management field.

In this paper, we make the following research contributions. (1) We develop a new method to compute bid prices in network revenue management problems. Our method explicitly considers the temporal dynamics of the arrivals of the itinerary requests and generates bid prices that depend on the remaining leg capacities. (2) Our method is based on relaxing certain constraints by associating Lagrange multipliers with them. We show that we can efficiently find a good set of Lagrange multipliers by using standard sub-gradient optimization. (3) We show that our method provides an upper bound on the optimal objective value of the network revenue management problem. A well-known method to obtain such an upper bound is to use the aforementioned deterministic linear program. We show that the upper bound obtained by our approach is tighter than the one obtained by the deterministic linear program. (4) Computational experiments indicate that the bid prices obtained by our method perform significantly better than the ones obtained by standard benchmark strategies. Furthermore, our method noticeably improves the upper bounds obtained by these benchmark strategies.

The rest of this paper is organized as follows. Section 1 formulates the network revenue management problem as a dynamic program. Section 2 describes the Lagrangian relaxation idea and shows that our method provides an upper bound on the optimal objective value of the network revenue management problem. Section 3 establishes that our method obtains bid prices that depend on the remaining leg capacities. Section 4 shows that our method can efficiently find a good set of Lagrange multipliers by using standard subgradient optimization. Section 5 contrasts our method with the deterministic linear program. Section 6 presents computational experiments. Section 7 contains concluding remarks.

1. Problem Formulation

We have a set of flight legs that can be used to satisfy the itinerary requests that arrive randomly over time. At each time period, an itinerary request arrives and we have to decide whether to accept or reject this itinerary request. An accepted itinerary request generates a revenue and consumes the capacities on the relevant flight legs. A rejected itinerary request simply leaves the system.

The problem takes place over the finite horizon J = {1, ..., [tau]} and all flight legs depart at time period [tau] + 1. The set of flight legs is L and the set of itineraries is J. If we accept a request for itinerary j, then we generate a revenue of [f.sub.j] and consume [a.sub.ij] units of capacity on flight leg i. If flight leg i is not in itinerary j, then we naturally have [a.sub.ij] = 0. The initial capacity on flight leg i is [c.sub.jl]. The probability that a request for itinerary j arrives into the system at time period t is [p.sub.jt]. For notational brevity, we assume that [[SIGMA].sub.j[member of]J] [p.sub.jt] = 1 for all t [member of] J. If there is a positive probability of having no itinerary requests at time period t, then we can handle this by defining a dummy itinerary [psi] with [a.sub.[i[phi]]] = for all i [member of] L, [f.sub.[phi]] = and [P.sub.[[phi]t]] = 1 - [[SIGMA].sub.j[member of]J] [P.sub.jt]. We assume that the itinerary requests at different time periods are independent of each other. Throughout the paper, we do not differentiate between column and row vectors. We use [absolute value of A] to denote the cardinality of set A.

We let [x.sub.it] be the remaining capacity on flight leg i at time period t so that [x.sub.t] = {[x.sub.it]: i [member of] L} captures the remaining leg capacities at time period t. We capture the decisions at time period t by [u.sub.t] = {[u.sub.jt]: j [member of] J}, where [u.sub.jt] takes value one if we accept the itinerary request at time period t whenever this itinerary request is for itinerary j, and takes value zero if we reject the itinerary request at time period t whenever this itinerary request is for itinerary j. Because our ability to accept an itinerary request is limited by...

View this article FREE - Now for a Limited Time, try Goliath Business News
Free for 3 Days!