# Optimization Problem of Pricing and Seat Allocation Based on Bilevel Multifollower Programming in High-Speed Railway

Authors: Lianbo Deng; Jing Xu; Ningxin Zeng; Xinlei Hu
Journal: Journal of Advanced Transportation
 (2021)

---

## Abstract

This paper studies the multistage pricing and seat allocation problems for multiple train services in a high-speed railway (HSR) with multiple origins and destinations (ODs). Taking the maximum total revenue of all trains as the objective function, a joint optimization model of multistage pricing and seat allocation is established. The actual operation constraints, including train seat capacity constraints, price time constraints in each period, and price space constraints among products, are fully considered. We reformulate the optimization model as a bilevel multifollower programming model in which the upper-level model solves the seat allocation problem for all trains serving multiple ODs in the whole booking horizon and the lower optimizes the pricing decisions for each train serving each OD in different decision periods. The upper and lower are a large-scale static seat allocation programming and many small-scale multistage dynamic pricing programming which can be solved independently, respectively. The solving difficulty can be significantly reduced by decomposing. Then, we design an effective solution method based on divide-and-conquer strategy. A real instance of the China’s Wuhan-Guangzhou high-speed railway is employed to validate the advantages of the proposed model and the solution method.


---

## Body

## 1. Introduction

In recent years, high-speed railway (HSR) in China has developed rapidly, but operating revenue varies greatly between HSR lines. To tap the potential of operating revenue and improve operating revenue is an important problem that needs to be solved in HSR operation. Ticket price and seat utilization are two important aspects to increase revenue. In terms of ticket price policy, since China Railway obtained pricing rights for HSR from National Development and Reform Commissions in 2016, the ticket price strategy of HSR has been more flexible, and dynamic price has received much attention. In the aspect of seat utilization, the conventional ticket organization strategies in China mainly include ticket preassignment, seat sharing strategy, seat reuse, and section-control strategy. With the upgrading of Ticket Selling and Booking System of China’s Railway, 12306 network booking systems can carry out real-time dynamic seat reuse, and these conventional ticket organization strategies have been weakened for HSR. Railway departments pay more attention to adjusting seats flexibly according to ticket sales results, but ‘preferentially selling long-distance tickets to long-distance passengers’ is still the basic principle of seat management. The reform of ticket price policy and seat management has created conditions for China’s HSR to implement revenue management (RM) strategy.Pricing strategy and inventory control strategy play important roles in RM systems for service industries, such as the retail industry, airline industry, and hospitality industry [1–7]. Inventory control techniques, normally known as seat allocation in the passenger transportation market, are used to maximize the total revenue of operators by determining the booking limit of seats for multiple OD pairs at a fixed price. However, the price of transportation products impacts not only passenger choice behavior but also the distribution of passenger demand during the whole booking horizon. The combined effects of price and booking limits on the realized passenger demand should be considered simultaneously. Although pricing problems and inventory allocation problems are interrelated, especially in the railway market, there are a few studies on the joint optimization problem of pricing and seat allocation decisions [4, 8, 9].High-speed and high-quality services are the advantages of high-speed railway and air transportation. However, multiple stops for a single HSR service are the most significant difference between these two transportation modes, which increases the complexity of joint pricing and seat allocation for HSR. In the small HSR shown in Figure1(a), there are multiple HSR trains providing passenger transportation services for a single OD. For example, OD A,C is served by Train 1, Train 2, and Train 4, while Train 1, Train 4, and Train 5 can provide services for OD B,C. In addition to multiple trains serving a single OD, for a train, the resources (i.e., seats) of each leg (i.e., the section between two adjacent station stops of the train) are shared by multiple ODs served, as shown in Figure 1(b). For example, an HSR Train 1 from A to D, stopping at stations B and C, can provide services for 6 origin-destination (OD). For Train 1, the capacity of leg B-C is shared by passengers of ODs A,C, A,D, B,C, and B,D served by Train 1. The complex relationship between multiple trains and multiple ODs forms multiple products (i.e., the transportation service from an origin to a destination provided by a train), which is written as Origin,Destination|Train. For example, in Figure 1(b), there are 6 products: A,B|Train1, A,C|Train1, A,D|Train1, B,C|Train1, B,D|Train1, and C,D|Train1. Thus, the joint optimization problem of pricing and seat allocation for HSR is a large-scale multiproduct and multileg RM problem, posing challenges not seen before for other modes of transportation, such as air transportation.Figure 1
A multi-OD HSR with multiple train services. (a) Multiple trains serving a single OD. (b) A train serving multiple ODs.
(a)(b)Most existing studies on the joint optimization of pricing and seat allocation in the rail market only considered a small network or a few train services, which leaves a large gap between the numerical experiments and real-world problems. This study attempts to make contributions to the existing research on large-scale joint optimization of pricing and seat allocation for HSR by (1) establishing a joint optimization model of multistage pricing and seat allocation, (2) reformulating the optimization model as a bilevel multifollower programming model in which the upper-level model solves the large-scale static seat allocation problem for multiple products in the whole booking horizon and the lower optimizes the small-scale multistage dynamic pricing decisions for each product in different decision periods, (3) improving the ticket price constraints considered by existing studies and considering price time constraints in each period and price space constraints among products, and (4) designing an efficient solution method based on divide-and-conquer strategy for large-scale problems.The remainder of this paper is organized as follows. Section2 summarizes the most relevant studies. Section 3 introduces the assumptions and notations. The bilevel multifollower programming model for joint HSR multistage pricing and seat allocation problems is proposed in Section 4. The details of the solution method, based on a divide-and-conquer strategy, are described in Section 5. Numerical experiments are provided in Section 6 to verify the availability and efficiency of the model and solution algorithm. In Section 7, conclusions and future research directions are summarized.


## 2. Literature Review

### 2.1. Pricing

Pricing strategy in RM usually refers to dynamic pricing. Gallego and Van Ryzin [10] combined dynamic pricing with RM and systematically studied the dynamic pricing problem of perishable commodities by the intensity control theory. In the twenty years since that paper, many researchers have studied and expanded the dynamic pricing problem by various methods. Passenger transportation is the main application field for dynamic pricing strategy. In the past, the research and application of dynamic pricing of passenger transportation mainly focused on the civil aviation industry, and in recent years, research in the railway industry has gradually increased.For civil aviation, Gallego and Van Ryzin [11] extended the model of Gallego and Van Ryzin [10] to a multiproduct joint pricing model and applied it to the case of multiple flights in a network. You [12] studied the pricing strategy with multiple seat classes for a single flight and multiple flights and established a discrete-time stochastic dynamic programming model. It simplified the ticket strategy and reduced it to sets of critical decision periods, which eliminated the need for large amounts of data storage. Zhang and Cooper [13] studied the dynamic pricing problem for parallel flights based on passenger choice behavior. They established a discrete-time stochastic dynamic model based on the Markov decision process. The high-dimensional Markov problem was solved by a heuristic algorithm, and the upper and lower bounds of the price function were obtained. Otero and Akhavan-Tabatabaei [14] used phase-type distributions to fit the decision-making process of passenger ticket purchase. They established a stochastic dynamic pricing model for a single flight with multiple price classes and solved it by a dynamic programming method.For the railway industry, due to the number of stops, the pricing problem of multiple train services and multiple ODs is difficult to solve; many early studies are focused on a single train servicing a single OD. Sibdari et al. [15] studied the discrete-time-pricing problem with multiple seat classes for a single train based on sales data from Amtrak. They proposed a pseudo-dynamic heuristic strategy: at the beginning of each day, a new price was calculated based on the inventory level. This strategy could correct pricing strategies from current sales. Sato and Sawaki [16] used multinomial logit models to describe the discrete passenger choice and established a dynamic pricing model for multiple HSR train services which compete with civil aviation. A small-scale instance was used to verify the effect of the model. Zheng and Liu [17] studied the pricing strategy optimization problem for a single train service with multiple ODs and established a mathematical programming model to optimize multistage prices. In the existing research, many studies mainly focused on small-scale problems because of the complexity of pricing problems in the railway industry.


### 2.2. Seat Allocation

Littlewood [18] first studied the seat allocation problem and proposed a principle to decide whether to accept or reject a reservation. Afterwards, many researchers have undertaken a lot of studies on this basis. Railway passenger transportation is often multileg, while aviation passenger transportation is point-to-point, so the scale of the problem of seat allocation is different between these two transportation modes. Ciancimino et al. [19] proposed a mathematical programming method for the multileg and single-fare seat allocation problem with nonnested structure. You [20] found a solution to the seat allocation problem in the railway network by integrating the advantages of mathematical methods and metaheuristic methods. Wang et al. [21] studied the single-stage and multistage stochastic programming models for the seat allocation problem. The model could be solved by equivalently transforming it into deterministic mathematical programming. Yuan et al. [22] studied the application of dynamic bidding price control in railway seat allocation. They built a dynamic programming model to calculate dynamic bid prices of multidimensional demand. Zhao and Zhao [23] studied a seat inventory control method for homogeneous seats of multiple train services with different stop-schedule plans. They proposed a heuristic algorithm to solve the nonlinear integer programming model. Yan et al. [24] relaxed the capacity constraint, combined with revenue management, and constructed a probabilistic nonlinear programming model to solve the seat inventory control and train composition decisions problems simultaneously. In these studies, they only considered how to allocate seats to improve the revenue.


