Multi-Leg Seat Inventory Control Based on EMSU and Virtual Bucket

Abstract

Expected marginal seat revenue (EMSR) is a well-known method for airline seat inventory control airlines. However, this method employs a static model to study the dynamic reservation process, and does not take into account the risk tolerance of policy makers. Expected marginal seat utility (EMSU) replaces revenue by utility, which addresses the real situation of seat inventory control. However, there is still a lack of multi-leg seat control algorithms based on EMSU. Therefore, using EMSU and bucket algorithms, this paper applies the Markov decision-making process to simulate the flight reservation process and builds a dynamic multi-leg seat inventory control model. Experimental results validate the effectiveness of the proposed method.

1. Introduction

Airline seat inventory control is about “selling the appropriate seat to the right person at the right time” [1]. If all the airline's seats are sold at a cheap price, travellers on urgent business cannot buy short-notice tickets just before the plane takes off. On the other hand, if too many seats are allocated for travellers able to pay high prices, this may lead to many empty seats. Therefore, optimization of airline seats aims to allocate reasonable numbers of seats for the different levels of fare, in order to maximize flight revenue.

The most well-known airline seat inventory control method today is the expected marginal seat revenue (EMSR) method proposed by Belobaba [2]. Because this method is easy to understand and easy to implement, it was quickly adopted by many airline companies. EMSR has become the classic airline seat inventory control method and the normal foundation of seat optimization algorithms. But EMSR has two disadvantages. First, a reservation limit produced by EMSR cannot be changed as the reservation process progresses. In other words, the method is static. Secondly, the method does not consider the risk in the decision-making process [3]. To address these two shortcomings, the research community has recently proposed the expected marginal seat utility (EMSU) method [3–4]. EMSU has been applied in the single-leg seat control algorithm; however, for the multi-leg seat control problem there is not yet a sound solution. A popular method to address the multi-leg problem is the virtual bucket [2]. In this paper, a model based on the virtual bucket and EMSU ideas is proposed in order to solve the multi-leg problem.

2. Background and Previous Research

2.1 Introduction to EMSU

EMSU uses the expected marginal utility to replace the expected marginal revenue in the EMSR model [3]. The utility function is:

$u_{\gamma }(x)=-exp(-\gamma x),\gamma \in (0,1)$

(1)

The model determines the level of risk. EMSU is defined as below:

$\begin{array}{l}{V}_n^{\gamma }(c,i)=\hspace{0.17em}max\{exp(-\gamma a{r}_i)\cdot \hfill \\ \sum _{j=0}^k{p}_{\mathit{\text{jn}}}{V}_{n-1}^{\gamma }(c-a,j)\}\hfill \end{array}$

(2)

In Equation (2), c represents the number of remaining seats, i shows the requested class level, r_i represents the fare of class i, γ means the risk factor, P_jn indicates the probability of requesting the level of class j in stage n, and a means the accepted number of passengers in stage n.

2.2 Virtual Bucket

To solve the multi-leg seat allocation problem, we should consider not only the fare level (F), but also the interaction between routing origin (O) and destination (D). The virtual bucket method is potentially important to solve multi-leg seat allocation effectively [4].

The steps are:

1. For each ODF combination fare, several virtual levels (or “buckets”) are set. The value of each bucket is the average of the ODF fares represented.

2. Each ODF fare is mapped to the corresponding bucket.

3. Every bucket can be treated as one level in a single-leg problem, and we can use the composite nested EMSR method to allocate seats.

4. Seats are allocated for each ODF. When an ODF seat is requested, the request can be accepted only if the bucket has seats. A connected ODF request can be accepted when all segments have seats.

3. Model and Policies

The assumptions of this study include:

1. Each passenger can only request one seat.

2. There is no overbooking and there are no cancellations.

3. There are several levels of ticket from 1 to k, where the corresponding fare is r_i, 0 < r_k < r_k-1 < … < r₁.

4. The aircraft capacity at each stopover point remains the same.

