Optimization of Train Working Plan based on Multiobjective Bi-level Programming Model

1. Introduction

With the rapid development of China’s economy, the demand for travel is continuously increasing. A survey of 3,082 people from 30 provinces regarding travel modes launched by the social survey center of China Youth Daily indicates that 82.2% of the interviewees preferred to board a train, 48.4% will take a car, 48% choose to fly on a plane, and 9.2% favor travelling by boat. China’s first true sense of the highspeed railway is the Beijing-Tianjin intercity railway, which opened on August 1, 2008. According to the National Development and Reform Commission, by the end of 2015, China’s high-speed rail operating mileage had reached 19000 km and accounted for more than 60% of the world’s total mileage of highspeed rail. China already has the world's largest high-speed rail network. The newly revised “medium and long term railway network planning” in 2016 projected that the railway network will reach a scale of 150,000 km by 2020, including 30,000 km of high-speed railways.

With the rapid development of the high-speed railway, the passenger rail transport network will be formed, constituted of the high-speed railway, the passenger dedicated line and normal-speed rail, and the mixed running line. China will take the transport organization mode based mostly on high-speed trains running on the passenger dedicated line and appropriately, on the normal-speed line, with medium-speed trains running across lines and normal-speed trains only running on the normal-speed line. The special transport organization mode makes the passenger train working plan more complicated, which has already been complex. The purpose of the high-speed railway construction is to better satisfy the travel requirements of passengers. It is related to the sound and rapid development of the high-speed railway in China to provide safe, convenient, and enjoyable travel experience for passengers in a reasonable train working plan setting. For China’s high-speed railway, it is the most urgent problem that requires a solution so as to develop a scientific and reasonable passenger train working plan.

Generally, optimization problems in train working plans are handled by single-objective approaches. The single planning objective is typically constructed from the perspective of either the passenger (such as time, distance, or cost) or the railway enterprise (such as cost, revenue, or capacity). However, the nature of the train working plan problem is inherently multiobjective. This is primarily because of the multiplicity of interests embodied by various stakeholders.

A reasonable passenger train working plan can best satisfy the different needs of passengers to protect their interests. Moreover, it is useful in assisting railway transportation enterprises to strive for as much market share of the high-speed railway as possible to ensure enterprise benefit. In the passenger transport market, the passenger fare performs an important function in the separation of passenger flow among different transport modes. Of course, a few factors, such as travel time, convenience, and safety similarly affect the transfer of passenger flow to different transport modes. In this study, multiple objects, such as the passenger fare, travel time, and profit of railway enterprises are used to study the optimization problem of the high-speed railway passenger train working plan.

To overcome the above challenges, we established a multiobjective bi-level programming model for the high-speed railway passenger train working plan centered on the interests of passengers as well as the interests of rail transport enterprises. In the upper-level programming, the minimum passenger transport cost and shortest travel time are regarded as the optimizing target, whereas in the lower-level programming, the target is to maximize the benefit of railway enterprises. Furthermore, the model solution algorithm based on the genetic algorithm is proposed. The algorithm utilizes the concept of solving by partition segment, which uses the real number coding method to express the passenger train working plan into the chromosome at first, and thereafter take the genetic operation to each section, merge the optimal solution of each section, and acquire the approximate optimal working plan of the high-speed railway passenger train. We used the simulation experiment to compare the approximate optimal train working plan with the current program so as to verify the scientism and rationality of our newly proposed model and algorithm. In contrast to previous related studies, this research considers both the interests of passengers and rail transport companies, which can better satisfy the inherent multiobjective nature of the train working plan problem.

The rest of this paper is organized as follows. Section 2 summarizes related work. Section 3 details a few of the preliminary analysis work before modeling, thereafter followed by the model for the train working plan optimization in Section 4. The solution algorithm of the model is discussed in Section 5. Section 6 shows the simulation experimental results, and Section 7 concludes the paper with the summary and future research direction.

2. Related Work

