Optimization of Stop Plan for Skip-Stop Operation on Suburban Railway Line

Abstract

A combination of express and local trains (E/L mode) is generally used to operate a suburban rail service, it can meet the rapid and direct service needs of long-distance travelers as well the needs of short-distance travelers. Generally, a stop plan is the core of the E/L mode. A stop plan optimization model in E/L mode, which aims to minimize the total passenger travel time and the number of operating trains during the peak period with the safe headway and departure frequency constraints, is proposed in this study. Meanwhile, an algorithm based on a genetic algorithm is designed to solve the proposed model. A case study of the Jiangjin Line, a suburban railway in Chongqing, China, is carried out. The results show the efficiency and feasibility of the proposed method. The calculation results also show that the total passenger travel time under E/L mode with the overtaking condition is significantly reduced compared with the all-stops (AS) mode and E/L mode without overtaking condition. The superiority of the E/L mode can be enhanced by reducing the dwell time at stations and adopting the overtaking condition.

1. Introduction

With its development of metropolises and urban agglomerations, China is now planning and constructing regional rapid rail transit networks within urban areas and between urban agglomerations on a large scale. Suburban rail connects the central area of a metropolis to its surrounding satellite cities, operates on long routes with long distances between stations, and primarily serves commuters during peak periods. To minimize commuter travel times and improve train utilization efficiency, suburban rail services are generally operated with a combination of express and local trains. This mode of operation referred to as E/L mode, express trains can satisfy the needs of passengers who travel over long distances, with rapid and direct service, whereas local trains accommodate the needs of those traveling over short distances along the same route [1].

E/L mode refers to the concurrent operation of both local trains that stop at every station and express trains that skip some or even all stations between two points along the same route, with the goal of meeting the needs of different passengers. E/L mode is shown in Figure 1.

Researchers around the world have studied E/L mode in urban rail transit systems. Cao et al. [2], Ghoseiri et al. [3], and Riejos et al. [4] studied stop plans of express trains from the perspective of passenger travel efficiency and found the following: (1) Allowing express trains to skip stations can effectively reduce both the train turnaround times and the travel times of passengers on long journeys; and (2) using reasonable schedules that allow express trains to overtake local trains can maximize route capacity. Suh et al. [5] developed a model incorporating several factors (e.g., inter-station distances, changes in passenger flow, and departure intervals) to optimize the stop plan for an E/L mode of the Seoul subway system and found that while operating both express and local trains during peak periods increased the passenger wait time t_wait, this mode of operation reduced the total passenger travel time t_total. Larrain et al. [6] examined four influencing factors for the attractiveness of express train services, namely, the direction of the route, the average passenger trip length, the scale of the passenger flow, and the level of imbalance, of which the average passenger trip length was identified as the principal factor.

The optimization problem of stop plan for skip-stop operation is usually defined as a mathematical optimization problem, and researchers have designed the mathematical models and algorithms. Gao et al. [7], Freyss et al. [8] and Jamili and Aghaee [9] developed the optimization models to minimize energy consumption and passenger travel costs for urban and suburban rail transit, respectively. Boos [10], Ulusoy et al. [11], and Abdelhafiez et al. [12] established the nonlinear integer programming models to minimize passenger travel times, with several parameters (e.g., the passenger flow demand, departure intervals, and the number of operating trains) as constraints, and they designed algorithms to solve these models. Parbo et al. [13] presented the formulation of the skip-stop problem as a bi-level optimization problem, and a heuristic method for large-scale urban networks is presented to solve this extremely complex bi-level problem, where the skip-stop optimization is a mixed-integer problem. Xie et al. [14] developed a model where the objectives consider the minimization of probability of train delays, energy consumption, and travel time of the trains, a parallelism selection genetic algorithm was designed to solve the model.

Moreover, some scholars have studied the synchronization optimization of the train stopping plan and timetable under E/L mode. Niu et al. [15] optimized the train timetable for a route based on a certain stop plan in E/L mode. Yang et al. [16] propose a new collaborative optimization method for both train stop planning and train scheduling problems that consider the minimization of the total dwelling time and total delay between the real and expected departure times from the origin station. Zhao et al. [17] proposed a mixed-integer nonlinear programming (MINLP) model to formulate the integrated planning of stop planning, train scheduling and rolling stock circulation, explicitly considering time-dependent origin–destination demand.

Passenger demand distribution has a significant impact on the optimization plan under E/L mode. Mignone and Accadia [18], and Lee et al. [19] calculated optimal stop plans for E/L mode to accommodate different passenger flow distributions. In addition to researches with static passenger demand, Tian et al. [20], Zhao et al. [21], Jong et al. [22,23] and Sogin et al. [24] developed models for optimizing the stop plan in E/L mode that are applicable to dynamic passenger flow patterns. Furthermore, Tang et al. [25], and Jiang et al. [26] proposed the mixed-integer linear programming models under express/local model consider the capacity constraints (Di et al. [27]) and “overtaking” condition.

In this study, a multi-objective optimization model is established for optimizing the stop plan and departure frequency of suburban railway under E/L mode. The model takes the upper and lower limits of train departure frequency as the constraints and aims to minimize the total passenger travel time and the total number of operating trains. Meanwhile, a solution approach based on a genetic algorithm (GA) is proposed to solve the model. Different from previous studies, this paper mainly focuses on the schedule adjustment and impacts on solution results under the overtaking condition. Finally, a case is taken to verify the effectiveness of the proposed model.

The rest of this paper is organized as follows. Section 2 describes the proposed problem and assumptions. Section 3 describes the overtaking judgment and adjustment; the multi-objective programming model is also established in this section. Furthermore, a solution algorithm based on GA is designed to search for the optimal solution in Section 4. Section 5 uses a case to demonstrate the effectiveness and superiority of the proposed model and algorithm. Finally, the conclusions and future work are presented in the last section.

