Coordination Optimization of the First and Last Trains' Departure Time on Urban Rail Transit Network

Abstract

Coordinating the departure times of different line directions' of first and the last trains contributes to passengers' transferring. In this paper, a coordination optimization model (i.e., M1) referring to the first train's departure time is constructed firstly to minimize passengers' total originating waiting time and transfer waiting time for the first trains. Meanwhile, the other coordination optimization model (i.e., M2) of the last trains' departure time is built to reduce passengers' transfer waiting time for the last trains and inaccessible passenger volume of all origin-destination (OD) and improve passengers' accessible reliability for the last trains. Secondly, two genetic algorithms, in which a fixed-length binary-encoding string is designed according to the time interval between the first train departure time and the earliest service time of each line direction or between the last train departure time and the latest service time of each line direction, are designed to solve M1 and M2, respectively. Finally, the validity and rationality of M1, M2, and their solving genetic algorithms are verified with numerical analysis, in which the effects of the parameters in M1 and M2 on coordination optimization result are analyzed.

1. Introduction

With the rapid development of urban rail transportation, urban rail transit networks have been formed in Beijing, Shanghai, Guangzhou, and many other big cities in China. Under the network operation and management of urban rail transportation, passengers' alternative travel routes are increased substantially because they can choose different stations to transfer, which greatly facilitates passengers' traveling but also increases the operation and organization difficulties of urban rail transportation. Coordinating trains of different lines is one of the main problems of network operation of urban rail transportation. The coordination of arrival and departure time of trains from different line directions at transfer time not only can effectively reduce the passenger transfer waiting time, but also can make lines transport capacities match each other better to improve all trains' operation efficiencies on urban rail transit network.

Train schedule optimization was studied extensively, and a series of excellent achievements has been made. The original researches aimed more at train schedule optimization of only one line. For example, Szpigel [1] first developed a linear programming model to optimize the train timetable for minimizing the total train travel time, subject to overtaking and crossing headway constraints. Higgins and Kozan [2] described the development and use of a model designed to optimize train schedules on single line rail corridors. Zhou and Zhong [3] proposed a generalized resource-constrained project scheduling formulation to minimize the total train travel time of the train timetable on the single-track railway. Li et al. [4] present a simulation method for solving the train timetabling problem to minimize the total travel time on the single-track railway. Zhou and Zhong [5] proposed a multimode resource-constrained project scheduling formulation to consider acceleration and deceleration time losses in double-track train timetabling applications. Carey [6] and Carey and Lockwood [7] solved the train timetabling and pathing problem in a rail network with one-way and two-way tracks. Lee and Chen [8] presented an optimization heuristic that includes both train pathing and train timetabling. Carey and Carville [9] devoted to scheduling and platforming trains at busy complex stations.

It is very difficult to solve the railway train schedule. Cai et al. [10] and Caprara et al. [11] regarded the train scheduling problem to be NP-hard. There are no accurate algorithms for solving the train schedule of large-scale and complex rail network within an acceptable time nowadays. In order to obtain a satisfactory train schedule within an acceptable time, the heuristic algorithms are usually designed to solve this problem. Greenberg [12], Jovanović and Harker [13], and Higgins et al. [14] developed a branch-and-bound solution framework to find feasible timetables. Kraft [15] presented a branch-and-bound approach for solving the train conflict to minimize a weighted sum of delay. Based on the branch-and-bound algorithm, Zhou and Zhong [5] incorporated effective dominance rules into this algorithm to generate pareto solution for train scheduling problem. Zhou and Zhong [3] presented to use a Lagrangian relaxation base lower bound rule, an exact lower bound rule, and a tight upper bound which are adapted in it to reduce the solution space. The priority rules, which determine the priority of each train in a conflict, depend on an estimate of the remaining crossing and overtaking delay, as well as the current delay used in some algorithm can effectively improve the optimal quality of train timetable. Carey [6] and Carey and Lockwood [7] developed an iterative decomposition approach which contains the several node branching, variable fixing, and bounding strategies to reduce the search space for solving the train timetabling and pathing problem. Dorfman and Medanic [16] incorporated some priority rules into a discrete event simulation framework to solve large-scale real-world train scheduling problem. Şahin [17], Higgins et al. [14], and Liu and Kozan [18] extended some priority rules to backtracking search, look-ahead search, and metaheuristic algorithms for train scheduling, respectively. Burdett and Kozan [19] divided the scheduling process into two levels: global scheduling to establish an initial train diagram without considering conflicts and local scheduling to repair conflicts. Dorfman and Medanic [16] developed a local feedback based travel advance strategy (TAS) by using a discrete event model of the train advance along the lines of railway. Li et al. [4], based on the TAS method proposed an algorithm based on the global information of the train to obtain an effective travel advance strategy of the train. In some literature, the train scheduling problem is modeled as a blocking parallel-machine job shop scheduling problem solved by the alternative graph model in some literature. Liu and Kozan [18] present a feasibility satisfaction procedure algorithm to solve the train scheduling problem which regarded as a blocking parallel-machine job shop scheduling problem. Burdett and Kozan [19] proposed a novel hybrid job shop approach to create new train schedules.

With network operation of urban rail transportation, more researchers became interested in train schedule optimization of the urban rail transit network. Compared to a single line, a new problem, that is, the arrival and departure time coordination of trains with different line directions, has arisen in the schedule optimization of urban rail transit network. An optimal train schedule of urban rail transit network is extremely difficult to obtain, even for a small urban rail transit network because of the large number of variables and constraints, the discrete nature of the variables, and the nonlinearity of the objective function and the constraints. In the past, attempts have been made to develop optimal train schedules of rail transit networks only with transfer time [20, 21], or both the transfer time and vehicle operating cost [20]. Carey and Crawford [21] were devoted to finding and resolving the conflicts in draft train schedules on a network of busy complex stations. Ghoseiri et al. [22] developing a multiobjective optimization model for the passenger train scheduling problem on a railroad network. Liu and Kozan [15] presented a feasibility satisfaction procedure algorithm to solve the train scheduling problem which is regarded as a blocking parallel-machine job shop scheduling problem. Burdett and Kozan [19] proposed a novel hybrid job shop approach to create new train schedules. Based on the TAS method proposed by Dorfman and Medanic [16], Li et al. [4] proposed an algorithm based on the global information of the train to obtain an effective travel advance strategy of the train.

