Collaborative optimization of high-speed railway ticket allocation and stopping plans based on time-period stochastic demands

Abstract

Ticket allocation and train stopping plans are important parts of railway transportation organization. At present, most of the ticket allocation plans are based on fixed train stopping plans, which limit the scope of ticket allocation. Trains can only serve passenger demands between stopping stations, leading to a loss of passenger demands at non-stopping stations, resulting in low seat occupancy rates and low revenue for railway enterprise. In order to better meet passenger demands, improve seat occupancy rates and increase the revenue of railway enterprises, this paper constructs a collaborative optimization model of ticket allocation and stopping plans based on stochastic demand and passenger choice behaviours in different time periods. Combined with CPLEX solver, the simulated annealing algorithm is designed to solve the problem. At the same time, new neighbourhood solution generation strategies of train stopping plans and ticket allocation plans under given stopping plans are designed. The experimental results show that in small-scale and large-scale experiments, the proposed method increases revenue by 0.14% and 9.09%, respectively, and effectively improves seat occupancy rates.

1. Introduction

In recent years, China's high-speed railway has developed rapidly. By the end of 2022, the mileage of high-speed railways in operation has reached 42,000 kilometres. The rapid development of railways has attracted more and more passengers to travel. However, the existing train capacity is relatively tight and cannot always meet rapidly growing passenger demands. This requires rail operators to efficiently use the precious train capacity or train seats for satisfying passengers’ travel to the maximal degree. Thus, making full use of train seat capacity, meeting passenger demands and increasing revenue have become the focus of railway enterprises.

High-speed railway ticket allocation is the practice of allocating the limited seat capacity of trains reasonably based on passenger demand in order to optimize revenue and seat occupancy rates, while the stopping plan is to determine the stopping sequence of each train in its operation section. Ticket allocation and train stopping plans are closely related. Let us consider a route with three stations where two trains operate. There are three possible combinations for the stopping plan:

• Case 1. Neither train stops at the intermediate station.

• Case 2. One train stops at the intermediate station, while the other does not.

• Case 3. Both trains stop at the intermediate station.

Assuming both trains have a capacity of 50, passenger demand and ticket prices are shown in Table 1. The total revenue of the railway enterprise under the combination of three stopping plans is as follows:

• Case 1. Train A and Train B only serve OD (1,3) with a passenger demand of 40, and the total capacity of both trains is 100. Therefore, the passenger demand of OD (1,3) can be entirely met, while the passenger demand of OD (1,2) and OD (2,3) is lost. If the passenger demand is evenly distributed among the trains, the seat occupancy rates for both trains in each section would be 40%. The total revenue of the railway enterprise is 40 × 20 = 800.

• Case 2. Both trains can serve OD (1,3), but only one train serves OD (1,2) and OD (2,3). In this case, the passenger demand of OD (1,3) can be fully met, while there will be some loss in passenger demand for OD (1,2) and OD (2,3). The seat occupancy rates for the two trains in each section would be 100% and 80%, respectively. The maximum revenue of the railway enterprise is 50 × 10 + 50 × 10 + 40 × 20 = 1800.

• Case 3. Both trains can serve all OD pairs, and all passenger demands can be met. If the passenger demand is evenly distributed among the trains, the seat occupancy rates for both trains in each section would be 95% and 100%. The total revenue of the railway enterprise is 60 × 10 + 55 × 10 + 40 × 20 = 1950.

The above analysis is based on the situation where the demand is smaller than the capacity. To further analyse the situation where the capacity is smaller than the demand, we keep train capacity and ticket prices unchanged, and the passenger demand for OD (1,2), OD (2,3) and OD (1,3) is changed to 80, 90 and 100, respectively. The analysis of ticket allocation results in the situation as follows:

• Case 1. Train A and Train B only serve OD (1,3) with a passenger demand of 100, and the total capacity of both trains is 100. Therefore, the passenger demand of OD (1,3) can be exactly met, while the passenger demand of OD (1,2) and OD (2,3) is lost. If the passenger demand is evenly distributed among the trains, the seat occupancy rates for both trains in each section would be 100%. The total revenue of the railway enterprise is 100 × 20 = 2000.

• Case 2. Both trains can serve OD (1,3), but only one train serves OD (1,2) and OD (2,3). In this case, the capacity of each train is fully utilized. The passenger demand of each OD has varying degrees of loss. The seat occupancy rates for the two trains in each section would be 100%. The maximum revenue of the railway enterprise is 50 × 10 + 50 × 10 + 50 × 20 = 2000.

