Timetable Design for Urban Rail Line with Capacity Constraints

Abstract

To design an efficient and economical timetable for a heavily congested urban rail corridor, a scheduling model is proposed in this paper. The objective of the proposed model is to find the departure time of trains at the start terminal to minimize the system cost, which includes passenger waiting cost and operating cost. To evaluate the performance of the timetable, a simulation model is developed to simulate the detailed movements of passengers and trains with strict constraints of station and train capacities. It assumes that passengers who arrive early will have more chances to access a station and board a train. The accessing and boarding processes of passengers are all based on a first-come-first-serve basis. When a station is full, passengers unable to access must wait outside until the number of waiting passengers at platform falls below a given value. When a train is full, passengers unable to board must wait at the platform for the next train to arrive. Then, based on the simulation results, a two-stage genetic algorithm is introduced to find the best timetable. Finally, a numerical example is given to demonstrate the effectiveness of the proposed model and solution method.

Yu-Ting Zhu 1,2 and Bao-Hua Mao 1, 2 and Lu Liu 1 and Ming-Gao Li 1

Academic Editor:Juan R. Torregrosa

1, MOE Key Laboratory for Urban Transportation Complex Systems Theory and Technology, Beijing Jiaotong University, Beijing 100044, China
2, School of Traffic and Transportation, Beijing Jiaotong University, Beijing 100044, China

Received 26 December 2014; Accepted 4 March 2015; 3 August 2015

This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.

1. Introduction

As the economy develops rapidly, deepening urbanization and the increasing urban population lead to a large demand for urban rail transit in many cities. In 2013, over 3.2 billion and 2.5 billion passenger rides were delivered by the Beijing and Shanghai subway systems, respectively; the average passenger rides on weekdays are more than 10 million and 7 million, respectively [1]. With such high demand, making urban rail transit more efficient has become a primary task for many cities. To improve the service quality of urban rail transit, a variety of operation strategies have been proposed, such as adjusting the speed of trains [2] and optimizing train formation [3]. Of all these strategies, timetable design has been accepted as the most straightforward and effective solution [4].

Timetable design problem (TDP) aims at determining a preoperational schedule for a set of trains and follows some train operational requirements [5]. The most popular technique to design timetable is to use mathematical programming, which is initialized by Amit and Goldfarb [6] in 1971 for railway transportation and developed by a large number of researches (such as Carey and Crawford [7], Castillo et al. [8, 9], and Castillo et al. [10]).

Although there are some differences between urban public transportation and railway transportation, the mathematical programming method has still been introduced to create efficient timetables for urban public transportation to reduce passenger waiting time. Cury et al. [11], Furth and Wilson [12], Wang et al. [13], and Barrena et al. [14] proposed optimization models to design a timetable for a single line. With the expansion of subway networks, some researchers have attempted to set up a timetable for multiple services in a connected transit network (de Palma and Lindsey [15], Caprara et al. [16], Liebchen [17], Wong et al. [18], and Aksu and Akyol [19]). However, most of them assumed that the capacity of the trains is always sufficient to receive all passengers who want to enter the train and the capacity of the stations is large enough to receive all passengers who need to be evacuated. Moreover, the average waiting time of passengers is always simplified as half of the transportation headway. In fact, infinite capacity is unrealistic and the average waiting time of passengers may be longer when capacity constraints are considered.

In order to provide a more efficient timetable for passengers, vehicle capacity has been widely considered. Ceder [20] first addressed the importance of ridership information and stated that service frequency should correspond to temporal passenger demand. One important target of this research is to avoid overcrowding (in an average sense) on the vehicles. For a further study, Ceder [21] proposed a scheduling model to replace constant headway. In this model, the ridership of each vehicle is under an ideal value. These models, however, are not suitable for a public service with high frequency [22]. Koutsopoulos et al. [23] proposed a model to find optimal headway by minimizing social cost. In their model, vehicle capacity is indirectly incorporated in the inconvenience cost due to crowding on the vehicles, and the inconvenience cost will increase as the volume to capacity ratio increases. However, as this setup will only increase the inconvenience cost when the transit vehicle is more congested, it still allows the capacity to be exceeded. Different from the three studies above, the capacity constraints are strictly enforced in the optimization models formulated in Sun et al. [4], Niu and Zhou [24], Albrecht [25], Chen [26], and Hassannayebi et al. [27]. In their models, all passengers boarding a vehicle obey the first-come-first-serve (FCFS) principle and when a vehicle is full, passengers unable to board must wait for the next vehicle to arrive. Thus, the waiting time of a passenger is the sum of time waiting for the first coming service and for the next one as a result of previous boarding failure.

Although there is a comprehensive body of literature on TDP, few studies have drawn attention to the limitation of station capacity; also, the outside-station waiting time (OSWT) caused by being unable to get into a crowding station has always been neglected. In fact, waiting outside the station is a common phenomenon in overcrowded urban rail transit systems, such as subway systems in China. In order to provide a safe and efficient movement in stations, especially in an underground station with more enclosed and very limited internal space, operators will routinely restrict the number of passengers in stations. That is to say, some passengers will be required to wait outside the station when the number of passengers in stations exceeds the safe-value. For example, in Beijing, 63 urban rail stations mainly along Line 1, Line 5, Line 6, Line 13, Batong Line, and Changping Line instituted these restrictions since July 8, 2014, during a.m. peak hours. And OSWT in some stations, such as ShaHe, an intermediate station of Changping Line, is more than 20 minutes.