The coordination of the first and last trains' arrival and departure time at transfer station is particularly prominent on urban rail transit network. Most reviewed researches about the first and last trains only struggled to reduce passenger transfer waiting time; however, besides that, the first train departure time influences passengers origin waiting time for the first train, while the last train departure time affects the inaccessible passenger volume and passengers' accessible reliability for last train. These passengers travel requirements are worthy of concerns especially when passengers care more about their travel service levels today. After analyzing the organization requirements of the first and last trains on urban rail transit network this paper aims to coordinate the first and last trains' departure time of each line direction so that first and last trains' arrival and departure time connect better at each of the transfer stations to meet as far as possible all travel service requirements of passenger.

The organization of this paper is as follows. Section 2 analyzes the coordination optimization goals and constraints of the first and last trains' departure time of all rail line directions. Section 3 describes passengers' travel route choice problem based on Logit model. Section 4 presents two optimization models, respectively, for the first and last trains' departure time on urban rail transit network. Section 5 deals with the genetic algorithm development, and Section 6 reports on our computational experiments. Finally some conclusions are drawn in Section 7.

2. Analysis of the First and Last Trains' Departure Time Coordination

In this section, some assumptions and symbol definitions are given firstly for the coordination optimization of the first and last trains' departure time in Section 2.1. Then the coordination optimization goals of the first and last trains' departure time are analyzed, respectively, in Sections 2.2 and 2.3, and the constraints of the first and last trains' departure time are analyzed in Section 2.4.

2.1. Symbol Definitions and Assumptions

Coordination optimization of the first and last trains' departure time based on urban rail transit network and passenger travel demands should not only meet passenger originating wait time requirement on each rail line direction, but also make the first and last trains' arrival and departure time of each rail line direction effectively connect at transfer stations so as to better meet passenger transfer time requirement from one rail line to another, especially to reduce the inaccessible passengers volume on urban rail transit network. In this paper, the coordination optimization of the first and last trains' departure time of each rail line direction is based on the following assumptions.

Assumption 1. The origin and terminal station of the first and last trains of one line direction are, respectively, line's two terminal stations, if this line is noncircular, otherwise, they are the station connecting to the railcars servicing depot.

Assumption 2. Each train capacity meets all passengers' boarding requirements on each line direction, which means that all passengers can get on the earliest arriving train after they arrived at station.

Assumption 3. Passengers' travel route choice obeys the Logit assignment principle based on generalized travel cost while there are multiple existing routes to be chosen for passengers.

The symbols related to coordination optimization include the symbols for describing urban rail transit network, OD travel demands, and a series of train operation parameters. All symbols used in this paper are defined as follows:

L: the set of rail line directions, l ∈ L;

K_l: the station sequence of rail line direction l ∈ L, k ∈ K_l;

K_h: the set of transfer stations;

L_k: the set of rail line directions linked to transfer station k, L_k ∈ L;

E: the set of OD pairs, in which (r, s) ∈ E represents the OD from origin station r to terminal station s;

P_rs(t): the set of alternative travel routes for OD pair (r, s) passengers arriving at station at time t, in which each travel route p ∈ P_rs(t) is composedone or more ordered rail line directions;

L_p: the set of rail line directions constituting travel route p;

t_rs^s: the earliest trip time of OD pair (r, s) passenger;

t_rs^e: the latest trip time of OD pair (r, s) passenger;

λ_rs(t): OD pair (r, s) passenger's arrival rate with time t (t_rs^s ≤ t ≤ t_rs^e);

φ_rs^p(t): selection probability of alternative route p ∈ P_rs(t) for passengers arriving at station at time t, which can be calculated according to passenger generalized travel cost of each alternative travel route;

x_l¹: the first train's departure time of rail line direction l;

x_l^e: the last train's departure time of rail line direction l;

x_lk¹: the first train's departure time of rail line direction l at station k;

y_lk¹: the first train's arrival time of rail line direction l at station k;

x_lk^e: the last train's departure time of rail line direction l at station k;

y_lk^e: the last train's arrival time of rail line direction l at station k;

x_lk^m: departure time of train m from station k on rail line direction l;

y_lk^m: arrival time of train m at station k on rail line direction l;

t_l^s: the earliest possible service time of rail line direction l;

t_l^e: the latest possible service time of rail line direction l;

b_ll′^k: passenger minimum walk time while passengers transfers from rail line direction l ∈ L_k to rail line direction l′ ∈ L_k at transfer station k;

I_l^s: train departure time interval of rail line direction l morning;

I_l^e: train departure time interval of rail line direction l at night;

t_l^{k, k + 1}: Train section running time including starting and stopping additional time in secton (k, k + 1) on rail line direction l;

τ_l^k: train stop time at station k on rail line direction l.

2.2. Coordination Optimization Goals of First Train's Departure Time

The coordination optimization of first train's departure time should not only reduce passengers' originating wait time for first train, but also make all first trains' arrival and departure time effectively connect at transfer station to minimize passengers transfer wait time from one rail line to another to the greatest extent. Therefore, the coordination optimization goals of first trains' departure time on urban rail transit network are selected as follows in this paper.