### 2.3. Joint Pricing and Seat Allocation

Although there have been many studies on pricing and seat allocation, most of the literature studied these two problems separately and there are relatively few joint studies. In practical applications, especially for civil aviation and railways, these two problems are interrelated.Most of the relevant research is in the field of civil aviation. Weatherford [25] studied the joint optimization of pricing and seat allocation at an early stage. The enumeration method was used to list the corresponding price and seat allocation under different demands. However, the scale of the study was small and only considered the situation of two or three price classes (seat classes) of a single flight; the demand constraint was relatively ideal. Kuyumcu and Garcia-Diaz [26] analyzed the joint optimization of pricing and seat allocation for multiple flights in a network and proposed a solution method based on graph theory. Without explicit assumptions about demands and characteristics of various products, it was not universal to reduce the difficulty of the solution through specific preprocessing in the numerical instance. Cote et al. [27] proposed a bilevel programming model for the joint optimization problem of pricing and seat allocation in the competitive environment of the aviation industry. The objective function of the upper-level problem was to maximize the network revenue, and the objective function of the lower-level problem was to minimize passengers’ individual perceived travel disutility. They assumed that the airline knew how competitors would react to its pricing strategy and that demand was fully known. The decision variables included price but did not include seat allocation. The seat allocation was obtained according to its own price strategy after knowing the competitors’ strategies. Feng and Xiao [1] studied a comprehensive decision-making model for optimal passenger cabin allocation and pricing and obtained an optimal cabin allocation and pricing strategy based on a sequence of threshold points, which was a function of inventory, price, and demand intensity. Finally, a numerical instance of a single flight with multiple price classes and multiple demands was presented. Walczak and Brumelle [28] established a semi-Markov model to study the joint optimization problem of pricing and seat control for a single resource with multiple price classes. Unlike most studies that adjusted operators' strategies on the assumption that demand was known or could be estimated, their study assumed that operators' strategies were determined in advance and that demand (including expected price) changed according to information variables. The passengers bought the ticket at the lowest price at first. After the low-priced tickets were sold out, they would buy the next higher-priced tickets. This situation would continue until the price was higher than the passenger's expected price. Cizaire [29] studied the joint optimization of the multistage pricing and seat allocation for a single flight in a single OD with multiple price classes. The authors established models for the cases of deterministic and stochastic demand. The deterministic demand model was solved by dynamic programming and the stochastic demand model was solved by a heuristic method.Compared with civil aviation, there is less research in the railway industry. Ongprasert [30] proposed a seat allocation model considering passenger choice and discounted fares in the competitive environment of civil aviation. The paper mainly focused on the seat allocation optimization problem based on passenger choice and only considered whether to offer discounted fares in the pricing optimization. There were multiple objective functions in the model. The model was verified in the case of multiple train services and multiple ODs on the intercity HSR in Japan. Hetrakul and Cirillo [4] used mathematical programming models to analyze the joint optimization problem of pricing and seat allocation for multiple train services in multiple ODs in an intercity railway. The multinomial logit (MNL) model and latent class (LC) model were used to simulate ticket purchase timing of passengers, and on this basis, the demand distribution on each booking day was obtained. Then, they defined an acceptance ratio of each OD to adjust seat allocation and controlled price changes by the probability of passenger ticket purchase in the model, where price and seat allocation were optimized simultaneously. Zheng [31] studied the differential pricing problem for multiple train services in a single sales period and established a bilevel programming model. The upper-level problem was differential pricing and the lower-level problem was seat allocation, where the user equilibrium traffic distribution method was adopted. The model was also extended to multiple stages and differential pricing was implemented at each stage. The multistage model was solved by an approximate dynamic programming algorithm. Hu et al. [8] proposed a nonlinear programming model for joint optimization of pricing and seat allocation in high-speed rail networks and designed a solution algorithm based on the Davidon–Fletcher–Powell method.According to the literature review in this section and the summary from the works of Cizaire [29] and Hetrakul and Cirillo [4], we summarize and compare the relevant studies from the main aspects of joint optimization of pricing and seat allocation in Table 1.Table 1
Literature review summary of joint optimization of pricing and seat allocation.
AuthorsMultiperiodMultilegJoint optimizationIndustryWeatherford [25]✗✗✓CKuyumcu and Garcia-Diaz [26]✗✓✗CCote et al. [27]✗✓✗CFeng and Xiao [1]✓✗✓CWalczak and Brumelle [28]✓✗✓CCizaire [29]✓✗✓COngprasert [30]✓✓✗RHetrakul and Cirillo [4]✓✓✓RZheng [31]✓✓✓RHu et al. [8]✓✓✓RThis research✓✓✓RNote. C, civil aviation; R, railway.To summarize, the methods proposed in most of the literature mentioned above are not universal or only applicable to small-scale problems. For the convenience of modeling and solving, some researchers have simplified a lot of constraints. Most of the existing joint optimization studies are based on passenger utility to allocate seats from the perspective of passengers. In this paper, both seat allocation and multistage pricing are optimized from the perspective of operators. Furthermore, we fully consider the actual price time constraints in each period and price space constraints among products.


## 2.1. Pricing

Pricing strategy in RM usually refers to dynamic pricing. Gallego and Van Ryzin [10] combined dynamic pricing with RM and systematically studied the dynamic pricing problem of perishable commodities by the intensity control theory. In the twenty years since that paper, many researchers have studied and expanded the dynamic pricing problem by various methods. Passenger transportation is the main application field for dynamic pricing strategy. In the past, the research and application of dynamic pricing of passenger transportation mainly focused on the civil aviation industry, and in recent years, research in the railway industry has gradually increased.For civil aviation, Gallego and Van Ryzin [11] extended the model of Gallego and Van Ryzin [10] to a multiproduct joint pricing model and applied it to the case of multiple flights in a network. You [12] studied the pricing strategy with multiple seat classes for a single flight and multiple flights and established a discrete-time stochastic dynamic programming model. It simplified the ticket strategy and reduced it to sets of critical decision periods, which eliminated the need for large amounts of data storage. Zhang and Cooper [13] studied the dynamic pricing problem for parallel flights based on passenger choice behavior. They established a discrete-time stochastic dynamic model based on the Markov decision process. The high-dimensional Markov problem was solved by a heuristic algorithm, and the upper and lower bounds of the price function were obtained. Otero and Akhavan-Tabatabaei [14] used phase-type distributions to fit the decision-making process of passenger ticket purchase. They established a stochastic dynamic pricing model for a single flight with multiple price classes and solved it by a dynamic programming method.For the railway industry, due to the number of stops, the pricing problem of multiple train services and multiple ODs is difficult to solve; many early studies are focused on a single train servicing a single OD. Sibdari et al. [15] studied the discrete-time-pricing problem with multiple seat classes for a single train based on sales data from Amtrak. They proposed a pseudo-dynamic heuristic strategy: at the beginning of each day, a new price was calculated based on the inventory level. This strategy could correct pricing strategies from current sales. Sato and Sawaki [16] used multinomial logit models to describe the discrete passenger choice and established a dynamic pricing model for multiple HSR train services which compete with civil aviation. A small-scale instance was used to verify the effect of the model. Zheng and Liu [17] studied the pricing strategy optimization problem for a single train service with multiple ODs and established a mathematical programming model to optimize multistage prices. In the existing research, many studies mainly focused on small-scale problems because of the complexity of pricing problems in the railway industry.


## 2.2. Seat Allocation

Littlewood [18] first studied the seat allocation problem and proposed a principle to decide whether to accept or reject a reservation. Afterwards, many researchers have undertaken a lot of studies on this basis. Railway passenger transportation is often multileg, while aviation passenger transportation is point-to-point, so the scale of the problem of seat allocation is different between these two transportation modes. Ciancimino et al. [19] proposed a mathematical programming method for the multileg and single-fare seat allocation problem with nonnested structure. You [20] found a solution to the seat allocation problem in the railway network by integrating the advantages of mathematical methods and metaheuristic methods. Wang et al. [21] studied the single-stage and multistage stochastic programming models for the seat allocation problem. The model could be solved by equivalently transforming it into deterministic mathematical programming. Yuan et al. [22] studied the application of dynamic bidding price control in railway seat allocation. They built a dynamic programming model to calculate dynamic bid prices of multidimensional demand. Zhao and Zhao [23] studied a seat inventory control method for homogeneous seats of multiple train services with different stop-schedule plans. They proposed a heuristic algorithm to solve the nonlinear integer programming model. Yan et al. [24] relaxed the capacity constraint, combined with revenue management, and constructed a probabilistic nonlinear programming model to solve the seat inventory control and train composition decisions problems simultaneously. In these studies, they only considered how to allocate seats to improve the revenue.


## 2.3. Joint Pricing and Seat Allocation

