Keywords

1 Introduction

Zhou and Zhong (2005) put a random accident scenario into a train schedule optimization model to optimize both the expected waiting time of high-speed train passengers and the total running time of high-speed and medium-speed trains. Goverde (2007) describes a method of using max-plus software systems to measure the stability of railway schedules and analyze the spread effects of railway delays. Liebchen (2008) used a script that lets emergencies occur periodically to optimize the timetable of the Berlin Metro to reduce passenger waiting time. Wong (2008) focuses on how to simultaneously optimize the entire transport network to minimize passenger waiting time.

2 Optimization Model of Departure Timetable

2.1 Problem Analysis

2.1.1 Characteristics of Subway Train Operation

Suppose a subway line has a total of N stations in one direction, then there will be 2n stations in both directions. In this paper, it is stipulated that the direction of the subway from the departure station is positive and the sequence of arrival codes is 1, 2, 3 … n. After arriving at the forward terminal, the turning head is turned to run again. At this time, the driving direction is set in the opposite direction and is encoded as n + 1, n + 2, n + 3 … 2n in sequence according to the arrival order. Once again back to the departure station, the train will enter the preparation time for the next drive.

2.1.2 Characteristics of Passenger

Compared with intercity railway, such as high-speed rail, passengers pay less attention to subway timetable when they take subway and other urban rail transit. They go directly to the platform to wait for the first train. If they can not go, they wait for the next train. The trip behavior will not be changed by the adjustment of departure time plan.

2.1.3 Hypothesis of Waiting Time for Passengers at Peak Hours

This paper assumes that passengers can all get on the train to simplify the optimization and choose the passenger flow as far as possible when choosing the example, compared with the maximum capacity of the train is not easy to occur because of too many passengers, the train can not let the passengers waiting on the platform get on the train at once.

2.1.4 Reasonable Arrangement of Trains and Routes

It is particularly important to coordinate and utilize the train and track resources reasonably. Otherwise, it is easy to appear the situation of “wired without train” and “wired without train”. For the general rail passenger transport, the whole flight arrangement is more systematic and passengers buy tickets in advance and travel on time, so it is not easy to waste resources or no resources can be provided. In the railway track freight transportation, the dispatching department of our country often adopts the method of “losing line” when dealing with the situation of “wired and no flow”.

2.2 Mathematical Model

Based on the analysis of the characteristics of the known passenger flow in Nanjing, the operation characteristics of the subway are analyzed, the parameters are selected and the model is established to solve the optimal departure interval of the subway timetable.

2.2.1 Basic Parameters

The parameters that will be used in the modeling process and their corresponding symbols are as follows:

  1. 1.

    the total number of subway g

Represents the number of metro vehicles set up on a predefined optimized subway line.

  1. 2.

    the number of run k and the total number of run m

K denotes the number of run of trains in the planned period, and M denotes the total number of run of trains in the planned period.

  1. 3.

    time t

  2. 4.

    the number of the stations i

Each platform will be numbered separately according to the direction of the train and the position in the whole line. I numbers range from 1, 2, 3, … 2n, and remember that Station I and Station 2n + 1-I are numbers of the same platform in different directions.

  1. 5.

    Passenger arrival rate pas (i,j,t)

Passenger arrival rate PAS (i, j, t) of station J is the destination of station I at time t. The unit is person/min. At the same time, it is clear that all passengers will alight when the train arrives at the forward terminal, so no passengers will ride from the forward terminal to the reverse, that is, the arrival rate of passengers at the right and the right time pAs (I, J, t) is always zero.

  1. 6.

    the time for train No. K to arrive at I station \( A_{i,k} \)

It means that the time for train No. K to arrive at I station is accurate to minutes.

  1. 7.

    the time that the subway comes from station I to station I + 1 \( B_{i,\;i + 1} \)

Indicates the time required for the subway from station I to station I + 1, including the stopping time at station I and the running time required for leaving station I to station I + 1. For the convenience of calculation, the accuracy is taken to minutes.

  1. 8.

    the time for train No. K to departure I station \( D_{i,k} \)

Because all the time units in this optimization scheme are all value to minutes, and the subway train usually stops at one station for less than one minute, so the default train departure time \( D_{i,k} \) is equal to the train arrival time \( A_{i,k} \).

  1. 9.

    \( P_{i,k} \) and \( Z_{i,k} \)