In addition, many studies in the area of TDP aim to minimize the waiting time of passengers [24-27]. This single-sided approach, however, results in timetables with high operational costs since timetables that offer the minimum waiting time for passengers usually require a high-frequency service even for transit lines with low demand. It should be noted that, although studies such as the work in [24] do not take operational interests into account explicitly, some constraints are considered to restrict the operational costs within reasonable values. A more realistic approach, which is also followed in this paper, is to minimize an objective function that consists of both the operational and passenger waiting costs, such as the approach proposed by [19].

This paper fully considers the constraints of station and train capacities. Thus, the passenger waiting time can be divided into three parts, namely, [figure omitted; refer to PDF] initial platform waiting time (IPWT), time spent waiting on the platform for the first coming train; [figure omitted; refer to PDF] extra platform waiting time (EPWT), waiting time spent by left-behind passengers, who fail to board the first coming train due to the limitation of train capacity; and [figure omitted; refer to PDF] OSWT, waiting time spent outside the station. Then, an optimization model is proposed to create an efficient and economical timetable. The contributions of this paper are summarized as follows.

(i) A simulation model is developed to simulate the movements of passengers and trains with constraints of capacities, such as train maximum capacity and station safety capacity.

(ii) The total waiting time of passengers, which includes IPWT, EPWT, and OSWT, is measured based on the outputs of the simulation model.

(iii): An optimization model is proposed to minimize the operational and passenger waiting costs; a two-stage simulation-based genetic algorithm is developed to solve the model.

The remainder of the paper is as follows. Section 2 describes the timetable design problem of urban rail line in detail. The simulation model of an urban rail line is presented in Section 3. Based on the simulation model in Section 3, a two-stage simulation-based optimization approach is proposed in Section 4. In Section 5, a numerical experiment is performed to show the application of the proposed model and solution algorithm. The final section concludes the paper and discusses future research issues.

2. Timetable Design Problem

2.1. Problem Description

This paper focuses on the TDP of an urban rail line with n stations, as shown in Figure 1. The stations are numbered consecutively with the index values [figure omitted; refer to PDF] , where stations 1 and [figure omitted; refer to PDF] denote the start terminal and the return terminal, respectively. Each train departs from station 1, makes a U-turn at station [figure omitted; refer to PDF] , comes back to station 1 after a given recovery time at return terminal [figure omitted; refer to PDF] , and then prepares for a new departure. To simplify, all trains are assumed to have the same travel time between two consecutive stations and the same dwelling time at each station. Thus, the TDP in this paper aims at determining a departure schedule for trains at the start terminal.

Figure 1: The representation of an urban transit rail line.

[figure omitted; refer to PDF]

Let [figure omitted; refer to PDF] denote the study period; that is, 0 and [figure omitted; refer to PDF] represent the start and end of the study hours. To simplify the problem, the paper divides the continuous study period [figure omitted; refer to PDF] equally into a number of equal-length time intervals. Then, the study period [figure omitted; refer to PDF] can be represented as a set of discrete time points of the form [figure omitted; refer to PDF] , where [figure omitted; refer to PDF] denotes the time interval which is equal to [figure omitted; refer to PDF] and [figure omitted; refer to PDF] is a positive integer. To simplify the presentation, we ignore [figure omitted; refer to PDF] and simply write [figure omitted; refer to PDF] as [figure omitted; refer to PDF] . We also assume that all times (section running times of trains, etc.) are multiples of [figure omitted; refer to PDF] . For example, a travel time of five units means, 5 × δ seconds.

Other assumptions made throughout the paper are explained as follows.

Assumption 1.

The distribution of passenger demand is given and is steady during the study period.

Assumption 2.

Whether a station is under an overcrowding situation is decided by the number of waiting passengers in station. That is, passengers cannot enter a station when the number of waiting passengers at station is larger than the safe-value. In fact, alighting passengers will also lead to a crowding situation at station. However, it is difficult for operators to forecast the number of alighting passengers of each train. For simplification, we only forecast the maximum possible number of alighting passengers. Then, the safe capacity for waiting passengers is equal to design capacity minus this maximum number.

Assumption 3.

In general, passengers who arrive early will have more chances to access a station or board a train. In order to facilitate simplification, the paper assumes that all passengers accessing a station or boarding a train obey the FCFS principle. The passengers who fail to access an overcrowding station or fail to board a full train must wait for the next chance.

Assumption 4.

The proposed model focuses on reducing passenger waiting time. The accessing walking time of passengers at a station is not considered in this model. Here, we assume that the accessing walking time of passenger is assumed to be fixed and equal to 0.

The following notations and parameters are used throughout this paper.

Sets are as follows:

[figure omitted; refer to PDF] :: set of time intervals,

[figure omitted; refer to PDF] :: set of stations,

[figure omitted; refer to PDF] :: set of trains.

Indices are as follows:

[figure omitted; refer to PDF] :: index of stations,

[figure omitted; refer to PDF] :: index of passengers,

[figure omitted; refer to PDF] :: index of trains,

[figure omitted; refer to PDF] :: index of modeling time intervals, [figure omitted; refer to PDF] ,

[figure omitted; refer to PDF] :: index of travel direction; let [figure omitted; refer to PDF] when a train travels from start terminal to return terminal and [figure omitted; refer to PDF] for the opposite direction.

Parameters are as follows:

[figure omitted; refer to PDF] :: number of passengers who arrive at station [figure omitted; refer to PDF] at time [figure omitted; refer to PDF] ,

[figure omitted; refer to PDF] :: passenger destination probability, the probability of potential destination station [figure omitted; refer to PDF] from origin station [figure omitted; refer to PDF] ,

[figure omitted; refer to PDF] :: total number of passengers who arrive at station [figure omitted; refer to PDF] during the study period,

[figure omitted; refer to PDF] :: dwelling time at station [figure omitted; refer to PDF] ,

[figure omitted; refer to PDF] :: running time between stations [figure omitted; refer to PDF] and [figure omitted; refer to PDF]

[figure omitted; refer to PDF] :: recovery times at start terminal and return terminal,

[figure omitted; refer to PDF] :: maximum number of trains

[figure omitted; refer to PDF] :: prespecified fleet size,

[figure omitted; refer to PDF] :: number of time intervals,

[figure omitted; refer to PDF] :: train operating cost per vehicle per unit time,

[figure omitted; refer to PDF] :: waiting time cost per passenger per unit time,

[figure omitted; refer to PDF] :: maximum service headway,

[figure omitted; refer to PDF] :: minimum service headway,

[figure omitted; refer to PDF] :: maximum capacity of trains,

[figure omitted; refer to PDF] :: design capacity of station [figure omitted; refer to PDF] ,

[figure omitted; refer to PDF] :: maximum possible number of passengers alighting at station [figure omitted; refer to PDF] during study period,

[figure omitted; refer to PDF] :: maximum capacity for waiting passengers at station [figure omitted; refer to PDF] , [figure omitted; refer to PDF] ,

[figure omitted; refer to PDF] :: threshold which is used to judge whether passengers can access the overcrowding station [figure omitted; refer to PDF] . Passengers waiting outside the station can access station [figure omitted; refer to PDF] if the number of passengers in station u is less than [figure omitted; refer to PDF] ; otherwise, they cannot access this station,

[figure omitted; refer to PDF] :: let [figure omitted; refer to PDF] if passenger can access the station [figure omitted; refer to PDF] at time [figure omitted; refer to PDF] , and 0 otherwise.

Intermediate variables in simulation modelare as follows:

[figure omitted; refer to PDF] :: number of boarded passengers on train [figure omitted; refer to PDF] at time [figure omitted; refer to PDF] ,

[figure omitted; refer to PDF] :: number of passengers waiting outside station [figure omitted; refer to PDF] at time [figure omitted; refer to PDF] ,

[figure omitted; refer to PDF] :: number of passengers waiting at time [figure omitted; refer to PDF] on the platform of station [figure omitted; refer to PDF] to board on train in direction [figure omitted; refer to PDF] ,

[figure omitted; refer to PDF] :: number of passengers alighting at station [figure omitted; refer to PDF] at time [figure omitted; refer to PDF] ,

[figure omitted; refer to PDF] :: departure time of train [figure omitted; refer to PDF] at station [figure omitted; refer to PDF] in direction [figure omitted; refer to PDF] ,

[figure omitted; refer to PDF] :: arrival time of train [figure omitted; refer to PDF] at station [figure omitted; refer to PDF] in direction [figure omitted; refer to PDF] ,

[figure omitted; refer to PDF] :: departure time of the first train for the direction of the [figure omitted; refer to PDF] th passenger who accesses the station [figure omitted; refer to PDF] at time [figure omitted; refer to PDF] ,

[figure omitted; refer to PDF] :: time by the end of the recovery operation after the train [figure omitted; refer to PDF] returns to the start terminal,

[figure omitted; refer to PDF] :: arrival time of the [figure omitted; refer to PDF] th passenger at station u,

[figure omitted; refer to PDF] :: accessing time of the [figure omitted; refer to PDF] th passenger at station [figure omitted; refer to PDF] ,

[figure omitted; refer to PDF] :: boarding time of the [figure omitted; refer to PDF] th passenger at station [figure omitted; refer to PDF] ,

[figure omitted; refer to PDF] :: number of idle train unit at time [figure omitted; refer to PDF] ; initialize [figure omitted; refer to PDF] ,

[figure omitted; refer to PDF] :: let [figure omitted; refer to PDF] if station [figure omitted; refer to PDF] is under an overcrowding situation at time [figure omitted; refer to PDF] and 0 otherwise.

Decision variable is as follows:

[figure omitted; refer to PDF] :: let [figure omitted; refer to PDF] if a train departs from start terminal at time [figure omitted; refer to PDF] and 0 otherwise.

2.2. Model Formulation