(1) Reduce Passengers' Total Originating Wait Time for First Train. Passenger's originating wait time for first train is the total time from the passenger's arriving at the station to his or her getting on the first train. Obviously, originating wait time w_rs^s(t) of OD (r, s) passengers, who arrive at origin station r at time t (t < x_lr¹) and then get on the first train of rail line direction l, is as follows:

w_{r s}^{s} (t) = x_{l r}^{1} - t .

(1)

The total originating wait time W_l for the first train of rail line direction l is calculated as follows:

W_{l} = \sum_{(r, s) : (r, s) \in E, r \in K_{l}} \sum_{p : p \in P_{r s}, l \in L_{p}} \int_{t_{r s}^{s}}^{x_{l r}^{s}} λ_{r s} (t) φ_{r s}^{p} (t) w_{r s}^{s} (t) d t .

(2)

The first coordination optimization goal of first trains' departure time is to reduce the total originating wait time W_l of originating passengers on urban rail transit network, namely,

\min \sum_{l \in L} W_{l} .

(3)

(2) Decrease Passengers' Transfer Wait Time for First Train. Generally, there are four transferring cases as shown in Figure 1: (1) from one line direction first train to another line direction first train, (2) from one line direction nonfirst train to another line direction first train, (3) from one line direction nonfirst train to another line direction nonfirst train, and (4) from one line direction first train to another line direction nonfirst train. In view that we only discuss the coordination optimization of first train departure time, two transferring cases, which passenger transferred from one line direction first train or nonfirst train to another line direction first train, are considered only in this paper.

Figure 1:

Passengers' transferring between two line directions linked to transfer station k.

Only when first train departure time x_l′k¹ of rail line direction l′ is not less than train m arrival time y_lk^m of rail line direction l plus passenger minimum walk time b_ll′^k, namely, y_lk^m + b_ll′^k ≤ x_l′k¹ is established, passengers will conveniently transfer from train m of direction l to direction l′ first train, and their transfer wait time is