When the train No. K leaves platform No. I, the number of passengers on board is \( P_{i,k} \) and the carrying rate of passengers is \( Z_{i,k} \).

  1. 10.

    Minimum preparation time \( B_{0} \)

When each train reaches Platform 2n, it needs to enter the platform to rest at least one minimum preparation time \( B_{0} \) before it can start again.

  1. 11.

    Remainder \( L_{i,k} \)

The number of passengers arriving at the destination after the arrival of the k th train at station I has not yet reached the number of passengers boarding the station

  1. 12.

    Maximum carrying capacity of train PN

In theory, the maximum passenger carrying capacity of a train is equal to the maximum passenger carrying capacity corresponding to the type of single carriage used by the train group (calculated by 9 persons per square) multiplied by the number of cars connected by each train group.

2.2.2 When the Train Leaves the Station, the Number of People on the Train i \( P_{i,k} \)

When train No. K arrives at I station, it is assumed that the passengers should obey the principle of “first down and back up”. Then \( P_{i,k} \) it can be obtained through distributed computation.

$$ L_{i,k} = P_{i - 1,k} - \sum\limits_{j = 1}^{i - 1} {\sum\limits_{{t = A_{j - 1,k - 1} + 1}}^{{A_{j - 1,k} }} {pas(j,i,t)} } \quad \text{k} = 1,2,3, \ldots ,\text{m};\;\text{i} = 2,3,4, \ldots ,2\text{n} $$
(1)
$$ P_{i,k} = L_{i,k} + \sum\limits_{j = i + 1}^{2n} {\sum\limits_{{t = A_{i,k - 1} + 1}}^{Ai,k} {pas(i,j,t)} } \quad \text{k} = 1,2,3, \ldots ,\text{m};\;\text{i} = 1,2,3, \ldots ,2\text{n} - \text{1} $$
(2)

(1) is used to calculate the remaining number of passengers after getting off the train., (2) is used to calculate the number of people on the train leaving the platform.

2.2.3 Arrival Time of Trains

Because it is assumed in this paper that the departure time of the train is the same as the arrival time of the train at each station, the arrival time of the k th train at Platform I can be obtained from the arrival time of the train at the departure station plus the travel time of the stations on the way.

$$ A_{i,k} = A_{1,k} + \sum\limits_{l = 1}^{i - 1} {B_{l,l + 1} } \quad \text{k} = 1,2,3, \ldots ,\text{m};\;\text{i} = 2,3,4, \ldots ,2\text{n} $$
(3)

2.3 Constraint

2.3.1 Restrictions on Vehicle Group Quantity

Since only Group G subway is put into operation on a subway line, no matter what timing scheme is adopted, the starting time of train K (k > g) must always be greater than or equal to the starting time of train K-G and the minimum preparation time. Expression is expressed by mathematical formula.

$$ A_{1,k} \ge A_{{1,k - {\text{g}}}} + \sum\limits_{i = 1}^{2n - 1} {B_{i,i + 1} } + B_{0} $$
(4)

2.3.2 The Restriction of the Minimum Passenger Rate \( {\mathbf{min}}\,\varvec{Z} \)

Here the following criteria are drawn up: if the number of \( Z_{i,k} < \hbox{min} \,Z \) is greater than the allowable number of occurrences Y, the arrangement of the K train is considered unreasonable and needs to be reconsidered.

2.3.3 Minimum Time Interval Between Adjacent Shift Vehicles J

In the subway operation, the departure time interval of the two subway trains must meet a minimum time interval value J, so as to meet the safety requirements.

$$ A_{1,k} - A_{1,k - 1} \ge \;J\quad \text{k} = 2,3,4, \ldots ,\text{m} $$
(5)

2.4 Objective Function

Suppose that if a group of passenger who want to go to station j arrive at station i at time t and t is between \( A_{i,k - 1} \) and \( A_{i,k} \), then they will take the k th subway to their destination and the waiting will be \( A_{i,k} - t \). So our objective function can be presented as follow

$$ \hbox{min} \sum\limits_{k = 1}^{m} {\sum\limits_{i = 1}^{{2{\text{n - }}1}} {\sum\limits_{j = 2}^{{2{\text{n}}}} {\sum\limits_{{t = A_{i,k - 1} + 1}}^{{A_{i,k} }} {(A_{i,k} - t)^{*} pas(i,j,t)} } } } /PN $$
(6)

