A Bilevel Programming Model to Optimize Train Operation Based on Satisfaction for an Intercity Rail Line
Abstract
The passenger travel demands for intercity rail lines fluctuate obviously during different time periods, which makes the rail departments unable to establish an even train operation scheme. This paper considers an optimization problem for train operations which respond to passenger travel demands of different periods in intercity rail lines. A satisfactory function of passenger travelling is proposed by means of analyzing the passengers’ travel choice behavior and correlative influencing factors. On this basis, the paper formulates a bilevel programming model which maximizes interests of railway enterprises and travelling satisfaction of each passenger. The trains operation in different periods can be optimized through upper layer planning of the model, while considering the passenger flow distribution problem based on the Wardrop user equilibrium principle in the lower layer planning. Then, a genetic algorithm is designed according to model features for solving the upper laying. The Frank-Wolfe algorithm is used for solving the lower layer planning. Finally, a numerical example is provided to demonstrate the application of the method proposed in this paper.
1. Introduction
On intercity rail lines, the train dispatching density is quite high and passengers normally choose their travel time according to their own travel habits. The passenger travel demand varies at different time periods, and the distribution of passenger flow during the day has obvious peaks and troughs. The railway department will fully consider the characteristic of passengers’ travel time when setting the train operation scheme of intercity rail lines. If the evened train dispatching mode is adopted for the whole day, it will cause the dissatisfaction of the demands in some peak periods and excess supply in some trough periods. Therefore, to divide the service time into several periods and adopt the evenly dispatching mode based on period will make a better balance between passengers’ travel demand and benefits of railway transportation. In addition, passengers will also consider traveling in high-satisfactory time periods according to the train operation scheme. Therefore, to develop a reasonable operation scheme can effectively eliminate the shortage issue of dispatching capacity on stations during peak hours, also leading passengers to travel at different time periods without reducing their travel satisfactions.
Domestic and overseas scholars have done a great amount of researches on the passenger train operation scheme of railway transportation. Considering that the traveling characteristic of intercity passenger flow is different from that of ordinary railway, some scholars have analyzed and researched passenger flow characteristics of intercity railway. Through massive investigation data, Mandel et al. have done a systematic research on the high-speed railway market and analyzed the fact that the characteristics of passengers’ demand are similar to those of city bus passenger demands on high-speed railway in Germany [1]. Zhao has systematically analyzed the fact that the traveling characteristics of intercity railway passenger flow are remarkably different from those of the urban residents in the aspects of traveling objective, time, intensity, distance, cost, and distribution [2]. Through numerous researches by domestic and overseas scholars, it is found that the passenger flow of intercity railway has a higher variability, on the elastic demand of which some scholars have done researches. Cascetta and Coppola have established an optimized model of train operation timetable under the elastic demand, aiming to optimize the ticket pricing structure of high-speed railway [3]. Shi et al. have analyzed the affecting factors related to the passenger train operation scheme and constructed a function of elastic passengers’ transport demand [4]. Some scholars believe that the reasonable distribution of passenger flow is the premise of optimizing the passenger train operation scheme. Peng and Zhu have described the interactive relationship between transport demand and the operation scheme, established a dynamic assignment model of passenger flow which reflects the transition process for different types of passenger flow, and constructed multiobjective planning model which gives a comprehensive consideration to maximum benefit of railway department, minimum total cost of passenger, and satisfaction of passenger flow demand to the greatest extent [5]. Some scholars have given enough thought to the impact of congestion on passengers’ travel when optimizing the train operation scheme. Niu and Zhou have studied the optimizing issue of train timetable for city rail transportation under time-varying and congestion condition. Using time-varying based passenger flow data collected from the automatic ticket inspection system of city rail transportation, they established the nonlinear integer planning model for dispatching trains on rail under the given condition by the number of motor train units [6]. There are many issues to be taken into account in order to develop a reasonable passenger train operation scheme, and the various factors often have association relationship with each other. Therefore, some scholars have tried to establish bilevel planning model to give mathematical description to this issue and obtained certain achievements. He et al. have analyzed the balancing condition of passenger flow for different types of trains and established the generalized cost function for different types of trains, based on which they have constructed multiobjective bilevel planning model for developing the dedicated passenger train operation scheme. This model takes the maximum benefit of train operation and maximum convenient degree of passenger as target and also considers the assignment issue of different types of trains based on minimum travel cost to passengers [7]. Shi et al. have analyzed the relevant cost and optimizing objective of the passenger train operation scheme, evenly considered the enterprise profit and the passengers’ demand, combined the train operation scheme and passenger transference scheme, and established the optimized bilevel planning model of the passenger train operation scheme which takes distribution of passenger flow in railway transference network as the lower layer planning [8]. Considering that the intercity railway train operation scheme may affect the travel convenience of passenger flow and passenger’s satisfactory degree, He et al. have studied the convenience for passengers in different time periods based on market investigation data [7]. Chang et al. developed a multiobjective programming model for the optimal allocation of passenger train service on an intercity high-speed rail line without branches. Minimizing the operator’s total operating cost and minimizing the passenger’s total travel time loss are the two planning objectives of the model [9]. Huang and Niu have analyzed the relevant factors that affected the traveling satisfaction of passengers and established an optimized model of train operation scheme aiming at getting maximum traveling satisfaction of passengers [10]. However, the above research did not consider the effect of passenger flow distribution for passengers’ satisfaction and the feedback relationship between train operations scheme and passengers’ demand. Therefore, this paper will construct a bilevel programming model to optimize train operations based on passengers’ satisfaction.
The remainder of this paper is organized as follows: Section 2 presents and analyzes the researching issues; Section 3 establishes bilevel planning model of intercity railway train operation scheme; Section 4 gets solution by adopting genetic algorithm based on model features; Section 5 verifies the model through examples; in the end, the content of study in this paper and the further issues to be researched are summarized.
2. Problem Statement
2.1. Division of Passenger Travelling Time Period
On intercity rail lines, different passengers will choose different travelling time periods based on their own demands. For example, some passengers will make decisions on travelling time in accordance with their habits; some will do so according to the congestion level of urban traffic, while some will do it as requested by their working hours and so on. However, through the research on the travelling time period of intercity railway passengers, it shows that passenger flow is not distributed equally in different time periods but has obvious peaks and troughs throughout the day.
According to the above analysis, the passengers’ travel demand is uneven in different time periods. Therefore, the passenger travel demand in different time periods needs to be taken into account when developing the intercity railway train operation scheme. In order to make an easy study, this paper divides the service time of intercity rail lines into m travel periods by hour; that is, one hour represents one travel period. P serves as the set of travelling time periods and P ∈ {p∣1,2, …, m}.
2.2. Generalized Passenger Travel Cost
where Qp is the passenger flow volume which is assigned in the travelling time period p; N is the service capacity of the station; exp(i) is the natural exponential function. The greater the N/Qp, the lower the passenger congestion (the value exp(−N/Qp) at this point gets closer to zero); the smaller the N/Qp, the higher the level of passenger congestion (the value exp(−N/Qp) at this point gets closer to 1).
2.3. Passenger’s Travelling Satisfaction
The passenger’s travelling satisfaction defined in this paper means the satisfaction level of expected travelling time and the generalized travel cost for all passengers in the same time period. The factors affecting passenger’s travelling satisfaction include two parts as follows.
where Mp is the passenger demand of the travelling time period p, which can be obtained through market survey; when Qp ≥ Mp, it indicates all passengers expecting to travel at the p time period, whose demands on travelling time can be satisfied. When Qp < Mp, it indicates that some passengers have to choose other time periods, and therefore the average satisfaction of the passengers will decrease. The value range of Qp/Mp is [0,1). The smaller the Qp is, the lower the passenger’s average satisfaction gets.
As mentioned above, the ticket cost C that passenger has to pay when travelling is a set value, while the generalized cost Vp paid by passenger at the travelling time period p is a variable value. Vp − C shows the extra cost paid by passenger in addition to the ticket cost. The more this part costs, the lower the passenger’s satisfaction level gets.
where ρ indicates the passenger’s preference of the travelling time period satisfaction and 0 < ρ < 1.
3. Bilevel Planning Model
3.1. Lower Layer Planning
where yp is the travel impedance of each passenger in the travelling time period p; ymin is the travel impedance under balanced status.
where the upper limit hp of integral indicates the segment flow on the route p.
This paper constructs passenger travel network, and every travelling time period is one route, with total of m routes. One route only has one segment. Therefore, segment flow hp is the route flow Qp.
3.2. Upper Layer Planning
where Xp is the quantity of trains operated in the travelling time period p; W is the operation cost of a single train; C · Qp is the ticket revenue; W · Xp is the operation cost for all trains in the travelling time period p.
where np is the dispatching capacity of the travelling time period p.
where D is the maximum seats of a train and ∑p∈PD · Xp shows the seating capacity of all trains provided by the railway department during one day.
D · Xp shows that the seating capacity provided by the railway department in the travelling time period p should be able to satisfy the passenger flow Qp of that time period.
where mod is the calculation of dividing modulus and keeping remainder and π is the maximum overload coefficient of the train.
3.3. Associations Relationship between Upper Layer Planning and Lower Layer Planning
Lower layer planning satisfies the UE flow distribution under the Wardrop equilibrium assignment condition and could generate the passenger flow distribution scheme Qp according to the passenger flow equilibrium assignment condition. Upper layer planning is the optimized model aiming at maximizing the railway operational benefit and can obtain the train operation scheme Xp through optimizing calculation.
This paper assumes that trains are evenly dispatched at one time period and each travelling time period equals 1 hour without exception. Therefore, 1/Xp shows the train dispatching interval of the time period p.
According to the passenger flow distribution scheme Qp of lower layer planning, the ticket revenue ∑p∈PC · Qp of upper layer planning and passenger flow constraint conditions of each time period can be obtained.
where ceil(j) is rounddown function and η is the minimum occupancy rate of the train; θ is variable between 0 and 1, the value of which is calculated according to formula (21).
4. Algorithm Design
The model established in this paper is a bilevel planning problem of nonlinear mixed integer and is widely acknowledged as one of the optimization problems that are extremely difficult to solve. This paper adopts a genetic algorithm to get the solution of the model. This algorithm has better global convergence and is able to search for satisfactory solution in a short time, the core concept of which is to keep the high fitness of the individual to the next generation while eliminating the low fitness ones, based on the principle of natural evolution “Survival of the fittest."
4.1. Genetic Algorithm Design
(1) Chromosome Coding. Chromosome is made up of m gene segments which indicate m travelling time periods, respectively. Integer coding is used for chromosome coding. The position of each chromosome indicates the quantity of dispatched trains in the corresponding time period. The structure is as shown in Figure 1.