The high-speed railway train working plan should fully consider the passenger travel choice behavior, satisfy the passenger travel demand as possible, and increase the service quality of high-speed railway. Zhang et al. [1] established an optimization model for the high-speed railway train operating scheme, which considers the benefits of the high-speed railway train and satisfaction of passengers. The model was designed according to the characteristics of the multi-object and nonlinear particle swarm optimization algorithm. Thereafter, the model and algorithm were used for a sample study by taking a certain high-speed railway as an example. Zhang and Zhang [2] established a model considering the total cost of minimized passenger delivery as the object, and suggested to calculate the number of train pairs for each type of path and forecasted passenger flow volume, so as to determine the train operating scheme of the railway. Chang et al. [3] developed a multiobjective programming model for the optimal allocation of passenger train services on an intercity high-speed rail line without branches. Minimizing the operator's total operating cost, as well as the passenger’s total travel time loss are the two planning objectives of the model, which are solved through a fuzzy mathematical programming approach to determine the best-compromise train service plan, including the train-stop schedule plan, service frequency, and fleet size. Shi et al. [4] established a multi-object optimum model of passenger train plans for dedicated passenger traffic lines by balancing the benefits of both railway transportation corporations and passengers. Moreover, a method to solve the optimization of passenger train plans is introduced. Ghoseiri et al. [5] proposed a multiobjective optimization model for the passenger trainscheduling problem on a railroad network. The model considers lowering the fuel consumption cost as the measure of satisfaction for the railway company, where as reducing the total passenger travel time is regarded as the passenger satisfaction criterion.

Currently, the research results of the train working plan optimization problem is more extensive. On the one hand, to make the passengers the center and provide high quality service for them is the core principle of the high-speed railway train working plan setting. On the other hand, for the railway transport sectors, as businesses are concerned, the train working plan setting should also take into account corporate earnings. However, in existing programming models, there are a few studies that take the interests of passengers as the center, as well as give attention to the interests of railway transport enterprises.

The high-speed railway has a large network scale and complex network structure. Furthermore, the influence factors of its train working plan are numerous and on different levels. Because the bi-level programming model can properly describe the hierarchical relationship of the actual problem, and the upper decision maker has a few constraints on the next layer, in this study, the multiobjective bi-level programming model of the high-speed railway passenger train working plan is established. It considers passenger travel cost and time minimizations as objectives of the upper-level programming, where as the railway the enterprise profit maximization is regarded as the objective of lower-level programming. Subsequently, the optimization solution algorithm is proposed for the above model.

3. Problem Analysis

3.1 Train Stop Strategy

The train stop schedule plan is one of the components of the train working plan, which is mainly related to the station grade and train grade. To make a reasonable train stop schedule plan, a strategy based on these factors is firstly needed. The specific strategies are as follows.

(1) Direct stop: Direct stop means that departures and arrivals are made only at designated passenger stations. Moreover, any passenger station does not handle passenger operation along the route except as departure and terminal stations. This kind of stop way fully reflects that the high-speed railway has the characteristics of high speed and large passenger flow. Direct stop can apply to first-level passenger stations and high-speed passenger trains.

(2) Selective stop: Selective stop refers to the handling of passenger operation only at selected passenger stations. This kind of stop way is used in order to reduce the passenger’s travel time and accelerate the turnaround of passenger trains. Selective stop can apply to passenger stations belonging to first two levels and high-speed passenger trains.

(3) Alternate stop: Alternate stop refers to alternately choosing other passenger stations to handle passenger operation based on selective stop. This kind of stop way has the advantage of convenience for passengers at small stations. Alternate stop can apply to passenger stations above the second level, and moderate and high speed passenger trains. In addition, according to the actual situation, such as when the number of passenger stations is less in some sections, the alternate stop will at times be adjusted to stopping station by station.

3.2 Basic Assumptions

In this study, some of the assumptions made are as follows.

(1) Because of the symmetry of the train working plan, this study only investigates the train working plan in a certain direction.

(2) It is assumed that there are two kinds of high-speed railway passenger trains in terms of speed grade: high-speed and moderate-speed trains.