2. Description of the Problem and Assumptions

A suburban railway line on which both express trains, which skip some stations, and local trains, which stop at every station, are operated concurrently is examined in this study. Stop plans for E/L mode that can accommodate the specific passenger flow pattern on this route are calculated from the inter-station distances, the design speed, the acceleration and deceleration rates of the trains, safe headway, and the passenger origin–destination (OD) flow distribution.

The following basic assumptions are made:

(1) Regardless of their type, all trains depart from the originating station at equal time intervals.

(2) Trains run on a double-track railway line on this route. The inter-station segments of this route are not equipped with facilities that allow one train to overtake another. Overtaking occurs only at stations equipped with the requisite facilities.

(3) Passengers entering each station during the period examined in this study follow a uniform distribution.

(4) A train accelerates when departing from a station, then travels at a constant speed (i.e., the maximum design operating speed), and finally decelerates when entering the next station it stops at.

(5) The departure frequency of local trains is an integer multiple of that of express trains (this assumption facilitates the operational scheduling for trains).

(6) A passenger can only be delayed once and can only transfer once.

(7) Each passenger waiting at a station boards the train when it arrives at the station.

(8) Express trains overtake local trains at overtaking stations without stopping.

3. Modeling

Based on the above modeling assumptions, a 0–1 integer programming model (IPM) for E/L mode is established, with the stop plan for express trains and the number of express/local trains that depart during peak hours (i.e., operating frequency) as decision variables. By traversing all the operating schedules for E/L mode, parameters (e.g., the train operating timetable, the number of passengers waiting at each station, the number of passengers on board in each inter-station segment, and the number of delayed passengers) are calculated for each schedule. Then, t_total and the total number of operating trains C_total in each schedule are obtained. The optimal schedule is found through comparison.

This study examines the morning peak period and the cyclic mode of operation. The study period T_R can be divided into several minimum cycles T_c. Let I and 1: n be the number of trains and the ratio of the number of departing express trains to the number of departing local trains in each cycle, respectively. Table 1 summarizes the main model parameters and their definition.

3.1. Train Timetable Calculations

Establishing a train timetable requires the calculation of the interval at which trains depart from the origin station and their travel times along each inter-station segment of the route, based on which the arrival and departure times of each train at each station can be obtained. Calculated timetables need to satisfy the t_min constraint. It is also necessary to determine whether overtaking occurs and, if so, to adjust the arrival and departure times to account for the overtaking.

3.1.1. Calculation of the Arrival and Departure Times of Trains at Each Station

1. Departure intervals

A train schedule should be formulated to satisfy the passenger flow demand on the route. The minimum operating frequency depends on the maximum sectional passenger volume during peak hours as well as the capacity and the passenger load factor of the trains. Then, the interval at which trains depart from the origin station can be calculated using Equation (1):

(1)$T=\frac{3600}{f_1+f_2}=3600/\frac{q_{jmax}}{D\cdot {\eta }_{max}}$

where f₁ and f₂ are the departure frequencies of local and express trains during the morning peak period, respectively, q_jmax is the maximum sectional inter-station passenger volume during the morning peak period (unit: persons), D is the capacity of the trains (unit: persons/train), and η_max is the maximum passenger load factor of the trains.

2. Inter-station travel times

The operation of a train between two adjacent stations is simplified to the following process: It accelerates when departing from a station, then travels at a constant speed, and finally decelerates when entering the next station. A train’s travel time between two adjacent stations consists of the time when it is uniformly accelerating, the time when it is traveling at a constant speed, and the time when it is uniformly decelerating. For an express train, because it skips some stations, the uniform acceleration time and the uniform deceleration time or both should be removed if it does not stop at one or both stations of a segment. The travel time of train i in inter-station segment j is calculated using Equation (2):

(2)$t_{i,j}=\frac{L_j-x_{i,j}\cdot \frac{v^2}{2a_1}-x_{i,j+1}\cdot \frac{v^2}{2a_2}}{v}+x_{i,j}\cdot \frac{v}{a_1}+x_{i,j+1}\cdot \frac{v}{a_2}=\frac{L_j}{v}+x_{i,j}\cdot \frac{v}{2a_1}+x_{i,j+1}\cdot \frac{v}{2a_2}$

where L_j is the distance between stations j and (j + 1) (meters, m), v is the speed at which train i travels between the stations (km/h), and a₁ and a₂ are the acceleration and deceleration rates of train i, respectively (m/s²).

3. Arrival and departure times of trains at each station

Based on the above-calculated departure interval and inter-station travel times combined with t_z, the arrival and departure times of each train at each station can be calculated using Equations (3)–(5). The arrival and departure times of an express train at a station where it does not stop are the same.

The departure time of each train at the origin station is calculated as follows:

(3)$d_{i+1,1}=d_{i,1}+T$

The departure time of each train at each station other than the origin station is calculated as follows:

(4)$d_{i,j}=a_{i,j}+x_{i,j}\cdot {tz}_{i,j},j>1$

In the above equations, tz_i,j is the time during which train i dwells at station j (s).

The arrival time of each train at each station is calculated as follows:

(5)$a_{i,j+1}=d_{i,j}+t_{i,j}$

3.1.2. The t_min Constraint

To ensure safe operation, t_min must be satisfied between successive trains. Usually, the interval between the time when a train departs from a station and the time when the next train arrives at the same station plays a key role in controlling t_min. The state of a train at a station can be categorized into three types: arriving, passing, and departing. Based on their type (express or local), the t_min between two successive trains is affected by three factors: the interval between the time when a train departs from a station and the time when the next train arrives at the same station, here called I_da; the interval between the time when a train passes through a station and the time when the next train arrives at the same station, called I_ta; and the interval between the time when a train departs from a station and the time when the next train passes through the same station, called I_dt. Then the interval between when a train departs from a station and when the next train arrives at the same station must satisfy Equation (6):