The TDP in this paper aims at determining the departure time of each service at start terminal. The objective is to minimize the total cost of the transit system [figure omitted; refer to PDF] , which is the sum of the operating cost [figure omitted; refer to PDF] and the passenger waiting cost [figure omitted; refer to PDF] . Thus, the problem can then be formulated as follows: [figure omitted; refer to PDF] subject to [figure omitted; refer to PDF]

In this formulation, the objective function (1) minimizes the total cost of transit system. Equation (2) calculates the total operation cost [figure omitted; refer to PDF] , which is the sum of the operating cost of all departure trains during the study period. Equation (3) calculates the total waiting cost of passengers [figure omitted; refer to PDF] , which is the product of the number of passengers and their waiting time. In general, total waiting time of a passenger can be simply calculated by [figure omitted; refer to PDF] . However, passengers may have different feelings for different kinds of waiting time [28], especially for OSWT, since passengers may need to brave the scorching sun or biting wind. Therefore, EPWT and OSWT may be presented at a higher rank. Here, two magnification factors [figure omitted; refer to PDF] and [figure omitted; refer to PDF] ( [figure omitted; refer to PDF] , [figure omitted; refer to PDF] ) are introduced to describe this higher rank.

Constraint (4) ensures that the headway between two successive trains should meet the safety requirement. Constraint (5) ensures that the headway between two successive trains should not be too long or else passenger will have to wait long time. Constraint (6) predefines the last service of the urban rail line. Constraints (7) and (8) correspond to the limited capacity, ensuring that occupancy of trains and stations is not more than capacity. Note that it is difficult for operators to forecast the number of alighting passengers of each train. Thus, a simplified constraint, [figure omitted; refer to PDF] , is proposed to replace the original constraint (8) based on Assumption 2. Constraint (9) guarantees that the accessing process occurs only when the station is under an undersaturated situation ( [figure omitted; refer to PDF] ) or the number of passengers at the station is less than threshold ( [figure omitted; refer to PDF] ). Constraint (10) guarantees that there exist available train units to depart from the start terminal at scheduled departure times. Constraint (11) ensures that the train supply could meet the total passenger demands during the study period.

For our case, the movement of passengers is restricted by a series of constraints, and it is difficult to use mathematical modeling approach to describe the detailed movement of passengers or calculate passenger waiting time. As mentioned in [13], minimizing passenger waiting time is a nonlinear nonconvex objective function and it is computationally expensive to evaluate. Here, due to the nonlinear nature of the optimization problem, an alternative approach, simulation modeling, is proposed to evaluate solutions.

3. Simulation Model

In this section, a simulation model of urban rail line is presented to evaluate the performance of timetables. It is characterized by a discrete-event and synchronous simulation to model dynamic processes. The simulation process is illustrated in Figure 2.

Figure 2: Framework of simulation model.

[figure omitted; refer to PDF]

As shown in Figure 2, six main events are defined in the simulation model. They can be divided into two kinds, namely, passenger dynamic event and train operation dynamic event. The details of the events are described as follows.

[figure omitted; refer to PDF] Events concern the passenger dynamics: four main events are defined to describe passenger dynamics. The flowcharts of system events and the changes in variables related to passenger arrival, accessing, boarding, and alighting are shown in Figures 3, 4, 5, and 6, respectively. Every time a new passenger arrives at the station, he or she accesses the station based on the FCFS rule. If the number of passengers in station is more than the safe-value, the passengers are required to stay outside the station and wait for permission to access the station (Figure 4). In station, passengers stay in a queue at the platform to board incoming trains. The boarding processes of passengers also obey the FCFS rule. The passengers who cannot board a full train should wait for the next incoming train at the platform (Figure 5). The variables in order to handle the logics and constraints, such as the length of queues ( [figure omitted; refer to PDF] and [figure omitted; refer to PDF] ) and the load of trains ( [figure omitted; refer to PDF] ), are updated at the time events. The arrival time ( [figure omitted; refer to PDF] ), accessing time ( [figure omitted; refer to PDF] ), and boarding time ( [figure omitted; refer to PDF] ) are recorded for calculating the waiting time of passengers.

Figure 3: Flowchart of passenger arrival event.

[figure omitted; refer to PDF]

Figure 4: Flowchart of passenger accessing event.

[figure omitted; refer to PDF]

Figure 5: Flowchart of passenger boarding event.

[figure omitted; refer to PDF]

Figure 6: Flowchart of passenger alighting event.

[figure omitted; refer to PDF]

[figure omitted; refer to PDF] Events concern the train dynamics: two main events are defined to describe passenger dynamics, namely, train arrival event (Figure 7) and departure event (Figure 8). Every time when a train needs to depart from the start terminal, the number of idle train units ( [figure omitted; refer to PDF] ) should be checked. If there exist available train units, the train can depart punctually and the number of idle train units decreases ( [figure omitted; refer to PDF] ); otherwise, the train cannot depart according to the given schedule, which means the given timetable is infeasible (Figure 8). After the train has departed from the start terminal, the details of train timetable including arrival time and departure time at each station are recorded at time events. When the train returns to the start terminal, the number of idle train units increases ( [figure omitted; refer to PDF] ) after a recovery time.