(3) It is assumed that the high-speed railway passenger train working plan considers one day as a fixed period.

3.3 Symbol Definition

In the mathematical model of this paper the following notations will be used:

S_i represents a passenger station; S^l represents a passenger station set, in which the grade of every station is l ; k represents the train type; S_k^D represents the departure station of type k train; S_k^T represents the terminal station of type k train; R_k represents the grade of type k train; P_k represents the stop-schedule plan of type k train; T_k(S_k^D,S_k^T,R_k,P_k),T_k for short, represents type k train, i.e., trains with the same departure station or terminal station. The train grade and stop-schedule plan should be seen as the same train; nT_k represents the train quantity of T_k; l_ab represents the distance from a [TeX:] $$S _ { a } \text { to } S _ { b } ; T P _ { k }$$ represents the stop strategy of type k train; [TeX:] $$P _ { k } \left( T P _ { k } , S _ { i } \right)$$ represents whether T_k stops at S_i or not; t_n represents the ticket booking time; P_k^t_n represents the fare of T_k when the ticket booking time is [TeX:] $$t _ { n } ; Q _ { k } ^ { t _ { n } }$$ represents the ticket sales volume corresponding to [TeX:] $$P _ { k } ^ { t _ { n } } ; P _ { k } ^ { \mathrm { t } _ { n } } \left( R _ { k } , S _ { a } , S _ { b } \right)$$ represents the fare from [TeX:] $$S _ { a } \text { to } S _ { b } \text { of } T _ { k }$$ when the ticket booking time is [TeX:] $$t _ { n } ; Q _ { k } ^ { t _ { n } } \left( R _ { k } , S _ { a } , S _ { b } \right)$$ represents the ticket sales volume corresponding to [TeX:] $$P _ { k } ^ { t _ { n } } \left( R _ { k } , S _ { a } , S _ { b } \right) ; n T _ { k } \left( S _ { a } , S _ { b } \right)$$ represents the train quantity of T_k passing through [TeX:] $$\left( S _ { a } , S _ { b } \right) ; n T _ { k } \left( \sec \left( S _ { a } , S _ { b } \right) \right)$$ represents the train quantity of [TeX:] $$T _ { k } \text { in } \left( S _ { a } , S _ { b } \right) ; c _ { per } \left( T _ { k } \right)$$ represents the running cost per kilometer of [TeX:] $$T _ { k } ; c _ { s t } \left( T _ { k } \right)$$ represents the cost produced by one stop of T_k; C_D(S_a) represents the departure capacity of [TeX:] $$S _ { a } ; C _ { T } \left( S _ { b } \right)$$ represents the arrival capacity of S_b; C_D(S_a,S_a) represents the carrying capacity of [TeX:] $$\left( S _ { a } , S _ { b } \right) ; T _ { S } \left( T _ { k } \right)$$ represents the seating capacity of T_k; d_i(T_k) represents the stop time at [TeX:] $$S _ { i } \text { of } T _ { k } ; V _ { k }$$ represents the running speed of T_k.

3.4 Travel Cost

The passenger travel cost is a comprehensive cost, which includes ticket price and other expenses [6]. Other expenses vary with the length of travel time and distance. Moreover, it is complicated, changeable, and difficult to quantify. Consequently, the travel cost here is equal to the cost of the fare. The passenger travel cost, C_passenger, is determined by the following formula:

3.5 Travel Time

The running time of the train is the total moving time of the train on the way. The running time of the train, T_running, is determined by the following formula:

The station dwell time refers to the total stopping time of the train at every station along the way. Station dwell time, T_dwell, is determined by the following formula:

The above is because waiting time, transfer time, and additional time are all easily influenced by personal factors, traffic conditions, and so on. Furthermore, they are difficult to quantify and are not considered here. Accordingly, the passenger travel time, T_all, is the sum of the running time and station dwell time. It is represented by the following formula:

3.6 Railway Enterprises Profit

The passenger ticket income depends on the train ticket sales in its running region and corresponding fare. The passenger ticket income from S_a to S_b is represented as I(S_a,S_b) and determined by the following formula:

Thus, when the total passenger ticket income of the railway enterprises is represented as I , it is determined by the following formula:

That is,

The fixed cost of railway enterprises refers to the necessary cost generated by operating a high-speed railway train, mainly determined by the running cost per kilometer of the train and corresponding running distance. The running cost per kilometer is related to the line class and train level, mainly including the cost of train energy consumption, materials, depreciation, and maintenance. Accordingly, the fixed cost of railway enterprises, C_fixed, is determined by the following formula:

The variable cost of railway enterprises mainly refers to the train stop cost, which is related to the train stop frequency. Thus, the variable cost of railway enterprises, C_variable, is determined by the following formula:

The operation cost of railway enterprises can be divided into fixed and variable costs. Therefore, the total transportation cost of railway enterprises, C_all, is determined by the following formula:

For the high-speed railway, the income of railway enterprise mainly comes from the passenger ticket income, which is also the only source of income considered in this study. As the profit is equal to income minus cost, the profit of railway enterprises, P, is determined by the following formula:

4. Model Formulation

On the one hand, passengers always want their own travel time to be as short as possible and travel cost to be as low as possible. On the other hand, the focus of railway enterprises is to obtain the maximum economic benefits. In this study, we want to establish a model, which considers the interests of passengers as the center and at the same time takes into account the interests of railway enterprises. In view of the above, the following multiobjective bi-level programming model for high-speed railway passenger train working plan was established.

Upper-level programming:

objectives

Lower-level programming:

objectives

subject to

The objective function of Eq. (12) is to minimize the passenger travel cost. The objective function of Eq. (13) is to minimize the passenger travel time. The objective function of Eq. (17) is to maximize the profit of railway enterprises.

Eq. (14) is the passenger station departure capacity constraint, which means that the number of trains originating from S_a should not be greater than its departure capacity. Eq. (15) is the passenger station arrival capacity constraint, which means that the number of trains arriving at S_b should not be greater than its arrival capacity. Eq. (16) is the train carrying capacity constraint, which means that the ticketing number of T_k on (S_a,S_b) cannot be greater than the upper limit of the passenger number of T_k. Eq. (18) is the line capacity constraint, which means that the number of trains through (S_a,S_b) should not be greater than its line capacity. Eq. (19) is the train stop frequency constraint, which means that the total stop frequency of T_k on (S_a,S_b) should be less than the total number of passenger stations on it.

5. Solution Algorithm

The above model not only has the characteristics of multiobjective, multi-level, and non-linearity etc., but also has characteristics of the large-scale system, including further constraint conditions and more complicated relationships between constraints and variables. This kind of problem generally belongs to the non-deterministic polynomial-time-hard problem which is more difficult to solve. Furthermore, there is no polynomial solving algorithm. Accordingly, it needs to use a heuristic algorithm. The genetic algorithm is a heuristic optimization algorithm, which has robust ability, global optimal solving capability and expandability. Additionally, with its standardized solving steps, it is more suitable for solving such problems mentioned above. Therefore, this study uses the genetic algorithm to solve the established two-layer programming model and attempts to determine the approximate optimal solution of the model.

The design of a train working plan solution algorithm based on the genetic algorithm, is as shown in Algorithm 1.

Algorithm 1:

In this algorithm, because of the concept of obtaining a solution by partition segment, the codes of the departure and terminal stations are not considered in the chromosome coding scheme. The chromosome gene coding structure of the train working plan in line 2 is shown as follows:

where TL is the train grade, in which TL = 1 represents the high speed train and TL = 2 represents the medium speed train; TN represents train quantity; TP is the train stop strategy, in which TP = 1 represents the direct stop, TP = 2 represents the selective stop, and TP = 3 represents the alternate stop; i is the serial number of the running section; ij is the chromosome number of the train working plan listed in ‘j’ of the “i” section; [TeX:] $$\left[ T L _ { i j } , T N _ { i j } , T P _ { i j } \right]$$ is one of the chromosomes representing the train working plan listed in ‘j’ of the “i” section constituted of three genes—[TeX:] $$T L _ { i j } , T N _ { i j } , T P _ { i j }$$.