In the formula, E indicates the target value of chromosome.
(3) Genetic Operation. Genetic operation (selection operation, crossover operation, and mutation operation) is the core step of genetic algorithm, and it can produce a new generation through the genetic operation to the population. This paper adopts the improved crossover mutation method in literature [11].
4.2. Algorithm Process
Step 1 (initialization). According to the above described chromosome coding regulations and formulae (14)–(18), randomly generate the initial population of feasible solution with the scale of popsize; set optimal goal E* = 0 of the upper layer planning; initialize operation scheme WP* to zero vector; proposal inspection set Ψ is an empty set; the number of iterations is t = 1.
Step 2 (genetic operation). Based on the genetic algorithm designed in Section 4.1, conduct the selection, crossover, and mutation operation to the initial population, and search for feasible solution (operation scheme) WPt with the highest fitness in the current population; the number of iterations is t = t + 1.
Step 3 (checking). If WPt ∉ Ψ, then add it into check set Ψ and go to Step 4; otherwise, go to Step 2.
Step 4 (user equilibrium assignment). For the current operation scheme WPt, use the Frank-Wolfe algorithm to get solution for lower layer planning, and obtain Qpt in conformity with the Wardrop user equilibrium criterion.
Step 5. Bring the current operation scheme WPt and passenger flow demand Qpt into the upper layer objective function, and calculate the objective function E; if E > E*, then let E* = E and WP* = WPt.
Step 6 (termination of inspection). If the number of iterations t is greater than the upper limits G, then generate the optimal solution WP*; otherwise, go to Step 2.
5. Numerical Example
The paper takes the optimization of train operation scheme on Beijing-Tianjin Intercity Railway as an example to verify the model and algorithm presented in this paper.
5.1. Parameter Value
(1) Division of Time Period. The paper divides the service time (7:00–23:00) of Beijing-Tianjin Intercity Railway into 17 intervals, on the basis of one hour per interval.
(2) Passenger Travel Demands. The paper uses the official forecast data of the Beijing Railway Bureau. The average daily passengers would reach 117,400 by 2015 on Beijing-Tianjin Intercity Railway; that is, M = 117400. According to passenger flow survey, the passenger travel demand proportion of different time periods on Beijing-Tianjin Intercity Railway is as shown in Figure 2. Therefore, the passenger travel demand Mp in each time period is as shown in Table 1.
p | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
---|---|---|---|---|---|---|---|---|---|
Mp | 2980 | 8939 | 11919 | 11919 | 5959 | 2384 | 1788 | 1192 | 5363 |
p | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | |
Mp | 4768 | 5959 | 9535 | 10727 | 11919 | 10131 | 7747 | 4172 |