• Case 3. Both trains can serve all OD pairs. In this case, the capacity of each train is fully utilized, and there are two ticket allocation schemes corresponding to the maximum revenue of the railway enterprise: one is that the capacity of both trains is used to serve the 100 passenger demands of OD (1,3), another is that one train serves the 50 passenger demands of OD (1,3) and another is that the train serves the 50 passenger demands of OD (1,2) and OD (2,3), respectively. The seat occupancy rates for both trains in each section would be 100%. The total revenue of the railway enterprise is 100 × 20 = 2000 or 50 × 10 + 50 × 10 + 50 × 20 = 2000.

Therefore, under the restriction of different stopping plans, the optimal ticket allocation plan is different, and the seat occupancy rate is also different. It can be seen that the stopping plan determines the travel train that passengers can choose, which indirectly determines the OD that the tickets can be allocated, and the ticket allocation determines whether passenger demands can be met. Han and Ren [1] proposed that there is a dynamic interaction between ticket allocation and the stopping plan, and pointed out the two need to coordinate with each other to ensure passenger demands. Qi et al. [2] also pointed out that the stopping plan is the basis of subsequent ticket allocation and can provide a reference for it.

In conclusion, train stopping plans and ticket allocation are important components of high-speed railway transportation organization. Collaboratively formulating high-speed railway ticket allocation plans and train stopping plans is of great significance for improving the use of train rate and the railway enterprise revenue. However, existing literature studies ticket allocation plans based on a fixed stopping plan, without considering the interaction between stopping plan and ticket allocation. This paper is devoted to studying the collaborative optimization problem of ticket allocation and train stopping plans. A probabilistic nonlinear programming model is constructed based on travel choice behaviours of stochastic demand, and a simulated annealing algorithm combined with CPLEX solver is designed to solve the problem.

2. Literature review

Our research mainly focuses on two fields: train stopping plans and ticket allocation. The research on stopping plans and ticket allocation is relatively mature. As an important part of railway transportation organization, the number of stops is very important. More stops mean the potential to serve more OD passengers, but they also increase the train's travel time and the stopping costs of the railway enterprise. Therefore, train stopping plans must balance train efficiency and passenger service. In recent years, many scholars have studied various aspects of train stopping plans. Eisele [3] divided the train stopping modes of suburban commuter railways into all-stop plans, skip-stop plans and zone-stop plans, suggesting that zone-stop plans better cater to commuter railway passenger demands. Park et al. [4, 5] transformed the optimization problems of train stopping plans into transportation path optimization problems, establishing a multi-objective linear programming model based on a multi-commodity flow structure. Liu et al. [6] proposed a machine learning method to solve stopping plan optimization problems, and the performance of the method was verified by the example of the Beijing–Shanghai high-speed railway. Parbo et al. [7] and Wang et al. [8] constructed a bi-level programming model considering passenger flow assignment. Some scholars have carried out research on passenger-related factors to better balance train efficiency and passenger service. Fu et al. [9] and Zha et al. [10] matched the characteristics of passenger demands with the combination of train stopping modes. Yin et al. [11] considered the fairness of passenger allocation and the cost of operation, and constructed the transportation network utility maximization model by jointly optimizing the passenger allocation and vehicle schedules. Altazin et al. [12] established a mixed integer linear programming model with the goal of minimizing the waiting time of passengers, and proposed to reduce the impact of external interference by skipping stations. Huang and Shuai [13] studied the adjustment method of high-speed railway train stop plans from the perspective of improving passenger transfer efficiency. Cheng et al. [14] considered the bounded rationality of passengers, and built a model to study skip-stop operation plans for urban rail transit with the goal of maximizing passenger travel time savings and maximizing congestion costs savings. Xu et al. [15] optimized the train stop schedule plan by considering the dissatisfaction with arrival time of passengers. In addition, it is necessary to combine other sub-problems of train operation plans and stopping plans. Qi et al. [2] proposed a comprehensive optimization method for train operation section, stopping plan and passenger flow assignment. Liao et al. [16] studied the train diagram optimization problem considering stop decisions under a complex train operation environment. For the collaborative optimization problem of stopping plans and train timetables, Yue et al. [17] designed a column-generation-based heuristic algorithm that considered passenger service demands and train scheduling. The results showed that the method could improve the service level of trains. Considering passenger demands and train energy saving, Xie et al. [18] constructed a model with the goal of minimizing train delay probability, energy consumption and train travel time, and designed a genetic algorithm to solve it. Cacchiani et al. [19] explored train arrival and departure times at each station and stopping plans, establishing a mixed integer linear programming model to obtain robust solutions adaptable to uncertain passenger demands. Dong et al. [20] constructed a mixed-integer nonlinear programming model for integrated combination optimization of train stop plans and timetables under more realistic conditions, and designed an adaptive large-scale neighbourhood search algorithm for a solution. Aiming at overcrowded subway lines, based on time-varying and elastic passenger demands, Shi et al. [21] studied the collaborative optimization of train timetables and train stopping plans from the perspective of traffic safety.