Although there have been many studies on pricing and seat allocation, most of the literature studied these two problems separately and there are relatively few joint studies. In practical applications, especially for civil aviation and railways, these two problems are interrelated.Most of the relevant research is in the field of civil aviation. Weatherford [25] studied the joint optimization of pricing and seat allocation at an early stage. The enumeration method was used to list the corresponding price and seat allocation under different demands. However, the scale of the study was small and only considered the situation of two or three price classes (seat classes) of a single flight; the demand constraint was relatively ideal. Kuyumcu and Garcia-Diaz [26] analyzed the joint optimization of pricing and seat allocation for multiple flights in a network and proposed a solution method based on graph theory. Without explicit assumptions about demands and characteristics of various products, it was not universal to reduce the difficulty of the solution through specific preprocessing in the numerical instance. Cote et al. [27] proposed a bilevel programming model for the joint optimization problem of pricing and seat allocation in the competitive environment of the aviation industry. The objective function of the upper-level problem was to maximize the network revenue, and the objective function of the lower-level problem was to minimize passengers’ individual perceived travel disutility. They assumed that the airline knew how competitors would react to its pricing strategy and that demand was fully known. The decision variables included price but did not include seat allocation. The seat allocation was obtained according to its own price strategy after knowing the competitors’ strategies. Feng and Xiao [1] studied a comprehensive decision-making model for optimal passenger cabin allocation and pricing and obtained an optimal cabin allocation and pricing strategy based on a sequence of threshold points, which was a function of inventory, price, and demand intensity. Finally, a numerical instance of a single flight with multiple price classes and multiple demands was presented. Walczak and Brumelle [28] established a semi-Markov model to study the joint optimization problem of pricing and seat control for a single resource with multiple price classes. Unlike most studies that adjusted operators' strategies on the assumption that demand was known or could be estimated, their study assumed that operators' strategies were determined in advance and that demand (including expected price) changed according to information variables. The passengers bought the ticket at the lowest price at first. After the low-priced tickets were sold out, they would buy the next higher-priced tickets. This situation would continue until the price was higher than the passenger's expected price. Cizaire [29] studied the joint optimization of the multistage pricing and seat allocation for a single flight in a single OD with multiple price classes. The authors established models for the cases of deterministic and stochastic demand. The deterministic demand model was solved by dynamic programming and the stochastic demand model was solved by a heuristic method.Compared with civil aviation, there is less research in the railway industry. Ongprasert [30] proposed a seat allocation model considering passenger choice and discounted fares in the competitive environment of civil aviation. The paper mainly focused on the seat allocation optimization problem based on passenger choice and only considered whether to offer discounted fares in the pricing optimization. There were multiple objective functions in the model. The model was verified in the case of multiple train services and multiple ODs on the intercity HSR in Japan. Hetrakul and Cirillo [4] used mathematical programming models to analyze the joint optimization problem of pricing and seat allocation for multiple train services in multiple ODs in an intercity railway. The multinomial logit (MNL) model and latent class (LC) model were used to simulate ticket purchase timing of passengers, and on this basis, the demand distribution on each booking day was obtained. Then, they defined an acceptance ratio of each OD to adjust seat allocation and controlled price changes by the probability of passenger ticket purchase in the model, where price and seat allocation were optimized simultaneously. Zheng [31] studied the differential pricing problem for multiple train services in a single sales period and established a bilevel programming model. The upper-level problem was differential pricing and the lower-level problem was seat allocation, where the user equilibrium traffic distribution method was adopted. The model was also extended to multiple stages and differential pricing was implemented at each stage. The multistage model was solved by an approximate dynamic programming algorithm. Hu et al. [8] proposed a nonlinear programming model for joint optimization of pricing and seat allocation in high-speed rail networks and designed a solution algorithm based on the Davidon–Fletcher–Powell method.According to the literature review in this section and the summary from the works of Cizaire [29] and Hetrakul and Cirillo [4], we summarize and compare the relevant studies from the main aspects of joint optimization of pricing and seat allocation in Table 1.Table 1
Literature review summary of joint optimization of pricing and seat allocation.
AuthorsMultiperiodMultilegJoint optimizationIndustryWeatherford [25]✗✗✓CKuyumcu and Garcia-Diaz [26]✗✓✗CCote et al. [27]✗✓✗CFeng and Xiao [1]✓✗✓CWalczak and Brumelle [28]✓✗✓CCizaire [29]✓✗✓COngprasert [30]✓✓✗RHetrakul and Cirillo [4]✓✓✓RZheng [31]✓✓✓RHu et al. [8]✓✓✓RThis research✓✓✓RNote. C, civil aviation; R, railway.To summarize, the methods proposed in most of the literature mentioned above are not universal or only applicable to small-scale problems. For the convenience of modeling and solving, some researchers have simplified a lot of constraints. Most of the existing joint optimization studies are based on passenger utility to allocate seats from the perspective of passengers. In this paper, both seat allocation and multistage pricing are optimized from the perspective of operators. Furthermore, we fully consider the actual price time constraints in each period and price space constraints among products.


## 3. Notations and Assumptions

### 3.1. Assumptions

Assumption 1.
We only consider the second-class seat.Assumption 2.
The passenger transfer is not taken into consideration.Assumption 3.
The travel demand of each OD is independent of each other.


### 3.2. Notations

This section introduces the notations in the study. We consider one direction on a HSR lineL with N stations. The stations are denoted in order, as 1,2,…,N. For OD i,j, 1≤i<j≤N. H denotes the set of trains and W is the set of all ODs on line L. Hij denotes the set of trains serving OD i,j. Ch is the train seat capacity of train h, h∈H. nh is the number of stop stations of train h. The leg l is the segment between two adjacent stop stations, 1≤l≤nh−1. That is to say, the first leg is the segment between the first stop station and the second stop station, the last leg is the segment between the nh−1th stop station and the nhth stop station. We denote the transportation service from i to j provided by train h as a product i,j|h. The booking horizon is divided into K booking periods. The earliest one is period 1 and the latest one is period K. Let mijhk denote the number of allocated seats for product i,j|h in period k. The number of allocated seats for product i,j|h can be defined as mijh:(1)mijh=∑k=1Kmijhk.For trainh∈Hij, i,j∈W, let p^ijh denote the full price which is with no discount and determined by the government. p¯ijh is the lower bound of the price which refers to the lowest allowable floating price of current execution price (i.e., actual price). p¯ijh is the upper bound of the price which refers to the highest allowable floating price of current execution price. Generally, these three types of prices should meet 0≤p¯ijh≤p¯ijh≤p^ijh. If the regulatory authorities do not impose restrictions on p¯ijh, it can be taken as p¯ijh=p^ijh. Let pijhk denote the price for product i,j|h in period k. During the booking periods, the value range of pijhk is limited to p¯ijh,p¯ijh. pijh is the average price for product i,j|h. It can be expressed as follows:(2)pijh=∑k=1Kpijhkmijhk∑k=1Kmijhk=∑k=1Kpijhkmijhkmijh.DefineR as the total revenue. It is the product of pijh and mijh:(3)R=∑i,j∈W∑h∈Hijpijhmijh=∑i,j∈W∑h∈Hij∑k=1Kpijhkmijhk.Letcijhk be the generalized travel cost of the passenger. It consists of the ticket price and the monetary cost of travel time. For product i,j|h in period k, the generalized travel cost of each passenger is as follows:(4)cijhk=tijhν+pijhk.where tijh is the travel time for product i,j|h, ν is the time value of the passenger, and cijhk is influenced by the travel time and price of the product and indicates the distinctions between different products.The average generalized travel cost of each passenger for ODi,j in period k can be expressed as(5)cijk=∑h∈Hrscijhkmijhk∑h∈Hrsmijhk.For ODi,j in period k, the elastic demand function can be described as follows:(6)qijk=q^ijkexpηk1−cijkc^ijk,where q^ijk is the initial travel demand corresponding to c^ijk and c^ijk is the initial average generalized travel cost. Therefore, q^ijk=qijkc^ijk. ηk is the price elastic parameter of passenger demand in period k, ηk>0. The closer the time is to the departure time, the smaller ηk is.The elastic demand function implies passenger choices.qijk is related to the generalized travel cost cijhk in period k. ∑k=1Kqijk is the total passenger flow volume calculated according to the elastic demand function. The railway operation department allocates seats according to the principle of revenue maximization. Among ∑k=1Kqijk, the number of passengers choosing train h during the whole booking horizon and in each booking period is mijh and mijhk, respectively. Therefore, mijh and mijhk are the consequences of passenger choices.We list the parameters and decision variables used in the model in Table2.Table 2
Parameters and decision variables.
NotationsMeaningLA HSR lineNThe number of stations on lineLi,jAn OD (the origin is stationi and the destination is station j)HThe set of train services on lineLWThe set of ODs on lineLHijThe set of trains serving ODi,jhA train serviceChThe train seat capacity of trainhnhThe number of stop stations of trainhlThe segment between two adjacent stop stationsi,j|hA product (a transportation service fromi to j provided by train h)KThe number of divided periodsmijhkThe number of allocated seats in periodk for product i,j|hkThekth booking periodmijhThe number of allocated seats for producti,j|hp^ijhFull pricep¯ijhThe lower bound of the pricep¯ijhThe upper bound of the pricepijhkThe price in periodk for product i,j|hpijhThe average price for producti,j|hRThe total revenuecijhkThe generalized travel cost of the passengertijhTravel time for producti,j|hνThe time value of passengercijkThe average generalized travel cost of passengers for ODi,j in period kc^ijkThe initial average generalized travel costq^ijkThe initial travel demand corresponding toc^ijkηkThe price elastic parameter of passenger demand in periodkqijkThe passenger travel demand for ODi,j in period k


