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

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.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 = ∑ ( r , s ) : ( r , s ) ∈ E , r ∈ K l ∑ p : p ∈ P r s , l ∈ L p ∫ 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 ∑ l ∈ 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.

OPEN IN VIEWER

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 = ∑ m : m ≥ 1 ; y l k m + b l l ′ k ≤ 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 ∑ k ∈ K h ∑ l , l ′ ∈ L k ; l ≠ 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.

OPEN IN VIEWER

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 = ∑ m : m ≥ 1 ; x l ′ k e - 1 ≤ y l k m + b l l ′ k ≤ 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 ∑ k ∈ K h ∑ l , l ′ ∈ L k ; l ≠ 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 ∈ P r s } .

(10)

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

Q r s b = ∫ 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 ∑ ( r , s ) ∈ 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 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 ′ ≤ 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 ) = ∏ l , l ′ ∈ 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 ∑ ( r , s ) ∈ E ∑ p ∈ 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:

x l 1 ≥ t l s , η l s ≥ η ^ l s ,

(16)

where η ^ l s , η l s is the minimum required and actual effective occupancy rate when the first train of line direction l departs:

η l s = ∑ ( r , s ) ∈ E ∑ p : l ∈ p ∈ P r s d r s p l ∫ 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:

x l e ≥ t l e , η l e ≥ η ^ l e ,

(18)

where η ^ 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 ) = γ ∑ l ∈ 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:

ξ r s p ( t ) = exp ( - θ c r s p / c r s m ) ∑ p exp ( - θ c r s p / c r s m ) , ∑ p ∈ P r s ξ r s p = 1 ,

(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 ′ ∈ 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:

min z s = ∑ l ∈ L W l + ∑ k ∈ K h ∑ l , l ′ ∈ L k ; l ≠ l ′ H l l ′ m s s . t . x l 1 ≥ t l s , l ∈ L , η l s ≥ η ^ l s , l ∈ L .

(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:

min z e = α ∑ k ∈ K h ∑ l , l ′ ∈ L k ; l ≠ l ′ H l l ′ m e + ∑ ( r , s ) ∈ E β r s ( Q r s b + ∑ p ∈ P r s ( 1 - R r s p ) q r s p ) s . t . x l e ≥ t l e , l ∈ L , η l e ≥ η ^ l e , l ∈ L ,

(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.

OPEN IN VIEWER

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.

OPEN IN VIEWER

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:

y l k 1 = x l 1 + ∑ k ′ = 1 k - 1 t l k ′ , k ′ + 1 + ∑ k ′ = 2 k - 1 τ l k ′ , k = 2,3 , … , K l , x l k 1 = x l 1 + ∑ k ′ = 1 k - 1 t l k ′ , k ′ + 1 + ∑ k ′ = 2 k τ l k ′ , k = 1,2 , … , K l - 1 , y l , k e = x l e + ∑ k ′ = 1 k - 1 t l k ′ , k ′ + 1 + ∑ k ′ = 2 k - 1 τ l k ′ , k = 2,3 , … , K l , x l , k e = x l e + ∑ k ′ = 1 k - 1 t l k ′ , k ′ + 1 + ∑ k ′ = 2 k τ l k ′ , k = 1,2 , … , K l - 1 .

(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 ∈ 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.

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.

OPEN IN VIEWER

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.

OPEN IN VIEWER

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
			Up bound/min	Down bound/min
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.

OPEN IN VIEWER

Figure 6:

GA convergence for first trains' departure time.

OPEN IN VIEWER

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.

OPEN IN VIEWER

Table 2:

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

Optimal object	Minimum occupancy rate: 50%			Minimum occupancy rate: 60%
	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.

OPEN IN VIEWER

Table 3:

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

Optimal objects	Minimum occupancy rate: 50%			Minimum occupancy rate: 60%
	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.

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.