Under the premise of determining train stopping plans, many scholars have explored the issue of ticket allocation. The research on ticket allocation originated from the theory of revenue management and has developed significantly. Ciancimino et al. [22] first applied revenue management to the railway seat allocation problem, constructed both deterministic linear programming and stochastic nonlinear programming models and designed a Lagrange algorithm to solve models. On the basis of Ciancimino et al. [22], You [23] studied railway seat allocation under two fare classes. Zhao et al. [24] studied the ticket allocation problem under multi-train and multi-stop plans, employing a particle swarm optimization algorithm for the solution. Based on stochastic demands and passenger choice behaviour, Wang et al. [25] established single-stage and multi-stage ticket allocation models and transformed them into equivalent linear models for a solution, while Yan et al. [26] studied the ticket allocation problem of multi-level ticket prices. However, the above studies are only from the perspective of ticket allocation, without considering the influence of other factors. Yan et al. [27] focused on the collaborative optimization of ticket allocation and flexible train composition based on stochastic demands. They constructed a stochastic nonlinear programming model and transformed it into an equivalent linear model to solve. Hetrakul and Cirillo [28], Xu et al. [29] and Ongprasert [30] studied the collaborative optimization of ticket allocation and ticket prices. Luo et al. [31] considered optimizing ticket allocation with the concept of ‘first-come, first-served’ seating. On the basis of Luo et al. [31], Zhou and Han [32] further considered an OD-shared ticket sales strategy to optimize the train ticket allocation plan.

Considering the interaction between ticket allocation and train stopping plans, Han et al. [1] constructed a model based on uncertain demands to maximize passenger satisfaction and average seat occupancy. Based on fixed demands, Zhang et al. [33] established an integer programming model with the goals of maximizing operator revenue and minimizing passenger costs, and solved it using the CVX toolbox. However, none of the aforementioned studies took into account passenger travel choice behaviour. Based on the above research, Chen and Wang [34] considered passenger travel choice behaviours, optimized the ticket allocation and train stopping plans based on fixed demands and designed a particle swarm harmony search algorithm.

On the one hand, the current optimization of ticket allocation is based on the given train stopping plan, which strictly limits the scope of ticket allocation. On the other hand, the same passenger demands will result in different ticket revenues for railway enterprises under different stopping plans. As one of its main sources of revenue, increasing ticket revenue is the main focus of railway enterprises. The biggest difference between the collaborative optimization of ticket allocation and stopping plans and traditional ticket allocation is that ticket allocation is no longer limited by stopping plans; and at the same time, the ticket allocation and stopping plans that maximize the revenue of the railway enterprise are obtained. This breaks the inherent pattern of first determining train stopping plans and then determining ticket allocation plans, and has great reference significance for guiding railway enterprises to improve transportation organization efficiency.

On the basis of previous studies, this paper studies the collaborative optimization of ticket allocation and stopping plans based on time-period stochastic demands and passenger choice behaviours, so as to maximize the revenue of railway enterprises. Different from Zhang et al. [33] and Chen and Wang [34], who based their work on fixed demand, this paper aligns more closely with practical scenarios by considering stochastic demand. In contrast to the objective function constructed by Han et al. [1], this paper constructs a probabilistic nonlinear programming model with the objective of maximizing railway enterprise revenue, and designs a simulated annealing algorithm combined with CPLEX solver for solving. The method in this paper can better improve the seat occupancy rate and revenue of railway enterprises.

The contributions of this paper are as follows:

1. The probabilistic nonlinear integer programming model for collaborative optimization of ticket allocation and stopping plans is constructed for the multi-train and multi-stop high-speed railway network. Considering the various constraints of ticket allocation and stopping plans, a mathematical model is constructed with the objectives of maximizing railway enterprise revenue and minimizing train stop costs. This paper achieves collaborative optimization of high-speed railway ticket allocation and train stopping plans, which balances passenger demands and train operation efficiency, thereby improving seat occupancy rates and revenue for the railway enterprise.

2. A heuristic algorithm combined with the CPLEX solver is designed to solve the proposed problem. Based on the framework of the simulated annealing algorithm, three neighbourhood solution generation strategies for stopping plans have been devised, significantly enhancing the efficiency of the solution with the utilization of the CPLEX solver.