Figure 7: Flowchart of train arrival event.

[figure omitted; refer to PDF]

Figure 8: Flowchart of train departure event.

[figure omitted; refer to PDF]

Note that the maximum number of alighting passengers ( [figure omitted; refer to PDF] ) is an important factor, which determines the maximum capacity for waiting passengers ( [figure omitted; refer to PDF] ). However, it is hard to forecast before the simulation. Thus, a feedback is designed to adjust the value of [figure omitted; refer to PDF] to ensure that the number of passengers in station is always under its design capacity.

4. Simulation-Based Optimization Approach

The TDP in this paper belongs to the NP-hard class (see [29]), which is difficult to solve by gradient-based methods or commercial optimization solvers. Therefore, an artificial intelligence algorithm is needed to solve the model to ensure that an optimal solution can be obtained within a reasonable amount of time.

The genetic algorithm (GA) is a stochastic search method that is inspired by the natural evolution of species. Due to its extensive generality, strong robustness, high efficiency, and practical applicability, GA has become increasingly popular in solving complex optimization problems since the seminal work of Holland [30]. In particular, it has been successfully applied to the research on transportation systems [5, 12, 14, 19, 20, 22]. In this paper, we apply GA to solve the proposed model.

4.1. Solution Representation

As the decision variable [figure omitted; refer to PDF] is a binary variable, a solution [figure omitted; refer to PDF] can be used as a chromosome in GA directly. It is obvious that the proposed chromosome structure can represent every possible solution, and the number of departing trains changes from 0 to [figure omitted; refer to PDF] . However, due to the constraints in the optimization model, most of the solutions are infeasible. For example, a solution with a gap or closeness between departures may not satisfy constraint (4) or (5). Thus, it is time-consuming to initialize a certain amount of feasible chromosomes randomly. In this paper, a preprocessing stage is proposed to reduce the time spent to generate initial chromosomes. The detailed procedure of the two-stage simulation-based GA-optimization framework is demonstrated in Figure 9.

Figure 9: Optimization procedure integrating simulation and GA.

[figure omitted; refer to PDF]

4.2. The First Stage: Generate Initial Solution Pool

An initial solution pool with pool-size chromosomes is generated in this stage. It is conceivable that even-headway timetables are solutions for the optimization model. Thus, the scheduled services that run with an even-headway are in question first, and the simulation experiments will be conducted to determine the feasible even-headway timetables. In this paper, a timetable is feasible if it satisfies all constraints (4)-(11). Then, add feasible even-timetables to the initial solution pool. Finally, a mutation operation is introduced to enrich the initial solution pool.

Mutation Operation . In order to guarantee the diversity and availability of the mutated timetable, two mutation principles are proposed as shown in Figures 10 and 11, respectively. The algorithm of mutation is described as follows. [figure omitted; refer to PDF] Randomly select a chromosome from feasible even-headway timetable set as the parent for mutation. [figure omitted; refer to PDF] Randomly generate a real number [figure omitted; refer to PDF] . If [figure omitted; refer to PDF] , obtain a mutated chromosome based on mutation operator I; otherwise, obtain a mutated chromosome based on mutation operator II.

Figure 10: Mutation operation I.

[figure omitted; refer to PDF]

Figure 11: Mutation operation II.

[figure omitted; refer to PDF]

4.3. The Second Stage: GA-Optimization Process

The procedure for GA includes the following. [figure omitted; refer to PDF] Initialize a population with pop-size chromosomes, which are selected from the initial solution pool randomly. [figure omitted; refer to PDF] Calculate evaluation function value [figure omitted; refer to PDF] ) of chromosome [figure omitted; refer to PDF] in the population based on the output of the simulation model. Here, we use objective function (1) as the evaluation function. The best individual is the chromosome with the minimum value of [figure omitted; refer to PDF] . [figure omitted; refer to PDF] Obtain fine chromosomes via selection, crossover, and mutation operations. [figure omitted; refer to PDF] Terminate when the maximum number of generations is reached. The flowchart of GA is demonstrated in Figure 9.

Mutation Operation . Different from the mutation operation in the first stage, mutation operation in this stage occurs with a certain probability [figure omitted; refer to PDF] . Randomly select a chromosome and generate a real number [figure omitted; refer to PDF] randomly. If [figure omitted; refer to PDF] , a mutated chromosome is obtained based on mutation operator I or mutation operator II. And then take it to replace the original one if it is feasible; otherwise, keep the original one.

Other detailed steps or approaches of GA, such as selection and crossover processes, are similar to the standard GA, and interested readers are referred to the related references (e.g., Gen and Cheng [31]).

5. Numerical Example

5.1. Input of Date and Parameter Settings

In order to show applications of the proposed model and solution algorithm, an urban rail line with seven stations, which is shown in Figure 12, is adopted. The stations are numbered consecutively with notations 1, 2, 3, 4, 5, 6, and 7, where stations 1 and 7 denote the start terminal and the return terminal, respectively. All the stations have an island platform. The section running time between two successive stations and dwelling time of each station are fixed at 5 min and 30 s, respectively. The recovery time at the start terminal and the return terminal is taken as 90 s; that is, [figure omitted; refer to PDF] s. The design capacity ( [figure omitted; refer to PDF] ) and control threshold ( [figure omitted; refer to PDF] ) of the station [figure omitted; refer to PDF] are taken as 1800 and 0.7.