(6)$a_{i,j}-d_{i-1,j}\ge x_{i-1,j}\cdot x_{i,j}\cdot I_{da}+(1-x_{i-1,j})\cdot x_{i,j}\cdot I_{ta}+x_{i-1,j}\cdot (1-x_{i,j})\cdot I_{dt}$

3.1.3. Overtaking Judgement and Adjustments

Due to the express trains have fewer stop stations and run faster than local trains, express trains will catch up with the local trains when they are running on the same route. At this moment, the express trains need to overtake the local trains. The overtaking judgment condition can be defined as follows: if the arrival interval between two successive trains cannot satisfy the required safe interval t_min at the last station, the rear train needs to overtake the front train (as shown in Equation (7)).

1. Overtaking judgement condition:

(7)$t_N^{i-1,i}=a_{i,N}-a_{i-1,N}-I_{aa}$

where $t_N^{i-1,i}$ is the value used to determine whether the interval between the arrival times of trains (i − 1) and i at the last station (i.e., station N) satisfies the required t_min ($t_N^{i-1,i}<0$ means that train i needs to overtake train (i − 1); $t_N^{i-1,i}\ge 0$ means that train i does not overtake train (i − 1)).

2. Determination of the locations of the overtaking stations

When overtaking is deemed essential, it is necessary to determine the locations of the overtaking station. Two scenarios require overtaking to occur (Figure 2).

Scenario 1: When the departing interval between the local train and the behind express train at station j satisfies the safety requirement, however, the arrival interval at the station (j + 1) is not satisfied, the express train needs to overtake the local train at station j, as shown in Figure 2a. Whether the train i overtake the local train at station j is calculated by Equation (8).