The model of the booking stage is divided into N stages.

In each stage, one person at most will arrive. The probability of one passenger arriving is found in the Poisson process. p_jn shows the probability when class j is requested in stage n. The probability of no passenger arriving is:

$p_{0n}=1-{\sum }_{j=1}^k{p}_{\mathit{\text{jn}}}.$

(3)

3.1 model description

Markov decision processes are used to choose an action from the decision-making space, according to the various stages of decision-making. Decision-makers can also make a new decision according to the new state observed. This study uses Markov for dynamic decision-making in the booking process.

A Markov decision-making process includes the state space, action set, decision epochs, rewards and transition probabilities. In the model study herein, these are defined as follows.

1. State space: S={0,1…C}×{0,1…k}, where the first dimension stands for the remaining seat capacity and the second dimension is the fare class, with artificial fare class 0 with fare F0 = 0. A state (c, i) says that as c seats are remaining, we have a request for fare class i. Aircraft capacity is C, and the remaining capacity is the variable c, c ≤ C.

2. Action set:

   $\begin{array}{c}A(c,i)=\{0,1\},\\ \forall (c,i)\in S,i>0,A(c,0)=\left\{0\right\}\end{array}$

   (4)

   This represents the “reject” and “accept” decision for a given state.

3. Decision epochs correspond to the time periods: T={0,1,.N}, where N represents the departure of flight and 0 is the start of booking.

4. $\text{Transition probabilities}:\hspace{0.17em}{r}_n\left(\left(c,i\right),a\right)=a\cdot r_i,c>0$

   (5)

5. $\text{Rewards}:\hspace{0.17em}{q}_n\left(\left(c,i\right),a\left(c-a,j\right)\right)=p_{\mathit{\text{jn}}}$

   (6)

To combine EMSU and virtual bucket, first we should divide the bucket according to the multi-leg fares; second, we attach the bucket to the corresponding leg, and then we calculate the EMSU values for every leg using Equation 1.

Then, we determine the structured protection number of various stages. The structured protection number is different from the protection number in the EMSR model: it means that the air company can accept reservations only when the remaining capacity is greater than the protection number. The calculation method is as follows:

$\begin{array}{c}{y}_{i-1}^{*\gamma }\left(n\right)=max\{exp\left(-\gamma r_i\right)>\\ \frac{{{\sum }_{j=0}^k{p}_{\mathit{\text{jn}}}V}_{n-1}^{\gamma }\left(c,j\right)}{{{\sum }_{j=0}^k{p}_{\mathit{\text{jn}}}V}_{n-1}^{\gamma }\left(c-1,j\right)}\},c\in \{0,\dots n-1\}\end{array}$

(7)

With the protection number, it is then possible to make a decision when a request arrives. The expression is:

$f_n^{\gamma }\left(c,i\right)=\{\begin{array}{l}1,c>{\gamma }_{i-1}^{*\gamma }\left(n\right)\hfill \\ 0,c\le {\gamma }_{i-1}^{*\gamma }\left(n\right)\hfill \end{array}$

(8)

In Equation (8), only when the remaining capacity is larger than the number of seats left at stage n can the reservation for the long leg ODF be accepted.

3.2 The division of stage and the transition probabilities' setting

As stated above, we require N-stage booking stages and transition probabilities based on the Poisson arrival process. These requirements are met as follows.

1. The booking time is divided into a series of short time intervals, and in each time interval the passenger arrival process follows a Poisson distribution.

2. Each interval is set to a number n, n=1,2,3…h. Time interval 1 represents the end of the booking time; time interval h represents the beginning of the booking.

3. Since the model assumes that each decision interval has at most one passenger arrival, each time interval described above is divided into intervals related to the decisions required by the model. µ_kⁿ means the expected arrivals in stage n at the required class level k. The expected arrivals in each class level in every stage corresponds to the following equation:

   ${\mu }^{\mathrm{n}}={\mu }_1^{\mathrm{n}}+{\mu }_2^{\mathrm{n}}+\cdots +{\mu }_{\mathrm{k}}^{\mathrm{n}}.$

   (9)

   In each time interval, passengers arrive according to the Poisson distribution with a mean μⁿ.

4. The interval n is divided into ν^k short decision intervals of equal length. Passenger arrivals in each short interval meet the Poisson distribution with a mean μⁿ/vⁿ; the most important constraint is that at most one passenger arrives in each interval.

5. ε is a very small probability value, which can be negligible; vⁿ must then satisfy the equation P(x ≫ 2) < ε, where x is the number of passengers arriving within a decision interval. Because each interval meets the Poisson distribution with a mean μ ⁿ /ν ⁿ , where v_n satisfies Equation 10, if given a value for ε we can easily find the value of v_n:

   $1-({\mu }^n/v^n)exp({\mu }^n/v^n)\hspace{0.17em}\hspace{0.17em}\hspace{0.17em}-\hspace{0.17em}exp(-{\mu }^n/v^n)\ll \varepsilon ,$

   (10)

6. The probability of passenger arrival in each decision interval is calculated. Passenger arrival meets the Poisson distribution with mean μ ⁿ /ν ⁿ , and

   $p_k(n)=({\mu }^n/v^n)\hspace{0.17em}exp(-{\mu }^n/v^n)$

   (11)

   p_k(n) stands for a passenger arriving, requiring class level k at stage n.

4. Numerical Simulation and Results

This study uses data from a Chinese domestic airline route, Nanjing (A) --- Shenzhen (B) --- Sanya (C), in simulation. Each ODF has two class level fares, Y and B, where Y denotes 100% fare and B denotes 80% fare. The number of available seats in the aircraft, C, is 140. There are three legs: AB, AC, and BC. We thus have ABY, ABB, ACY, ACB, BCY, and BCB as the six ODF combinations. ODF fares and demand data are shown in Table 1.

Table 1.

ODF fares and demand information

number	1	2	3	4	5	6
ODF	ABY	ABB	ACY	ACB	BCY	BCB
Fare	1000	800	1200	960	400	320
demand	42	66	35	50	41	71

Because the number of ODF is not too high, we take each fare as a bucket. There are thus six virtual buckets. For the given data, the results of bucket division are as follows:

Table 2.

Results of bucket division

A-B			B-C
bucket F		fare	bucket F	class	fare
1	ACY	1200	1	ACY	1200
2	ABY	1000	2	ACB	960
3	ACB	960	3	BCY	400
4	ABB	800	4	BCB	320

As passengers arrive in non-homogeneous Poisson distribution, we can obtain the probability and the number of passengers arriving at each stage, according to section B. The stimulation results are shown in Tables 3 and 4.

Table 3.

Probabilities of passenger arrival

stage	ACY	ABY	ACB	ABB	BCY	BCB
0–180	0.037	0.042	0.011	0.016	0.027	0.011
181–360	0.027	0.032	0.016	0.027	0.027	0.022
361–510	0.025	0.032	0.019	0.019	0.032	0.026
511–660	0.019	0.025	0.019	0.025	0.025	0.025
661–840	0.016	0.021	0.021	0.027	0.021	0.032
841–990	0.019	0.019	0.025	0.032	0.025	0.038
991–1170	0.016	0.016	0.027	0.037	0.016	0.042
1171–1350	0.010	0.016	0.032	0.037	0.016	0.042
1351–1550	0.010	0.010	0.029	0.038	0.014	0.043
1551–1750	0.010	0.010	0.029	0.043	0.014	0.047
1751–1950	0.005	0.010	0.038	0.047	0.019	0.010

Table 4.

Passenger arrival

ODF	Arrival at interval t
ABY	48,55,67,71,84,93,173,200,208,217,232,247,260, 262,333,398,413,435,444,461,504,521,533,544, 547,560,594,642,661,703,783,869,999,1004, 1071,1103,1120,1163,1217,1221,1276,1302, 1322,1383,1438,1536,1618,1693,1737,1763,1828, 1919
ABB	79,148,177,223,228,258,266,314,354,411,428,448, 483,484,498,577,628,709,712,732,756,789,817, 833,853,862,868,935,991,1019,1106,1187,1193, 1219,1230,1317,1319,1335,1336,1401,1409,1424, 1483,1492,1506,1520,1537,1538,1647,1673,1677, 1684,1710,1747,1782,1788,1806,1840,1842,1846, 1853,1866,1867,1893,1905,1914,1942,
ACY	11,30,31,46,74,89,90,96,127,214,219,246,265,337, 359,409,447,477,489,492,526,530,561,602,607, 608,635,648,689,701,832,854,889,917,925,933, 939,982,1026,1107,1207,1471,1597,1751,1845
ACB	116,321,433,456,497,571,600,625,636,691,696, 720,729,791,830,846,888,988,1042,1052,1129, 1226,1255,1282,1315,1329,1330,1368,1388, 1407,1488,1531,1535,1727,1739,1755,1767, 1778,1834,1874,1878,1922,1923,1936,1943
BCY	17,24,65,92,215,251,285,295,303,341,345,367, 368,387,422,424,458,462,469,488,494,511,546, 651,656,700,704,719,731,735,823,855,914,920, 937,951,973,983,1032,1047,1114,1120,1229, 1235,1236,1269,1289,1405,1616,1654
BCB	18,292,334,374,382,468,474,524,615,641,713, 761,812,816,842,852,865,877,885,913,964,974, 1003,1025,1046,1049,1059,1118,1125,1132, 1160,1180,1184,1207,1234,1266,1311,1341,1342, 1343,1380,1394,1399,1454,1470,1509,1512,1517, 1519,1530,1560,1623,1682,1697,1713,1731,1775, 1799,1813,1823,1850,1856,1865,1882,1891,1902, 1912,1924,1932,1934,1945

In this case, the risk factor γ was set to 0.002. Then, the protection number was obtained in each stage. The protection number of the AB leg is expressed in Fig. 1, and that of BC in Fig. 2. The risk factor was changed to 0.001, and the results are expressed in Figs. 3 and 4.

Figure 1.

Segment AB's protection level

Figure 2.

Segment BC's protection level

Figure 3.

Segment AB's protection level

Figure 4.

Segment BC's protection level

(See Table 2.) In Figs. 1 and 3, buckets 2, 3, and 4 mark the protected seats for ACY and respectively represent ODFs ABY, ACB and ABB. In Figs. 2 and 4, buckets 2,3, and 4 mark the protected seats for ACY and respectively represent ODFs ACB, BCY and BCB.

A comparison of the four graphs shows that a different risk factor may lead to different protected seats. It also indicates that the smaller the risk factor, the bigger the number of protected seats in general, and vice versa.

On the other hand, how does risk factor affect flight revenue? Table 5 shows the latest sales state of a simulation flight using the above method. The last column about the flight revenue shows that the smaller risk factor may bring more revenue; of course, this is on the premise that, no matter what the risk factors set, the flight requests should be consistent.

Table 5.

Last sales state and revenue of flight

γ	ABY	ABB	ACY	ACB	BCY	BCB	Rev
.002	25	43	38	34	8	37	152680
.001	31	32	41	36	8	37	155400

Risk factor equates to risk tolerance, and is always set by the decision-maker or seat control employees in airlines. The decision-maker may thus control different seat allocation schemes at every stage over the sales period of a flight by setting different risk factors.

5. Conclusion

This paper combines the EMSU and the virtual bucket methods using a Markov decision process to approach the multi-leg seat inventory control problem. The authors simulated the arrival procedure of passengers with non-homogeneous Poisson distribution. The theoretical analysis and the experimental results show that with the reduction of the risk factor, the number of protected high-class seats rises. With the addition of risk-sensitive conditions that surpass the subjective rationality of decision-makers, the decision-making process better corresponds to real situations.