3. Taking the high-speed railway from Beijing to Shanghai as a case study, both small- and large-scale experiments were designed to verify the effectiveness of the algorithm. At the same time, comparative experiments were designed to illustrate the necessity of collaborative optimization of ticket allocation and train stopping plans.

The organizational structure of this paper is as follows. Section 3 provides a detailed description of the problem, basic assumptions, symbol definitions and passenger choice behaviours. The mathematical model is proposed in Section 4. Section 5 presents the design of heuristic algorithms, including neighbourhood solution generation, initial solution construction, etc. In section 6, numerical experiments are given. Finally, section 7 presents conclusions and further research directions.

3. Problem analysis and description

3.1. The influence of the train stopping plan on ticket allocation

Suppose that there are four stations, A, B, C and D, on a high-speed rail line and two trains are operated, namely train 1 and train 2, with the capacity of each train being 100 people. The train stopping plans have four patterns, as shown in Fig. 1. Among these, stopping patterns 1, 2 and 3 are known, while stopping pattern 4 is unknown. The OD passenger demands and ticket prices are shown in Table 2. By solving the following model, the ticket allocation results for each stopping pattern can be obtained. The definitions of each notation in the model are shown in Table 3.

The constraints are as follows:

1) Capacity constraint

Ticket allocation should ensure that the sum of seat numbers on any section for each train in its operation cannot exceed the train's capacity limit; that is, the maximum capacity constraint of the train is satisfied.

2) Passenger demands constraint

The total allocated ticket numbers at any OD cannot exceed the passenger demands of the corresponding OD.

3) Train service constraints

Trains can only allocate tickets at the stopping station.

4) Constraint on the value of the ticket decision variables

The ticket decision variable must be a non-negative integer.

The above model is a linear integer programming model, without considering overcrowding of the trains. The optimal ticket allocation plan and the revenue of the railway enterprise under each stopping pattern are solved by MATLAB calling the ‘intlinprog’ function, as shown in Table 2.

Through the ticket allocation results in Table 2, it can be seen that the corresponding optimal revenue of the first three fixed stopping patterns is lower than that of the non-fixed stopping pattern. When the stopping plan is fixed, trains can only serve passenger demands originating from and destined for stations where they stop, resulting in a loss of passenger demands for stations where trains do not stop. When the stopping plan is non-fixed, tickets can be flexibly allocated and train stopping plans can be determined according to passenger demands. It can be seen that the ticket allocation under the fixed stopping plan will cause trains to fail to serve some OD passenger demands even if they have surplus capacity, while a non-fixed stopping plan can make full use of the train's ability to better meet the passenger demands, so that the train’s transportation capacity and passenger demands can be better matched, which will correspondingly increase the total revenue of the railway enterprise. To provide a globally superior solution for both the stopping plan and the ticket allocation plan, with the aim of better meeting passenger demands and improving seat occupancy rates and the revenue of the railway enterprise, this paper combines the two to optimize.

3.2. Problem description and basic assumptions

Consider the downward direction of a high-speed railway double-track line composed of |S| stations, as shown in Fig. 2. Station 1 represents the initial station and station |S| represents the terminal station. The link between two adjacent stations is defined as the section represented by a, and there are |A| sections along the line, so |S| = |A| + 1. There are |K| trains running on this line. Each train starts from the same initial station and reaches the same terminal station. The stopping plan of each train at the intermediate station is unknown, but the departure time of each train at the initial station is known. (i, j) is the OD pair from station i to station j, where i = 1, 2, …, |S|−1, j = i + 1, …, |S|.

We consider the passenger demands of 6:00–22:00 in a day, with 2 hours as a time period, and then divide the entire day into eight time periods. The passenger demand for each OD pair (i, j) within each time period is modelled as a non-homogeneous Poisson distribution process, as described in Ref. [25]. Specifically, passenger demands of the |$w$|-th OD pair in time period t follow the Poisson distribution with parameter λ_ωt. The product 〈k, (i, j), t〉 represents the service provided by train k for OD (i, j) in time period t.

The research problem in this paper can be described as follows: given a specific high-speed railway line, the operation of trains and stochastic passenger demands data, the objective is to determine the stopping plans and ticket allocation plans for each train in order to maximize the overall revenue of the railway enterprise.

To simplify the complexity of the problem, the following four assumptions are set:

1. The type and speed level of trains are the same, and the seat capacity of each train is fixed.

2. Passenger transfers and overloading are not considered.

3. Only second-class seats are considered.

4. Passenger demands can be lost. If passenger demands are not met, it is considered that the passenger cancels the trip.

3.3. Symbol definition

The symbol definitions of this paper are shown in Table 4.

3.4. Passenger choice behaviours