## 3.1. Assumptions

Assumption 1.
We only consider the second-class seat.Assumption 2.
The passenger transfer is not taken into consideration.Assumption 3.
The travel demand of each OD is independent of each other.


## 3.2. Notations

This section introduces the notations in the study. We consider one direction on a HSR lineL with N stations. The stations are denoted in order, as 1,2,…,N. For OD i,j, 1≤i<j≤N. H denotes the set of trains and W is the set of all ODs on line L. Hij denotes the set of trains serving OD i,j. Ch is the train seat capacity of train h, h∈H. nh is the number of stop stations of train h. The leg l is the segment between two adjacent stop stations, 1≤l≤nh−1. That is to say, the first leg is the segment between the first stop station and the second stop station, the last leg is the segment between the nh−1th stop station and the nhth stop station. We denote the transportation service from i to j provided by train h as a product i,j|h. The booking horizon is divided into K booking periods. The earliest one is period 1 and the latest one is period K. Let mijhk denote the number of allocated seats for product i,j|h in period k. The number of allocated seats for product i,j|h can be defined as mijh:(1)mijh=∑k=1Kmijhk.For trainh∈Hij, i,j∈W, let p^ijh denote the full price which is with no discount and determined by the government. p¯ijh is the lower bound of the price which refers to the lowest allowable floating price of current execution price (i.e., actual price). p¯ijh is the upper bound of the price which refers to the highest allowable floating price of current execution price. Generally, these three types of prices should meet 0≤p¯ijh≤p¯ijh≤p^ijh. If the regulatory authorities do not impose restrictions on p¯ijh, it can be taken as p¯ijh=p^ijh. Let pijhk denote the price for product i,j|h in period k. During the booking periods, the value range of pijhk is limited to p¯ijh,p¯ijh. pijh is the average price for product i,j|h. It can be expressed as follows:(2)pijh=∑k=1Kpijhkmijhk∑k=1Kmijhk=∑k=1Kpijhkmijhkmijh.DefineR as the total revenue. It is the product of pijh and mijh:(3)R=∑i,j∈W∑h∈Hijpijhmijh=∑i,j∈W∑h∈Hij∑k=1Kpijhkmijhk.Letcijhk be the generalized travel cost of the passenger. It consists of the ticket price and the monetary cost of travel time. For product i,j|h in period k, the generalized travel cost of each passenger is as follows:(4)cijhk=tijhν+pijhk.where tijh is the travel time for product i,j|h, ν is the time value of the passenger, and cijhk is influenced by the travel time and price of the product and indicates the distinctions between different products.The average generalized travel cost of each passenger for ODi,j in period k can be expressed as(5)cijk=∑h∈Hrscijhkmijhk∑h∈Hrsmijhk.For ODi,j in period k, the elastic demand function can be described as follows:(6)qijk=q^ijkexpηk1−cijkc^ijk,where q^ijk is the initial travel demand corresponding to c^ijk and c^ijk is the initial average generalized travel cost. Therefore, q^ijk=qijkc^ijk. ηk is the price elastic parameter of passenger demand in period k, ηk>0. The closer the time is to the departure time, the smaller ηk is.The elastic demand function implies passenger choices.qijk is related to the generalized travel cost cijhk in period k. ∑k=1Kqijk is the total passenger flow volume calculated according to the elastic demand function. The railway operation department allocates seats according to the principle of revenue maximization. Among ∑k=1Kqijk, the number of passengers choosing train h during the whole booking horizon and in each booking period is mijh and mijhk, respectively. Therefore, mijh and mijhk are the consequences of passenger choices.We list the parameters and decision variables used in the model in Table2.Table 2
Parameters and decision variables.
NotationsMeaningLA HSR lineNThe number of stations on lineLi,jAn OD (the origin is stationi and the destination is station j)HThe set of train services on lineLWThe set of ODs on lineLHijThe set of trains serving ODi,jhA train serviceChThe train seat capacity of trainhnhThe number of stop stations of trainhlThe segment between two adjacent stop stationsi,j|hA product (a transportation service fromi to j provided by train h)KThe number of divided periodsmijhkThe number of allocated seats in periodk for product i,j|hkThekth booking periodmijhThe number of allocated seats for producti,j|hp^ijhFull pricep¯ijhThe lower bound of the pricep¯ijhThe upper bound of the pricepijhkThe price in periodk for product i,j|hpijhThe average price for producti,j|hRThe total revenuecijhkThe generalized travel cost of the passengertijhTravel time for producti,j|hνThe time value of passengercijkThe average generalized travel cost of passengers for ODi,j in period kc^ijkThe initial average generalized travel costq^ijkThe initial travel demand corresponding toc^ijkηkThe price elastic parameter of passenger demand in periodkqijkThe passenger travel demand for ODi,j in period k


## 4. Model

This study establishes an optimization model to solve the price and the number of allocated seats in periodk for product i,j|h. The objective function is to maximize the total revenue for all products in all periods. Taking pijhk and mijhk as decision variables, the mathematical programming model is constructed as follows:(7)maxR=∑i,j∈W∑h∈Hij∑k=1Kpijhkmijhk,which subject to(8)∑i=1l∑j=l+1nh∑k=1Kmijhk≤Ch,1≤l≤nh,h∈H,(9)mijhk≥0,i,j∈W,h∈Hij,1≤k≤K,(10)∑h∈Hijmijhk≤qijk,i,j∈W,1≤k≤K,(11)p¯ijh≤pijhk≤p¯ijh,i,j∈W,h∈Hij,1≤k≤K,(12)pijhk≤pi1j1hk,i1≤i,j≤j1,i,j,i1,j1∈W,h∈Hij,1≤k≤K,(13)pijhk1≤pijhk2,i,j∈W,h∈Hij,1≤k1≤k2≤K.Constraints in (8) are train seat capacity constraints, assuring that, for each train h, the seat capacity of each leg l is shared by passengers of ODs which cover this leg l and is served by this train h. Constraints in (9) guarantee the number of allocated seats for each product i,j|h in each period k is positive. Constraints in (10) define demand is the upper bound of the number of allocated seats for OD i,j in period k. Constraints in (11) are the upper and lower bounds of price for product i,j|h in period k. p¯ijh and p¯ijh are the highest and lowest allowable floating price of current execution price. Constraints in (12) assure that, for the same train and the same period, if the travel range of a long-distance product covers the travel range of another short-distance product, the price of the long-distance product is higher than that of the short-distance product. Constraints in (13) enforce that the price in period k+1 is more than or equal to the price in period k for the same product i,j|h. When the purchasing day is closer to the departure day, the ticket price is more expensive.In order to solve this problem, we transform the model into a bilevel multifollower programming model by decomposing this mathematical programming model. The upper-level model is a seat allocation model for multiple products in the whole booking horizon. The lower-level model includes many multistage dynamic pricing models for each product. Thus, the multistage pricing and seat allocation problem for multiple trains and multiple ODs are divided into two parts: the seat allocation plan for multiple trains and the multistage pricing strategy for each product.The details of bilevel multifollower programming are described below.


### 4.1. The Upper-Level Model (Model 1)

The upper-level model simultaneously solves the number of allocated seats and corresponding price for all products in the whole booking horizon. The model is as follows:(14)maxR=∑i,j∈W∑h∈Hijpijhmijh,which subject to(15)∑i=1l∑j=l+1nhmijh≤Ch,1≤l≤nh,h∈H.where the constraints in (15) are train seat capacity constraints for each leg of each train. The value of mijh and pijh can be obtained by mijhk and pijhk, according to equations (1) and (2), respectively. pijhk and mijhk are from the initial solution or the output of the last iteration in the lower-level model.


### 4.2. The Lower-Level Model (Model 2)

Based on the number of allocated seats of each producti,j|h solved by the upper-level model, the lower-level model solves the price pijhk and the number of allocated seats mijhk in each period k for each product i,j|h. For each product i,j|h, the pricing model is as follows:(16)maxR=∑k=1Kpijhkmijhk,which subject to(17)∑k=1Kmijhk≤mijh,(18)mijhk≥0,1≤k≤K,(19)∑h∈Hijmijhk≤qijk,1≤k≤K,(20)p¯ijh≤pijhk≤p¯ijh,1≤k≤K,(21)pijhk≤pi1j1hk,i1≤i,j≤j1,i1,j1∈W,1≤k≤K,(22)pijhk1≤pijhk2,1≤k1≤k2≤K,where the constraint in (17) is the seat allocation constraint, which enforces that the sum of the number of seats in each period cannot exceed the total number of seats in the whole booking horizon. Other constraints are similar to equations (9)–(13).


## 4.1. The Upper-Level Model (Model 1)

The upper-level model simultaneously solves the number of allocated seats and corresponding price for all products in the whole booking horizon. The model is as follows:(14)maxR=∑i,j∈W∑h∈Hijpijhmijh,which subject to(15)∑i=1l∑j=l+1nhmijh≤Ch,1≤l≤nh,h∈H.where the constraints in (15) are train seat capacity constraints for each leg of each train. The value of mijh and pijh can be obtained by mijhk and pijhk, according to equations (1) and (2), respectively. pijhk and mijhk are from the initial solution or the output of the last iteration in the lower-level model.