h_{l l^{'}}^{m s} = x_{l^{'} k}^{1} - y_{l k}^{m} - b_{l l^{'}}^{k} .

(4)

The total transfer wait time H_ll′^ms of all passengers transferring from train m of rail line direction l to rail line direction l′ first train at transfer station k is obtained as follows by summing up transfer wait time h_ll′^ms of each passenger:

H_{l l^{'}}^{m s} = \sum_{m : {m \geq 1; y}_{l k}^{m} + b_{l l^{'}}^{k} \leq x_{l^{'} k}^{s}} h_{l l^{'}}^{m s} q_{k l l^{'}}^{m s},

(5)

where q_kll′^ms is the passenger volume transferring from train m of rail line direction l to rail line direction l′ first train at transfer station k.

Decreasing passengers' transfer wait time for first train is regarded as the second coordination optimization goal of first trains' departure time, namely,

\min \sum_{k \in K_{h}} \sum_{l, l^{'} \in L_{k}; l \neq l^{'}} H_{l l^{'}}^{m s} .

(6)

2.3. Coordination Optimization Goals of Last Trains' Departure Time

Passengers arriving at station after the last train departing will not reach their destination by urban rail transportation because there are no trains to take them at that time, which is called inaccessibility. Compared with the first trains' departure time, the last trains' departure time influences passenger's travel quality more extensively. It not only determines passengers transfer wait time for the last train, but also affects network inaccessible passenger volume and passenger accessible reliability for last trains. In this paper, the coordination optimization goals of last trains' departure time are summarized as follows.

(1) Minimize Passengers' Transfer Wait Time for the Last Train. Passenger transfers from one line direction train to another line direction last train can be shown in Figure 2.

Figure 2:

Passenger transfer to a line direction last train.

Only when last train departure time x_l′k^e of rail line direction l′ is more than train m arrival time y_lk^m of rail line direction l plus passenger minimum walk time b_ll′^k between these two rail line directions at transfer station k and any other direction l′ nonlast train's departure time at transfer station k is less than that, namely, x_l′k^{e – 1} ≤ y_lk^m + b_ll′^k ≤ x_l′k^e is established, passengers will conveniently transfer from train m of direction l to the last train of rail line direction l′, and their transfer wait time is as follows:

h_{l l^{'}}^{m e} = x_{l^{'} k}^{e} - y_{l k}^{m} - b_{l l^{'}}^{k} .

(7)

The total transfer wait time H_ll′^me from train m of rail line direction l to rail line direction l′ last train at transfer station k is obtained as follows by summing up transfer wait time h_ll′^me of each passenger:

H_{l l^{'}}^{m e} = \sum_{m : {m \geq 1; x_{l^{'} k}^{e - 1} \leq y}_{l k}^{m} + b_{l l^{'}}^{k} \leq x_{l^{'} k}^{e}} h_{l l^{'}}^{m e} q_{k l l^{'}}^{m e},

(8)

where q_kll′^me is the passenger volume transferring from train m of rail line direction l to rail line direction l′ last train at transfer station k.

Reducing passengers' transfer wait time for last trains is regarded as the first coordination optimization goal of last trains' departure time, namely,

\min \sum_{k \in K_{h}} \sum_{l, l^{'} \in L_{k}; l \neq l^{'}} H_{l l^{'}}^{m e} .

(9)

(2) Decreasing Network Inaccessible Passengers Volume. A travel route is inaccessible when passenger arrives at the station after the last train departs from there in the process of travel with this route. For OD (r, s) passengers, if all their alternative travel routes are inaccessible, they will not reach their destination by urban rail transportation on that day, which is called OD inaccessibility. Denote t_p^d as the latest accessible time of travel route p ∈ P_rs, which can be calculated according to the last train departure time on each rail line direction included in this travel route and passenger minimum walk time between two adjacent line directions. Then the latest accessible time t_rs^d of OD (r, s) passenger is calculated as follows:

t_{r s}^{d} = \max {t_{p}^{d} ∣ p \in P_{r s}} .

(10)

Therefore, the inaccessible passenger volume Q_rs^b of OD (r, s) is identified as follows:

Q_{r s}^{b} = \int_{t_{r s}^{d}}^{t_{r s}^{e}} λ_{r s} (t) d t .

(11)

Minimizing inaccessible passenger volume of all ODs is another coordination optimization goal of last trains' departure time, namely,

\min \sum_{(r, s) \in E} Q_{r s}^{b} .

(12)

(3) Improve Passengers' Accessible Reliability for Last Trains. Passenger's transfer time at transfer station changes randomly because of the influence of some random factors such as train arrival delay and walk interference transferring between different two line directions. The random uncertainty of passenger transfer time may lead to passenger fail in transferring. If this fail is just for transferring to a nonlast train, it has no effect on passengers because they still have other trains to transfer. Otherwise, it affects passengers badly because this transfer fail leads to their travel inaccessibility. Transfer reliability for a last train is defined to describe the probability that passengers transfer smoothly to a last train with a given longest transfer time. The transfer reliability for a nonlast train is regarded as 1. Denote ${\hat{h}}_{l l^{'}}$ as the maximum transfer time to line direction l′ last train from line direction l, which is determined according to last train running time, and denote h_ll′ as the transfer time between direction l and l′; then last train transfer reliability is described as follows:

R_{l l^{'}} = p {h_{l l^{'}} \leq {\hat{h}}_{l l^{'}}} .

(13)

Passengers will reach their destinations with a travel route only when they successfully transfer between any two connecting line directions included in this route. Travel route can be regarded as a system with one or more ordered transfer stations which are independent of each other. Thus, accessible reliability R_rs^p(t) of OD (r, s) passengers, who arrive at station at time t and choose route p ∈ P_rs(t) for traveling, is represented as

R_{r s}^{p} (t) = \prod_{l, l^{'} \in p; l^{+} = l^{'}} R_{l l^{'}} .

(14)

In general, the more passengers transfer to a last train in a travel route, the accessible reliability of this route gives more weight. This paper only considers the accessible reliability of routes in which passengers have to transfer to one or more last trains. The third coordination optimization goal of last trains' departure time is to improve travel route accessible reliability with a weight of passenger volume, which is equal to

\min \sum_{(r, s) \in E} \sum_{p \in P_{r s}} (1 - R_{r s}^{p}) q_{r s}^{p},

(15)

where q_rs^p is the passenger volume of OD (r, s) selecting route p ∈ P_rs to travel.

In fact, the third goal contradicts with the first goal in the process of coordination optimization of last trains' departure time. Thus, these two goals should be balanced according to passengers' actual requirements. So each goal is given weight and weighed by setting the weight value.

2.4. Constraints of First and Last Trains' Departure Time

Besides meeting passengers' travel requirement, first and last trains' departure times should not only satisfy the earliest and latest operating time of each rail line but also fulfill train minimum occupancy rate requirement to ensure train operation efficiency.

The constraints of meeting earliest operating time and minimum occupancy rate of each line direction first train can be expressed as follows:

\begin{matrix} x_{l}^{1} \geq t_{l}^{s}, \\ η_{l}^{s} \geq {\hat{η}}_{l}^{s}, \end{matrix}

(16)

where ${\hat{η}}_{l}^{s}, η_{l}^{s}$ is the minimum required and actual effective occupancy rate when the first train of line direction l departs:

η_{l}^{s} = \frac{\sum_{(r, s) \in E} \sum_{p : l \in p \in P_{r s}} d_{r s}^{p l} \int_{t_{r s}^{s}}^{t_{r s}^{p l}} λ_{r s}^{s} (t) φ_{r s}^{s p} (t) d t}{d_{l} ε_{l}},

(17)

where d_rs^pl is the travel mileage on line direction l for OD (r, s) passengers travel with route p, d_l is the total mileage of line direction l, and ε_l is train's fixed passenger number of line direction l.

The constraints of meeting latest operating time and minimum occupancy rate of each line direction last train can be described as follows:

\begin{matrix} x_{l}^{e} \geq t_{l}^{e}, \\ η_{l}^{e} \geq {\hat{η}}_{l}^{e}, \end{matrix}

(18)

where ${\hat{η}}_{l}^{e}, η_{l}^{e}$ is the minimum required and actual effective occupancy rate when the last train of line direction l departs, of which η_l^e is calculated according to formula (17) analogously.

3. Passenger Travel Route Choice Based on Logit Model

The choice of travel route mainly depends on originating wait time, travel time, and ticket price of each alternative travel route. It is worth noting that OD passengers alternative travel routes are not fixed and some routes become inaccessible after the last train departs, so these routes will no longer be selected by passengers.

For OD (r, s) passengers arriving at time t, to whom travel route p ∈ P_rs(t) satisfies their inaccessibility requirement, their considered costs of travelling with travel route p are calculated as follows.

(1) Originating Wait Time. Originating wait time is the time from the passengers' arriving at station to their getting on train. Denoting x_rs^p(t) as the departure time of the train, which arrived at station earliest after time t, the originating wait time at time t is calculated as follows:

w_{r s}^{p} (t) = x_{r s}^{p} (t) - t .

(19)

(2) Travel Time. Passengers travel time contains all the time taken from the origin to the destination, including train running time in sections, train stop time at stations, transfer walking time, and transfer wait time. If all routes' travel time is close, the less transfer times in a travel route, the greater the rate of being selected. Therefore, the same transfer time outweighs the same travel time on train, and the transfer time should be appropriately enlarged with a punish coefficient. Denote μ_rs^p(t) as the travel time of OD (r, s) passengers arriving at time t and selecting route p ∈ P_rs(t) for travel; then it is calculated as follows:

μ_{r s}^{p} (t) = a_{r s}^{p} + δ b_{r s}^{p},

(20)

where a_rs^p and b_rs^p are the travel time on train and the transfer time at transfer stations from passengers' original station to their destination station, respectively, and δ is the punish coefficient for enlarging the transfer time.

(3) Ticket Price. For convenience, ticket price is the product of fare rate per mileage per passenger and passenger travel mileages, which means that the longer the travel route, the higher the ticket price. Denote φ_rs^p(t) as the ticket price paid by passengers of OD (r, s) arriving at time t and selecting route p ∈ P_rs(t) for travel; then it is calculated as follows:

φ_{r s}^{p} (t) = γ \sum_{{l \in L}_{p}} d_{l}^{p},

(21)

where γ is the product of fare rate and d_l^p is the travel mileage on line direction l of passengers traveling with route p.

By introducing passenger travel value of time β to unify the unit of each travel cost, generalized travel cost of passengers of OD (r, s) arriving at time t and traveling with route p ∈ P_rs(t) is described as follows:

c_{r s}^{p} (t) = β (w_{r s}^{p} (t) + μ_{r s}^{p} (t)) + φ_{r s}^{p} (t) + ε_{r}^{q},

(22)

where ε_r^q is the random error term of generalized travel cost.

Generally, the less route generalized travel cost, the greater route choice probability. Assuming that the random error terms ε_r^q of each route travel cost are independent and obey the same Gumbel distribution, route selected probability is obtained by Logit stochastic route choice model. In the traditional Logit model, all route choice probabilities are decided by absolute cost differences between two routes' travel cost, which will lead to some unreasonable results in the allocation process. Therefore, route choice probabilities based on relative cost differences are calculated as follows:

\begin{matrix} ξ_{r s}^{p} (t) = \frac{\exp (- θ c_{r s}^{p} / c_{r s}^{m})}{\sum_{p} \exp (- θ c_{r s}^{p} / c_{r s}^{m})}, \\ \sum_{p \in P_{r s}} ξ_{r s}^{p} = 1, \end{matrix}

(23)

where ξ_rs^p(t) is the probability of choosing route p ∈ P_rs for passengers of OD (r, s) arriving at time t, θ is the parameter of Logit model, and c_rs^m is the minimum generalized travel cost of all alternative travel routes, which is calculated as follows:

c_{r s}^{m} = \min {c_{r s}^{p^{'}} ∣ p^{'} \in P_{r s}} .

(24)

Finally, the passenger volume of each alternative travel route is obtained according to each route's choiced probability, and then originating passengers and transfer passengers of the first and last trains in each line can be calculated based on the route passenger volume.

4. Coordination Optimization Model of First and Last Trains' Departure Time

4.1. Coordination Optimization Model of First Trains' Departure Time

The coordination optimization model M1, whose decision variables are first trains' departure time x_l¹ (l ∈ L) of each line direction, is constructed to minimize the total of originating wait time and transfer wait time for first trains subject to constraints of train's minimum effective occupancy rate requirement and earliest service time of rail line direction:

\begin{matrix} \min z_{s} = \sum_{l \in L} W_{l} + \sum_{k \in K_{h}} \sum_{l, l^{'} \in L_{k}; l \neq l^{'}} H_{l l^{'}}^{m s} \\ s . t . x_{l}^{1} \geq t_{l}^{s}, l \in L, \\ η_{l}^{s} \geq {\hat{η}}_{l}^{s}, l \in L . \end{matrix}

(25)

4.2. Coordination Optimization Model of Last Trains' Departure Time

The coordination optimization model M2 is built to optimize last trains' departure time x_l^e (l ∈ L) of all rail line direction on urban rail transit network, which aims to reduce passengers' transfer wait time for last trains and inaccessible passenger volume of all ODs, and improve passengers' accessible reliability for last trains subject to the constraints of trains' minimum effective occupancy rate requirement and latest service time of rail line direction. The goal of this model is to minimize the generalized costs considering three objectives simultaneously as follows:

\begin{matrix} \min z_{e} = α \sum_{k \in K_{h}} \sum_{l, l^{'} \in L_{k}; l \neq l^{'}} H_{l l^{'}}^{m e} + \sum_{(r, s) \in E} β_{r s} (Q_{r s}^{b} + \sum_{p \in P_{r s}} (1 - R_{r s}^{p}) q_{r s}^{p}) \\ s . t . x_{l}^{e} \geq t_{l}^{e}, l \in L, \\ η_{l}^{e} \geq {\hat{η}}_{l}^{e}, l \in L, \end{matrix}

(26)

where α is passenger's value of time and β_rs is the average increased cost when OD (r, s) passengers travel with other alternative traffic modes instead of urban railway transport.

5. Genetic Algorithm Design

Due to the complexities of train schedule, genetic algorithm (GA) is commonly designed to solve this train schedule coordination problem. GA is a self-adaptive global optimization probability search algorithm through simulating the genetic and evolutionary process of organisms in the natural environment. GA starts to search from a set of initial solutions generated randomly, namely, population, in which each encoded individual is corresponding to a solution. A certain number of individuals are selected as the next generation according to the fitness of each individual. GA can rapidly search good solutions in large solution space because it can treat multiple individuals at the same time and it is with invisible parallelism.

In the following, two GAs of coordination optimization of first and last trains' departure times are designed, respectively, according to these optimization problems' characteristics. The process of genetic algorithm is shown in Figure 3, which mainly involves encoding and decoding method, individual fitness calculation, selection operator, crossover operator, mutation operator, algorithm running parameters setting, and so on.

Figure 3:

The process of genetic algorithm.

(1) Encoding. Given that a first train departure time should not be more than rail line earliest operating time, the first train departure time can be obtained by adding a smaller time length on the basis of earliest operating time. For example, the incremental time length is 35 minutes when the earliest operating time is 6:00 AM and the first train departure time is 6:35 AM of one line direction. The solution code of first trains' departure time is obtained by two steps: the first is to express the incremental time length with a fixed-length binary number which is usually only six lengths expressing the maximum time length of 63 minutes and the second is to order binary numbers. Then a fixed-length binary code shown in Figure 4 is 101101111000011100…100000 when first trains' departure times are 6:45, 6:56, 6:28, …, and 6:32, respectively. This coding method not only can ensure the effectiveness of the code, but at the same time can reduce the coding length and give play to the advantages of binary code.

Figure 4:

The encoding method of the first and last trains' departure time.

Similarly, given that last train departure time should not be less than rail line latest operating time, the last train departure time can be obtained by subtracting a smaller time length on the basis of the latest operating time. For example, the decreased time length is 45 minutes when the latest operating time is 23:00 and the last train departure time is 22:15. The solution code of last trains' departure time is obtained by a string of fixed-length binary number which expresses the decreased time length. A fixed-length binary code shown in Figure 4 is 001111000100110010…011100 when last trains' departure times are 22:45, 22:56, 22:10, …, and 22:32, respectively.

(2) Decoding and Fitness Calculation. Based on the above encoding method, an incremental or decreased time length is obtained according to a solution code. Then the first train departure time is obtained by adding the earliest operating time to the increase time length, and the last train departure time is also obtained by subtracting the decrease time length from the latest operating time. Based on this, trains' arrival and departure time at each passing stations can be calculated according to train running time at each section and stop time at each station:

\begin{matrix} y_{l k}^{1} = x_{l}^{1} + \sum_{k^{'} = 1}^{k - 1} t_{l}^{k^{'}, k^{'} + 1} + \sum_{k^{'} = 2}^{k - 1} τ_{l}^{k^{'}}, k = 2,3, \dots, K_{l}, \\ x_{l k}^{1} = x_{l}^{1} + \sum_{k^{'} = 1}^{k - 1} t_{l}^{k^{'}, k^{'} + 1} + \sum_{k^{'} = 2}^{k} τ_{l}^{k^{'}}, k = 1,2, \dots, K_{l} - 1, \\ y_{l, k}^{e} = x_{l}^{e} + \sum_{k^{'} = 1}^{k - 1} t_{l}^{k^{'}, k^{'} + 1} + \sum_{k^{'} = 2}^{k - 1} τ_{l}^{k^{'}}, k = 2,3, \dots, K_{l}, \\ x_{l, k}^{e} = x_{l}^{e} + \sum_{k^{'} = 1}^{k - 1} t_{l}^{k^{'}, k^{'} + 1} + \sum_{k^{'} = 2}^{k} τ_{l}^{k^{'}}, k = 1,2, \dots, K_{l} - 1 . \end{matrix}

(27)

Each individual's objective function value can be calculated according to the first or last trains running time and the Logit model of passenger travel route choice. Then the fitness of each individual is calculated by the following formula:

f_{i} = \max {z_{j} ∣ s_{j} \in S} - z_{i},

(28)

where f_i is the fitness of individual s_i, z_i is the objective function value of individual s_i, and S is the population composed of all individuals.

(3) Selection, Crossover, and Mutation Operator. Selection operator is the combination of roulette wheel selection method and optimal preservation strategy; namely, the best individual in current generation replaces the former best individual if it is better than the former one. Therefore, the best individual will not be destroyed with the optimal preservation strategy in the process of evolutionary iteration.

The single-point crossover is selected as the crossover operator here because multipoint crossover candestroy some good individual pattern easily. The combination of uniform mutation and basic bit mutation is adopted as the mutation operator, and each gene value is mutated randomly in a smaller probability in the early stage, and a selection gene value is mutated randomly in a smaller probability in the late stage.

(4) Genetic Algorithm Running Parameters. The parameters whose values need to be determined in the process of GA design are mainly population size M, crossover probability p_c, mutation probability p_m, and termination condition. In this paper, the value of population size M is 40, the value of crossover probability p_c is 0.5, and the value of mutation probability p_m is 0.01. The termination conditions are that the best solution keep same for 20 iterations or the number of iterations reaches 100 iterations.

To sum up, genetic algorithm steps of coordination optimization of first trains' departure time are designed as follows.

Begin.

Let i = 1, population size M = 40, population S = ∅, iteration step n = 1, maximum iterations N = 100, and K = 20.

When i ≤ M, do loops.

Begin 1.

Generate a binary number with fixed length for each rail line direction randomly, and then arrange them as one solution chromosome s_i, S ← S ∪ {s_i}, i ← i + 1.

Return to begin 1.

For s_i ∈ S, calculate its object function value z_i and its fitness function f_i accordingly.

When n < N or j < K, do loops.

Begin 2.

Calculate choice probability $p_{i} = f_{i} / \sum_{s_{j} \in S} f_{j}$ , s_i ∈ S, and find the chromosome s^* with maximal fitness function f_i.

Selection operator: Firstly, select M individuals from S in probability p_i with roulette wheel selection method to compose a new population S′, and then find out the best individual s_L^* from S′. If individual s_L^* is better than individual s^*, then s^* = s_L^*, j = 1, otherwise j⁺⁺.

Crossover operator: Pair individuals of populationS′, and then do crossover operator using single-point crossover method in probability P_c for each individual pair.

Mutation operator: If $n \leq N / 2$ , mutate each gene value of individual in population S′ in probability P_m; otherwise, select one gene randomly and mutate its value in probability P_m for each individual in population S′.

Let S ← S′ ∪ {s^*}, n ← n + 1.

Return to begin 2.

First trains' departure times set ${x_{l}^{1} ∣ l \in L}$ and its corresponding object function value z^* are obtained by decoding the optimal individual.

Return.

The genetic algorithm steps of coordination optimization of last trains' departure time on urban rail transit network can be designed similarly.

6. Numerical Analysis

Guangzhou Metro is China's third largest metro network, composed of 7 lines which are line 1, line 2, line 3, line 4, line 5, line 8, and GF line. The total operation mileage of this network is 236 km at present, and the long-term planning length is 600 km. Metro has become one of the main travel modes in Guangzhou, and the average daily passenger flow is about 4.8 million. A ketch network shown in Figure 5, is obtained by retaining all transfer, original and terminal stations of Guangzhou Metro.

Figure 5:

A sketch network based on Guangzhou Metro network.

Train departure time interval, earliest and latest operation time, and the earliest and latest travel time of each line are shown in Table 1. It is worth mentioning that the earliest and latest operation time is just the earliest and latest time when trains are allowed to depart, and the actual earliest and latest service time depends on the first and the last trains, departure time.

Table 1:

Trains departing time interval, operating time range, and passenger travel timescope of each line.

Line name	Origin station	Terminal station	Train departing time interval		Line earliest service time	Line latest service time	Passenger earliest travel time	Passenger latest travel time
Line name	Origin station	Terminal station	Up bound/min	Down bound/min	Line earliest service time	Line latest service time	Passenger earliest travel time	Passenger latest travel time

Line 1	Guangzhou East Rail Station	Xilang	7.5	8	6:00	11:30	6:00	11:30
Line 2	Jiahewanggang	Guangzhou South Rail Station	6.5	7	6:00	11:30	6:00	11:30
Line 3	Tianhe Coach Terminal	Panyu Square	7	7.5	6:00	11:00	6:00	11:00
Line 3+	Airport S	Tiyu Xilu	6.5	7	6:00	11:00	6:00	11:00
Line 4	Huangcun	Jinzhou	7	7	7:00	10:30	7:00	10:30
Line 5	Jiaokou	Wenchong	7.5	7	7:00	10:30	7:00	10:30
Line 8	Fenghuang Xincun	Wangshengwei	8	7.5	7:00	10:00	7:00	10:30
Line GF	Xilang	Kuiqi road	8	8.5	7:30	9:40	7:30	9:40

Passenger minimum walk time transferring from one line to another at each transfer station is 2 minutes, and train stop time at each of the passing stations is 30 seconds. More train running data such as train running time between two adjacent stations on the rail network can be found at http://www.gzmtr.com. In addition, passenger arriving rate of each OD pair in the morning and evening are generated randomly.

When the generation time is 100, the population size is 100, the cross probability is 0.6, and the variation probability is 0.005, the convergence of designed genetic algorithm of coordinate optimization of first and last trains' departure time is shown in Figures 6 and 7, respectively.

Figure 6:

GA convergence for first trains' departure time.

Figure 7:

GA convergence for last trains' departure time.

Figures 6 and 7 show that the designed genetic algorithm of coordinate optimization of first and last trains' departure time can converge with 60 generation times, which demonstrates that two algorithms can converge efficiently and can solve the first and last trains' departure time effectively.

Firstly, M1, whose optimal goal is minimizing sum of passengers' transfer wait time and originating wait time, is solved using the designed genetic algorithm. Correspondingly the transfer wait time and originating wait time per passenger are obtained as shown in Table 2 while the train minimum required occupancy rate is, respectively, 50% and 60%. In Table 2, TWT is the transfer wait time, and OWT represents the originating wait time.

Table 2:

Coordination optimization result of first trains' departure time with different optimal object.

Optimal object	Minimum occupancy rate: 50%			Minimum occupancy rate: 60%
Optimal object	OWT per passenger/min	TWT per passenger/min	OWT and TWT per passenger/min	TWT per passenger/min	OWT per passenger/min	OWT and TWT per passenger/min

TWT	13.2	3.8	17	15	3.8	18.8
OWT	8.8	11.4	20.2	9.6	11.2	20.8
TWT & OWT	9.5	6.2	15.7	10.5	5.9	16.4

When the minimum occupancy rate is 50%, the transfer wait time per passenger is 3.8 min which is the smallest value in three situations, and the originating wait time per passenger is 8.8 min which is the smallest value in three situations. But the sum of transfer wait time and originating wait time is larger than the minimum value 15.7 min attained by model M1. The same conclusion can be obtained while the minimum occupancy rate is 60%.

Secondly, model M2 with different optimal object is solved by the designed genetic algorithm of coordinate optimization of the last train departure time in this paper. Thus, transfer wait time per passenger, inaccessible passenger volume, and passenger accessibility reliability of last train are obtained as shown in Table 3 when the train minimum required occupancy rates are, respectively, 50% and 60%. In Table 3, TWT is the transfer wait time, IPV is the inaccessible passenger volume, and ARL represents the accessibility reliability for last train.

Table 3:

Coordination optimization result of last trains' departure time with different optimal object.

Optimal objects	Minimum occupancy rate: 50%			Minimum occupancy rate: 60%
Optimal objects	TWT per passenger/min	IPV	ARL	TWT per passenger/min	IPV	ARL

IPV & ARL	8.8	853	0.95	8.9	1106	0.97
TWT & IPV	5.6	954	0.68	5.4	1035	0.66
TWT & ARL	6.4	1218	0.82	6.4	1371	0.83
IPV & TWT & ARL	6.7	1023	0.84	6.8	1241	0.85

Comparing transfer wait time per passenger, inaccessible passenger volume, and accessibility reliability for last trains in Table 3, the following conclusions are drawn.

When the minimum occupancy rate is 50%, if transfer waiting time is not considered in the optimization goal, it leads transfer waiting time per passenger reach 8.8 min; if minimizing network inaccessible passenger volume is not considered, then the calculated network inaccessible passengers reach 1218 people. In the same way, ifaccessibility reliability for the last train is not considered, the accessibility reliability for the last train would reach 0.68. If all of them are considered, relatively ideal values for each objective can be obtained simultaneously. The same situation also appears when the minimum occupancy rate is 60%.

With the increase of last train minimum required occupancy rate increased from 50% to 60%, the network inaccessible passenger volume increases, but the change of the transferring wait time per passenger and the accessibility reliability for last trains depends on passenger arriving rate.

7. Conclusion

In this paper, we firstly analyzed passenger travel cost and the travel route choice behavior of passengers with Logit model. Then a coordination optimization model M1 was constructed to minimize the total passengers originating waiting time and transfer waiting time for first trains, subjecting to the constraints of the minimum effective occupancy rate and earliest service time. Similarly, a second coordination optimization model M2 was also built to reduce passengers' transfer waiting time for last trains, minimize the inaccessible passenger volume of all OD pairs, and improve passengers' accessible reliability for the last trains. Two genetic algorithms have also been designed, respectively, to solve the models M1 and M2. From the numerical analysis, we found that the designed genetic algorithms of coordinate optimization of first and last trains' departure time can converge with 60 iterations reaching a minimum sum of transfer waiting time and origin waiting time at 15.7 minutes in model M1. Besides, the relatively ideal values of transfer waiting time, inaccessible passenger volume, and accessibility reliability could be obtained simultaneously in model M2.

Footnotes

Acknowledgments

This paper was supported partially by the National Natural Science Foundation of China (Grant no. 71171200), the Doctoral Scientific Fund Project of the Ministry of Education of China (Grant no. 20120162120042), and the fund of Hunan Province Science and Technology Hall (Grant no. 2012FJ4082).

References

Szpigel

, “Optimal train scheduling on a single track railway,” Operational Research, vol. 34, no. 4, pp. 343–352, 1973.

Higgins

Kozan

, and Ferreira

, “Optimal scheduling of trains on a single line track,” Transportation Research Part B, vol. 30, no. 2, pp. 147–158, 1996.

Zhou

X. S.

and Zhong

, “Single-track train timetabling with guaranteed optimality: branch-and-bound algorithms with enhanced lower bounds,” Transportation Research Part B, vol. 41, no. 3, pp. 320–341, 2007.

Gao

Z. Y.

K. P.

, and Yang

, “Efficient scheduling of railway traffic based on global information of train,” Transportation Research Part B, vol. 42, no. 10, pp. 1008–1030, 2008.

Zhou

X. S.

and Zhong

, “Bicriteria train scheduling for high-speed passenger railroad planning applications,” European Journal of Operational Research, vol. 167, no. 3, pp. 752–771, 2005.

Carey

, “A model and strategy for train pathing with choice of lines, platforms, and routes,” Transportation Research Part B, vol. 28, no. 5, pp. 333–353, 1994.

Carey

and Lockwood

, “Model, algorithms and strategy for train pathing,” Journal of the Operational Research Society, vol. 46, no. 8, pp. 988–1005, 1995.

Lee

and Chen

C.-Y.

, “A heuristic for the train pathing and timetabling problem,” Transportation Research Part B, vol. 43, no. 8–9, pp. 837–851, 2009.

Carey

and Carville

, “Scheduling and platforming trains at busy complex stations,” Transportation Research Part A, vol. 37, no. 3, pp. 195–224, 2003.

10.

Cai

Goh

C. J.

, and Mees

A. I.

, “Greedy heuristics for rapid scheduling of trains on a single track,” IIE Transactions, vol. 30, no. 5, pp. 481–493, 1998.

11.

Caprara

Fischetti

, and Toth

, “Modeling and solving the train timetabling problem,” Operations Research, vol. 50, no. 5, pp. 851–916, 2002.

12.

Greenberg

, “A branch-bound solution to the general scheduling problem,” Operations Research, vol. 16, no. 2, pp. 353–361, 1968.

13.

Jovanović

and Harker

P. T.

, “Tactical scheduling of rail operations. The SCAN I system,” Transportation Science, vol. 25, no. 1, pp. 46–64, 1991.

14.

Higgins

Kozan

, and Ferreira

, “Optimal scheduling of trains on a single line track,” Transportation Research Part B, vol. 30, no. 2, pp. 147–158, 1996.

15.

Kraft

E. R.

, “A branch and bound procedure for optimal train dispatching,” Journal of the Transportation Research Forum, vol. 28, no. 1, pp. 263–276, 1987.

16.

Dorfman

M. J.

and Medanic

, “Scheduling trains on a railway network using a discrete event model of railway traffic,” Transportation Research Part B, vol. 38, no. 1, pp. 81–98, 2004.

17.

Şahin

, “Railway traffic control and train scheduling based on inter-train conflict management,” Transportation Research Part B, vol. 33, no. 7, pp. 511–534, 1999.

18.

Liu

S. Q.

and Kozan

, “Scheduling trains as a blocking parallel-machine job shop scheduling problem,” Computers and Operations Research, vol. 36, no. 10, pp. 2840–2852, 2009.

19.

Burdett

R. L.

and Kozan

, “A disjunctive graph model and framework for constructing new train schedules,” European Journal of Operational Research, vol. 200, no. 1, pp. 85–98, 2010.

20.

Shrivastav

and Dhingra

S. L.

, “Development of feeder routes for Suburban railway stations using heuristic approach,” Journal of Transportation Engineering, vol. 127, no. 4, pp. 334–341, 2001.

21.

Carey

and Crawford

, “Scheduling trains on a network of busy complex stations,” Transportation Research Part B, vol. 41, no. 2, pp. 159–178, 2007.

22.

Ghoseiri

Szidarovszky

, and Asgharpour

M. J.

, “A multi-objective train scheduling model and solution,” Transportation Research Part B, vol. 38, no. 10, pp. 927–952, 2004.