Expert Systems with Applications 37 (2010) 7276–7279
Contents lists available at ScienceDirect
Expert Systems with Applications journal homepage: www.elsevier.com/locate/eswa
Percolated simulation approach for optimization of preserve service system design Peng Zhou a,*, Yi Wu a, Jian Lin a,b, Wanhua Qiu a a b
School of Economics and Management, Beijing University of Aeronautics and Astronautics, Beijing 100191, China Institute of Education, Tsinghua University, Beijing 100191, China
a r t i c l e
i n f o
Keywords: Percolated Monte Carlo Simulation optimization
a b s t r a c t A novel concept of probabilistic design for soft real-time preserve service systems and a simulation methodology to optimize the design are proposed. Motivated by the challenge of how to maximize revenue, revenue management, is the process of accurately accounting for the utility of both service providers and customers while at the same time optimizing the total revenue. Using classical mathematical methods, revenue management can be a very difﬁcult and complex task. Our goal is to bridge the gap between real-time preserve service system analysis and optimization for robust and reliable system design. Our method that is both simple and novel takes advantage of soft real-time preserve service system’s unique features to maximize the revenue. The method uses Monte Carlo simulations, logic and graphics to achieve useful probabilistic design results in a very efﬁcient and visual manner. Ó 2010 Elsevier Ltd. All rights reserved.
1. Introduction A commonly recognized broad deﬁnition of revenue management is the process of allocating the right capacity or inventory unit to the right customer at the right price so as to maximize revenue or yield. It is a sophisticated tool that helps ﬁrms to maximize their revenue by demand forecasting, overbooking, pricing and capacity (Bharill & Rangaraj, 2008; Levin, McGill, & Nediak, 2008). The capacity control theory was ﬁrst raised by Littlewood for two fare classes in 1972. This model could effectively work out the optimal reserve capacity between two fare classes and therefore supports decision making in operation (Bearden, Murphy, & Rapoport, 2008; Gallego, Kou, & Phillips, 2008; Ioannidis & Kouikoglou, 2008). Proved to be effective, capacity control has been widely used in airlines, hotels, car rentals, traveling, etc. Attracted by the enormous revenue generated by capacity control of revenue management among diversiﬁed industries, domestic research on this topic was in progress (Lan, Gao, Ball, & Karaesmen, 2008; Yeung, Yeo, & Liu, 1998). However, most of the research was focused on the traditional industries and research on revenue management in domestic community education is still at a primary stage. Targeting on the adult education department of BAA Community School, this article makes research on capacity control of revenue management in domestic community education. We ﬁrst established a capacity control model in community school, on the basis of Littlewood’s rule. Then we calculated the parameters in the model based on the data collected from the sur-
* Corresponding author. E-mail address: [email protected]
(P. Zhou). 0957-4174/$ - see front matter Ó 2010 Elsevier Ltd. All rights reserved. doi:10.1016/j.eswa.2010.03.042
vey on the students of BAA Community School. According to the model and the parameters, we ﬁnally worked out the optimal reserve capacity of different kinds of classes in BAA Community School.
2. Background and related work Littlewood’s model assumes two product classes, with associated prices p1 > p2. The capacity is C, and the model assumes there is no cancellations or overbooking. Demand for class j is denoted Dj and its distribution is Fj (). Demand for class 2 arrives ﬁrst. The problem is to decide how much class 2 demand could be accepted before seeing the realization of class 1 demand. Suppose a ﬁrm have x units of capacity remaining and a request for class 2 is received. If the ﬁrm accepts the request, it collects revenue of p2. If the ﬁrm do not accept it, it will sell unit x (the marginal unit) at p1 if and only if demand for class 1 is x or higher. That is, if D1 P x. Thus the expected gain from reserving the xth unit for class 1 (the expected marginal value) is p1P(D1 P x). Therefore, the ﬁrm should accept a class 2 request as long as its price exceeds this marginal value, or equivalently, if and only if p2 P p1P(D1 P x). Note the right-hand side of the equation is decreasing in x. Therefore, there will be an optimal protection level, denoted y1 , such that we accept class 2 if the remaining capacity exceeds y1 and reject it if the remaining capacity is y1 or less. Formally, y1 satisﬁes p2 < p1 P D1 y1 and p2 > p1 P D1 y1 þ 1 . This is known as Littlewood’s rule. Setting a protection level of y1 for class 1 according to Littlewood’s rule is an optimal policy. According to Littlewood’s rule, if two product classes using one resource, we can apply capacity control. After a thorough
P. Zhou et al. / Expert Systems with Applications 37 (2010) 7276–7279
investigation on the adult education department of community school, we found that the classes are applicable.
4.2. Symbols and model Based on the assumptions of utilities of community schools and student, we modify the Littlewood’s model and establish a twoclass capacity control model for the seats in common and advanced classes. The symbols in the model is listed below,
3. Capacity control in community school 3.1. Background of classes at community school
p1 P2 D1
As the primary education organization, a domestic community school only has two classes: the advanced class and the common class. Take BAA Community School as an example, the price for a seat in the common class is 22 RMB, while in the advanced class it is 220 RMB. Usually, demand for seats at common class is much larger. Seats in advanced class are often left unused due to its expensiveness. BAA Community School has 83 seats in common class and four seats in advanced class. The only differences between these two classes are room space and facility, while the course that served is similar. The marginal cost to school when a seat is used nearly equals zero.
D2 mlj m2k e1j e2k
3.2. Analysis on capacity control of classes of community schools Although most community schools face a heavy demand on their seats, they do not have a scientiﬁc capacity control method for seats. All of the community schools use ﬁrst come, ﬁrst serve rule allocating seats in both classes. If all of the seats in common class are occupied, schools will reject request for seat in common class, even though there are seats left in advanced class. The current allocation rule seems fair to students. However, this mechanism does not maximize the utility of both schools and students. Since the variable cost of service in advanced class is the same with the common class, we can simply regard seats in both classed as two product classes using the same resource (total empty seats). Therefore, it is reasonable to apply Littlewood’s rule of capacity control in allocating seats. 4. Capacity control model in community school
y1 V(1, j) V(2, k) U(1, j)
seat price of in the advanced class seat price of in the common class daily demand for the seats in the advanced class daily demand for the seats in the common class the reserve price of the student j for a seat in the advanced class the reserve price of the student k for a seat in the common class the expect price of student j for a seat in the advanced class the expect price of student k for a seat in the common class the optimal protection level of seats in advanced classes the utility of student j, when he gets a seat in the advanced class. the utility of student k, when he gets a seat in the common class the sum utility of community school and student j, when he gets a seat in the advanced class the sum utility of community school and student k-,when he gets a seat in the common class
Combining the utilities of the community school and student, we have
e1j p e2j Uð2; kÞ ¼ p2 þ ðm2j p2 Þ p
Uð1; jÞ ¼ p1 þ ðm1j p1 Þ 4.1. Utilities of community schools and students To maximize the total beneﬁts of both students and school are the mission of a domestic community school. Thus we should quantify the utility of schools and students. We assume that when a student accepts the service of a community school, the school achieves full utility which equals the price of the seat, otherwise the school gains no utility. Denote p as the price of a seat, the utility of the school is,
if a student is accepted
0 if a student is projected
We deﬁned the utility of a student as his consumer surplus adjusted by his sensitivity to price. We deﬁne the student’s sensitivity to price equals the ratio of his expect price (the price he thinks to be most reasonable) to the real price. Due to the students’ different conditions, the utility of receiving an education service varies even the price stays stable. The sensitivity is also a parameter which shows the fairness a student feels when he receives an education service. Let m stand for the reserve price of a student (the highest service price he could accept) and e stand for the expect price of the student. As deﬁned above, the consumer surplus is m p and the sensitivity to price is e/p Therefore, the utility of a student is
ðm pÞ pe when m p 0
when m < p
According to Littlewood’s rule, we have the following conclusion. Suppose there is no seat left in the common class and x seats left in the advanced class. If another student comes and requests for a seat in common classes, the community school should not simply reject the request but offer the student a seat in the advanced class at the price of the common class. If the school does so, its utility is just the same as offering the student a seat in the common class, which is U(2, k). If the school rejects the request, the expected utility is U(1, j)P(D1 > x). As long as U(2, k) exceeds U(1, j)P(D1 > x) the school should offer the student a seat in the advance class at the price of a seat in the common class. Since U(1, j)and U(2, k)are random variables, we can use either the expectation of them and derive the model as follows:
EðUð2; kÞ E½Uð1; jÞP D1 y1 EðUð2; kÞ > E½Uð1; jÞP D1 y1 þ 1
Where y1 is the optimal protection level of seats in advanced classes. To be speciﬁc,
8 > <
h i h i E p2 þ ðm2k e2k Þ ep2k E p1 þ ðm1k e1k Þ ep1k p D1 y1 2 1 h i h i > : E p2 þ ðm2k e2k Þ ep2k > E p1 þ ðm1k e1k Þ ep1k p D1 y1 þ 1 2 1 ð6Þ
ð2Þ or the Percolated simulation methods as follows:
P. Zhou et al. / Expert Systems with Applications 37 (2010) 7276–7279
max : y1 y1 1
X 1:5k ST : Uð2; kÞ Uð1; jÞ 1 e1:5 k! k¼0
U(1, j) and U(2, k) are random variables generated by random generator according to their probability distribution. And this model can be solved by Percolated simulation optimization algorithm. 4.3. Estimation of the variables In order to get the actual value of the variables (the reserve price and expect price), we made a survey on the students of BAA Community School. We collect students’ reserve price and expect price for the seat in common class, then V(2, k) = (m2k P2)e2k/ P2 can be computed. The result shows that the data ﬁts normal distribution with mean of 26.81085 and standard deviation of 17.56604 at the signiﬁcant level of 0.1. Thus we regard that V(2, k) N(26.81085, 17.56604) Since U(2, k) = V(2, k) + P2, we have U(2, k) N(48.81, 17.57). We also get the reserve price and expected price for students in advanced class. The result shows that the data ﬁts normal distribution with mean of 81.33493 and standard deviation of 40.29886 at the signiﬁcant level of 0.05. Thus we regard that V(1, j) N(81.33493, 40.29886) and U(1, j) N(283.33, 40.30). From the investigation on the in student record from March 15th 2008 to March 15th 2008, we got the data of daily demand on seats in advanced classes. Since the distribution of daily demand should be similar to the distribution of an arrival process, we assume the demand distribution to be Poisson distribution. Again we make the goodness-of-ﬁt test and get the following result: we could accept the assumption that D1 P(1.5). 4.4. Result analysis Knowing the distribution of the variables, we now can work out the optimal protection level y1 according to our capacity control model (Eq. (6)), Since E[U(1, j)] = 283.33, E[U(2, k)] = 48.81, y 1
1 X 1:5k 1:5 P D1 y1 ¼ 1 P D1 < y1 ¼ 1 e k! k¼0
Fig. 1. probability distribution of the Eq. (9). Table 1 The parameters of the probability distribution of the Eq. (9). The distribution of Py1 1 1:5k 1:5 . e Uð2; kÞ Uð1; jÞ 1 k¼0 k! Percentile (%)
0 10 20 30 40 50 60 70 80 90 100
60.32 29.05 20.81 15.01 10.06 5.73 1.04 5.2 10.9 20.04 55.79
Trials Mean Median Standard Deviation Variance Skewness Kurtosis Coeff. of variability Minimum Maximum
1000 4.98 5.73 19.21 369.15 0.097 2.92 3.86 60.32 55.79
tion”. And the maximum of these kept y1 is the optimal reserve number for seats in advanced class. After 1000 trials simulation has ran, two y1 values are kept: y1 ¼ 1; y1 ¼ 2. The maximum of them is y1 ¼ 2, which is the same with the result of expectation model in Section 4.4. But there is something interesting need to be noticed, the percolated simulation algorithm put the y1 ¼ 2 in the simulation model and generate random variables U(2, k), U(1, j) at very simulation trial at the same time the algorithm record the value of the restriction
The optimal model is
8 y1 1 > P > > > 48:81 283:33 1 > < k¼0 y1 > > P > > 48:81 > 283:33 1 > :
! 1:5k k!
Uð2; kÞ Uð1; jÞ 1
Solving the equations, we have y1 ¼ 2, which is the optimal reserve number for seats in advanced class. As mentioned before, there are four seats in advanced classes in BAA Community School. Therefore, when all seats in common classes are allocated and a student requests for a seat in common class, the school can offer the student a seat in advanced class at the price of the seat in common class and beneﬁt both the school and the student if there are two or more empty seats in advanced class.
X 1:5k e1:5 k! k¼0
After the simulation has run, we can get the probability distribution of the Eq. (9) (Fig. 1). From Fig. 1 and Table 1, we can see that P ðUð2; kÞ > Py1 1 1:5k 1:5 e Uð1; jÞ 1 k¼0 ¼ 60:59% when y1 ¼ 2. That is to say k! that y1 ¼ 2 satisfy the restriction with the probability 0.6. Therefore when all seats in common classes are allocated and a student requests for a seat in common class, the school offer the student a seat in advanced class at the price of the seat in common class and the risk of advanced class seat shortage is 0.4 if there are two or more empty seats in advanced class. So the risk liker will choose y1 ¼ 2, risk evader will choose y1 ¼ 2. And the risk information cannot be got by expectation method in Section 4.4.
4.5. Percolated simulation analysis 5. Conclusion Knowing the distribution of the variables, percolated simulation can also work out the optimal protection level y1 according to our capacity control model. y1 is a discrete variable range from 0 to 4. The percolated simulation algorithm put every possible y1 in the simulation model (Eq. (7)), then these y1 satisfy the constrain will be kept, other values are discarded. This process is called ‘‘percola-
This article makes a research on the capacity control of revenue management in domestic community schools. Targeting on BAA Community School, we established a capacity control model on the basis of maximizing the utilities of both students and the community school. Then we calculated the parameters in the model
P. Zhou et al. / Expert Systems with Applications 37 (2010) 7276–7279
based on the data collected from the survey on the students of BAA Community School. Finally we worked out the optimal reserve number of seats in the advanced classes in BAA Community School. With this new perspective of seats allocating method, both school and student can gain more proﬁt.
References Bearden, J. Neil, Murphy, Ryan O., & Rapoport, Amnon (2008). Decision biases in revenue management: Some behavioral evidence. Manufacturing and Service Operations Management, 10(4), 625–636.
Bharill, Rohit, & Rangaraj, Narayan (2008). Revenue management in railway operations: A study of the Rajdhani express, Indian railways. Transportation Research Part A: Policy and Practice, 42(9), 1195–1207. Gallego, Guillermo, Kou, S. G., & Phillips, Robert (2008). Revenue management of callable products. Management Science, 54(3), 550–564. Ioannidis, S., & Kouikoglou, V. S. (2008). International Journal of Production Research, 46(22), 6513–6532. Lan, Yingjie, Gao, Huina, Ball, Michael O., & Karaesmen, Itir (2008). Revenue management with limited demand information. Management Science, 54(9), 1594–1609. Levin, Yuri, McGill, Jeff, & Nediak, Mikhail (2008). Risk in revenue management and dynamic pricing. Operations Research, 56(2), 326–343. Yeung, M. M., Yeo, B. L., & Liu, B. (1998). Segmentation of video by clustering and graph analysis. Computer Vision and Image Understanding, 71(1), 94–109.