## 4.2. The Lower-Level Model (Model 2)

Based on the number of allocated seats of each producti,j|h solved by the upper-level model, the lower-level model solves the price pijhk and the number of allocated seats mijhk in each period k for each product i,j|h. For each product i,j|h, the pricing model is as follows:(16)maxR=∑k=1Kpijhkmijhk,which subject to(17)∑k=1Kmijhk≤mijh,(18)mijhk≥0,1≤k≤K,(19)∑h∈Hijmijhk≤qijk,1≤k≤K,(20)p¯ijh≤pijhk≤p¯ijh,1≤k≤K,(21)pijhk≤pi1j1hk,i1≤i,j≤j1,i1,j1∈W,1≤k≤K,(22)pijhk1≤pijhk2,1≤k1≤k2≤K,where the constraint in (17) is the seat allocation constraint, which enforces that the sum of the number of seats in each period cannot exceed the total number of seats in the whole booking horizon. Other constraints are similar to equations (9)–(13).


## 5. Solution Method

The resolving thoughts are as follows. First, we solve the number of allocated seatsmijh for all products in Model 1. Then, based on mijh, we solve price in each period for each product in Model 2. Through the linkage solution of Model 1 and Model 2, the joint optimization of seat allocation and dynamic price is realized. By rebuilding Model 1 and Model 2 based on divide-and-conquer strategy, the bilevel multifollower model is solved.


### 5.1. The Equivalent Model of the Upper-Level Model (Model 1’)

Δmijh denotes the improving direction of mijh in Model 1. Correspondingly, Δpijh is the improving direction of pijh. Using the first derivative to express the relation between mijh and pijh, the equivalent model (Model 1’) of the upper-level model can be obtained.The objective function is to improve the total revenue of all products. It can be equivalently expressed as follows:(23)maxR=∑i,j∈W∑h∈Hijpijh+Δpijhmijh+Δmijh.The relationship betweenΔmijh and Δpijh can be expressed as follows:(24)Δpijh=dpijhdmijhΔmijh.Hence, Model 1’ can be transformed as follows:(25)maxR=∑i,j∈W∑h∈Hijpijh+dpijhdmijhΔmijhmijh+Δmijh,which subject to(26)∑i=1l∑j=l+1nhmijh+Δmijh≤Ch,1≤l≤nh,h∈H,(27)mijh+Δmijh≥0,i,j∈W,h∈Hij,(28)p¯ijh≤pijh+dpijhdmijhΔmijh≤p¯ijh,i,j∈W,h∈Hij,(29)Δmijh≤δ,i,j∈W,h∈Hij,where δ is the range parameter of ticket adjustment in the neighborhood of mijh. Since dpijh/dmijh is only valid in the neighborhood of mijh and pijh, the variation range of Δmijh should be limited to ensure the validity of the solution. In order to improve the efficiency of solving, δ is constantly changing in the iterative process, δ=δ0I−i/i, where i is the current iteration number, δ0 is the initial value of the range parameter of ticket adjustment in the neighborhood of mijh, and I is the preset maximum iteration number.The constraints include train seat capacity constraints, nonnegative constraints, price constraints, and neighborhood constraints. For each product, the sum ofΔmijhk in all periods cannot exceed Δmijh, so when Δmijh is small, it can be considered that Δmijh is mainly concentrated on a certain Δmijhk, which means the change amount of mijh is mainly from the change amount of mijhk in a certain period k. Price is negatively correlated to the number of allocated seats, that is, dpijh/dmijhk<0. Therefore, we can obtain(30)dpijhdmijh=mindpijhdmijhkΔmijh<0maxdpijhdmijhkΔmijh≥0,1≤k≤K,where dpijh/dmijhk can be expressed as follows:(31)dpijhdmijhk=cijk−cijhk−c^ijk∑h∈Hijmijhk/qijkηkmijh+pijhkmijh−∑k=1Kpijhkmijhkmijh×mijh.The derivation of equation (31) is shown in Appendix A.


### 5.2. The Equivalent Model of the Lower-Level Model (Model 2’)

By allocatingΔmijh to each period to obtain Δmijhk for each product i,j|h, the equivalent model (Model 2’) of the lower-level model can be obtained. Corresponding to Δmijhk, Δpijhk is the change amount of price in period k for product i,j|h. Model 2’ can be expressed as follows:(32)maxR=∑k=1Kpijhk+Δpijhkmijhk+Δmijhk,which subject to(33)∑k=1KΔmijhk≤Δmijh,(34)mijhk+Δmijhk≥0,1≤k≤K,(35)p¯ijh≤pijhk+Δpijhk≤p¯ijh,1≤k≤K,(36)pijhk+Δpijhk≤pi1j1hk,i1≤i,j≤j1,i1,j1∈W,1≤k≤K,(37)pijhk1+Δpijhk1≤pijhk2+Δpijhk2,1≤k1≤k2≤K,where the constraints in (33)–(37) are similar to constraints in (17) and (18) and (20)–(22). According to equations (4)–(6) and equation (19), we can obtain the relationship between Δmijhk and Δpijhk as follows:(38)Δpijhk=∑h∈Hijmijhkmijhkc^ijk−cijk−c^ijkηklnΔmijhk+qijkq^ijk.The derivation process of equation (38) is shown in Appendix B.


### 5.3. Solution Algorithm Framework

The divide-and-conquer solution algorithm framework of the bilevel multifollower programming model is shown in Algorithm1.Algorithm 1: Divide-and-conquer solution algorithm.
Set an initial feasible solution,mijhk=q^ijhk,pijhk=p^ijhk;Calculate the initial total revenue,R0=∑i,j∈W∑h∈Hij∑k=1Kpijhkmijhk;RepeatCalculatemijh=∑k=1Kmijhk; pijh=∑k=1Kpijhkmijhk/mijh;SolveΔmijh for all products by Model 1’;RepeatSolveΔmijhk for each product by Model 2’;Updatemijhk=mijhk+Δmijhk; pijhk=pijhk+Δpijhk;Calculate the total revenue,R=∑i,j∈W∑h∈Hij∑k=1Kpijhkmijhk;Compare the old and new revenue. Update the optimalmijhk and pijhk at the higher total revenue;Stop if the value of objective function does not improve in successive iterations;Output: final solution.


## 5.1. The Equivalent Model of the Upper-Level Model (Model 1’)

Δmijh denotes the improving direction of mijh in Model 1. Correspondingly, Δpijh is the improving direction of pijh. Using the first derivative to express the relation between mijh and pijh, the equivalent model (Model 1’) of the upper-level model can be obtained.The objective function is to improve the total revenue of all products. It can be equivalently expressed as follows:(23)maxR=∑i,j∈W∑h∈Hijpijh+Δpijhmijh+Δmijh.The relationship betweenΔmijh and Δpijh can be expressed as follows:(24)Δpijh=dpijhdmijhΔmijh.Hence, Model 1’ can be transformed as follows:(25)maxR=∑i,j∈W∑h∈Hijpijh+dpijhdmijhΔmijhmijh+Δmijh,which subject to(26)∑i=1l∑j=l+1nhmijh+Δmijh≤Ch,1≤l≤nh,h∈H,(27)mijh+Δmijh≥0,i,j∈W,h∈Hij,(28)p¯ijh≤pijh+dpijhdmijhΔmijh≤p¯ijh,i,j∈W,h∈Hij,(29)Δmijh≤δ,i,j∈W,h∈Hij,where δ is the range parameter of ticket adjustment in the neighborhood of mijh. Since dpijh/dmijh is only valid in the neighborhood of mijh and pijh, the variation range of Δmijh should be limited to ensure the validity of the solution. In order to improve the efficiency of solving, δ is constantly changing in the iterative process, δ=δ0I−i/i, where i is the current iteration number, δ0 is the initial value of the range parameter of ticket adjustment in the neighborhood of mijh, and I is the preset maximum iteration number.The constraints include train seat capacity constraints, nonnegative constraints, price constraints, and neighborhood constraints. For each product, the sum ofΔmijhk in all periods cannot exceed Δmijh, so when Δmijh is small, it can be considered that Δmijh is mainly concentrated on a certain Δmijhk, which means the change amount of mijh is mainly from the change amount of mijhk in a certain period k. Price is negatively correlated to the number of allocated seats, that is, dpijh/dmijhk<0. Therefore, we can obtain(30)dpijhdmijh=mindpijhdmijhkΔmijh<0maxdpijhdmijhkΔmijh≥0,1≤k≤K,where dpijh/dmijhk can be expressed as follows:(31)dpijhdmijhk=cijk−cijhk−c^ijk∑h∈Hijmijhk/qijkηkmijh+pijhkmijh−∑k=1Kpijhkmijhkmijh×mijh.The derivation of equation (31) is shown in Appendix A.


## 5.2. The Equivalent Model of the Lower-Level Model (Model 2’)