3 Genetic Algorithm

Genetic algorithm is a stochastic global search and optimization method which imitates the evolution mechanism of natural organisms. Its essence is an efficient, parallel and global search method. It can automatically acquire, accumulate and learn the knowledge about search space in the process of search operation, and adaptively control the search process to obtain the optimal results.

4 Simulation

4.1 Sloving

In this paper, the genetic algorithm is used to solve the model. Chromosomes are encoded in traditional binary system. Each gene position corresponds to every possible departure time in the optimization period. For this time, “1” will have a train to send out, and “0” will not have a train to send out. The optimal time interval is 5 h and the unit is min. There are 300 possible departure times, that is, the individual chromosome length is 300. When calculating individual fitness, the constraints are combined with the objective function, and the individuals who do not meet the constraints will add penalty value to the objective function to reduce their fitness. Some parameters in the algorithm are as follows: the minimum time interval of trains is 2 min, the maximum carrying capacity of trains is 1 440, the minimum carrying rate of trains is 6.5%, the number of low-load passengers is 3, the number of trains available for dispatching is 15, the population size is 50, the number of genetic iterations is 500, and the crossover probability is 0.70, respectively. The probability of element variation is 0.5.

4.2 Data

Nanjing Line S1 is an important Metro extension line located in the south of Nanjing. The length of Nanjing Line S1 is 35.8 km, including 18.2 km underground, 0.7 km transitional and 16.9 km viaduct. Because this paper calculates the flow of people in minutes and the train stops at one stop for no more than one minute, it is of little significance to set the train stopping time. The train departure time is the train arrival time. It can be seen from the above that the early peak of Nanjing passenger flow is at 8–9, so the study of optimization period selected 6–11 points (Tables 1 and 2).

Table 1. Station number of Nanjing line S1
Full size table
Table 2. The time consumed between stations in Nanjing S1 line
Full size table

The Nanjing Metro’s current record of passenger information is shown in Table 3.

Table 3. Nanjing metro passenger information record form
Full size table

Therefore, according to the information provided in the table above, the flow of people between any two stations in Nanjing S1 line can be calculated. At the same time, the flow of people from Nanjing S1 line to other lines and from other lines to S1 line should also be calculated. After calculation and collation, the following figure of Nanjing Line S1 passenger flow in the optimization period of change chart (1 min) (Fig. 1).

Fig. 1.
figure 1

Variation of passenger flow in Nanjing S1 line over time

Full size image
Fig. 2.
figure 2

Trains running from 6 a.m. to 11 a.m. on Nanjing line S1

Full size image

As can be seen from the above chart, although passenger flow fluctuates greatly over time, the overall trend is always increasing and gradually stabilized

Table 4. The optimal departure time for all trains
Full size table
Table 5. The optimal departure time for all trains
Full size table

4.3 Conclusion

Because of the randomness of the genetic algorithm, we have solved it many times and analyzed and compared the results of each calculation, so as to avoid getting unreasonable conclusions because of the premature convergence of the algorithm.

After solving the mathematical model and the genetic algorithm code, the following subway timetable is obtained from one of the optimal solutions. The optimal departure times are 46 times and the average waiting time is 4.98 min (Tables 4 and 5).

The train diagram of Nanjing Line S1 is drawn from the above plan. As shown in the following diagram, abscissa represents time, ordinate represents station, slant represents subway line, slope greater than 0 represents forward running, slope less than 0 represents reverse running, and slope equal to 0 represents preparation for running at the corresponding station (Fig. 2).

Comparing the two charts with the previous passenger flow chart, it can be seen that the change of departure interval coincides with the change of passenger flow with the time interval. In reality, the train of Nanjing Line S1, which usually needs to wait for 10 min, can reduce the average waiting time to 4.98 min under the conditions of meeting the constraints of transferable train group and low-load passenger rate, greatly reducing the waiting time and providing great convenience.

5 Summary

The optimization results show that the waiting time of passengers will be significantly shortened after using the model. It proves that the model proposed in this paper has a certain role in solving the problem of average waiting time of passengers in urban rail transit.