For determining the obtained revenue of trains with a given stop plan and ticket allocation plan, we must describe passenger train-choice behaviours for calculating the number of passengers choosing each train for travelling. Due to the differences in departure time, travel time and ticket prices of multiple trains serving the same OD, different passengers of the same OD will have different choice preferences. Different products provided by different trains will have different effects on passengers. Note that the product in this research refers to a travel service by a given train with a specified price. This paper considers the influence of passenger departure time deviation, total travel time and ticket prices on the choice of passengers among multiple trains, and establishes the following measurable utility of passengers:

Assuming that the random utility items of each product are independent of each other and follow the Gumbel distribution, the MNL model is used to calculate the passenger demands sharing rate of different trains. The probability that stochastic passenger demands q_ijt of OD(i, j) in the |$t$|-th time period select train k is:

For OD(i, j), the stochastic demand for passengers who expect to depart in the |$t$|-th time period to choose the k-th train is:

4. Mathematical model

The total revenue of the railway enterprise is composed of the difference between the total ticket revenue and the costs of train operation. Train operation costs mainly include the train organization cost and the train operation cost. The organization cost is the fixed cost required for train operation, including the related cost of crew and the purchase cost of EMU. This cost is related to whether the trains are operated. In this paper, all trains are in operation, so this cost is the same and does not need to be expressed in the objective function. The train operation cost is proportional to the travel time of running trains, mainly including the line usage fee, the train stop fee, the depreciation fee of EMU, etc. This paper assumes that all trains have the same speed level and the same running section, so the running time is the same, which can be simplified as the stop cost. For |$\forall a,b \in R$|⁠, define |$a \wedge b$| to denote min{a, b}, then |$E[ {q_{ijt}^k \wedge b_{ijt}^k} ]$| denotes the expected ticket sales quantity of train k on OD(i, j) in the |$t$|-th time period. The objective function is expressed as follows:

The model also makes train tickets and stop selection meet the following constraints:

1) Capacity constraint

Because of the fixed train composition capacity and the exclusion of overloading, the allocation of tickets should ensure that the sum of seat numbers on any section for each train in its operation cannot exceed the train's capacity limit, that is, the maximum capacity constraint of the train is satisfied.

2) Constraint on the value of ticket decision variables

The ticket decision variable must be a non-negative integer.

3) The relationship between the ticket variable and the stop variable

If there is a passenger arrival or departure at a station, the train must stop at the station; if there is no arrival or departure of passengers at a station, the train does not stop at the station.

In this formula, M is any sufficiently large number.

4) Constraint on the number of trains stopping at the station.

For each station, to ensure the station's necessary service level, it is necessary to specify the minimum number of trains stopping throughout the day. At the same time, the total number of arriving and departing trains at the station must not exceed the station's arrival and departure capacity.

5) Constraint of train stop frequency

Having too many stops can slow down the train's travel speed, thereby increasing passenger travel time. Having too few stops may leave passenger demands at intermediate stations unmet. Therefore, it is necessary to set upper and lower limits on the number of train stops to restrict them.

6) Constraint on mandatory stops at starting and terminal stations

The train must stop at the starting and terminal stations.

5. Algorithm design

The model proposed in this paper is a nonlinear programming model. The number of variables and constraints increases as the numbers of trains, stations and time periods increase, making it difficult to solve using existing exact algorithms or optimization software. The simulated annealing algorithm is suitable for solving large-scale combinatorial optimization problems, and offers advantages such as simplicity in description, high operational efficiency and less sensitivity to initial conditions. Therefore, the solution algorithm of this paper is designed based on the simulated annealing algorithm framework. Firstly, an initial stopping plan that satisfies the stopping constraints is randomly generated, and the CPLEX solver is called to generate the initial ticket allocation plan based on the initial stopping plan. Next, based on the neighbourhood solution strategy of the stopping plan, a new stopping plan is generated, then a new ticket allocation plan is generated by using the model in Section 5.2. Finally, the metropolis criterion is used to determine whether to accept the new solution. This process is iterated sequentially until the optimal solution is found.

5.1. Neighbourhood solution generation strategy of train stopping plans

In this paper, three neighbourhood solution generation strategies for train stopping plans are designed, one of which is randomly adopted each time, and each strategy is selected with equal probability.