By allocatingΔmijh to each period to obtain Δmijhk for each product i,j|h, the equivalent model (Model 2’) of the lower-level model can be obtained. Corresponding to Δmijhk, Δpijhk is the change amount of price in period k for product i,j|h. Model 2’ can be expressed as follows:(32)maxR=∑k=1Kpijhk+Δpijhkmijhk+Δmijhk,which subject to(33)∑k=1KΔmijhk≤Δmijh,(34)mijhk+Δmijhk≥0,1≤k≤K,(35)p¯ijh≤pijhk+Δpijhk≤p¯ijh,1≤k≤K,(36)pijhk+Δpijhk≤pi1j1hk,i1≤i,j≤j1,i1,j1∈W,1≤k≤K,(37)pijhk1+Δpijhk1≤pijhk2+Δpijhk2,1≤k1≤k2≤K,where the constraints in (33)–(37) are similar to constraints in (17) and (18) and (20)–(22). According to equations (4)–(6) and equation (19), we can obtain the relationship between Δmijhk and Δpijhk as follows:(38)Δpijhk=∑h∈Hijmijhkmijhkc^ijk−cijk−c^ijkηklnΔmijhk+qijkq^ijk.The derivation process of equation (38) is shown in Appendix B.


## 5.3. Solution Algorithm Framework

The divide-and-conquer solution algorithm framework of the bilevel multifollower programming model is shown in Algorithm1.Algorithm 1: Divide-and-conquer solution algorithm.
Set an initial feasible solution,mijhk=q^ijhk,pijhk=p^ijhk;Calculate the initial total revenue,R0=∑i,j∈W∑h∈Hij∑k=1Kpijhkmijhk;RepeatCalculatemijh=∑k=1Kmijhk; pijh=∑k=1Kpijhkmijhk/mijh;SolveΔmijh for all products by Model 1’;RepeatSolveΔmijhk for each product by Model 2’;Updatemijhk=mijhk+Δmijhk; pijhk=pijhk+Δpijhk;Calculate the total revenue,R=∑i,j∈W∑h∈Hij∑k=1Kpijhkmijhk;Compare the old and new revenue. Update the optimalmijhk and pijhk at the higher total revenue;Stop if the value of objective function does not improve in successive iterations;Output: final solution.


## 6. Numerical Instances

### 6.1. Data

In this section, we use the data of train and passenger flow in the downward direction of Wuhan (WH) Station to Shenzhen North (SZN) Station of the China Wuhan-Guangzhou High-Speed Railway (WGHSR) (as shown in Figure2) to design a small-scale instance and a large-scale instance to verify the effectiveness of the proposed model and solution algorithm. The small-scale instance is performed to explore the influence of parameters such as price elastic parameters and train seat capacity on the optimal results. The solution algorithm was developed by MATLAB 2014a, and the numerical instances were performed on a Windows-based workstation with an Intel(R) Xeon(R) 3.70 GHz processor and 128 GB RAM.Figure 2
The line map of the downward direction of WH to SZN of China WGHSR.The numerical instance includes 20 trains serving the line (shown in Figure2), and these trains and the train trips are shown in Table 3. Among them, G1003, G1011, and G1133 comprise 16 carriages, each holding 1118 passengers. The rest of the trains travel with 8 carriages and could carry 559 passengers. For trains with the same departure and arrival stations, the stop plans are different and the departure times are distributed in different periods of the day. Each passenger station along the line is served by at least one train. There are 116 OD, served by 20 trains in total. 20 trains and 116 ODs are combined into 350 products. The maximum number of intermediate stops is 8 and the minimum number is 1 among the 20 trains.Table 3
Train composition table of numerical instance.
Train tripsWH-SZNWH-GZSCSS-SZNCSS-GZSGZS-SZNNumber of trains25436Train no.G1003G1011G1107G1123G1133G1141G1159G6001G6015G6021G6027G6107G6115G6121G6205G6215G6221G6229G6233G6243The current ticket booking horizon in China HSR is 30 days and the whole booking horizon is divided intoK=4 periods. 20 trains are divided into two categories according to their departure time. Trains departing before 12:00 are considered as category A, and trains departing after 12:00 are considered as category B. The fourth period is the closest to departure time, and in this period, a fixed fare without discount is adopted. The other three periods are dynamic pricing periods, which adopt dynamic discounts to sell tickets. The price elasticity parameters of the three periods are η1=2, η2=1.7, and η3=1.4, respectively. The specific division of booking horizon is shown in Table 4.Table 4
Booking horizon division of numerical instance.
Period no.k1234Start timeThe 1st dayA: the 19th dayA: the 25th dayA: the 29th dayB: the 20th dayB: the 26th dayB: the 30th dayEnd timeA: the 18th dayA: the 24th dayA: the 28th dayOne hour before departingB: the 19th dayB: the 25th dayB: the 29th dayThe real ticket sale data are taken as the initial solution of the instance. Set the initial value of the range parameter of ticket adjustment in the neighborhood ofmijh as 5, that is, δ0=5. The influence of different values of δ0 on the solution will be analyzed later.


### 6.2. Small-Scale Instance

The small-scale numerical instance is made up of two down trains, G6229 and G6233, from GZ to SZN along WGHSR, including 8 ODs and 9 products in total. In this instance, the relationship between trains and ODs is shown in Figure3.Figure 3
The relationship between trains and ODs in small-scale instance.The optimization process curves of total revenue and total passenger kilometer in the small-scale instance are shown in Figure4. As can be seen from this figure, the optimization process obtains the final solution at the 15th iteration. Compared with the initial solution, the total revenue increased from 31,986.35 Yuan to 333,233.18 Yuan, with an increase rate of 3.90%. The total passenger kilometer increased by 28.00% from 43,874.58 passenger⋅kilometer (pkm) to 56,157.93 pkm. The average passenger-kilometer price decreased from 0.73 Yuan to 0.59 Yuan, with a decrease of 13.73%. Price discount makes the passenger flow increase significantly, which increases the passenger revenue to a certain extent.Figure 4
Optimization process curves of small-scale numerical instance.The comparison of the price and number of allocated seats for each product in each period (before and after optimization) is shown in Table5 (the passenger flow of product 4 is 0, so this product is omitted). As seen in Figure 5, for most products, price is reduced to attract more demand, which could achieve the purpose of increasing revenue.Table 5
The comparison of price and number of allocated seats before and after optimization.
Productsp0ijhm0ijhp˜ijhρp%m˜ijhρm%TrainODpijh1,pijh2,pijh3mijh1,mijh2,mijh3G6229GZS-QS24.5320.3 (14.7, 17.0, 20.3)−17.123 (0, 0, 3)10.94GZS-GMC59.51849.5 (35.7, 41.4, 49.5)−16.8920 (0, 0, 20)10.50GZS-SZN74.522061.2 (44.7, 51.0, 62.1)−17.89247 (2, 18, 227)12.15QS-SZN49.51240.1 (30.5, 35.3, 42.1)−18.9414 (0, 4, 10)14.32GMC-SZN14.5612.3 (9.2, 10.7, 12.7)−15.236 (0, 1, 5)8.14G6233GZS-HM34.51635.3 (28.0, 31.2, 35.7)2.4114 (0, 1, 13)−12.60GZS-SZN84.521459.5 (47.4, 55.0, 66.4)−29.59255 (58, 58, 139)19.17HM-SZN39.52129.6 (23.7, 26.5, 31.6)−24.9827 (4, 4, 19)27.10Notes:p˜ijh, the average price in the first three periods; m˜ijh, the average number of allocated seats in the first three periods; p0ijh, the initial price; m0ijh, the initial number of allocated seats before optimization; ρp, the increase rate of the average price compared with initial values; ρm, the increase rate of the average number of allocated seats compared with initial values. The unit of price is Chinese Yuan.Figure 5
Price and number of seats during the booking horizon before and after optimization.


### 6.3. Sensitivity Analysis

In this section, based on the small-scale instance in the previous section, we explore the influence of the critical parameter changes on the optimization results and carry out sensitivity analysis on price elasticity parameter, train seat capacity, and the initial valueδ0 of the range parameter of ticket adjustment in the neighborhood of mijh.


#### 6.3.1. Sensitivity Analysis on Price Elasticity Parameter

In order to analyze the influence of price elasticity parameters on total revenue, the price elasticity parameters in each period,η1, η2, and η3, were changed by multiples of 0.75, 1.00, 1.25, 1.50, 1.75, and 2.00. The change curve of total revenue with five groups of price elasticity parameters is shown in Figure 6.Figure 6
The total revenue changing with five groups of price elasticity parameters.As can be seen from Figure6, the total revenue is positively correlated with the price elasticity parameter. The larger the price elasticity parameter is, the more significant the attraction effect of adjusting price on passenger flow will be, and the larger the number of iterations reaching convergence, the slower the convergence speed.


#### 6.3.2. Sensitivity Analysis on Train Seat Capacity

Train seat capacity determines the number of seats available for allocation. In this section, we analyze the impact of train seat capacity on total revenue. When the number of seats on train G6233 increases from 500 to 700, with a step size of 10, the changing trend of total revenue is shown in Figure7. With the increase of seat capacity, the total revenue shows an increasing trend between 500 and 580; at the same time, the growth rate gradually slows down and tends to stabilize when seat capacity exceeds 580. The results show that the increase of train seat capacity can improve revenue to some extent, but when the capacity is too loose, it cannot bring more revenue; this is because price cannot be reduced indefinitely.Figure 7
The total revenue changing with train seat capacity.


#### 6.3.3. Sensitivity Analysis on Initial Value of the Range Parameter of Ticket Adjustment

