کنترل موجودی صندلی برای پروازهای متعدد و متوالی با رفتار انتخاب مشتری

This paper considers a seat inventory control problem in which flights depart sequentially and passengers purchase available seats depending on customer choice behavior. Customer choice behavior can lead to either a horizontal shift or a booking loss when a desired fare class is unavailable. This problem is mathematically challenging and intractable via exact mathematical models. As an alternative heuristic approach, this paper develops a simulation-based greedy grid-search algorithm and illustrates simulation experiments using the newly developed algorithm. This paper obtains encouraging numerical results with the approach proposed here, but additional studies are required for accommodating more general assumptions such as booking arrival patterns, booking control mechanisms (e.g., cancellation and overbooking) and strategic customer behavior.

In the airline industry, there are two basic types of seat management problems (Wollmer, 1992). In the first type, when the fare classes are first class and coach, passengers seated in different classes use different sections of the aircraft, and the seat management problem is to partition the aircraft into a fixed number of seats for each class. Different partitions require different cabin configurations that cannot be adjusted on short notice. In the second type, considered in this paper, passengers in all fare classes compete for the same seats. It is common practice for airlines to charge several different fares even for the same seat pool, and passengers paying higher fare usually have more flexibility while passengers paying lower fares have more restrictions. This practice exists in competitive environments because the airline industry is highly capital intensive. Specifically, the marginal cost of carrying an additional passenger is very low, while the fixed cost of a flight is extremely high. Therefore, each passenger’s fare only covers the marginal cost, but all passengers together must cover the fixed costs. A single fare class would allocate the fixed costs equally among all passengers, while multiple fare levels result in uneven allocation. Efforts to manage the revenue mix of passengers involve both pricing and seat inventory control. Although pricing has a direct impact on revenues, an airline can seldom change prices without taking the reactions of its competitors into account. The fare levels offered on flights are determined by pressures to match competitor fares in the same city-pair market in most situations. Seat inventory control is a tactical component of revenue management that is entirely under the control of each individual airline. This control has the potential of enabling an airline to influence total revenues on a flight-by-flight basis within a given price structure. Controlling the mix of fares sold for a particular flight is considered the most important aspect of fare competition, more important than the actual prices that are charged (Belobaba, 1987 and Belobaba, 1989). This paper considers a seat inventory control problem in which flights depart sequentially during a similar time-interval and passengers purchase available seats depending on individual customer choice behavior. When a desired fare class is unavailable, customer choice behavior can lead to either a horizontal shift to consider the next flight or a booking loss to leave the system. By assuming that all accepted passengers purchase a seat, this paper bypasses the variables of cancellation and overbooking. The related seat inventory control problem involves determining the number of seats that should be allocated to each fare class so as to maximize expected total revenue for a scheduled future flight leg departure. Many studies have assessed the problem of seat inventory control since 1972, when Ken Littlewood first introduced the application of mathematical models to the development of revenue management in the airline industry. Starting with Littlewood’s rule for two fare classes, these studies include not only the expected marginal seat revenue (EMSR) method for multiple classes, but also the optimal booking limits for single-leg flights, segment control, and origin–destination fare control (McGill & van Ryzin, 1999). Overviews of the literature are provided by Belobaba, 1987, Weatherford and Bodily, 1992, McGill and van Ryzin, 1999 and Boyd and Bilegan, 2003, and Chiang, Chen, and Xu (2007). While considerable progress has been made in seat inventory control studies, this paper first reviews the fundamental seat inventory control literature because it provides insights into the nature of seat inventory control problem and serves as a basis for the present study. Most of the fundamental seat inventory control research was conducted under the following assumptions: (1) low-before-high demand – booking requests arrive in strict fare sequence from lowest to highest as flight departure approaches; (2) independent demand for different fare classes; (3) no cancellations, no no-shows, and no overbooking; (4) single flight legs with no consideration of network effects; and (5) no batch booking. Table 1 summarizes the fundamental seat inventory control literature.The seat inventory control research presented in Table 1 can be classified by arrival pattern. In the airline context, the sequential booking classes assume that requests for bookings in particular classes are not interleaved; for example, all A-class requests arrive before any B-class requests. Although this assumption is rarely satisfied in practice, it is close enough to permit significant revenue gains using methods based on the assumption (McGill & van Ryzin, 1999). Compared with the sequential booking classes, the interspersed arrivals have liberal characteristics and assume an arrival process in which requests for booking in different classes do not arrive in any particular order. In addition to the sequential booking classes, some research has also considered a model in which booking time limits are fixed prior to booking the first customer. In this case, all requests that arrived before the booking time limits are accepted. Diversion in Table 1 is defined as the willingness of potential customers to purchase a seat in a different fare class from the one they originally requested or intended to purchase (Belobaba & Weatherford, 1996). Diversion usually occurs from a lower fare class to a higher fare class (i.e., diversion-up), when an airline decides to curtail further sales in the lower fare class. For example, a passenger, who cannot obtain a seat on his or her desired flight at the lowest advertised fare, might be willing to accept a seat in the next lowest fare class. The earliest consideration of the seat inventory control problem is Littlewood’s (1972) analysis of a simple, two-fare-class model on a single flight leg, which first presented the simple decision rule: an airline will continue to sell a discounted fare class as long as the revenue from selling that discounted fare class exceeds the revenue of full fare class times the probability of selling all remaining seats to full-fare class passengers. Pfeifer (1989) extended the simple, two-fare-class model by considering diversion, in which a customer might purchase a more expensive seat, if cheaper seats are not available. Methods for obtaining optimal booking limits for multiple fare classes using stochastic dynamic programming were provided by Wollmer, 1992 and Brumelle and McGill, 1993, and Robinson (1995). Besides using booking limits as decision variables for seat inventory control problems, Sen and Zhang (1999) and Lautenbasher and Stidham (1999) provided methods that considered additional booking time limits as decision variables. Next, for the interspersed arrival pattern, Belobaba, 1987 and Belobaba, 1989 extended Littlewood’s rule to multiple fare classes, introducing the concept of EMSR to heuristic booking policy for multiple fare classes. The EMSR method does not produce optimal booking limits except in the two-fare-class model, although it is particularly easy to implement. In the same stream, Curry, 1990 and Lee and Hersh, 1993, and Liang (1999) used stochastic dynamic programming to determine optimal booking policy. Lautenbasher and Stidham (1999) provided a unified model of this and other related work. Li and Oum (2002) provided a note on the rough equivalence of the optimum conditions of Wollmer, 1992 and Curry, 1990 and Brumelle and McGill (1993). Belobaba and Weatherford (1996) proposed corrections to the EMSR method in the presence of customer diversion. Other studies that modeled ‘buy-up’ include Weatherford et al., 1993 and Bodily and Weatherford, 1995, and Talluri and van Ryzin (2004). As mentioned earlier, all of the research cited above was based on the assumption of independent demands for different fare classes. However, Brumelle, McGill, Oum, Sawaki, and Tretheway (1990) examined a seat inventory control problem in which the demands of fare classes were stochastically dependent and showed that a variant of Littlewood’s rule was optimal for two fare classes, when discounted and full fare demands were statistically dependent, subject to a mild monotonicity assumption on the nature of the dependency. Most early seat inventory control studies assumed that customers were passive (Shen & Su, 2007). In other words, their modeling approaches assumed that customers do not engage in any decision-making processes and are simply governed by the demand profile specified at the outset. However, in reality, all customers do at some point actively evaluate alternatives and make choices. This suggests that customer decision processes when determining, for example, how much to pay, which product to buy, when to buy, etc., deserve some attention. Among several approaches to modeling customer decision processes, diversion is the early simple consideration. In Table 1, Pfeifer, 1989, Sen and Zhang, 1999, Weatherford et al., 1993, Bodily and Weatherford, 1995 and Belobaba and Weatherford, 1996, and Talluri and van Ryzin (2004) address diversion as customer choice behavior. Anderson and Wilson (2003) examined strategic customer behavior when the same seat on the same flight is offered at different fares at different times. In follow-up work, Wilson, Anderson, and Kim (2006) investigated how to set optimal booking limits when customers behave strategically. Shen and Su (2007) provided a detailed literature review of customer behavior modeling in revenue management. The literature reviewed above examines the issue of seat inventory control with or without consideration of customer behavior on a single flight in which passengers purchase different fare classes from a common seat inventory pool. However, in this paper we consider customer choice behavior over sequential multiple flights that depart sequentially during a similar time-interval, each drawing from a separate seat inventory. Some previous studies deal with the seat inventory control problem on multiple flights. Netessine and Shumsky (2005) examined the seat inventory control problem under the assumption that two airlines compete for passengers on the same flight leg with a firm-specific demand. If this demand is unmet, it overflows into a market demand serviced by all firms. Unlike Netessine and Shumsky (2005), under the assumption of no firm-specific demand, Li, Oum, and Anderson (2007) examined a seat allocation game between two airlines for flights with two fare classes. Zhang and Cooper (2005) considered the seat inventory control of multiple parallel single-leg flights in the presence of customer choice behavior. The simulation-based optimization approach seeks to identify optimal booking limits in airline revenue management. This approach can be classified into the model-based search approach and the model-free search approach. The model-based search approach was addressed by Bertsimas and de Boer (2005) and van Ryzin and Vulcano (2008). Based on a discrete model of capacity and demand, Bertsimas and de Boer (2005) utilized a stochastic gradient algorithm to identify the best booking limits on the surface of an objective function. Then van Ryzin and Vulcano (2008) analyzed a continuous model of the problem that retained most of the desirable feature of the Bertsimas–de Boer method, yet avoided many of its pitfalls. Basically, the model-based search approach is suitable for finding the global optimal solution when the objective function is convex or concave. However, without the certainty of the objective function’s convexity or concavity, the reliability of the searched solution depends on the initial starting solution, often identifying the local optimal solution. The model-free search approach was attempted by Gosavi, Ozkaya, and Kahraman (2007). Regardless of the shape of the objective function, the model-free search approach can be used to find the global optimal solution. Gosavi et al. (2007) utilized simultaneous perturbation in combination with simulated annealing to identify the best booking limits. Simultaneous perturbation is a relatively new technique for gradient-ascent and has the remarkable feature that its computational burden is not proportional to the number of decision variables. Simulated annealing is a well known meta-heuristic for discrete optimization. Other meta-heuristics such as the genetic algorithm and tabu search (Gendreau and Potvin, 2010 and Spall, 2003) are also applicable. The problem considered in this paper, seat inventory control for sequential multiple flights with customer choice behavior, is fundamentally different from the problems considered in the approaches described above. Until now, no studies have addressed the problem considered in this paper. Section 2 describes the problem statement, which includes a challenging analytic task and, more often than not, is analytically intractable. Section 3 explains the simulation-based greedy grid-search algorithm developed in this paper, and Section 4 presents the results of simulation experiments conducted by utilizing our newly developed algorithm. Section 5 concludes this paper.

This paper dealt with the seat inventory control problem in which flights depart sequentially and passengers purchase available seats depending on individual customer choice behavior. In order to solve the seat inventory control problem, we developed the SBGGSA and performed simulation experiments using the newly developed algorithm. For future studies, the seat inventory control problem may be extended in several ways. Future studies are required to model various booking arrival patterns. For example, this paper considered aggregate seat demands. Future studies need to include independent seat demands for fare classes in sequential or concurrent booking arrival patterns. Next, future studies are required to model various booking control mechanisms. For example, we consider partitioned booking control, because seat demands are aggregated in the sequential booking arrival pattern. Future studies should include various nesting modes (e.g., parallel nesting or serial nesting). Lastly, future studies are required to model various customer strategic behaviors. For example, our paper considers that customer choice behavior can lead to either horizontal shift or booking loss. Future studies need to include diversion, delaying purchases to a future point in time, and other factors.