1. Randomly select two trains, then for each of the selected trains randomly choose a station other than the starting and terminal stations. Invert the two stop variables separately, so that the stop situation is opposite to the original situation, as shown in the following:

   $$\begin{eqnarray} \left\{ {\begin{array}{@{}*{1}{c}@{}} {\left\{ {1,1,0,1, \cdots ,1,0,1,1} \right\}}\\ {\left\{ {1,1,1,0, \cdots ,0,1,0,1} \right\}}\\ { \cdots \cdots }\\ {\left\{ {1,0,0,1, \cdots ,0,1,1,1} \right\}} \end{array}} \right\} \to \left\{ {\begin{array}{@{}*{1}{c}@{}} {\left\{ {1,1,1,1, \cdots ,1,0,1,1} \right\}}\\ {\left\{ {1,1,1,0, \cdots ,0,1,0,1} \right\}}\\ { \cdots \cdots }\\ {\left\{ {1,0,0,1, \cdots ,0,0,1,1} \right\}} \end{array}} \right\} \end{eqnarray}$$
2. Randomly select one train and, for all stations other than the starting and terminal stations, calculate their occupancy rate one by one. For all stopping stations, find the station with the highest occupancy rate among their corresponding occupancy rates, and record its station position. Among the stations with the highest occupancy rate, randomly select one station and set it as a non-stopping station. For all non-stopping stations, find the station with the lowest occupancy rate among their corresponding occupancy rates, and record its station position. Among the stations with the lowest occupancy rate, randomly select one station and set it as a stopping station, as shown in the following:

   $$\begin{eqnarray} \left\{ {\begin{array}{@{}*{1}{c}@{}} {\left\{ {1,1,0,1, \cdots ,1,0,1,1} \right\}}\\ {\left\{ {1,1,1,0, \cdots ,0,1,0,1} \right\}}\\ { \cdots \cdots }\\ {\left\{ {1,0,0,1, \cdots 0,1,1,1} \right\}} \end{array}} \right\} \to \left\{ {\begin{array}{@{}*{1}{c}@{}} {\left\{ {1,1,0,1, \cdots ,1,0,1,1} \right\}}\\ {\left\{ {1,1,1,0, \cdots ,0,1,0,1} \right\}}\\ { \cdots \cdots }\\ {\left\{ {1,1,0,1, \cdots ,0,0,1,1} \right\}} \end{array}} \right\} \end{eqnarray}$$
3. Randomly select one train, and choose any two stations other than the starting and terminal stations. Use the 2-opt method to swap the stopping sequence between these two stations, as shown in the following:

   $$\begin{eqnarray} \left\{ {\begin{array}{@{}*{1}{c}@{}} {\left\{ {1,1,0,1, \cdots ,1,0,1,1} \right\}}\\ {\left\{ {1,1,1,0, \cdots ,0,1,0,1} \right\}}\\ { \cdots \cdots }\\ {\left\{ {1,0,0,1, \cdots 0,1,1,1} \right\}} \end{array}} \right\} \to \left\{ {\begin{array}{@{}*{1}{c}@{}} {\left\{ {1,1,0,1, \cdots ,1,0,1,1} \right\}}\\ {\left\{ {1,0,1,0, \cdots ,0,1,1,1} \right\}}\\ { \cdots \cdots }\\ {\left\{ {1,1,0,1, \cdots ,0,0,1,1} \right\}} \end{array}} \right\} \end{eqnarray}$$

5.2. Neighbourhood solution generation strategy of the seat allocation plan under the given stopping plan

When train stopping plans are known, the original model becomes a model that only contains the ticket decision variable. Referring to Refs. [25] and [27], the original model can be equivalently transformed into a linear model and solved using the CPLEX solver.

Define |$\;y_{k,( {i,j} ),t}^l \in \{ {0,1} \}$|⁠, |$y_{k,( {i,j} ),t}^l = 1$| indicates that the l-th resource can be allocated to product 〈k, (i, j), t〉, otherwise |$y_{k,( {i,j} ),t}^l = 0$|⁠. The expected passenger demand of product 〈k, (i, j), t〉, denoted as |$q_{ijt}^k$|⁠, follows a Poisson distribution with parameter |${\lambda _{\omega t}}P( {k{\rm{|}}i,j,t} )$|⁠, which can ensure that |$P( {q_{ijt}^k \ge l} )$| decreases with l, and |$ E[{q_{ijt}^{k} \wedge b_{ijt}^{k}}] = {\sum\limits^{C_k}_{l = 1} P({q_{ijt}^k \ge l})}$| decreases with l. The equivalent integer linear programming model is as follows:

s.t.

5.3. Steps of the simulated annealing algorithm

During the implementation of the algorithm, the initial temperature |$\varPsi$|₀ is set to a relatively high value, the termination temperature is T_end and the cooling coefficient is θ. The maximum number of iterations at the same temperature is U_max, and the number of times that the optimal solution remains unchanged continuously is Θ. The algorithm termination condition is that the current temperature is lower than the termination temperature T_end, and the optimal solution does not change after Θ iterations.