Figure 12: An urban rail line with 7 stations.

[figure omitted; refer to PDF]

In this example, we aim to determine the departure time of each service at station 1 during the morning peak period [figure omitted; refer to PDF] . For the convenience of the expression of passenger demand, we use "second" as a basic unit to describe the study period. That is, 0 denotes the time 7:00, 3600 denotes the time 8:00, and the representations of other times can be deduced by analogy. Then, after determining the length of modeling time interval [figure omitted; refer to PDF] , the passenger demand of station u at the t th time interval (i.e., time period [figure omitted; refer to PDF] can be calculated by [figure omitted; refer to PDF] where [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] are characteristic parameters of station [figure omitted; refer to PDF] , and the values of them are shown in Table 1. Here, we give an example of how to calculate. If we let [figure omitted; refer to PDF] s, the passenger demand of station 1 at the first time interval (i.e., time period [figure omitted; refer to PDF] ) will be 443 passengers, which can be obtained by the formula above with the value of [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] ( [figure omitted; refer to PDF] , [figure omitted; refer to PDF] , and [figure omitted; refer to PDF] ) in Table 1.

Table 1: Value of demand related parameters.

	[figure omitted; refer to PDF]
	1	2	3	4	5	6	7
[figure omitted; refer to PDF]	19800	18000	12600	3000	18000	15600	10200
[figure omitted; refer to PDF]	1680	1680	1800	900	1800	2100	1800
[figure omitted; refer to PDF]	2700	2700	2100	4200	3300	3600	3600

Another important parameter related to demand, passenger destination probability [figure omitted; refer to PDF] , is depicted in Table 2. As we can see, 10% of the passengers enter the urban rail transit system from station 3 and then travel to station 1.

Table 2: Passenger destination probability [figure omitted; refer to PDF] .

	To
From	[figure omitted; refer to PDF]
	1	2	3	4	5	6	7
u	1	-	0.05	0.05	0.05	0.2	0.4	0.25
2	0.05	-	0.05	0.1	0.2	0.3	0.3
3	0.1	0.05	-	0.05	0.1	0.35	0.35
4	0.05	0.1	0.05	-	0.25	0.2	0.35
5	0.1	0.1	0.05	0.05	-	0.3	0.4
6	0.05	0.05	0.05	0.05	0.4	-	0.4
7	0.2	0.2	0.05	0.15	0.2	0.2	-

Other necessary parameters used in the simulation model and GA are summarized in Table 3. [figure omitted; refer to PDF] and [figure omitted; refer to PDF] denote the crossover and mutation rate, respectively.

Table 3: Parameters used in numerical example.

Parameters

[figure omitted; refer to PDF]

[figure omitted; refer to PDF]

[figure omitted; refer to PDF]

CT

[figure omitted; refer to PDF]

[figure omitted; refer to PDF]

[figure omitted; refer to PDF]

[figure omitted; refer to PDF]

Pop-size

Pool-size

Max-generation

[figure omitted; refer to PDF]

[figure omitted; refer to PDF]

Value

40

15 min

120 s

1680

640 USD/h

1 USD/h

1

1

40

260

Up to 70

0.9

0.2

All experiments in this paper are tested on a personal computer with an Inter Celeron G1620 2.7 GHz and 2 GB RAM. The simulation-based optimization model is coded in MATLAB 7.11.

5.2. Optimization Results with Different Time Intervals

In this section, we solve the optimization problem with different time intervals, namely, [figure omitted; refer to PDF] s, 10 s, and 30 s. The optimization process of GA is shown in Figure 13, and the comparison between different optimal results is shown in Table 4. Several conclusions are put forward here.

Table 4: Comparison between different optimal results.

δ (s)	[figure omitted; refer to PDF] (USD)	[figure omitted; refer to PDF] (USD)	[figure omitted; refer to PDF] (USD)	CPU (s)
[figure omitted; refer to PDF]	2810.59	12693.33	15503.92 (85.2%)	5834.57
[figure omitted; refer to PDF]	2841.84	12693.33	15535.17 (85.4%)	2768.51
[figure omitted; refer to PDF]	3136.25	12693.33	15829.58 (87.0%)	929.09
Even-headway	3259.35	14933.33	18192.69 (100%)	281.36

Figure 13: Optimization process of GA.

[figure omitted; refer to PDF]

[figure omitted; refer to PDF] The objective value is obtained using numerical calculation of the operation cost and passenger waiting cost in the system. By optimizing the objective, the scheduled timetable makes a balance between operators and passengers. Figure 13 shows that the proposed two-stage GA in this paper is convergent and the optimal objective can be obtained before 70 generations.

[figure omitted; refer to PDF] The objective value [figure omitted; refer to PDF] and the CPU time are different with different time intervals. And the shorter the time interval [figure omitted; refer to PDF] is, the better the objective value can be obtained and the longer the CPU time will be needed. As shown in Table 4, the best found value 15503.92 USD is obtained with the minimum time interval ( [figure omitted; refer to PDF] s) with the longest CPU time 5834.57 s. Table 5 gives the departure time of trains at the start terminal with the best found value.

Table 5: Best solution: departure times of trains at the start terminal.

Train	Departure time
1	7:04:55
2	7:09:30
3	7:14:20
4	7:18:20
5	7:21:40
6	7:25:10
7	7:29:10
8	7:33:10
9	7:37:10
10	7:41:30
11	7:47:30
12	7:51:30
13	7:56:35
14	8:02:25
15	8:08:50
16	8:16:45
17	8:30:00

[figure omitted; refer to PDF] In order to show the superiority of the model, the optimal results are also compared with the best even-headway timetable (shown in Table 4). The results show that the proposed optimization model can not only reduce passenger waiting cost but also reduce operational cost, and the total cost of the transportation system has been reduced by almost 15%, which clearly demonstrates the effectiveness of the proposed optimization model. The main reason of this result is that, comparing with even-headway timetable, the proposed optimization model is more flexible that it can adjust the departure time of each train, and the headways between any two consecutive departures vary more appropriately based on the time-varying demand. As we can see in Table 5, the headways in the optimal timetable range from 200 s to 795 s.

5.3. Analysis of the Impact of Station Capacity

Station capacity is an important constraint in our model. In order to analyze the impact of station capacity [figure omitted; refer to PDF] , sensitivity analysis is conducted with [figure omitted; refer to PDF] s against [figure omitted; refer to PDF] . The results are shown in Figure 14.

Figure 14: Optimal values with different station capacities.

[figure omitted; refer to PDF]

As we can see, when [figure omitted; refer to PDF] pax, a decreasing trend in system cost can be observed with the growth of station capacity. The total system cost improved from 29777.60 USD to 15837.34 USD when the capacities of stations increase from 1000 pax to 1400 pax. When [figure omitted; refer to PDF] pax, however, the system cost remains at a relatively stable value (about 15854 USD). This is mainly because the larger the station capacity is, the fewer the passengers will need to wait outside station and the less the outside waiting time a passenger will have. Also, fewer trains used to quicken the decreasing of the number of waiting passengers at platform are needed. Just as shown in Figure 14, the operational cost decreases nearly monotonically from 17920.00 USD to 12693.33 USD (i.e., the number of departure trains decreases from 24 to 17) with the increase of station capacity. Then, the system cost will decrease. However, when a particular value ( [figure omitted; refer to PDF] pax in this example) is reached, the total waiting time of passenger outside station will become rather small, which is difficult to have influence on the optimal result. Thus, the system cost will not change evidently.

These results indicate that a limited station capacity will have a great influence on the service quality and operation plan of urban rail transit. And the smaller the station capacity is the higher system cost will be. However, on the other side, a too large capacity for a station will contribute little to the improving of transportation system but may bring a high infrastructure cost. Therefore, it is necessary to preestimate the system cost in the operation stage before building the station.

6. Conclusions

In this paper, we present a scheduling approach for a heavily congested urban rail line. It aims to create an efficient timetable with minimal passenger waiting cost and operational cost. In order to evaluate the performance of the created timetable, a simulation model is proposed with strict constraints on train and station capacities. Then, based on the simulation results, a two-stage GA is designed to find the best timetable. Finally, the feasibility of the solution method is demonstrated through a numerical example.

Although only a small case is discussed in this paper, it is shown that the strict constraint of station capacity is essential for TDP; the timetable designed by the proposed model will have a better balance between passengers and operators.

In addition, the passenger demand in our work is assumed to be steady. However, in real work, timetables will have a feedback on the distribution of passenger demand. In our future research, we will try to create a new timetable considering this feedback.

Acknowledgments

This research was funded by the Nation Basic Research Program of China (no. 2012CB725406) and the National Natural Science Foundation of China (nos. 71131001 and 71201007). The authors also thank the anonymous reviewers and the editor for their suggestions to improve this paper.

Conflict of Interests

The authors declare that there is no conflict of interests regarding the publication of this paper.

References

[1] Research Group of Annual Report of China Urban Mass Transit 2013 Annual Report of China Urban Mass Transit , Beijing Jiaotong University Press, Beijing, China, 2014.

[2] X. Feng, B. Mao, X. Feng, J. Feng, "Study on the maximum operation speeds of metro trains for energy saving as well as transport efficiency improvement," Energy , vol. 36, no. 11, pp. 6577-6582, 2011.

[3] X. Feng, H. Liu, H. Zhang, B. Wang, Q. Sun, "Rational formations of a metro train improve its efficiencies of both traction energy utilization and passenger transport," Mathematical Problems in Engineering , vol. 2013, 2013.

[4] L. Sun, J. G. Jin, D.-H. Lee, K. W. Axhausen, A. Erath, "Demand-driven timetable design for metro services," Transportation Research Part C: Emerging Technologies , vol. 46, pp. 284-299, 2014.

[5] L. Kang, J. Wu, H. Sun, X. Zhu, B. Wang, "A practical model for last train rescheduling with train delay in urban railway transit networks," Omega , vol. 50, pp. 29-42, 2015.

[6] I. Amit, D. Goldfarb, "The timetable problem for railways," Developments in Operations Research , vol. 2, pp. 379-387, 1971.

[7] M. Carey, I. Crawford, "Scheduling trains on a network of busy complex stations," Transportation Research Part B: Methodological , vol. 41, no. 2, pp. 159-178, 2007.

[8] E. Castillo, I. Gallego, J. M. Ureña, J. M. Coronado, "Timetabling optimization of a single railway track line with sensitivity analysis," TOP , vol. 17, no. 2, pp. 256-287, 2009.

[9] E. Castillo, I. Gallego, J. M. Ureña, J. M. Coronado, "Timetabling optimization of a mixed double- and single-tracked railway network," Applied Mathematical Modelling , vol. 35, no. 2, pp. 859-878, 2011.

[10] E. Castillo, I. Gallego, S. Sanchez-Cambronero, J. M. Menendez, A. Rivas, M. Nogal, Z. Grande, "An alternate double-single track proposal for high-speed peripheral railway lines," Computer-Aided Civil and Infrastructure Engineering , vol. 30, no. 3, pp. 181-201, 2015.

[11] J. E. Cury, F. A. C. Gomide, M. J. Mendes, "A methodology for generation of optimal schedules for an underground railway system," IEEE Transactions on Automatic Control , vol. 25, no. 2, pp. 217-222, 1980.

[12] P. G. Furth, N. H. M. Wilson, "Setting frequencies on bus routes: theory and practice," Transportation Research Record , vol. 818, pp. 1-7, 1981.

[13] Y. Wang, B. de Schutter, T. van den Boom, B. Ning, T. Tang, "Real-time scheduling for single lines in urban rail transit systems," in Proceedings of the IEEE International Conference on Intelligent Rail Transportation (ICIRT '13), pp. 1-6, Beijing, China, September 2013.

[14] E. Barrena, D. Canca, L. C. Coelho, G. Laporte, "Single-line rail rapid transit timetabling under dynamic passenger demand," Transportation Research Part B: Methodological , vol. 70, pp. 134-150, 2014.

[15] A. de Palma, R. Lindsey, "Optimal timetables for public transportation," Transportation Research Part B: Methodological , vol. 35, no. 8, pp. 789-813, 2001.

[16] A. Caprara, M. Fischetti, P. Toth, "Modeling and solving the train timetabling problem," Operations Research , vol. 50, no. 5, pp. 851-861, 2002.

[17] C. Liebchen, "The first optimized railway timetable in practice," Transportation Science , vol. 42, no. 4, pp. 420-435, 2008.

[18] R. C. W. Wong, T. W. Y. Yuen, K. W. Fung, J. M. Y. Leung, "Optimizing timetable synchronization for rail mass transit," Transportation Science , vol. 42, no. 1, pp. 57-69, 2008.

[19] D. T. Aksu, U. Akyol, "Transit coordination using integer-ratio headways," IEEE Intelligent Transportation Systems Magazine , vol. 15, no. 4, pp. 1633-1642, 2014.

[20] A. Ceder, "Bus frequency determination using passenger count data," Transportation Research Part A: General , vol. 18, no. 5-6, pp. 439-453, 1984.

[21] A. Ceder, "Bus timetables with even passenger loads as opposed to even headways," Transportation Research Record , vol. 1760, no. 1, pp. 3-9, 2001.

[22] A. Ceder Public Transit Planning and Operation: Theory, Modeling and Practice , Butterworth-Heinemann, 2007.

[23] H. N. Koutsopoulos, A. Odoni, N. H. M. Wilson, "Determination of headways as a function of time varying characteristics on a transit network," Computer Scheduling of Public Transport , vol. 2, pp. 391-413, 1985.

[24] H. Niu, X. Zhou, "Optimizing urban rail timetable under time-dependent demand and oversaturated conditions," Transportation Research Part C: Emerging Technologies , vol. 36, pp. 212-230, 2013.

[25] T. Albrecht, "Automated timetable design for demand-oriented service on suburban railways," Public Transport , vol. 1, no. 1, pp. 5-20, 2009.

[26] Q. Chen, "Global optimization for bus line timetable setting problem," Discrete Dynamics in Nature and Society , vol. 2014, 2014.

[27] E. Hassannayebi, A. Sajedinejad, S. Mardani, "Urban rail transit planning using a two-stage simulation-based optimization approach," Simulation Modelling Practice and Theory , vol. 49, pp. 151-166, 2014.

[28] X.-M. Chen, Q.-X. Liu, G. Du, "Estimation of travel time values for urban public transport passengers based on SP survey," Journal of Transportation Systems Engineering and Information Technology , vol. 11, no. 4, pp. 77-84, 2011.

[29] O. J. Ibarra-Rojas, Y. A. Rios-Solis, "Synchronization of bus timetabling," Transportation Research Part B: Methodological , vol. 46, no. 5, pp. 599-614, 2012.

[30] J. H. Holland Adaptation in Natural and Artificial Systems , University of Michigan Press, Ann Arbor, Mich, USA, 1975.

[31] M. Gen, R. W. Cheng Genetic Algorithms and Engineering Optimization , John Wiley & Sons, 2000.