In the optimization algorithm, the initial valueδ0 of the range parameter of ticket adjustment in the neighborhood of mijh limits the adjustment amplitude of the number of seats. In order to analyze the influence of δ0 on the solution results, δ0 is set at 1, 3, 5, 7, and 10, and the change curves of total revenue under different δ0 are shown in Figure 8.Figure 8
The total revenue changing with differentδ0.Figure8 shows that the smaller δ0 is, the better the optimization result is, but the slower the convergence rate. In this small-scale instance, the difference between the lowest total revenue (when δ0=10) and the highest total revenue (when δ0=1) is only 40.95 Yuan (-0.12%). We set δ0=5 in this instance, and there is almost no difference (only −0.05%) in total revenue when δ0=5 and when δ0=1.


### 6.4. Large-Scale Instance

In this section, the large-scale instance consisting of 20 trains and 116 ODs on WGHSR was optimized. The final solution was obtained through 21 iterations, which takes about 1.15 hours. The optimization process curves of total revenue and passenger kilometer are shown in Figure9.Figure 9
Optimization process curve of large-scale numerical instance.The total revenue of the final solution is 2,206,256.79 Yuan, which increased by 1.61% compared with the initial solution. The final total passenger kilometer reaches 5,716,751pkm, with a growth rate of 23.37%. The average passenger-kilometer price reduced from 0.47 Yuan to 0.39 Yuan, with a 17.64% decrease. In the large-scale instance, the large price discount brings an obvious increase in passenger flow, which improves the total revenue to a certain extent.Compared with the initial solution, the revenue change rate of each train is shown in Figure10. Among them, the revenue change rate of 17 trains is positive and the maximum revenue change rate of a single train is 8.72%. For most trains, the revenue is improved. The revenue of three long-distance trains (G1003, G1107, and G1123) decreases, except for G1123, which has the largest decline of 3.28%; the other two trains decreased by less than 1%.Figure 10
The comparison of each train’s revenue change rate.We carried out a further analysis based on travel distance (i.e., the distance a train travels from origin to destination). Figure11 shows the change rate of average revenue and passenger-kilometer rise with fluctuations when travel distance increases; the improving amplitude of total revenue and the growth rate of passenger kilometer of long-distance trains are greater than those of short-distance trains.Figure 11
The rate of average revenue and passenger kilometer to travel distance.Furthermore, we select GZS-SZN and WH-GZS as typical short-distance OD and long-distance OD, respectively, for analysis. After optimization, the average revenue growth rate of GZS-SZN is 4.10%, while the average revenue growth rate of WH-GZS is 2.92%. The average revenue improvement amplitude of long-distance OD is smaller than that of short-distance OD. Further analysis of the revenue rate, passenger flow change rate, and price change rate shows that the difference among products serving short-distance OD is more obvious than that serving long-distance OD, as shown in Figure12. This is because there are more trains available for short-distance passengers to travel and the difference between the products selected by passengers is more obvious.Figure 12
(a) Index variation of products in GZS-SZN. (b) Index variation of products in WH-GZS.
(a)(b)In Figure12, for short-distance OD GZS,SZN, the revenue of product GZS,SZN|G6207 serving by long-distance train G6027 decreased slightly, but the total revenue of train G6027 increased (see Figure 10). Meanwhile, the revenue of other products serving OD GZS,SZN all increased, especially the revenue of products GZS,SZN|G6215 and GZS,SZN|G6221 served by short-distance trains increased most obviously. It shows that the seat allocation mechanism objectively causes the result of “preferentially selling long-distance tickets to long-distance passengers.”


## 6.1. Data

In this section, we use the data of train and passenger flow in the downward direction of Wuhan (WH) Station to Shenzhen North (SZN) Station of the China Wuhan-Guangzhou High-Speed Railway (WGHSR) (as shown in Figure2) to design a small-scale instance and a large-scale instance to verify the effectiveness of the proposed model and solution algorithm. The small-scale instance is performed to explore the influence of parameters such as price elastic parameters and train seat capacity on the optimal results. The solution algorithm was developed by MATLAB 2014a, and the numerical instances were performed on a Windows-based workstation with an Intel(R) Xeon(R) 3.70 GHz processor and 128 GB RAM.Figure 2
The line map of the downward direction of WH to SZN of China WGHSR.The numerical instance includes 20 trains serving the line (shown in Figure2), and these trains and the train trips are shown in Table 3. Among them, G1003, G1011, and G1133 comprise 16 carriages, each holding 1118 passengers. The rest of the trains travel with 8 carriages and could carry 559 passengers. For trains with the same departure and arrival stations, the stop plans are different and the departure times are distributed in different periods of the day. Each passenger station along the line is served by at least one train. There are 116 OD, served by 20 trains in total. 20 trains and 116 ODs are combined into 350 products. The maximum number of intermediate stops is 8 and the minimum number is 1 among the 20 trains.Table 3
Train composition table of numerical instance.
Train tripsWH-SZNWH-GZSCSS-SZNCSS-GZSGZS-SZNNumber of trains25436Train no.G1003G1011G1107G1123G1133G1141G1159G6001G6015G6021G6027G6107G6115G6121G6205G6215G6221G6229G6233G6243The current ticket booking horizon in China HSR is 30 days and the whole booking horizon is divided intoK=4 periods. 20 trains are divided into two categories according to their departure time. Trains departing before 12:00 are considered as category A, and trains departing after 12:00 are considered as category B. The fourth period is the closest to departure time, and in this period, a fixed fare without discount is adopted. The other three periods are dynamic pricing periods, which adopt dynamic discounts to sell tickets. The price elasticity parameters of the three periods are η1=2, η2=1.7, and η3=1.4, respectively. The specific division of booking horizon is shown in Table 4.Table 4
Booking horizon division of numerical instance.
Period no.k1234Start timeThe 1st dayA: the 19th dayA: the 25th dayA: the 29th dayB: the 20th dayB: the 26th dayB: the 30th dayEnd timeA: the 18th dayA: the 24th dayA: the 28th dayOne hour before departingB: the 19th dayB: the 25th dayB: the 29th dayThe real ticket sale data are taken as the initial solution of the instance. Set the initial value of the range parameter of ticket adjustment in the neighborhood ofmijh as 5, that is, δ0=5. The influence of different values of δ0 on the solution will be analyzed later.


## 6.2. Small-Scale Instance

The small-scale numerical instance is made up of two down trains, G6229 and G6233, from GZ to SZN along WGHSR, including 8 ODs and 9 products in total. In this instance, the relationship between trains and ODs is shown in Figure3.Figure 3
The relationship between trains and ODs in small-scale instance.The optimization process curves of total revenue and total passenger kilometer in the small-scale instance are shown in Figure4. As can be seen from this figure, the optimization process obtains the final solution at the 15th iteration. Compared with the initial solution, the total revenue increased from 31,986.35 Yuan to 333,233.18 Yuan, with an increase rate of 3.90%. The total passenger kilometer increased by 28.00% from 43,874.58 passenger⋅kilometer (pkm) to 56,157.93 pkm. The average passenger-kilometer price decreased from 0.73 Yuan to 0.59 Yuan, with a decrease of 13.73%. Price discount makes the passenger flow increase significantly, which increases the passenger revenue to a certain extent.Figure 4
Optimization process curves of small-scale numerical instance.The comparison of the price and number of allocated seats for each product in each period (before and after optimization) is shown in Table5 (the passenger flow of product 4 is 0, so this product is omitted). As seen in Figure 5, for most products, price is reduced to attract more demand, which could achieve the purpose of increasing revenue.Table 5
The comparison of price and number of allocated seats before and after optimization.
Productsp0ijhm0ijhp˜ijhρp%m˜ijhρm%TrainODpijh1,pijh2,pijh3mijh1,mijh2,mijh3G6229GZS-QS24.5320.3 (14.7, 17.0, 20.3)−17.123 (0, 0, 3)10.94GZS-GMC59.51849.5 (35.7, 41.4, 49.5)−16.8920 (0, 0, 20)10.50GZS-SZN74.522061.2 (44.7, 51.0, 62.1)−17.89247 (2, 18, 227)12.15QS-SZN49.51240.1 (30.5, 35.3, 42.1)−18.9414 (0, 4, 10)14.32GMC-SZN14.5612.3 (9.2, 10.7, 12.7)−15.236 (0, 1, 5)8.14G6233GZS-HM34.51635.3 (28.0, 31.2, 35.7)2.4114 (0, 1, 13)−12.60GZS-SZN84.521459.5 (47.4, 55.0, 66.4)−29.59255 (58, 58, 139)19.17HM-SZN39.52129.6 (23.7, 26.5, 31.6)−24.9827 (4, 4, 19)27.10Notes:p˜ijh, the average price in the first three periods; m˜ijh, the average number of allocated seats in the first three periods; p0ijh, the initial price; m0ijh, the initial number of allocated seats before optimization; ρp, the increase rate of the average price compared with initial values; ρm, the increase rate of the average number of allocated seats compared with initial values. The unit of price is Chinese Yuan.Figure 5
Price and number of seats during the booking horizon before and after optimization.


## 6.3. Sensitivity Analysis