(8)$y_{i,j}=\{\begin{array}{c}\begin{array}{cc}1,& {tdd}_j^{i-1,i}\ge x_{i,j}\cdot I_{dd}+(1-x_{i,j})\cdot I_{dt} and {taa}_{j+1}^{i-1,i}<I_{aa}\end{array}\\ \begin{array}{cc}0,& {tdd}_j^{i-1,i}\ge x_{i,j}\cdot I_{dd}+(1-x_{i,j})\cdot I_{dt} and {taa}_{j+1}^{i-1,i}\ge I_{aa}\end{array}\end{array}$

where ${tdd}_j^{i-1,i}$ is the departing interval between the two successive trains at station j and ${taa}_{j+1}^{i-1,i}$ is the arrival interval between two trains at the station (j + 1).

Scenario 2: When the arrival interval between the local train and the behind express train at station j satisfies the safety requirement, however, the departing interval at station j is not satisfied, the express train needs to overtake the local train at station j, as shown in Figure 2b. In this scenario, whether the train i overtake the local train at station j is calculated by Equation (9).

(9)$y_{i,j}=\{\begin{array}{c}\begin{array}{cc}1,& {taa}_j^{i-1,i}\ge x_{i,j}\cdot I_{aa}+(1-x_{i,j})\cdot I_a{}_t and {tdd}_j^{i-1,i}<x_{i,j}\cdot I_{dd}+(1-x_{i,j})\cdot I_{dt}\end{array}\\ \begin{array}{cc}0,& {taa}_j^{i-1,i}\ge x_{i,j}\cdot I_{aa}+(1-x_{i,j})\cdot I_{at} and {tdd}_j^{i-1,i}\ge x_{i,j}\cdot I_{dd}+(1-x_{i,j})\cdot I_{dt}\end{array}\end{array}$

3. Adjustment of the train timetable after an overtaking

If overtaking occurs, the t_z of the overtaken train at the overtaking station needs to be extended. The departure time of the overtaken train at the overtaking station is changed to the original time at which overtake train passes through the overtaking station plus I_td. The arrival and departure times of the overtaken train at each subsequent station need to be recalculated based on the corresponding inter-station travel time and t_z.

The timetable for each subsequent train needs to be adjusted accordingly based on the t_min constraint. If the interval constraint is unsatisfied, then the absolute value of the difference between the required and actual intervals needs to be added to the current arrival and departure times. The arrival and departure times at each subsequent station need to be recalculated based on the corresponding inter-station travel time and t_z.

3.2. Passenger Flow Parameters

Our model calculations involve the following main passenger flow parameters: the number of waiting passengers at each station, the number of boarding passengers, the number of alighting passengers, the number of onboard passengers, and the number of delayed passengers.

3.2.1. Number of Passengers Waiting at the Origin Station of the Line

Under the assumption that passengers arriving at the origin station follow a uniform distribution during the study period, the total number of passengers who enter the origin station of the line between the departures of trains j(l) and j(l − 1) and whose destinations are the other stations is as follows:

(10)$q_{j(l),1}^{wait}={\displaystyle \sum _{s=2}^N\left\{\frac{{od}_{1,s}}{T_R}\cdot \left[d_{j(l),1}-d_{j(l-1),1}\right]\right\}}$

Overtaking occurs on the route and causes changes in the order in which trains arrive at each station. Therefore, j(l) is used to denote the lth train that dwells at station j.

3.2.2. Number of Passengers Waiting for Trains Who Are Delayed at Each Station Other Than the Origin Station

Unlike the passengers waiting at the origin station, the passengers waiting at station j(j ≠ 1) consist of both the passengers who arrive during the current time period and those that were unable to board the preceding train (i.e., train j(l − 1)) because its capacity was reached (i.e., delayed passengers). The total number of passengers waiting at station j is as follows:

(11)$q_{j(l),j}^{wait}=q_{j(l-1),j}^{det}+{\displaystyle \sum _{s=r+1}^N\left\{\frac{{od}_{r,s}}{T_R}\cdot \left[d_{j(l),j}-d_{j(l-1),j}\right]\right\}}$

The number of delayed passengers, that is, passengers who were unable to board train j(l − 1) because the number of passengers waiting for train j(l − 1) exceeded its capacity is as follows:

(12)$q_{j(l-1),j}^{det}=q_{j(l-1),j}^{wait}-n_{j(l-1),j}^{up}$

The number of passengers who board train j(l) at station j depends on two factors: (1) the remaining capacity of train j(l) after passengers alighting at station j; and (2) the current number of waiting passengers. If the number of waiting passengers is lower than the remaining capacity of the train, then all the waiting passengers can board the train; otherwise, only some of the waiting passengers can board the train, while the rest need to wait for the next train:

(13)$n_{j(l),j}^{up}=\min \left\{{\eta }_{max}\cdot D-n_{j(l),j-1}+n_{j(l),j}^{down},x_{j(l),j}\cdot q_{j(l),j}^{wait}\right\}$

where $n_{j\left(l\right),j-1}$ is the number of passengers onboard train j(l) at the time when the train departs from station (j − 1), which is calculated using the following equation:

(14)$n_{j(l),j-1}=n_{j(l),j-2}-n_{j(l),j-1}^{down}+n_{j(l),j-1}^{up}$

where $n_{j\left(l\right),j-1}^{down}$ is the number of passengers who alight from train j(l) at station (j − 1), which is calculated as follows:

(15)$n_{j(l),j-1}^{down}={\displaystyle \sum _{r=1}^{j-1}\left\{\frac{{od}_{r,j-1}}{T_R}\cdot \left[d_{j(l),r}-d_{j(l-1),r}\right]\right\}}$

3.3. Objective Functions

High departure frequencies can reduce t_wait and thus t_total but increase C_total. The objectives of the optimization model established in this study are to minimize both t_total and C_total.

3.3.1. Total Passenger Travel Time t_total

t_total consists of t_wait, the time spent onboard trains t_onboard, and the time spent transferring between express and local trains t_tran.

1. t_wait

The average t_wait is set to half of the interval between the departure times of two successive trains. For delayed passengers, their t_wait is set to the average t_wait plus the whole interval between the departure times of trains (i + 1) and i.

(16)$t_i^{wait}={\displaystyle \sum _{j=1}^{N-1}\left[q_{i,j}^{wait}\cdot \frac{d_{i,j}-d_{i-1,j}}{2}+q_{i,j}^{det}\cdot (d_{i+1,j}-d_{i,j})\right]}$

2. t_onboard and t_tran

t_total includes t_onboard and t_tran. The sum of t_onboard and t_tran can be calculated by subtracting the departure time from the starting station from the arrival time at the destination station:

(17)$t_i^{onboard}+t_i^{tran}={\displaystyle \sum _{k=2}^N{\displaystyle \sum _{j=1}^{k-1}\left\{\left[\frac{{od}_{j,k}}{T_R}\cdot (d_{i,j}-d_{i-1,j})\right]\cdot (a_{i^{\prime },k}-d_{i,j})\right\}}}$

where i’ is the number of the train that the passenger takes to reach the destination station, and i is the number of the train that the passenger takes at the starting station (if the passenger does not transfer between trains, then I = i’; otherwise, I ≠ i’).

The t_total during the study period is as follows:

(18)$t_{total}=\frac{T_R}{T_c}\cdot {\displaystyle \sum _{i=1}^I\left(t_i^{wait}+t_i^{onboard}+t_i^{tran}\right)}$

3.3.2. Total Number of Operating Trains C_total

C_total is the sum of the number of operating express trains C_e and the number of operating local trains C_l. It depends on the operating cycle and frequency of trains. Regardless of type, a train’s one-way travel time consists of the one-way turn-back time t_back, the t_z at each station, and the total inter-station travel time. The one-way travel times of an express train and a local train are calculated using Equations (19) and (20), respectively.

(19)$t_e=t_{back}+(a_{e,N}-d_{e,1})+{tz}_{e,1}+{tz}_{e,N}$

(20)$t_l=t_{back}+(a_{l,N}-d_{l,1})+{tz}_{l,1}+{tz}_{l,N}$

Then C_e and C_l are calculated as follows:

(21)$C_e=\frac{2\times t_e\times f_2}{3600}$

(22)$C_l=\frac{2\times t_l\times f_1}{3600}$

C_total is calculated as follows:

(23)$C_{total}=C_e+C_l$

3.3.3. Normalization of the Objective Functions

The dimensions of the two optimization objectives of the model are different and need to be unified before the model is solved. First, the two objectives are separately normalized. Then, the two-objective optimization problem is transformed using the linear weighting method to a single-objective optimization problem. To reflect the importance attached by different decision-makers to t_total and C_total, two normalized values are calculated for two objectives. Then, the two normalized values are linearly weighted and summed [28], as shown in Equation (26):

(24)$t_{total}^{nom}=\frac{t_{total}^{}-t_{total}^{min}}{t_{total}^{max}-t_{total}^{min}}$

(25)$C_{total}^{nom}=\frac{C_{total}^{}-C_{total}^{min}}{C_{total}^{max}-C_{total}^{min}}$

(26)$MinZ=\alpha \cdot t_{total}^{nom}+\beta \cdot C_{total}^{nom} (\alpha +\beta =1)$

3.4. Constraints

The following constraints are placed on the model:

1. Maximum departure frequency:

(27)$f_1+f_2\le \frac{T_R}{I_{dd}}$

2. Minimum departure frequencies:

(28)$f_1\ge f_l^{\min } and f_2\ge f_e^{\min }$

where $f_l^{\min }$ and $f_e^{\min }$ are the minimum departure frequencies of local and express trains, respectively.

3. The departure frequency of local trains is an integer multiple of that of express trains:

(29)$f_1=n\cdot f_2 (n \mathrm{is} \mathrm{a} \mathrm{positive} \mathrm{integer})$

4. Express trains must stop at the first and last stations:

(30)$x_{i,1}\cdot x_{i,N}=1, \forall i$

4. Algorithm Design

The proposed model includes many decision variables, such as f₁, f₂ and x_i,j. The two-objective optimization problem described by the optimization model is transformed using the normalization method to a single-objective optimization problem, which can be solved using an algorithm based on genetic algorithm (GA) with elite strategy, the procedure of algorithm is provided below.

Step 1: Generate the initial population.

Generate the random initial population of 40 chromosomes. One chromosome has 19 genes, the corresponding gene is a binary variable equal to 1 or 0. Furthermore, one chromosome can be divided into three segments, coding for express train stop plan x_i,j (2 ≤ j ≤ 10), local train departure frequency f₁ and express train departure frequency f₂, respectively. The binary encoding of the chromosome is shown in Figure 3.

Step 2: Calculate the fitness.

Generate the timetable according to the stop plan and frequencies of express and local train which are decoded by the chromosome. Then the overtaking condition is judged according to the safe time interval and the schedule is adjusted when overtaking occurs. If the stop plan and departure frequencies corresponding to the chromosome do not satisfy the constraints, this chromosome is discarded. If it satisfies the constraints, calculate the value of the objective function under the adjusted schedule and the fitness value of each chromosome by using the rank-based fitness method.

Step 3: Selection, crossover and mutation.

Select the chromosomes which have higher fitness to form the new subgroups and then generate a new population by using the crossover and mutation methods.

Step 4: Termination criteria.

If it reaches the maximum iteration times, stop the calculation and output the optimal result, otherwise, return to Step 2.

The flowchart of the algorithm is shown in Figure 4.

5. Case Study

A case study of the Jiangjin Line in Chongqing in the direction towards the city center during the morning peak period was carried out to find an optimal stop plan in E/L mode for this line. The Jiangjin Line stretches 42.1 km across 11 stations, starting from the Tiaodeng Station and ending at the Zhiping Station, with an average inter-station distance of 4.21 km. Figure 5 and Figure 6 show the map of the Jiangjin Line and a schematic of its stations, respectively. Table 2 summarizes the inter-station distances.

5.1. Parameter Values

Table 3 and Table 4 summarize the values of various model parameters.

5.2. Passenger OD

The Jiangjin Line is a radiating urban rail transit line with a terminal station connected to Chongqing’s No. 5 Metro Line. The majority of the passengers on the Jiangjin Line travel to the city center. As a result, many passengers transfer from the Jiangjin Line to the No. 5 Metro Line at the Tiaodeng Station (station No. 11). The passenger flow volume on the Jiangjin Line gradually increases in the direction of the city center. Table 5 and Table 6 summarize the passenger OD matrix and the sectional passenger flow volume in each inter-station segment, respectively.

5.3. Calculation Results and Analysis

5.3.1. Convergence Process

Calculations yielded an optimal stop plan in E/L mode for the Jiangjin Line during morning peak hours. Figure 7 shows the optimal trace of every generation. It can be seen that the optimal value of objective converges at 89th generation to 0.1936. The proposed algorithm shows a fast convergence speed.

5.3.2. Optimal Solution in E/L Mode

The stop plan of the express train corresponding to the optimal solution is (1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1) of which the express train skips stations No. 2, 3, 5, 6, 7, 9, and the express train overtakes the local train at stations No. 2 and 6, as shown in Figure 8. The optimal departure frequency of the local train is f₁ = 12 trains/h and the frequency of the express train is f₂ = 6 trains/h. The adjusted train timetable under overtaking conditions is shown in Figure 9.

5.3.3. Comparison of Optimal Results between Different Modes

1. Comparison between E/L Mode (Overtake) and AS Mode

Under the overtaking situation, the total wait time t_wait in optimal E/L mode is 994.05 h, which is 132.63 h higher than that (861.42 h) in all-stop (AS) mode, this is because the express train skip at some stations leads to longer waiting time for passengers at skip stations. Moreover, the total in-vehicle time t_onboard in optimal E/L mode is 6158.83 h, which is 1633.03 h (20.96%) less than that (7791.86 h) in AS mode. This is because the express train skips some stations leading to higher operating speeds and less running time between stations. Overall, the total time t_total is less than that in AS mode, reduced by 1500.04 h (approximately 17.34%). Moreover, the optimal E/L mode requires 23 trains, more than the 20 trains needed by AS mode. Although the number of trains in E/L mode is greater than that in AS mode, the E/L mode is better overall because the total travel time in E/L mode is less and the weight of passenger travel time in the normalized objective function is greater than the weight of the number of trains. Table 7 summarizes the comparison results between E/L mode with the overtaking condition and AS mode.

2. Comparison between E/L Mode (Overtake) and E/L Mode (No Overtake)

When the line adopts E/L mode but the overtaking condition is not allowed, the total wait time t_wait in is 1593.02 h, which is 598.97 h higher than that in E/L mode with the overtaking condition, this is because in non-overtaking mode, the interval between express train and local train at each station becomes very long in order to meet the safety interval requirements. Moreover, the total in-vehicle time t_onboard in non-overtaking mode is 6849.58 h, which is 690.75 h (10.08%) greater than that in E/L mode with the overtaking condition. The extra time is mainly caused by the longer transfer time of non-direct passengers at the transfer station. Overall, the total time t_total with the overtaking condition is less than that with the non-overtaking condition, it can reduce 1289.72 h (approximately 15.28%). As the express train cannot overtake the local train, the departure frequency of the train is very small to ensure the safe operation interval, thus the total number of trains required is fewer. Table 8 summarizes the comparison results between E/L mode with the overtaking condition and E/L mode without overtaking condition.

5.3.4. Sensitivity Analysis

Calculations were carried out to analyze the effects of t_z on the optimization results for AS mode, E/L mode with overtaking condition and E/L mode without overtaking condition at a t_min of 90 s and a load factor of 100% while the other conditions were kept unchanged. Figure 10 shows the comparison results of different t_z values.

The following conclusions can be drawn from Figure 10.

(1) With the increase in stop time t_z, the total travel time of passengers t_total increases. The increase in t_z has a greater impact on the t_total in AS mode than other modes. As t_z increases from 30 to 60 s, the t_total in AS mode increases by 1025.6 h (12.60%), from 8141.54 to 9167.14 h, while the t_total in E/L mode with the overtaking condition increases by 523.7 h (7.53%) from 6950.92 to 7474.62 h, the t_total in E/L mode without the overtaking condition increases by 977.12 h (12.27%) from 7960.92 to 8938.04 h.

(2) Increasing t_z enhances the superiority of E/L mode over AS mode in terms of t_total. At t_z = 30 s, the t_total in E/L mode with the overtaking condition is 14.62% less than that in AS mode, and the number grows to 18.46% as t_z increases to 60 s. Therefore, the formulation of a train operating schedule requires the determination of a reasonable t_z based on the actual operational conditions on the route in conjunction with the passenger flow.

6. Conclusions

In this paper, a 0–1 integer programming model is built for optimizing the stop plan and departure frequency of a suburban railway under a skip-stop operation mode. The model takes the stop plan of an express train and the departure frequencies of both express and local trains as decision variables, the upper and lower limits of train departure frequency as the constraints. The optimization objectives of the model are to minimize the total passenger travel time and the total number of operating trains. Meanwhile, a solution algorithm based on a genetic algorithm is proposed to solve the model. On the basis of previous research, this paper mainly focuses on schedule adjustment, optimization of a stop plan and frequency under the overtaking condition, which can maximize the line capacity. A case of Jiangjin Line in Chongqing is used to show the reasonability and effectiveness of the proposed model and algorithm. The results show that total travel time in E/L mode with the overtaking condition is significantly reduced compared with AS mode and E/L mode without the overtaking condition. Although the number of trains in the optimal solution is more than other modes, the E/L mode with the overtaking condition is still better than other modes on the whole. Increasing the station stop time can enhance the superiority of E/L mode over AS mode.

The research results of this paper can provide a reference for the optimization research of skip-stop operation under overtaking conditions and provide evidence for urban rail transit operators and planners. There are still some aspects that can be extended in future work. Firstly, this paper assumes that passengers take the first train to arrive at the station, whether it is the express train or local train. In reality, the passenger’s choice of train is a probability problem, therefore the passenger route choice behavior considering the train congestion should be considered in future studies. Moreover, genetic algorithms have the characteristics of obtaining partial optimal solutions rather than global optimal solutions. The optimization problem of the genetic algorithm for solving skip-stop operation optimization models is also an important research tendency.

Author Contributions

Both authors took part in the discussion of the work described in this paper. Writing—original draft preparation, J.X.; methodology, J.X.; writing—review and editing, Q.L.; data curation, X.H., L.W. All authors have read and agreed to the published version of the manuscript.

Funding

This research received no external funding.

Institutional Review Board Statement

Not applicable.

Informed Consent Statement

Not applicable.

Data Availability Statement

The data presented in this study are available on request from the corresponding author.

Acknowledgments

The authors thank Songsong Li and Kuo Han, for their constructive comments and suggestions in this study.

Conflicts of Interest

The authors declare no conflict of interest.

Publisher’s Note: MDPI stays neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Figures and Tables

Figure 1. E/L mode.

Figure 2. Two scenarios where the express train overtakes the local train: (a) Scenario 1; (b) Scenario 2.

Figure 3. The coding illustration of a chromosome.

Figure 4. Flowchart of the algorithm designed to solve the optimization model.

Figure 5. Map of the Jiangjin Line.

Figure 6. Stations on the Jiangjin Line.

Figure 7. Optimal trace of every generation.

Figure 8. Optimal E/L mode for the Jiangjin Line.

Figure 9. Timetable of the optimal solution result.

Figure 10. Comparison of different tz values.

Table 1

Definition of model parameters.

Parameter	Definition
i	Train number
j	Station number
N	Number of stations
xi,j	Whether train i stops at station j (xi,j = 1 means that train i stops at station j; xi,j = 0 means that train i does not stop at station j)
yi,j	Whether train i overtakes the preceding local train at station j (yi,j = 1 means that train i overtakes the preceding local train; yi,j = 0 means that train i does not overtake the preceding local train)
Iaa	Minimum interval between two successive trains arriving at the same station (seconds, s)
Idd	Minimum interval between two successive trains departing from the same station (s)
Ida	Minimum interval between one train departing from a station and the next train arriving at the same station (s)
Ita	Minimum interval between a train passing through a station without stopping and the next train arriving at the same station (s)
Iat	Minimum interval between one train arriving at a station and the next train passing through the same station without stopping (s)
Idt	Minimum interval between one train departing from a station and the next train passing through the same station without stopping (s)
TR	Duration of the study period (s)
TC	Duration of one cycle (s)
odr,s	Passenger OD volume from station r to station s during the study period (persons)

Table 2

Inter-station distances on the Jiangjin Line.

Station No.	1		2		3		4		5		6		7		8		9		10		11
Inter-station segment No.		1		2		3		4		5		6		7		8		9		10
Inter-station distance/m		10,400		1600		1300		2500		4000		4400		5300		4500		5100		3000

Table 3

Parameter values.

Symbol	Definition	Value	Unit
TR	Duration of the study period	3600	s
N	Number of stations on the Jiangjin Line	11	stations
v	Maximum inter-station operating speed	100	km/h
a 1	Acceleration rate of trains	1	m/s2
a 2	Deceleration rate of trains	1.1	m/s2
D	Capacity of trains	1572	persons
Dc	Overload limit of trains	2322	persons
tback	Turn-back time of trains	120	s
α	Weight of total travel time	0.65	-
β	Weight of total operating trains	0.35	-

Table 4

t_min values.

Symbol	Definition	Value
Ida	Minimum interval between a train departing from a station and the next train arriving at the same station	90 s
Idt	Minimum interval between a train departing from a station and the next train passing through the same station without stopping	150 s
Ita	Minimum interval between a train passing through a station without stopping and the next train arriving at the same station	120 s
Iat	Minimum interval between a train arriving at a station and the next train overtaking it by passing through the same station without stopping	60 s
Itd	Minimum interval between a train passing through a station where it overtakes the preceding train and the overtaken train departing from the same station	90 s

Table 5

Passenger OD matrix for the Jiangjin Line during long-term morning peak hours (unit: persons/h).

Station No.	1	2	3	4	5	6	7	8	9	10	11
1	-	45	175	485	190	196	105	156	124	15	347
2	-	-	92	318	172	133	102	167	98	23	535
3	-	-	-	206	402	327	183	314	97	86	2721
4	-	-	-	-	972	676	369	572	143	236	7473
5	-	-	-	-	-	68	55	77	68	96	2272
6	-	-	-	-	-	-	55	41	52	50	1187
7	-	-	-	-	-	-	-	54	29	23	541
8	-	-	-	-	-	-	-	-	53	34	809
9	-	-	-	-	-	-	-	-	-	49	1317
10	-	-	-	-	-	-	-	-	-	-	658
11	-	-	-	-	-	-	-	-	-	-	-

Table 6

Numbers of boarding and alighting passengers at each station and sectional passenger volume on the Jiangjin Line during long-term morning peak hours (unit: persons/h).

Station No.	Station Name	Number of Boarding Passengers	Number of Alighting Passengers	Sectional Passenger Volume
1	Zhiping	1838	0
				1838
2	New Passenger Transport Center	1640	45
				3433
3	Langshan	4336	267
				7502
4	Jijiang	10,441	1009
				16,934
5	Binjiang New Town South	2636	1736
				17,834
6	Binjiang New Town North	1385	1400
				17,819
7	Shuangfu West	647	869
				17,597
8	Shuangfu East	896	1381
				17,112
9	Jiulongyuan	1366	664
				17,814
10	Cambridge C Station	658	612
				17,860
11	Tiaodeng	0	17,860

Table 7

Comparison of the results for the optimal E/L (overtake) and AS modes for Jiangjin Line.

Operating Mode	twait (h)	tonboard (h)	ttotal (h)	Ctotal
AS	861.42	7791.86	8653.28	20
Optimal E/L (overtake)	994.05	6158.83	7152.88	23
Comparison results	+15.40%	−20.96%	−17.34%	+15.00%

Table 8

Comparison of the results for E/L mode with the overtaking condition and E/L mode without the overtaking condition.

Operating Mode	twait (h)	tonboard (h)	ttotal (h)	Ctotal
Optimal E/L (no overtake)	1593.02	6849.58	8442.60	15
Optimal E/L (overtake)	994.05	6158.83	7152.88	23
Comparison results	−37.60%	−10.08%	−15.28%	+53.33%

References

1. Vuchic, V.R. Urban Transit: Operations, Planning, and Economics; John Wiley & Sons: Hoboken, NJ, USA, 2006; pp. 74-75.

2. Cao, Z.; Ceder, A. Autonomous shuttle bus service timetabling and vehicle scheduling using skip-stop tactic. Transp. Res. Part C-Emerg. Technol.; 2019; 102, pp. 370-395. [DOI: https://dx.doi.org/10.1016/j.trc.2019.03.018]

3. Ghoseiri, K.; Szidarovszky, F.; Asgharpour, M.J. A multi-objective train scheduling model and solution. Transp. Res. Part B-Methodol.; 2004; 38, pp. 927-952. [DOI: https://dx.doi.org/10.1016/j.trb.2004.02.004]

4. Riejos, F.A.O.; Barrena, E.; Ortiz, J.D.C.; Laporte, G. Analyzing the theoretical capacity of railway networks with a radial-backbone topology. Transp. Res. Part A-Policy Pract.; 2016; 84, pp. 83-92. [DOI: https://dx.doi.org/10.1016/j.tra.2015.03.018]

5. Suh, W.; Chon, K.; Rhee, S. Effect of skip-stop policy on a Korean subway system. Transp. Res. Rec.; 2002; 1793, pp. 33-39. [DOI: https://dx.doi.org/10.3141/1793-05]

6. Larrain, H.; Giesen, R.; Muñoz, J.C. Choosing the Right Express Services for Bus Corridor with Capacity Restrictions. Transp. Res. Rec.; 2010; 2197, pp. 63-70. [DOI: https://dx.doi.org/10.3141/2197-08]

7. Gao, Y.; Yang, L.; Gao, Z. Energy consumption and travel time analysis for metro lines with express/local mode. Transp. Res. Part D-Transp. Env.; 2016; 60, pp. 7-27. [DOI: https://dx.doi.org/10.1016/j.trd.2016.10.009]

8. Freyss, M.; Giesen, R.; Muñoz, J.C. Continuous approximation for skip-stop operation in rail transit. Transp. Res. Part C-Emerg. Technol.; 2013; 36, pp. 419-433. [DOI: https://dx.doi.org/10.1016/j.trc.2013.07.004]

9. Jamili, A.; Aghaee, M.P. Robust stop-skipping patterns in urban railway operations under traffic alteration situation. Transp. Res. Part C-Emerg. Technol.; 2015; 61, pp. 63-74. [DOI: https://dx.doi.org/10.1016/j.trc.2015.09.013]

10. Boos, K. Line Planning in Railway Systems. Seminar on Algorithms and Models for Railway Optimization; University of Konstanz: Konstanz, Germany, 2002.

11. Ulusoy, Y.; Chien, S.; Wei, C. Optimal all-stop, short-turn, and express transit services under heterogeneous demand. Transp. Res. Rec.; 2010; 2197, pp. 8-18. [DOI: https://dx.doi.org/10.3141/2197-02]

12. Abdelhafiez, E.A.; Salama, M.R.; Shalaby, M.A. Minimizing passenger travel time in URT system adopting skip-stop strategy. J. Rail Transport Plan Manag.; 2017; 7, pp. 277-290. [DOI: https://dx.doi.org/10.1016/j.jrtpm.2017.11.001]

13. Parbo, J.; Nielsen, O.A.; Prato, C.G. Reducing passengers’ travel time by optimising stopping patterns in a large-scale network: A case-study in the Copenhagen Region. Transp. Res. Part A-Policy Pract.; 2018; 113, pp. 197-212. [DOI: https://dx.doi.org/10.1016/j.tra.2018.04.012]

14. Xie, J.; Zhang, J.; Sun, K.; Ni, S.; Chen, D. Passenger and energy-saving oriented train timetable and stop plan synchronization optimization model. Transp. Res. Part D-Transp. Environ.; 2021; 98, 102975. [DOI: https://dx.doi.org/10.1016/j.trd.2021.102975]

15. Niu, H.; Zhou, X.; Gao, R. Train scheduling for minimizing passenger waiting time with time-dependent demand and skip-stop patterns: Nonlinear integer programming models with linear constraints. Transp. Res. Part B-Methodol.; 2015; 76, pp. 117-135. [DOI: https://dx.doi.org/10.1016/j.trb.2015.03.004]

16. Yang, L.; Qi, J.; Li, S.; Gao, Y. Collaborative optimization for train scheduling and train stop planning on high-speed railways. Omega; 2015; 64, pp. 57-76. [DOI: https://dx.doi.org/10.1016/j.omega.2015.11.003]

17. Zhao, S.; Yang, H.; Wu, Y. An integrated approach of train scheduling and rolling stock circulation with skip-stopping pattern for urban rail transit lines. Transp. Res. Part C-Emerg. Technol.; 2021; 128, 103170. [DOI: https://dx.doi.org/10.1016/j.trc.2021.103170]

18. Mignone, A.; Accadia, G. Operations Research Models for Programming Support of Cadenced Timetables. Ing. Ferrov.; 2010; 65, pp. 9-29.

19. Lee, Y.J.; Shariat, S.; Choi, K. Mathematical Modeling for Optimizing Skip-Stop Rail Transit Operation Strategy Using Genetic Algorithm. Proceedings of the Transportation Research Board 92nd Annual Meeting; Washington, DC, USA, 13 January 2013.

20. Tian, X.; Niu, H. Optimization of demand-oriented train timetables under overtaking operations: A surrogate-dual-variable column generation for eliminating indivisibility. Transp. Res. Part B-Methodol.; 2020; 142, pp. 143-173. [DOI: https://dx.doi.org/10.1016/j.trb.2020.09.010]

21. Zhao, J.; Ye, M.; Yang, Z.; Xing, Z.; Zhang, Z. Operation optimizing for minimizing passenger travel time cost and operating cost with time-dependent demand and skip-stop patterns: Nonlinear integer programming model with linear constraints. Transp. Res. Interdiscip. Perspect.; 2021; 9, 100309. [DOI: https://dx.doi.org/10.1016/j.trip.2021.100309]

22. Jong, J.; Suen, C.; Chang, S. Decision support system to optimize railway stopping patterns: Application to Taiwan high-speed rail. Transp. Res. Rec.; 2012; 2289, pp. 24-33. [DOI: https://dx.doi.org/10.3141/2289-04]

23. Jong, J.C.; Suen, C.S. A train service planning model with dynamic demand for intercity railway systems. J. East. Asia Soc. Transp. Stud.; 2007; 6, pp. 1598-1613. [DOI: https://dx.doi.org/10.11175/eastpro.2007.0.207.0]

24. Sogin, S.L.; Caughron, B.M.; Chadwick, S.G. Optimizing Skip Stop Service in Passenger Rail Transportation. Proceedings of the 2012 Joint Rail Conference; Philadelphia, PA, USA, 17 April 2012.

25. Tang, L.H.; D’Ariano, A.; Xu, X.F.; Li, Y.T.; Ding, X.B.; Samà, M. Scheduling local and express trains in suburban rail transit lines: Mixed–integer nonlinear programming and adaptive genetic algorithm. Comput. Oper. Res.; 2021; 135, 105436. [DOI: https://dx.doi.org/10.1016/j.cor.2021.105436]

26. Jiang, Z.; Gu, J.; Fan, W.; Liu, W.; Zhu, B. Q-learning approach to coordinated optimization of passenger inflow control with train skip-stopping on an urban rail transit line. Comput. Ind. Eng.; 2018; 127, pp. 1131-1142. [DOI: https://dx.doi.org/10.1016/j.cie.2018.05.050]

27. Di Nardo, M.; Clericuzio, M.; Murino, T.; Madonna, M. An Adaptive Resilience Approach for a High Capacity Railway. Int. Rev. Civ. Eng.; 2020; 11, pp. 98-105. [DOI: https://dx.doi.org/10.15866/irece.v11i3.19025]

28. Zhao, X.; Sun, Q.; Zhu, Y. Multi-routing planning design of Y-type urban rail transit. Adv. Mech. Eng.; 2016; 8, pp. 1-12. [DOI: https://dx.doi.org/10.1177/1687814016667385]