(3) Relevant Operation Parameters of Beijing-Tianjin Intercity Railway. Relevant operation parameters are set as [8, 9]: C is 57.25 yuan, D is 928 person, W is 18000 yuan/train, N is 5000 person, λ is 21.3 yuan, π is 0.2, η is 0.6, np = {10,12,12,10,10, 10,10,10,10,10, 12,12,12,10, 10,10,10 }, and p ∈ P.
(4) Algorithm Parameter Settings. According to the algorithm designed in the paper, the population size popsize = 100; obtaining crossover probability Pc = 0.6 and mutation probability Pm = 0.4 based on experience, the maximum stagnation iteration number is 15 and the maximum iteration number is 500.
5.2. Calculation Result and Analysis
This paper considers three kinds of situations, ρ = 0.25, ρ = 0.5, and ρ = 0.75, and calculates the passenger flow Qp, quantity of trains operated Xp, and average occupancy rate τp in each time period, respectively. The calculation result is as shown in Table 2.
p | ρ = 0.25 | ρ = 0.5 | ρ = 0.75 | ||||||
---|---|---|---|---|---|---|---|---|---|
Qp | Xp | τp | Qp | Xp | τp | Qp | Xp | τp | |
1 | 6212 | 7 | 0.96 | 6763 | 7 | 1.04 | 6084 | 7 | 0.94 |
2 | 6212 | 7 | 0.96 | 8846 | 10 | 0.95 | 8196 | 9 | 0.98 |
3 | 5218 | 6 | 0.94 | 6763 | 7 | 1.04 | 10014 | 11 | 0.98 |
4 | 8324 | 9 | 1 | 7310 | 8 | 0.98 | 8068 | 9 | 0.97 |
5 | 7454 | 8 | 1 | 7586 | 8 | 1.02 | 7301 | 8 | 0.98 |
6 | 7827 | 8 | 1.05 | 6043 | 7 | 0.93 | 5635 | 6 | 1.01 |
7 | 6833 | 7 | 1.05 | 6783 | 7 | 1.04 | 3458 | 4 | 0.93 |
8 | 5466 | 6 | 0.98 | 6783 | 7 | 1.04 | 7556 | 8 | 1.02 |
9 | 7206 | 8 | 0.97 | 5566 | 6 | 1 | 7684 | 8 | 1.04 |
10 | 7206 | 8 | 0.97 | 8390 | 9 | 1 | 7300 | 8 | 0.98 |
11 | 8199 | 9 | 0.98 | 8866 | 10 | 0.96 | 6403 | 7 | 0.99 |
12 | 5218 | 6 | 0.94 | 3923 | 4 | 1.06 | 6019 | 6 | 1.08 |
13 | 9939 | 11 | 0.97 | 7023 | 8 | 0.95 | 8196 | 9 | 0.98 |
14 | 6460 | 7 | 0.99 | 6773 | 7 | 1.04 | 8837 | 10 | 0.95 |
15 | 4100 | 4 | 1.1 | 6773 | 7 | 1.04 | 6916 | 7 | 1.06 |
16 | 9314 | 10 | 1 | 6470 | 7 | 1 | 4354 | 5 | 0.94 |
17 | 6212 | 7 | 0.96 | 6739 | 7 | 1.04 | 5379 | 6 | 0.97 |
Total | 117400 | 128 | / | 117400 | 126 | / | 117400 | 128 | / |
The paper obtains the following information based on the calculation data in Table 2. (1) Quantity of trains operated Xp in each time period is less than dispatching capacity np, which meets the train operation condition. (2) Average train occupancy rate τp of each time period is greater than the minimum occupancy rate η and τp − 1 is less than the maximum overload rate π. (3) When ρ increases, passenger’s requirements of travelling time period satisfaction rise and passenger flow Qp shows obvious peaks and troughs in each time period. When ρ = 0.75, passenger flow Qp changing trend of each time period is consistent with transport demand Mp to the greatest extent, as shown in Figure 3. (4) When ρ = 0.5, the total number of dispatched trains in all time periods is 126; when ρ = 0.75 and ρ = 0.25, the total number of dispatched trains in all time periods is 128.

6. Conclusions
The paper applies the UE equilibrium assignment theory to the decision of travel plans for intercity railway passengers and proposes the bilevel planning model of train operation scheme on intercity rail lines. Aiming at maximizing passenger’s average travelling satisfaction, the paper constructs the passenger’s travel impedance function and uses this function as passenger flow equilibrium assignment condition for lower layer planning to conduct assignment; meanwhile, it takes the maximum benefit of railway transport enterprises as target to make optimization. Through optimizing calculation, it obtains the passenger flow of each time period and the train operation scheme. By analyzing the calculation results, the model and algorithm proposed in this paper can effectively optimize the train operation scheme of intercity rail lines. Next, the paper will conduct a deep research on passenger travel choice under the condition of time-based pricing.
Conflict of Interests
The authors declare that there is no conflict of interests regarding the publication of this paper.
Acknowledgment
The work described in the paper was supported by the National Natural Science Foundation of China under Grant no. 71261014.