In this section, based on the small-scale instance in the previous section, we explore the influence of the critical parameter changes on the optimization results and carry out sensitivity analysis on price elasticity parameter, train seat capacity, and the initial valueδ0 of the range parameter of ticket adjustment in the neighborhood of mijh.


### 6.3.1. Sensitivity Analysis on Price Elasticity Parameter

In order to analyze the influence of price elasticity parameters on total revenue, the price elasticity parameters in each period,η1, η2, and η3, were changed by multiples of 0.75, 1.00, 1.25, 1.50, 1.75, and 2.00. The change curve of total revenue with five groups of price elasticity parameters is shown in Figure 6.Figure 6
The total revenue changing with five groups of price elasticity parameters.As can be seen from Figure6, the total revenue is positively correlated with the price elasticity parameter. The larger the price elasticity parameter is, the more significant the attraction effect of adjusting price on passenger flow will be, and the larger the number of iterations reaching convergence, the slower the convergence speed.


### 6.3.2. Sensitivity Analysis on Train Seat Capacity

Train seat capacity determines the number of seats available for allocation. In this section, we analyze the impact of train seat capacity on total revenue. When the number of seats on train G6233 increases from 500 to 700, with a step size of 10, the changing trend of total revenue is shown in Figure7. With the increase of seat capacity, the total revenue shows an increasing trend between 500 and 580; at the same time, the growth rate gradually slows down and tends to stabilize when seat capacity exceeds 580. The results show that the increase of train seat capacity can improve revenue to some extent, but when the capacity is too loose, it cannot bring more revenue; this is because price cannot be reduced indefinitely.Figure 7
The total revenue changing with train seat capacity.


### 6.3.3. Sensitivity Analysis on Initial Value of the Range Parameter of Ticket Adjustment

In the optimization algorithm, the initial valueδ0 of the range parameter of ticket adjustment in the neighborhood of mijh limits the adjustment amplitude of the number of seats. In order to analyze the influence of δ0 on the solution results, δ0 is set at 1, 3, 5, 7, and 10, and the change curves of total revenue under different δ0 are shown in Figure 8.Figure 8
The total revenue changing with differentδ0.Figure8 shows that the smaller δ0 is, the better the optimization result is, but the slower the convergence rate. In this small-scale instance, the difference between the lowest total revenue (when δ0=10) and the highest total revenue (when δ0=1) is only 40.95 Yuan (-0.12%). We set δ0=5 in this instance, and there is almost no difference (only −0.05%) in total revenue when δ0=5 and when δ0=1.


## 6.3.1. Sensitivity Analysis on Price Elasticity Parameter

In order to analyze the influence of price elasticity parameters on total revenue, the price elasticity parameters in each period,η1, η2, and η3, were changed by multiples of 0.75, 1.00, 1.25, 1.50, 1.75, and 2.00. The change curve of total revenue with five groups of price elasticity parameters is shown in Figure 6.Figure 6
The total revenue changing with five groups of price elasticity parameters.As can be seen from Figure6, the total revenue is positively correlated with the price elasticity parameter. The larger the price elasticity parameter is, the more significant the attraction effect of adjusting price on passenger flow will be, and the larger the number of iterations reaching convergence, the slower the convergence speed.


## 6.3.2. Sensitivity Analysis on Train Seat Capacity

Train seat capacity determines the number of seats available for allocation. In this section, we analyze the impact of train seat capacity on total revenue. When the number of seats on train G6233 increases from 500 to 700, with a step size of 10, the changing trend of total revenue is shown in Figure7. With the increase of seat capacity, the total revenue shows an increasing trend between 500 and 580; at the same time, the growth rate gradually slows down and tends to stabilize when seat capacity exceeds 580. The results show that the increase of train seat capacity can improve revenue to some extent, but when the capacity is too loose, it cannot bring more revenue; this is because price cannot be reduced indefinitely.Figure 7
The total revenue changing with train seat capacity.


## 6.3.3. Sensitivity Analysis on Initial Value of the Range Parameter of Ticket Adjustment

In the optimization algorithm, the initial valueδ0 of the range parameter of ticket adjustment in the neighborhood of mijh limits the adjustment amplitude of the number of seats. In order to analyze the influence of δ0 on the solution results, δ0 is set at 1, 3, 5, 7, and 10, and the change curves of total revenue under different δ0 are shown in Figure 8.Figure 8
The total revenue changing with differentδ0.Figure8 shows that the smaller δ0 is, the better the optimization result is, but the slower the convergence rate. In this small-scale instance, the difference between the lowest total revenue (when δ0=10) and the highest total revenue (when δ0=1) is only 40.95 Yuan (-0.12%). We set δ0=5 in this instance, and there is almost no difference (only −0.05%) in total revenue when δ0=5 and when δ0=1.


## 6.4. Large-Scale Instance

In this section, the large-scale instance consisting of 20 trains and 116 ODs on WGHSR was optimized. The final solution was obtained through 21 iterations, which takes about 1.15 hours. The optimization process curves of total revenue and passenger kilometer are shown in Figure9.Figure 9
Optimization process curve of large-scale numerical instance.The total revenue of the final solution is 2,206,256.79 Yuan, which increased by 1.61% compared with the initial solution. The final total passenger kilometer reaches 5,716,751pkm, with a growth rate of 23.37%. The average passenger-kilometer price reduced from 0.47 Yuan to 0.39 Yuan, with a 17.64% decrease. In the large-scale instance, the large price discount brings an obvious increase in passenger flow, which improves the total revenue to a certain extent.Compared with the initial solution, the revenue change rate of each train is shown in Figure10. Among them, the revenue change rate of 17 trains is positive and the maximum revenue change rate of a single train is 8.72%. For most trains, the revenue is improved. The revenue of three long-distance trains (G1003, G1107, and G1123) decreases, except for G1123, which has the largest decline of 3.28%; the other two trains decreased by less than 1%.Figure 10
The comparison of each train’s revenue change rate.We carried out a further analysis based on travel distance (i.e., the distance a train travels from origin to destination). Figure11 shows the change rate of average revenue and passenger-kilometer rise with fluctuations when travel distance increases; the improving amplitude of total revenue and the growth rate of passenger kilometer of long-distance trains are greater than those of short-distance trains.Figure 11
The rate of average revenue and passenger kilometer to travel distance.Furthermore, we select GZS-SZN and WH-GZS as typical short-distance OD and long-distance OD, respectively, for analysis. After optimization, the average revenue growth rate of GZS-SZN is 4.10%, while the average revenue growth rate of WH-GZS is 2.92%. The average revenue improvement amplitude of long-distance OD is smaller than that of short-distance OD. Further analysis of the revenue rate, passenger flow change rate, and price change rate shows that the difference among products serving short-distance OD is more obvious than that serving long-distance OD, as shown in Figure12. This is because there are more trains available for short-distance passengers to travel and the difference between the products selected by passengers is more obvious.Figure 12
(a) Index variation of products in GZS-SZN. (b) Index variation of products in WH-GZS.
(a)(b)In Figure12, for short-distance OD GZS,SZN, the revenue of product GZS,SZN|G6207 serving by long-distance train G6027 decreased slightly, but the total revenue of train G6027 increased (see Figure 10). Meanwhile, the revenue of other products serving OD GZS,SZN all increased, especially the revenue of products GZS,SZN|G6215 and GZS,SZN|G6221 served by short-distance trains increased most obviously. It shows that the seat allocation mechanism objectively causes the result of “preferentially selling long-distance tickets to long-distance passengers.”


## 7. Conclusions

This paper studies the joint optimization of multistage dynamic pricing and seat allocation for multitrain and multi-OD in HSR. A mathematical programming model is constructed to maximize the total revenue of all trains as the objective function. The constraints include the price time constraints in each period and price space constraints among products, which makes the model more consistent with the real operation situation. Then, the model is transformed into a bilevel multifollower programming model, which includes a large-scale static seat allocation model in the whole booking horizon for all products and many small-scale dynamic pricing optimization models for each product in each decision period. Based on divide-and-conquer strategy the solution method we proposed effectively reduces the solving scale and difficulty by adjusting the number of tickets among trains using a seat allocation model and solving the multistage price of each product.The instance on China’s WGHSR shows that the model and algorithm have a good solving effect. In the large-scale instance, the total revenue increases by 1.61%. The passenger flow increases significantly through dynamic pricing. The model and algorithm parameters affect the solving results. The price elasticity parameter is positively correlated with total revenue. Total revenue can be improved by moderately increasing train seat capacity. The initial value of range parameter of ticket adjustment has a great influence on the solving efficiency, but has little influence on the final solution quality. Through the dynamic pricing strategy, the revenue of most trains is increased. The revenue growth rate of short-distance trains is higher than that of long-distance trains and the differences of the revenue growth rate among short-distance trains is more obvious.However, some factors were not taken into account in this study. In this paper, the whole booking horizon is divided into 4 pre-given periods which include 3 dynamic price periods. A way to accurately divide the booking horizon is worth further study. In addition, in actual operations, HSR trains have different seat classes. The dynamic pricing of multiple seats is also one of the future research directions. The last but not least, if there is a special requirement to guide demand and make the equilibrium of capacity utilization among different trains better, optimization objectives or constraints about the range of the train full load rate can be added on the basis of the optimization model proposed in this paper, but the solution method needs further research.



---

*Source: 5316574-2021-12-24.xml*