In summary, the solving steps are as follows:

Input: OD information, train information, stochastic demand parameters, relevant parameters of the model and algorithm.

Output: train stopping plan x_best, ticket allocation plan b_best, revenue of railway enterprise Z_best.

Step 1: Set the initial value of the parameters. Set initial temperature |$\varPsi$|₀, the termination temperature T_end and the cooling coefficient θ. The maximum number of iterations at constant temperature is U_max, and the maximum times that the optimal solution is continuously maintained is Θ.

Step 2: Generate initial solutions randomly. Randomly generate an initial stopping solution|$\;{x_0}$| that satisfies constraints (13)–(15), and then transform the original model into a linear model about the ticket decision variable. According to the MNL model in Equations (6)–(8), calculate the Poisson distribution parameters for passenger demands allocated to train k for OD(i, j) in the |$t$|-th time period, and use CPLEX to solve for the initial ticket allocation plan b₀ and revenue Z₀ of the railway enterprise. Set the current temperature |$\varPsi$| = |$\varPsi$|₀, the constant temperature iteration number u = 1, the initial optimal solution holding number ξ = 1, the current solution x = x₀, b = b₀, Z = Z₀ and the current optimal solution x_best = x₀, b_best = b₀.

Step 3: Generate new solutions. According to the stopping plan neighbourhood solution generation strategy and the current ticket allocation plan b, generate a new stopping plan x₁ that satisfies the constraints. According to the transformed linear model, the new ticket allocation plan b₁ and the revenue of the railway enterprise Z₁ are obtained by CPLEX. Calculate the difference between Z₁ and Z, denoted as ∆Z.

Step 4: The metropolis criterion is used to determine whether the new solution is accepted. If ∆Z > 0, then new solutions x₁ and b₁ are accepted, that is, x = x₁, b = b₁. Otherwise, the probability of accepting the new solution is calculated according to exp(∆Z/T). When exp(∆Z/T) > random(0, 1), x = x₁, b = b₁. Otherwise, keep the current solutions x and b unchanged.

Step 5: Compare Z and Z_best, if Z > Z_best, then b_best = b, x_best = x, Z_best = Z, ξ = 1. Otherwise, the current optimal solution x_best, b_best, Z_best remains unchanged, ξ = ξ+1.

Step 6: u = u + 1, when u > U_max, end the state, u = 1. Otherwise, return to Step 3.

Step 7: Reduce temperature. |$\varPsi$|= |$\varPsi$| × θ.

Step 8: Termination check. If |$\varPsi$| ≤ T_end and ξ ≥ Θ, then output the current optimal solution x_best, b_best and the corresponding Z_best, and terminate the programme. Otherwise, return to Step 3.

6. Numerical experiments

6.1. Input data

In this section, taking the Beijing–Shanghai high-speed railway corridor as an example, a small-scale experiment (SSE) and a large-scale experiment (LSE) are carried out to verify the correctness and superiority of the model. The total length of the line is 1311 km.

The day's operating time [6:00, 22:00] is divided into eight time periods with 2 hours as a time period. Train operation-related parameters: the train running speed is 300 km/h, the maximum train seat capacity in each section is 560, the train stop time at the intermediate station is 6 min and the cost of stopping the train once is CNY 900. The parameter of the MNL model θ = 0.012. Time value coefficient θ₁ = 0.8 ¥/min, θ₂ = 1 ¥/min.

In the SSE, four trains were selected for the experiment, involving 10 ODs and five stations (Beijing South, Tianjin South, Jinan West, Nanjing South and Shanghai Hongqiao, successively numbered 1–5), including the starting station, the terminal station and three intermediate stations. The distances between adjacent stations are 122 km, 285 km, 619 km and 285 km, respectively. The departure time of each train is 8:05, 12:30, 15:50 and 19:20, respectively. The OD ticket prices and the Poisson distribution parameters of the stochastic demands in each period are shown in Tables 5 and 6.

In LSE, 19 trains were selected for the experiment, involving 45 ODs and 10 stations (Beijing South, Langfang, Tianjin South, Dezhou East, Jinan West, Xuzhou East, Bengbu South, Nanjing South, Wuxi East and Shanghai Hongqiao, numbered 1–10 in turn), including the starting station, the terminal station and eight intermediate stations. The distances between adjacent stations are 60 km, 192 km, 93 km, 287 km, 156 km, 176 km, 183 km and 102 km, respectively. The schematic diagram of the line is shown in Fig. 3. The departure time of each train, the OD ticket prices and the Poisson distribution parameters of the stochastic demands in each period are shown in Tables 7 to 9. Other parameters are shown in Table 10.