In addition, the roulette wheel selection operator, intermediate recombination operator, and BGA mutation operator are selected for the genetic operation in line 4.

6. Empirical Study

A high-speed railway was opened to traffic on June 30, 2011. It has 23 stations, with a total length of 1318 km. The proposed model and algorithm are verified by considering this high-speed railway as an example.

(1) Parameter Determination

The experimental parameters are summarized in Table 1. The starting point of the modeling is to consider the interests of passengers as the center, as well as to take into account the interests of the railway transport enterprises. Thus, the target priority here, from the high to the low order are {T_all,C_passenger,P}, and the weights are {0.35,0.35,0.3}, respectively. The train station hierarchical division of this high-speed railway can be found in literature [7]. The origin-destination flow prediction can similarly be found in literature [8].

(2) Case Assumption

In order to cope with existing data and reduce the computational difficulty, a few assumptions are made as follows: Only the passenger flow of this high-speed railway line is considered; only the train working plan of this high-speed railway from B to S is studied; there are two kinds of train levels on this high-speed railway: moderate-speed and high-speed; the train working plan considers one day as a fixed period; trains of the same levels have the same stop time at different level passenger stations.

(3) Experimental Result

Programming with MATLAB 7.0 was performed to implement the proposed algorithm. The population size, pop_size is 20. The iteration number, MAXGEN , is 100. The crossover probability, P_c, is 0.8. The mutation probability, P_m, is 0.09. The approximate optimal train working plan is shown in Fig. 1.

(4) Result Analysis

We selected some key indicators, such as the average service frequency, average service frequency of the first-level passenger station, passenger turnover, direct ratio, train number, and average train stop frequency for the comparison of the approximate optimal train working plan obtained in this study with the actual plan of this high-speed railway[11], as summarized in Table 2.

The average service frequency of the optimized plan is improved when compared with the actual plan. The reduced waiting time makes passenger travel more convenient, and having less average train stop frequency can decrease passenger travel time. Consequently, the comfort of passengers will be improved. The average service frequency of the first-level passenger station has increased, which makes it convenient for passengers to transfer, as well as enhancing the passenger distribution capacity of the hub passenger station. The passenger turnover and train number have been greatly improved, which shows that the transport capacity of the high-speed railway is enhanced. This is not only convenient for passengers, but also makes it possible for railway transport enterprises to derive higher profits. The increased direct rate can reduce the frequency of passenger transfer and enhance the ability of highspeed railway to attract passenger flow. In conclusion, the approximate optimal train working plan in is better than the actual one in all selected indicators, which shows that the proposed model and algorithm are effective and reasonable.

7. Conclusions

The rationality of the high-speed railway passenger train working plan directly affects the interests of both passengers and railway enterprises. Thus, the multiobjective bi-level programming model of the high-speed railway passenger train working plan was established in this study. This model considers passenger travel cost and travel time minimizations as the objectives of the upper-level programming, and railway enterprise profit maximization as the objective of the lower-level programming. Subsequently, the model solution algorithm based on genetic algorithm was proposed. Finally, through an empirical study, the feasibility and rationality of the model and algorithm were proved. This model considers passenger maximum benefits as the center, which is an attempt to provide a new concept for creating a high-speed railway train working plan. This can guide railway transport enterprises to modify their concepts to realize the importance of the passengers as the ultimate consumer of passenger service, and thereafter aid them to achieve the dominant position in the passenger transport market. However, the determination of some parameters in the model are more complicated, and it is necessary to further study the set of parameter values with sufficient theoretical support.

Acknowledgement

This work is supported by the Natural Science Foundation of Inner Mongolia (No. 2016MS0706, 2017MS0702), the Institution of Higher Learning Science Research Project of Inner Mongolia (No. NJZY078), and the Science Research Project of Inner Mongolia University of Technology (No. ZD201522).