6.2. Convergence analysis

In the SSE, the current revenue value (CRV) and the historical maximum revenue value (HMRV) change with the times of iterations, as shown in Fig. 4, and begin to converge at about 203 iterations. The solving time of the SSE is about 1 hour. The objective function value increased from the initial CNY 1,531,990 to CNY 1,541,480, an increase of 0.62%.

In the LSE, the iterative convergence process of the algorithm is shown in Fig. 5, and the convergence begins when the iteration is about 1500 times. The solving time of the LSE is 38.1 hours. The objective function value increased from the initial CNY 6,549,230 to CNY 7,070,108, an increase of 7.95%.

It can be seen that regardless of SSE or LSE, the algorithm designed in this paper can produce better results in an acceptable time range, so the performance of the algorithm in this paper is better.

6.3. Comparative analysis

The solving time of the SSE is 1 hour, while the solving time of the LSE is 38.1 hours. It can be seen that the solving time of the SSE is much less than that of the LSE. To fully utilize this advantage, we further test the revenue of the railway enterprise under different demand intensities based on the SSE, as shown in Table 11. From the results in the table, it can be seen that the revenue of the railway enterprise increases with the increase of passenger demand intensity, and the increment of growth shows a trend of first fast and then slow. This is because when there are sufficient passenger demands, the capacity of trains is almost fully utilized, so the revenue growth of the railway enterprise will become slow.

In order to verify the advantages of the collaborative optimization method (COM) proposed in this paper, we compared the ticket allocation plan under the fixed stopping plan (existing allocation method, EAM) and tested it based on two different sets of data: SSE and LSE. The stopping plans of the SSE and LSE are shown in Figs. 6 and 7.

The results of the comparative experiment are shown in Table 12. Whether it is SSE or LSE, the revenues of the COM are higher than those of the EAM, and the larger the scale of the problem the more obvious the effect of the COM on improving revenues.

Using the results of the LSE, we draw the passenger demands of each OD in each time period as shown in Fig. 8. Figs. 9(a) and (b) are the actual ticket sales volume of the EAM and COM respectively. It can be clearly seen from the figure that the method in this paper can meet more passenger demands.

At the same time, the train seat occupancy rates in each section are calculated. Fig. 10(a) is the seat occupancy rate of the COM, and Fig. 10(b) is the seat occupancy rate of the EAM. The results show that the seat occupancy rates of all trains using the COM method reach 100% in six sections, and the seat occupancy rates of the other sections are relatively high. It is concluded that the proposed method in this paper can make full use of train capacity and improve the seat occupancy rates and revenue of the railway enterprise.

7. Conclusions

This paper studies the collaborative optimization problem of high-speed railway train stopping plans and ticket allocation plans. By adjusting train stops, a train stopping plan and a ticket allocation plan that maximize the revenue of the railway enterprise are obtained. The main contributions and conclusions are as follows:

1. A collaborative optimization model of the train stopping plan and the ticket allocation plan is constructed. Assuming that stochastic passenger demands obey the Poisson distribution process, passenger choice behaviours are taken into account from three aspects: ticket prices, passenger travel time deviations and passenger travel time.

2. The corresponding simulated annealing algorithm is designed in combination with the CPLEX solver to solve the problem. The revenue of the railway enterprise is composed of ticket revenues and stop costs. With the goal of maximizing the revenue of the railway enterprise, a mathematical model is constructed by comprehensively considering the relevant constraints of stops and ticket allocation.

3. A small-scale experiment, large-scale experiment and comparative experiment are designed to verify the effectiveness of the model and algorithm. The results show that the proposed method can effectively improve seat occupancy rates and increase revenue by 0.14% and 9.09%, respectively.

The next research work will be carried out from the following three aspects:

1. Collaborative optimization research on stopping plans and ticket allocation based on passenger transfer behaviour and passenger refund behaviour to better improve passenger service quality.

2. Collaborative optimization research on ticket prices, stopping plans and ticket allocation based on multi-level ticket prices and elastic passenger demands.

3. Considering multiple seat levels and train levels, carry out optimization research on train stopping plans and ticket allocation plans.

Author contributions statement

Wenliang Zhou put forward the research idea, proposed the framework of the manuscript and carried out the experiment. Qianqian Yan collated the data and wrote the manuscript. Wenliang Zhou revised the manuscript.

Funding

This work was supported by the National Natural Science Foundation of China (Grant No. 72471247); the General Project of the Hunan Provincial Natural Science Foundation of China (Grant No. 2022JJ30057); and the Systematic Major Research Project of the China Railway (Grant No. P2022×012).

Conflict of interest statement. None declared.

References