# Optimization of Bus Bridging Service under Unexpected Metro Disruptions with Dynamic Passenger Flows

Authors: Jiadong Wang; Zhenzhou Yuan; Yonghao Yin
Journal: Journal of Advanced Transportation
 (2019)

---

## Abstract

A metro disruption is a situation where metro service is suspended for some time due to unexpected events such as equipment failure and extreme weather. Metro disruptions reduce the level of service of metro systems and leave numerous passengers stranded at disrupted stations. As a means of disruption management, bus bridging has been widely used to evacuate stranded passengers. This paper focuses on the bus bridging problem under operational disruptions on a single metro line. Unlike previous studies, we consider dynamic passenger flows during the disruption. A multi-objective optimization model is established with objectives to minimize total waiting time, the number of stranded passengers and dispatched vehicles with constraints such as fleet size and vehicle capacity. The NSGA-II algorithm is used for the solution. Finally, we apply the proposed model to Shanghai Metro to access the effectiveness of our approaches in comparison with the current bridging strategy. Sensitivity analysis of the bus fleet size involved in the bus bridging problem was conducted.


---

## Body

## 1. Introduction

Metro disruptions, usually caused by emergency events such as infrastructure blockages, accidents and extreme weather, have frequently occurred in lots of cities [1]. A disruption is a relatively large external incident leading to large delays or cancellations of a number of trains in the timetable [2]. When the disruption lasts for a long time, for the purpose of reducing the impacts of disruptions, the affected metro line tends to operate in a short turning mode, on residual railway sections beyond the track crossovers. Metro disruptions prevent trains operate according to planning timetables. In addition, disrupted stations are unable to provide services to passengers resulting that numerous passengers are stranded. Pender et al. [3] found through the survey that bus bridging is the most common response to metro disruption especially line blockages. As an alternative mode for metro, a current approach to bus bridging is that buses travel parallelly to the disrupted metro line. However this approach usually unlikely achieves satisfactory effects. Due to the limited capacity of public transport, passengers at disrupted stations especially intermediate stations need to wait for several buses to get on the bus.When operational disruptions occur, the most commonly used disruption management strategies mainly include adjusting timetable and rescheduling rolling stock. Considering an over-crowed passenger flow following a disruption, Gao et al. [4] proposed a stop-skipping strategy and built an optimization model to reschedule a metro train. Since metro lines are generally equipped with storage lines and backup trains, Yin et al. [5] proposed a MILP model for rescheduling metro trains and timetable by using backup trains. In addition to timetables, operational disruptions will also affect rolling stock plans. Veelenturf et al. [6] proposed a disruption management method integrating rescheduling of the timetable and rolling stock by taking dynamic passenger demand into account. Considering that passengers affected by the disruptions may change their travel plans [1], Cadarso et al. [7] proposed a two-stage approach to combine the timetable and rolling stock with passengers’ behavior in an integrated optimization model.When the disruption lasts for a long time, for example, 30 minutes or more, it is unlikely to clear up the stranded passengers by adjusting the metro system itself. In this situation the bus bridging service is required. Kepaptsoglou and Karlaftis [8] first defined the bus bridging as the temporary routes to “bridge” disrupted stations and proposed a methodology for designing a bus bridging network. Codina et al. [9] established a nonlinear programming model to optimize a congested bus bridging system. The output included frequencies and the number of bus for each candidate bus lines. Jin et al. [10] proposed a systematic approach to optimizing bus bridging services. Firstly a column generation algorithm was used to generate candidate bus routes, then a path-based multicommodity network flow model was established to optimize bus bridging network. Similarly, Van der Hurk et al. [11] proposed a formulation to minimize passenger inconvenience cost including transfers and waiting cost with a minimal frequency constraint. Deng et al. [12] developed a model to design bus bridging routes considering passenger route choice behavior and the bridging station capacity.The above research focused on a frequency-based modelling framework with the assumption that buses run on routes with fixed headway, which is similar to the traditional transit network design problem (TNDP) [13]. Nevertheless, when the metro service is disrupted, the transit agency must arrange the bus bridging service as soon as possible. Thus, it is necessary to take into consideration time spent required to dispatch buses. Recently, bus bridging operation strategies proposed to deal with unexpected disruptions did not require buses to operate based on fixed frequencies [1]. They proposed a type of models based on Bus Evacuation Problem (BEP) [14]. For example, Wang et al. [15] established a feeder-bus dispatch planning model to minimize the total transit operation cost in the evacuation. Hu et al. [16] proposed an efficient bus bridging strategy and constructed a multi-circle bus dispatching model minimizing the total evacuation time without taking dynamic passenger demands into account. Considering uncertainties under unexpected situation, Lv et al. [17] proposed a bus evacuation model based on interval chance-constrained integer programming method. The above research designated buses to shuttle between fixed stations resulting that the operation flexibility and evacuation efficiency may be limited. Recently, Gu et al. [1] proposed a flexible strategy allocating and scheduling buses to different bridging routes. They formulated a two-step model to optimize the bus bridging schedule minimizing total evacuation time and passenger delay, respectively. Although dynamic passenger demand was taken into account with a rolling horizon approach, the essence is taking static passenger flows at the end of each rolling period as the input of the proposed model.Some other researchers studied travel behavior of passengers and travel demand after disruptions, which could provide references for this study [18–20]. For example, Wang et al. [18] studied the demand modelling of affected passengers and formulated it as a bulk queuing problem with the theory of stochastic process. The results showed the bridging demand continued for hours. Yin et al. [19] proposed a three-layer discrete choice behavior model to predict dynamic passenger flows. It was found that as time passed, an increasing number of passengers would alter their planned routes or quit metro journeys during the disruption. As a result, there are continuously passengers who transfer to buses during the disruption. Duan et al. [20] conducted studies using mobile phone data to investigate the impact on passengers of the collision accident of Metro Line 10 in Shanghai, China, on 27 September 2011. The result revealed that in the second evacuation stage over 60% of stranded passengers left the accident stations by ground transportation. They suggested that buses should be dispatched to connect disrupted stations, especially the non-interchange stations to the nearest operating stations. Related work has also been done to integrate bus bridging with other aspects. For example, Yang et al. [21] develop a joint approach to integrate passenger flow control and bus bridging to alleviate oversaturated situation for commuting metro lines. Kang et al. [22] coordinated last train timetabling and bus bridging service to deal with the stranded passengers. Zhang et al. [23] studied the optimal bus bridging starting time under uncertain recovery time, considering the uncertainty of the recovery time, but did not give a specific vehicle scheduling scheme.In this research, we investigate how to efficiently operate bus bridging service in response to a metro operational disruption. Based on the strategy proposed by Gu et al. [1], a multi-objective programming model was formulated. Compared with previous studies, contributions of our research are summarized as follows: (i) an optimization-based model was proposed considering dynamic passenger flow demands during the disruption. (ii) The model was formulated with the objective to minimize total waiting time, the number of stranded passengers and dispatched buses, rather than evacuation time. (iii) A large-scale case study was conducted to evaluate the method. The remainder of this paper is organized as follows. A detailed description of bus bridging problem under unexpected metro disruptions is presented in Section 2. An optimization model is formulated in Section 3. A solution approach based on NSGA-II algorithm is described in Section 4. Benefits of our bus bridging strategy are analyzed with a large-scale case study in Section 5. Finally, conclusions and future research outlook are summarized in Section 6.


## 2. The Problem Description

### 2.1. Problem Description

Consider a metro disruption that several stations suspend service between two stations with track crossovers (see Figure1.) Trains operate in short turning mode on residual metro lines. Buses need to be dispatched for emergency evacuation from bus depots and to evacuate the passengers to the turnover stations.Figure 1
Disruption scenario.We suppose that the bus bridging stops are near metro station exits. Bus bridging stops are set on both sides of the roads corresponding to opposite directions of the same metro station. Assume that metro operators can predict disruption recovery time precisely and start bus bridging service immediately after disruption occurs. The metro line returns to normal operation at timeT. Let [0,T] denote the disruption duration period. When the metro disruption resumes, passengers return to the metro system and will be rapidly evacuated. Therefore, we limit the effective time of bus bridging to [0,T]. In order to represent dynamic passenger flows, we divide [0,T] equally into several time intervals of one minute. We hereafter refer to time interval as time and usetto index it. The passenger demand at stationi at timetis denoted as λi(t). Let M be the set of buses available. Let D be the set of depots. Let N be the set of stations, including the set of disrupted stations I and the set of turnover stations J. We desire to dispatch buses in the following manner: bus m∈M is dispatched from depot d∈D, visits one disrupted station i∈I and transports passengers with the capacity constraintC to turnover station j∈J, come back to visit another disrupted station k∈I, then go to turnover station l∈J and so on, until the disruption returns to the normal operation. We refer the station that a bus is dispatched to its designated station [1]. We assume that a significant number of passengers choose to transfer to buses; whenever a bus visits a station, it gets fully loaded immediately. The journey that a bus transports passengers from an affected station to the turnover station is defined as a bridging trip of the bus. Multiple bridging trips constitute the bridging route of a bus. Note that the origin of the first bridging trip should be its designated station. aimr denotes the departure time of busm in ther th bridging trip at stationi. Different buses may visit a station one after the other, and let bif indicate the departure time of thef th pickup at stationi. Figure 2(a) illustrates an example of a metro disruption with four stations and three buses in one depot. The number in the circle indicates stations while the number beside the link denotes the travel time between stations or depots. Figure 2(b) presents bridging route for each bus. Solid arrows indicate bridging trips loading passengers and dotted arrows denote deadheading trips. For example, bus 3 visits station 3, station 2 and station 4 sequentially. For station 2, the first pickup is at the fourth minute by bus 1 and the second pickup is at 12th minute by bus 3, i.e. b21=4, b22=12.Figure 2
Illustration of bus bridging trips and pickups.
(a) (b)As for stations, we focus on waiting time. As shown in Figure3, the horizontal axis represents time, and the yellow curve and blue curve indicate the cumulative arrival curve and the cumulative departure curve of passengers, respectively. Assuming that passenger arrival rate is constant during the time period [0,H], p0 indicates the number of passengers who quit metro and transfer to buses at the beginning of the disruption. Note that we only consider passengers who arrive withinH minutes after the disruption. p indicates the sum of arrival passengers during the disruption. The area bounded by the two curves and line y=T represents total waiting time for passengers. In Section 3, we propose a variant model of Vehicle Routing Problem (VRP). One of the objectives of the proposed model is to minimize total waiting time. The decision is to plan the bus bridging routing, that is, for each bus to determine which bridging trips are selected and what is the optimal order of them. We use binary variables xijmr to determine whether busmtransport passengers from stationi to stationj in ther th bridging trip and binary variables ydim to determine whether busm is dispatched from depotd to stationi.Figure 3
Total waiting time.To illustrate the modelling framework, consider a metro disruption case with five disrupted stations. Assuming that there are totally five buses available, a time space diagram of each bus is as shown in Figure4(a). Buses are shown by different colors. We seek to obtain the optimal bus bridging solution with the minimum total waiting time. Figure 4(b) shows the optimized bus bridging solution. As can be seen, the optimized bus trajectories are more dispersed. Table 1 presents their specific bridging trips. The first number in the bracket represents the origin of the bridging trip and the second number represents the destination. For example, bus 1 as red trajectory shows is dispatched from depot 1 to station 2 and travels through bridging trips (2,1) → (2,1) → (3,5) → (4,1) sequentially. Figure 5 shows the cumulative arrival curves and cumulative departure curves of station 3 in the upward direction before and after optimization. As can be seen from Figure 5(a), before optimization there are three pickups at station 3, at 22th, 47th, and 50th minute, respectively. The total waiting time is 896 hours, with 762 passengers stranded. In contrast, in the optimized solution, the total waiting time is 123 hours, with 288 passengers stranded. As shown in Figure 5(b), the cumulative departure curve is much closer to the cumulative arrival curve than the initial plan.Table 1
Optimization results in illustrative example.
Bus index Depot Bridging process 1 D1 (2,1) → (2,1) → (3,5) → (4,1) 2 D2 (3,5) → (4,5) → (5,1) 3 D2 (3,1) → (2,5) → (4,5) → (5,1) 4 D3 (4,1) → (2,1) → (2,5) → (5,1) 5 D3 (1,5) → (5,1) → (1,5)Figure 4
Comparing time space diagram of buses before and after optimization in illustrative example.
(a) (b)Figure 5
Comparing cumulative arrival departure curves of station 3 in upward direction before and after optimization in illustrative example.
(a) (b)


### 2.2. Assumptions

To simplify the problem, the following assumptions are made.(1)
Neglect delays due to traffic congestions and bus travel times between stations are constant.(2)
The parking capacity of the bus stop is large enough and the queue delay caused by the simultaneous arrival of multiple buses is not considered.(3)
Buses immediately depart from a station after arriving there and boarding time for passengers at each station is equal.


### 2.3. Notations

For illustrative purpose, main notations for the model are listed as follows.Indices i , k: index of disruption stations, i,k∈I j , l: index of turnover stations, j,l∈J g: index of directions, g=1 represents upward direction, g=2 represents downward direction m: index of buses, m∈M d: index of bus depots, d∈D r: index of bridging trips for a bus, r=1,2,...R f: index of pickups at a station, f=1,2,...FSets I: set of disrupted stations, I=I1∪I2 J: set of turnover stations, J=J1∪J2 N: set of all stations, Ng=Ig∪Jg, N=N1∪N2 D: set of bus depots M: set of busesParameters R: the maximum allowed number of bridging trips for each bus F: the maximum allowed number of pickups at each station V d: number of buses available in depot d C: bus capacity T: time when the metro line resumes operation t i j: bus travel time between stationi and stationj t d i: bus travel time between depotdand stationi λ i ( t ): number of arrival passengers at timet at stationi a i m r: departure time of ther th bridging trip of busm at stationi b i f: departure time of thef th bus visiting stationi W i f: number of passengers waiting for thefth bus at stationi L i f: number of passengers left behind by thefth bus at stationi P: penalty coefficients for stranded passengersDecision Variables x i j m r: binary variable that equals 1 if ther th bridging trip of busm traverses arc (i,j), else 0 y d i m: binary variable that equals 1 if busm is dispatched to stationifrom bus depotd, else 0 p i j m r: number of passengers form stationi to turnover stationj by ther th bridging trip of busm


## 2.1. Problem Description

Consider a metro disruption that several stations suspend service between two stations with track crossovers (see Figure1.) Trains operate in short turning mode on residual metro lines. Buses need to be dispatched for emergency evacuation from bus depots and to evacuate the passengers to the turnover stations.Figure 1
Disruption scenario.We suppose that the bus bridging stops are near metro station exits. Bus bridging stops are set on both sides of the roads corresponding to opposite directions of the same metro station. Assume that metro operators can predict disruption recovery time precisely and start bus bridging service immediately after disruption occurs. The metro line returns to normal operation at timeT. Let [0,T] denote the disruption duration period. When the metro disruption resumes, passengers return to the metro system and will be rapidly evacuated. Therefore, we limit the effective time of bus bridging to [0,T]. In order to represent dynamic passenger flows, we divide [0,T] equally into several time intervals of one minute. We hereafter refer to time interval as time and usetto index it. The passenger demand at stationi at timetis denoted as λi(t). Let M be the set of buses available. Let D be the set of depots. Let N be the set of stations, including the set of disrupted stations I and the set of turnover stations J. We desire to dispatch buses in the following manner: bus m∈M is dispatched from depot d∈D, visits one disrupted station i∈I and transports passengers with the capacity constraintC to turnover station j∈J, come back to visit another disrupted station k∈I, then go to turnover station l∈J and so on, until the disruption returns to the normal operation. We refer the station that a bus is dispatched to its designated station [1]. We assume that a significant number of passengers choose to transfer to buses; whenever a bus visits a station, it gets fully loaded immediately. The journey that a bus transports passengers from an affected station to the turnover station is defined as a bridging trip of the bus. Multiple bridging trips constitute the bridging route of a bus. Note that the origin of the first bridging trip should be its designated station. aimr denotes the departure time of busm in ther th bridging trip at stationi. Different buses may visit a station one after the other, and let bif indicate the departure time of thef th pickup at stationi. Figure 2(a) illustrates an example of a metro disruption with four stations and three buses in one depot. The number in the circle indicates stations while the number beside the link denotes the travel time between stations or depots. Figure 2(b) presents bridging route for each bus. Solid arrows indicate bridging trips loading passengers and dotted arrows denote deadheading trips. For example, bus 3 visits station 3, station 2 and station 4 sequentially. For station 2, the first pickup is at the fourth minute by bus 1 and the second pickup is at 12th minute by bus 3, i.e. b21=4, b22=12.Figure 2
Illustration of bus bridging trips and pickups.
(a) (b)As for stations, we focus on waiting time. As shown in Figure3, the horizontal axis represents time, and the yellow curve and blue curve indicate the cumulative arrival curve and the cumulative departure curve of passengers, respectively. Assuming that passenger arrival rate is constant during the time period [0,H], p0 indicates the number of passengers who quit metro and transfer to buses at the beginning of the disruption. Note that we only consider passengers who arrive withinH minutes after the disruption. p indicates the sum of arrival passengers during the disruption. The area bounded by the two curves and line y=T represents total waiting time for passengers. In Section 3, we propose a variant model of Vehicle Routing Problem (VRP). One of the objectives of the proposed model is to minimize total waiting time. The decision is to plan the bus bridging routing, that is, for each bus to determine which bridging trips are selected and what is the optimal order of them. We use binary variables xijmr to determine whether busmtransport passengers from stationi to stationj in ther th bridging trip and binary variables ydim to determine whether busm is dispatched from depotd to stationi.Figure 3
Total waiting time.To illustrate the modelling framework, consider a metro disruption case with five disrupted stations. Assuming that there are totally five buses available, a time space diagram of each bus is as shown in Figure4(a). Buses are shown by different colors. We seek to obtain the optimal bus bridging solution with the minimum total waiting time. Figure 4(b) shows the optimized bus bridging solution. As can be seen, the optimized bus trajectories are more dispersed. Table 1 presents their specific bridging trips. The first number in the bracket represents the origin of the bridging trip and the second number represents the destination. For example, bus 1 as red trajectory shows is dispatched from depot 1 to station 2 and travels through bridging trips (2,1) → (2,1) → (3,5) → (4,1) sequentially. Figure 5 shows the cumulative arrival curves and cumulative departure curves of station 3 in the upward direction before and after optimization. As can be seen from Figure 5(a), before optimization there are three pickups at station 3, at 22th, 47th, and 50th minute, respectively. The total waiting time is 896 hours, with 762 passengers stranded. In contrast, in the optimized solution, the total waiting time is 123 hours, with 288 passengers stranded. As shown in Figure 5(b), the cumulative departure curve is much closer to the cumulative arrival curve than the initial plan.Table 1
Optimization results in illustrative example.
Bus index Depot Bridging process 1 D1 (2,1) → (2,1) → (3,5) → (4,1) 2 D2 (3,5) → (4,5) → (5,1) 3 D2 (3,1) → (2,5) → (4,5) → (5,1) 4 D3 (4,1) → (2,1) → (2,5) → (5,1) 5 D3 (1,5) → (5,1) → (1,5)Figure 4
Comparing time space diagram of buses before and after optimization in illustrative example.
(a) (b)Figure 5
Comparing cumulative arrival departure curves of station 3 in upward direction before and after optimization in illustrative example.
(a) (b)


## 2.2. Assumptions

To simplify the problem, the following assumptions are made.(1)
Neglect delays due to traffic congestions and bus travel times between stations are constant.(2)
The parking capacity of the bus stop is large enough and the queue delay caused by the simultaneous arrival of multiple buses is not considered.(3)
Buses immediately depart from a station after arriving there and boarding time for passengers at each station is equal.


## 2.3. Notations

For illustrative purpose, main notations for the model are listed as follows.Indices i , k: index of disruption stations, i,k∈I j , l: index of turnover stations, j,l∈J g: index of directions, g=1 represents upward direction, g=2 represents downward direction m: index of buses, m∈M d: index of bus depots, d∈D r: index of bridging trips for a bus, r=1,2,...R f: index of pickups at a station, f=1,2,...FSets I: set of disrupted stations, I=I1∪I2 J: set of turnover stations, J=J1∪J2 N: set of all stations, Ng=Ig∪Jg, N=N1∪N2 D: set of bus depots M: set of busesParameters R: the maximum allowed number of bridging trips for each bus F: the maximum allowed number of pickups at each station V d: number of buses available in depot d C: bus capacity T: time when the metro line resumes operation t i j: bus travel time between stationi and stationj t d i: bus travel time between depotdand stationi λ i ( t ): number of arrival passengers at timet at stationi a i m r: departure time of ther th bridging trip of busm at stationi b i f: departure time of thef th bus visiting stationi W i f: number of passengers waiting for thefth bus at stationi L i f: number of passengers left behind by thefth bus at stationi P: penalty coefficients for stranded passengersDecision Variables x i j m r: binary variable that equals 1 if ther th bridging trip of busm traverses arc (i,j), else 0 y d i m: binary variable that equals 1 if busm is dispatched to stationifrom bus depotd, else 0 p i j m r: number of passengers form stationi to turnover stationj by ther th bridging trip of busm


## 3. Model Formulations

### 3.1. Objective Functions

A multi-objective model is formulated to design the bus dispatching plans. The first objective is to minimize total waiting time of passengers and the number of stranded passengers. Total waiting time represents interests of affected passengers, while from the respective of transit agencies, evacuating as many passengers as possible is critical. The number of stranded passengers is negative related to evacuation efficiency. The fewer stranded passengers indicate the higher evacuation efficiency. For model simplicity, set a virtual bus with zero capacity at timeT, that is biF=T. Thus the total stranded passengers at a station during the disruption can be represented by the number of passengers who failed to board on theFth bus denoted by LiF. We convert LiF into time by multiplying it by a penalty coefficientP. Added to the waiting time, the number of stranded passengers constitutes the first goal given by(1)minZ1=∑i∈N∑f=2F∑t∈bif-1,bifλitbif-t2+∑i∈N∑f=2FLif-1bif-bif-1+∑i∈NP·LiFwhere the first two terms represent total waiting time. The first term calculates the waiting time of all passengers arriving during the disruption. The second term represents the waiting time of the passengers who were left behind by overcrowded buses. The number of passengers who failed to board thefth bus at stationi is given by(2)Lif=max⁡Wif-C,0whereC represents bus capacity, and Wif denotes the number of passengers who wait for thefth bus at stationi. Wif is given by(3)Wif=Lif-1+∑t∈bif-1,bifλitEquation (3) involves two terms: the first one is the number of passengers who were left behind by thef-1 th bus at stationi and the second one is the number passengers who arrived at stationiduring the period between the departure time of two consecutive buses, i.e. [bif-1,bif).Buses are mainly sourced from spare vehicles at bus depots or borrowed from the regular bus operating lines. Bus resources are tight during peak hours. In order to minimize the impact on the operation of regular bus lines, the second objective is to minimize the number of buses dispatched in bus bridging services given by(4)minZ2=∑m∈M∑d∈D∑i∈Nydim


### 3.2. Model Formulations

The objective functions and constraints are as follows.Equation (1)(4)(5)s.t.∑i∈N∑j∈Jxijmr≤1∀m∈M,r=1,2,…,R(6)∑i∈N1∑j∈J2xijmr=∑i∈N2∑j∈J1xijmr=0∀m∈M,r=1,2,…,R(7)∑j∈N∑i∈Ixjimr=0∀m∈M,r=1,2,…,R(8)∑i∈Ixijmr-1-∑l∈Jxjlmr≥0∀j∈J,∀m∈M,r=2,…,R(9)∑d∈D∑i∈Iydim≤1∀m∈M(10)∑d∈Dydim=∑j∈Jxijm1∀i∈N,∀m∈M(11)∑m∈M∑i∈Iydim≤Vd∀d∈D(12)pijmr≤Cxijmr∀i,j∈N,∀m∈M,r=1,2,…,R(13)aim1=∑d∈D∑i∈Ntdiydim∀i∈N,∀m∈M(14)aimr=akmr-1+∑k∈N∑j∈Jtkjxkjmr-1+tji∑k∈Nxkjmr-1+∑l∈Jxilmr-1∀i∈N,m∈M,r=2,…,R(15)∑i∈N∑j∈Nxijmr≤∑i∈N∑j∈Nxijmr-1∀m∈M,r=2,…,R(16)aimr-T≤M1-∑j∈Nxijmr∀m∈M,i∈N,r=1,2,…,R(17)T-aimr≤M∑j∈Nxijmr∀m∈M,i∈N,r=1,2,…,R(18)⋃m∈Maimrr=1R=biff=1F∀i∈N(19)xijmr∈0,1,ydim∈0,1,pijmr≥0∀i,j∈N,d∈D,m∈M,r=1,2,…,REquation (1) is the first objective to minimize total waiting time of passengers. Equation (4) is the second objective to minimize total dispatched buses. Constraints (5)-(8) ensure the construction of valid bridging routes. Constraint (5) makes sure that one bus can link two stations at most per bridging trip. Equation (6) prevents that a bus links two stations in different directions per bridging trip. The subscripts indicate directions; 1 represents upward direction and 2 represents downward direction. For example, I1 corresponds to set of bus stops in the downward direction. Equation (7) prevents that buses transport passengers from the turnover stations to disrupted stations. Constraint (8) indicates that the origin of the current bridging trip does not have to be the same as the destination of the previous one. Constraints (9)-(11) are dispatching constraints. Constraint (9) ensures that any bus can only be dispatched to one disrupted station. Constraint (10) indicates the relationship between variablesxandy, and ensures that for any bus the origin of the first bridging trip should be its designated station. Constraint (11) indicates that the number of buses dispatched from any depot cannot exceed its fleet size. Constraint (12) prevents any bus from picking up passengers from a station unless it is visiting the station and enforces the bus capacity restriction. Equations (13)-(14) depict the calculation of the departure time. Equation (13) indicates that for each bus the departure time of its first bridging trip is equal to the travel time between its depot and its designated station. Equation (14) indicates the relationship between the departure time of ther-1th bridging trip and therth bridging trip. The second term in the right side denotes the travel time of ther-1 bridging trip. The third term denotes the deadheading time between two consecutive bridging trips. Constraint (15) prevents that a bus restarts after it quits bus bridging. Constraints (16)-(17) ensure that the departure time of each bridging trip cannot exceed the recovery time.M is a large number. Equation (18) indicates the relationship of departure time for buses and pickup time for stations. For any station, the sequence of pickup time is the union of departure time of all buses visiting the station. Constraint (19) specifies binary and nonnegative integer types of decision variables.


## 3.1. Objective Functions

A multi-objective model is formulated to design the bus dispatching plans. The first objective is to minimize total waiting time of passengers and the number of stranded passengers. Total waiting time represents interests of affected passengers, while from the respective of transit agencies, evacuating as many passengers as possible is critical. The number of stranded passengers is negative related to evacuation efficiency. The fewer stranded passengers indicate the higher evacuation efficiency. For model simplicity, set a virtual bus with zero capacity at timeT, that is biF=T. Thus the total stranded passengers at a station during the disruption can be represented by the number of passengers who failed to board on theFth bus denoted by LiF. We convert LiF into time by multiplying it by a penalty coefficientP. Added to the waiting time, the number of stranded passengers constitutes the first goal given by(1)minZ1=∑i∈N∑f=2F∑t∈bif-1,bifλitbif-t2+∑i∈N∑f=2FLif-1bif-bif-1+∑i∈NP·LiFwhere the first two terms represent total waiting time. The first term calculates the waiting time of all passengers arriving during the disruption. The second term represents the waiting time of the passengers who were left behind by overcrowded buses. The number of passengers who failed to board thefth bus at stationi is given by(2)Lif=max⁡Wif-C,0whereC represents bus capacity, and Wif denotes the number of passengers who wait for thefth bus at stationi. Wif is given by(3)Wif=Lif-1+∑t∈bif-1,bifλitEquation (3) involves two terms: the first one is the number of passengers who were left behind by thef-1 th bus at stationi and the second one is the number passengers who arrived at stationiduring the period between the departure time of two consecutive buses, i.e. [bif-1,bif).Buses are mainly sourced from spare vehicles at bus depots or borrowed from the regular bus operating lines. Bus resources are tight during peak hours. In order to minimize the impact on the operation of regular bus lines, the second objective is to minimize the number of buses dispatched in bus bridging services given by(4)minZ2=∑m∈M∑d∈D∑i∈Nydim


## 3.2. Model Formulations

The objective functions and constraints are as follows.Equation (1)(4)(5)s.t.∑i∈N∑j∈Jxijmr≤1∀m∈M,r=1,2,…,R(6)∑i∈N1∑j∈J2xijmr=∑i∈N2∑j∈J1xijmr=0∀m∈M,r=1,2,…,R(7)∑j∈N∑i∈Ixjimr=0∀m∈M,r=1,2,…,R(8)∑i∈Ixijmr-1-∑l∈Jxjlmr≥0∀j∈J,∀m∈M,r=2,…,R(9)∑d∈D∑i∈Iydim≤1∀m∈M(10)∑d∈Dydim=∑j∈Jxijm1∀i∈N,∀m∈M(11)∑m∈M∑i∈Iydim≤Vd∀d∈D(12)pijmr≤Cxijmr∀i,j∈N,∀m∈M,r=1,2,…,R(13)aim1=∑d∈D∑i∈Ntdiydim∀i∈N,∀m∈M(14)aimr=akmr-1+∑k∈N∑j∈Jtkjxkjmr-1+tji∑k∈Nxkjmr-1+∑l∈Jxilmr-1∀i∈N,m∈M,r=2,…,R(15)∑i∈N∑j∈Nxijmr≤∑i∈N∑j∈Nxijmr-1∀m∈M,r=2,…,R(16)aimr-T≤M1-∑j∈Nxijmr∀m∈M,i∈N,r=1,2,…,R(17)T-aimr≤M∑j∈Nxijmr∀m∈M,i∈N,r=1,2,…,R(18)⋃m∈Maimrr=1R=biff=1F∀i∈N(19)xijmr∈0,1,ydim∈0,1,pijmr≥0∀i,j∈N,d∈D,m∈M,r=1,2,…,REquation (1) is the first objective to minimize total waiting time of passengers. Equation (4) is the second objective to minimize total dispatched buses. Constraints (5)-(8) ensure the construction of valid bridging routes. Constraint (5) makes sure that one bus can link two stations at most per bridging trip. Equation (6) prevents that a bus links two stations in different directions per bridging trip. The subscripts indicate directions; 1 represents upward direction and 2 represents downward direction. For example, I1 corresponds to set of bus stops in the downward direction. Equation (7) prevents that buses transport passengers from the turnover stations to disrupted stations. Constraint (8) indicates that the origin of the current bridging trip does not have to be the same as the destination of the previous one. Constraints (9)-(11) are dispatching constraints. Constraint (9) ensures that any bus can only be dispatched to one disrupted station. Constraint (10) indicates the relationship between variablesxandy, and ensures that for any bus the origin of the first bridging trip should be its designated station. Constraint (11) indicates that the number of buses dispatched from any depot cannot exceed its fleet size. Constraint (12) prevents any bus from picking up passengers from a station unless it is visiting the station and enforces the bus capacity restriction. Equations (13)-(14) depict the calculation of the departure time. Equation (13) indicates that for each bus the departure time of its first bridging trip is equal to the travel time between its depot and its designated station. Equation (14) indicates the relationship between the departure time of ther-1th bridging trip and therth bridging trip. The second term in the right side denotes the travel time of ther-1 bridging trip. The third term denotes the deadheading time between two consecutive bridging trips. Constraint (15) prevents that a bus restarts after it quits bus bridging. Constraints (16)-(17) ensure that the departure time of each bridging trip cannot exceed the recovery time.M is a large number. Equation (18) indicates the relationship of departure time for buses and pickup time for stations. For any station, the sequence of pickup time is the union of departure time of all buses visiting the station. Constraint (19) specifies binary and nonnegative integer types of decision variables.


## 4. Solution Algorithm

The proposed model is a multi-objective optimization model based on VRP, belonging to NP-hard problems. It is difficult to obtain an optimal solution in a limited time using an accurate algorithm. A usual approach to solve multi-objective optimization model is to assign a weight to each objective and transform it into a single-objective one. However, different transit agencies often have dissimilar preference in the weights. Hence, it is more practicable to offer the Pareto optimal solution to decision makers. Multi-objective evolutionary algorithms optimize multiple objectives simultaneously and they are widely used in the transportation field. Multi-objective evolutionary algorithms include several such as Non-dominated Sorting Genetic Algorithm (NSGA-II) [24], Multi-Objective Simulated Annealing (MOSA) [25], Multi-Objective Tabu Search Algorithm (MOTS) [26], and Multi-Objective Particle Swarm Optimization (MOPSO) [27]. However, NSGA-II performs better in terms of finding a diverse set of solutions and in converging to near the true pareto-optimal set compared with others. In addition, it is convenient to code for the bus bridging problem [28]. Therefore, we use NSGA-II algorithm to find the Pareto solution set of the problem.


### 4.1. Code Representation

Filter out all the bridging trips that satisfy the constraints (5)-(8) and number these bridging paths sequentially. The chromosome length is set as the product of fleet size and the maximum allowed number of bridging trips of each bus (R). Each code on the chromosome indicates the trip number chosen as ther th bridging trip of the bus. Consider the illustrated example with five stations in Section 2.1. For upward direction, there are four alternative bridging trips: (1,5), (2,5), (3,5) and (4,5). Similarly there are four counterparts in the downward direction. Number these bridging trips from one to eight. SetR= 5, as Figure 6 shows, the codes numbered 3, 4, and 8 correspond to the bridging trip (3,5), (4,5), and (5,1), respectively. The first zero code and the subsequent code belonging to the bus are treated as empty codes. The total number of bus bridging trips is equal to the sum of occurrences of non-zero codes. As shown in Figure 6, Bus 2 has a total of three bridging trips.Figure 6
Coding of bridging path.


### 4.2. Fitness Function

Use the objective function of the model as the fitness function, i.e., the minimum total waiting time and the minimum number of dispatched buses.


### 4.3. Algorithm Process

The concrete steps of the NSGA-II algorithm in the proposed model are as follows:Step 1 (initiation).
Lets=0 and set population size Z, Cross probability pc, Mutation probability pm. The maximum iterations S. Randomly generate initial parent population P0. Calculate the minimum total waiting time and the minimum dispatching buses for all individuals in P0.Step 2.
Perform a fast non-dominated sort operation forPs to obtain non-dominated sort values for all individuals.Step 3.
Perform selection, crossover, and mutation operations forPs to generate individuals of descendant population Qs. Calculate the minimum total waiting time and the minimum using buses for all individuals in Qs.Step 4.
CombinePs and Qs into new populations called Rs. Perform a fast non-dominated sort operation for Rs to obtain non-dominated sort values for all individuals.Step 5 (elite retention operation).
LetPs+1=⌀,r=1. If the sum of the number of individuals with the non-dominated dominance sorting value of r is not larger than Z, put all the individuals in Rs with the non-dominated dominance sort value of r into Ps+1. Otherwise, calculate the crowding distance of individuals in the non-dominated sort value of r. Put those individuals into Ps+1 in order of their crowding distances from the largest to the smallest, until the number of individuals in the group Ps+1 is Z.Step 6.
Perform a fast non-dominated sort operation forPs+1 to obtain non-dominated sort values for all individuals.Step 7 (update Pareto solution set).
All individuals with a non-dominant ranking value of 1 inPs+1 constitute the Pareto solution set.Step 8 (determine whether the termination condition is met).
Ifs=S, then output the Pareto solution set, terminate the algorithm, otherwise, let s=s+1 and go to Step 3.


## 4.1. Code Representation

Filter out all the bridging trips that satisfy the constraints (5)-(8) and number these bridging paths sequentially. The chromosome length is set as the product of fleet size and the maximum allowed number of bridging trips of each bus (R). Each code on the chromosome indicates the trip number chosen as ther th bridging trip of the bus. Consider the illustrated example with five stations in Section 2.1. For upward direction, there are four alternative bridging trips: (1,5), (2,5), (3,5) and (4,5). Similarly there are four counterparts in the downward direction. Number these bridging trips from one to eight. SetR= 5, as Figure 6 shows, the codes numbered 3, 4, and 8 correspond to the bridging trip (3,5), (4,5), and (5,1), respectively. The first zero code and the subsequent code belonging to the bus are treated as empty codes. The total number of bus bridging trips is equal to the sum of occurrences of non-zero codes. As shown in Figure 6, Bus 2 has a total of three bridging trips.Figure 6
Coding of bridging path.


## 4.2. Fitness Function

Use the objective function of the model as the fitness function, i.e., the minimum total waiting time and the minimum number of dispatched buses.


## 4.3. Algorithm Process

The concrete steps of the NSGA-II algorithm in the proposed model are as follows:Step 1 (initiation).
Lets=0 and set population size Z, Cross probability pc, Mutation probability pm. The maximum iterations S. Randomly generate initial parent population P0. Calculate the minimum total waiting time and the minimum dispatching buses for all individuals in P0.Step 2.
Perform a fast non-dominated sort operation forPs to obtain non-dominated sort values for all individuals.Step 3.
Perform selection, crossover, and mutation operations forPs to generate individuals of descendant population Qs. Calculate the minimum total waiting time and the minimum using buses for all individuals in Qs.Step 4.
CombinePs and Qs into new populations called Rs. Perform a fast non-dominated sort operation for Rs to obtain non-dominated sort values for all individuals.Step 5 (elite retention operation).
LetPs+1=⌀,r=1. If the sum of the number of individuals with the non-dominated dominance sorting value of r is not larger than Z, put all the individuals in Rs with the non-dominated dominance sort value of r into Ps+1. Otherwise, calculate the crowding distance of individuals in the non-dominated sort value of r. Put those individuals into Ps+1 in order of their crowding distances from the largest to the smallest, until the number of individuals in the group Ps+1 is Z.Step 6.
Perform a fast non-dominated sort operation forPs+1 to obtain non-dominated sort values for all individuals.Step 7 (update Pareto solution set).
All individuals with a non-dominant ranking value of 1 inPs+1 constitute the Pareto solution set.Step 8 (determine whether the termination condition is met).
Ifs=S, then output the Pareto solution set, terminate the algorithm, otherwise, let s=s+1 and go to Step 3.


## 5. Numerical Experiment

### 5.1. Case Setup

The numerical experiment considers an emergent disruption on a metro line (No.9) in Shanghai, China (see Figure7). Five stations suspend services form 9:00 am to 10:30 am on a weekday. Station 1 and station 7 are equipped with track crossovers. Totally 60 available spare buses are reserved in seven nearby depots.Figure 7
Disrupted scenario of the metro line in the case study.Table2 presents passenger flow demands at each station. Continuous passenger flows until 10:00 am are taken into account. It should be noted that the destinations of bus bridging are set as either upward or downward turnover stations. Passenger demands between disrupted stations are not considered. The assumption is reasonable since we conduct the case study on a commuting line where the majority of passengers transfer at turnover stations. Table 3 shows the amount of available buses at depots and their travel time between depots and stations. Table 4 presents bus travel time between stations. Bus capacity is 80 passengers. ParametersR andF in the proposed model are set as 10 and 90, respectively.Table 2
Passengers flow demands in the numerical case.
stations upward downward Initial strandedpassengers Arrival rates(units: min−1) Initial strandedpassengers Arrival rates(units: min−1) S1 300 19 — — S2 200 9 100 10 S3 140 8 150 11 S4 120 8 130 8 S5 170 7 210 7 S6 200 11 150 7 S7 — — 400 19Table 3
Specific data of buses at depots and travel times between depots and stations.
Depots Number of buses Stations (units: min) S1 S2 S3 S4 S5 S6 S7 D1 8 11 7 6 10 13 16 27 D2 5 24 20 15 12 11 11 15 D3 7 25 20 16 12 8 6 10 D4 12 12 9 4 6 8 13 22 D5 9 16 13 11 11 14 17 19 D6 10 21 17 13 10 7 9 13 D7 9 19 15 10 6 6 9 12Table 4
Travel time between stations in the numerical case (units: min).
Stations S1 S2 S3 S4 S5 S6 S7 S1 — 6 15 23 28 34 38 S2 6 — 14 21 22 27 25 S3 15 11 — 9 13 18 22 S4 25 19 8 — 9 10 14 S5 28 20 10 8 — 8 12 S6 36 25 15 9 7 — 7 S7 38 29 19 11 9 7 —ParametersZ,S,pc,pm in solution algorithm are set at 500, 100, 0.9, and 0.4, respectively. All experiments are performed on a PC with a 1.6 GHz Intel Core i5 CPU and 8.0 GB memory, and the algorithm is in MATLAB. The computational time for solving the proposed model is 7min.


### 5.2. Optimal Results and Analysis

A total of 14 Pareto approximate optimal solutions were obtained. Figure8 presents the first objective function value and the number of dispatched buses. For example, in Pareto solution 1, all 60 buses are dispatched to handle the emergency. Table 5 presents the total waiting time and the number of stranded passengers. The standard bus bridging plan described in Section 1 is set for comparison. In the standard plan, the buses are dispatched firstly to the nearby turnover stations and then shuttle on routes parallel with the disrupted lines. Buses load passengers at each station along the routesTable 5
Comparing of optimization results before and after optimization.
Waiting time(units: hours) Number of stranded passengers Number of dispatchedbuses Optimal plan 1504 0 60 Standard plan 4724 1737 60Figure 8
Pareto solutions of case study.As can be seen, in the standard plan, there are as many as 1737 passengers stranded at the end of disruption and the total waiting time is much higher than that of the optimal plan.Figure9 shows the distribution of total waiting time of each station in the upward direction before and after optimization. As can be seen, the total waiting time in the optimal plan was much lower than that in the standard plan especially for downstream stations. For example, at station 5 and station 6, the total waiting time in the optimal plan decreased by 82.6% and 82.1%, respectively. In the standard plan a large number of passengers got aboard at upstream stations, while the passengers at downstream stations were unlikely to get on buses due to insufficient remaining capacity. Similarly, in Figure 10, for example, passengers at station 4 were unlikely to get on board until 40 minutes after the disruption and no passengers at station 6 could board buses. Our bridging strategy achieved a more equitable condition for passengers among all stations.Figure 9
Comparing of waiting time at each station in upward direction before and after optimization.Figure 10
Cumulative arrival and boarding process at stations in upward direction.Figure10 describes the accumulative arrival/boarding curves of passengers at each station in the upward direction to station 7. All passengers board buses when the boarding curve (red/ blue) coincides with arrival curve(grey). As can be seen from Figure 10, the red curve is closer to the grey one than blue one which indicates the total waiting time (enclosed area by the two curves) in the proposed plan is shorter than that in the standard plan. Total evacuation time when all passengers get on board of the optimal plan is shorter than that of the standard plan for any station except for station 2. For example, in station 5, total evacuation time was 72 minutes in the optimal plan, while it was not until the last minute before the operation resumed that all passengers got on board in the standard plan.In the standard plan, multiple vehicles were firstly dispatched to turnover stations, so passengers could be quickly evacuated in the early stage of the evacuation. However, due to quite long turnaround time of buses, few buses arrived again in a long time period (about 40 minutes) until buses in the opposite direction turned over, resulting in long waiting time. In contrast, in the optimal plan, with the node-to-node transportation mode buses were able to operate flexibly on different bridging trips. These trips covered different travel times, resulting buses turned over at various time. Therefore, the pickup time distribution of stations was more discrete, which more accorded with linear passenger arrival.


### 5.3. Sensitivity Analysis

We further investigate the impact of recovery time and fleet size on results. Figure11 presents total waiting time and the number of the stranded passengers given varying bus fleet sizes under certain recovery time. As the fleet size grew, the total waiting time and the number of stranded passengers both lessoned with smaller decreasing amplitude which is in accordance with empirical laws. For example, when recovery time was 90 minutes (see Figure 11(c)), total waiting time decreased by 30.9% when the fleet size increased from 30 to 40, while it only decreased by 2.5% when the fleet size increased from 80 to 90. According to Figure 11(c), if the goal is achieving a complete evacuation before the recovery time, the lowest level of availability for buses should be maintained at 60.Figure 11
Waiting time and stranded passengers for different recovery time.
(a)
Recovery time is 30 minutes (b)
Recovery time is 60 minutes (c)
Recovery time is 90 minutes (d)
Recovery time is 120 minutesFigure12 shows the variation of average waiting time with variable fleet size under different recovery time. The horizontal axis indicates fleet size. Four curves represent the variation of average waiting time under different recovery time. It is shown that as bus fleet size increases the average waiting time decreases, but the decrease rate is smaller with larger fleet size. The variation range gets larger under the longer recovery time. For example, when the recovery time is 30 minutes the average waiting time decreases from 11 mins to 5 mins, while the recovery time is 2 hours it deceases from 34 mins to 5 mins. Here are some suggestions for transit agencies: when the recovery time is quite long, e.g., 90 minutes, as many buses as possible should be dispatched, while when it is shorter, e.g., 30 minutes, the fleet size can be smaller.Figure 12
Performance of waiting time with varying bus fleet size.Since passenger demand increases until timeH (one hour in the case study) and we only consider the period before recovery timeT; when T is above or belowH, the passenger demand is different. For example, we can calculate from Table 2: whenT is 90 minutes the passenger demand is 9710 while whenT is 30 minutes the demand is 5990. It can be seen that under different recovery time the absolute quantity of stranded passengers cannot reflect the actual evacuation efficiency. Therefore, we look into an indicator:evacuation efficiency factor. Define evacuation efficiency factor as the proportion of the number of passengers who have got on board before recovery time to total passenger flows. Evacuation efficiency factor is given by:(20)η=1-ΦΛ×100%In Equation (20), η indicates evacuation efficiency factor, Φ=∑i∈NLiF represents the total number of stranded passengers, and Λ=∑i∈N∑t∈[0,T]λi(t) denotes the total passenger flows.Figure13 presents the variation of evacuation efficiency factor with different fleet size. The horizontal axis represents fleet size and four curves represent evacuation efficiency factors under different recovery time. As the fleet size increased, η also increased. For example, when recovery time was 90 minutes and the fleet size was 30 vehicles, the corresponding η was only 77.4%, while when the fleet size increased to 60, η reached 100%. In addition, when the recovery time was less than 60 minutes, the evacuation efficiency factor was significantly lower than that of longer recovery time at the same fleet size. For example, when the recovery time was 30 minutes, even if the fleet size increased to 100, it was still unlikely to evacuate all passengers. When there were 60 available buses, η reached nearly 90%. It was unnecessary for transit agencies to dispatch numerous buses.Figure 13
Performance of evacuation efficiency factor with varying bus fleet size.


## 5.1. Case Setup

The numerical experiment considers an emergent disruption on a metro line (No.9) in Shanghai, China (see Figure7). Five stations suspend services form 9:00 am to 10:30 am on a weekday. Station 1 and station 7 are equipped with track crossovers. Totally 60 available spare buses are reserved in seven nearby depots.Figure 7
Disrupted scenario of the metro line in the case study.Table2 presents passenger flow demands at each station. Continuous passenger flows until 10:00 am are taken into account. It should be noted that the destinations of bus bridging are set as either upward or downward turnover stations. Passenger demands between disrupted stations are not considered. The assumption is reasonable since we conduct the case study on a commuting line where the majority of passengers transfer at turnover stations. Table 3 shows the amount of available buses at depots and their travel time between depots and stations. Table 4 presents bus travel time between stations. Bus capacity is 80 passengers. ParametersR andF in the proposed model are set as 10 and 90, respectively.Table 2
Passengers flow demands in the numerical case.
stations upward downward Initial strandedpassengers Arrival rates(units: min−1) Initial strandedpassengers Arrival rates(units: min−1) S1 300 19 — — S2 200 9 100 10 S3 140 8 150 11 S4 120 8 130 8 S5 170 7 210 7 S6 200 11 150 7 S7 — — 400 19Table 3
Specific data of buses at depots and travel times between depots and stations.
Depots Number of buses Stations (units: min) S1 S2 S3 S4 S5 S6 S7 D1 8 11 7 6 10 13 16 27 D2 5 24 20 15 12 11 11 15 D3 7 25 20 16 12 8 6 10 D4 12 12 9 4 6 8 13 22 D5 9 16 13 11 11 14 17 19 D6 10 21 17 13 10 7 9 13 D7 9 19 15 10 6 6 9 12Table 4
Travel time between stations in the numerical case (units: min).
Stations S1 S2 S3 S4 S5 S6 S7 S1 — 6 15 23 28 34 38 S2 6 — 14 21 22 27 25 S3 15 11 — 9 13 18 22 S4 25 19 8 — 9 10 14 S5 28 20 10 8 — 8 12 S6 36 25 15 9 7 — 7 S7 38 29 19 11 9 7 —ParametersZ,S,pc,pm in solution algorithm are set at 500, 100, 0.9, and 0.4, respectively. All experiments are performed on a PC with a 1.6 GHz Intel Core i5 CPU and 8.0 GB memory, and the algorithm is in MATLAB. The computational time for solving the proposed model is 7min.


## 5.2. Optimal Results and Analysis

A total of 14 Pareto approximate optimal solutions were obtained. Figure8 presents the first objective function value and the number of dispatched buses. For example, in Pareto solution 1, all 60 buses are dispatched to handle the emergency. Table 5 presents the total waiting time and the number of stranded passengers. The standard bus bridging plan described in Section 1 is set for comparison. In the standard plan, the buses are dispatched firstly to the nearby turnover stations and then shuttle on routes parallel with the disrupted lines. Buses load passengers at each station along the routesTable 5
Comparing of optimization results before and after optimization.
Waiting time(units: hours) Number of stranded passengers Number of dispatchedbuses Optimal plan 1504 0 60 Standard plan 4724 1737 60Figure 8
Pareto solutions of case study.As can be seen, in the standard plan, there are as many as 1737 passengers stranded at the end of disruption and the total waiting time is much higher than that of the optimal plan.Figure9 shows the distribution of total waiting time of each station in the upward direction before and after optimization. As can be seen, the total waiting time in the optimal plan was much lower than that in the standard plan especially for downstream stations. For example, at station 5 and station 6, the total waiting time in the optimal plan decreased by 82.6% and 82.1%, respectively. In the standard plan a large number of passengers got aboard at upstream stations, while the passengers at downstream stations were unlikely to get on buses due to insufficient remaining capacity. Similarly, in Figure 10, for example, passengers at station 4 were unlikely to get on board until 40 minutes after the disruption and no passengers at station 6 could board buses. Our bridging strategy achieved a more equitable condition for passengers among all stations.Figure 9
Comparing of waiting time at each station in upward direction before and after optimization.Figure 10
Cumulative arrival and boarding process at stations in upward direction.Figure10 describes the accumulative arrival/boarding curves of passengers at each station in the upward direction to station 7. All passengers board buses when the boarding curve (red/ blue) coincides with arrival curve(grey). As can be seen from Figure 10, the red curve is closer to the grey one than blue one which indicates the total waiting time (enclosed area by the two curves) in the proposed plan is shorter than that in the standard plan. Total evacuation time when all passengers get on board of the optimal plan is shorter than that of the standard plan for any station except for station 2. For example, in station 5, total evacuation time was 72 minutes in the optimal plan, while it was not until the last minute before the operation resumed that all passengers got on board in the standard plan.In the standard plan, multiple vehicles were firstly dispatched to turnover stations, so passengers could be quickly evacuated in the early stage of the evacuation. However, due to quite long turnaround time of buses, few buses arrived again in a long time period (about 40 minutes) until buses in the opposite direction turned over, resulting in long waiting time. In contrast, in the optimal plan, with the node-to-node transportation mode buses were able to operate flexibly on different bridging trips. These trips covered different travel times, resulting buses turned over at various time. Therefore, the pickup time distribution of stations was more discrete, which more accorded with linear passenger arrival.


## 5.3. Sensitivity Analysis

We further investigate the impact of recovery time and fleet size on results. Figure11 presents total waiting time and the number of the stranded passengers given varying bus fleet sizes under certain recovery time. As the fleet size grew, the total waiting time and the number of stranded passengers both lessoned with smaller decreasing amplitude which is in accordance with empirical laws. For example, when recovery time was 90 minutes (see Figure 11(c)), total waiting time decreased by 30.9% when the fleet size increased from 30 to 40, while it only decreased by 2.5% when the fleet size increased from 80 to 90. According to Figure 11(c), if the goal is achieving a complete evacuation before the recovery time, the lowest level of availability for buses should be maintained at 60.Figure 11
Waiting time and stranded passengers for different recovery time.
(a)
Recovery time is 30 minutes (b)
Recovery time is 60 minutes (c)
Recovery time is 90 minutes (d)
Recovery time is 120 minutesFigure12 shows the variation of average waiting time with variable fleet size under different recovery time. The horizontal axis indicates fleet size. Four curves represent the variation of average waiting time under different recovery time. It is shown that as bus fleet size increases the average waiting time decreases, but the decrease rate is smaller with larger fleet size. The variation range gets larger under the longer recovery time. For example, when the recovery time is 30 minutes the average waiting time decreases from 11 mins to 5 mins, while the recovery time is 2 hours it deceases from 34 mins to 5 mins. Here are some suggestions for transit agencies: when the recovery time is quite long, e.g., 90 minutes, as many buses as possible should be dispatched, while when it is shorter, e.g., 30 minutes, the fleet size can be smaller.Figure 12
Performance of waiting time with varying bus fleet size.Since passenger demand increases until timeH (one hour in the case study) and we only consider the period before recovery timeT; when T is above or belowH, the passenger demand is different. For example, we can calculate from Table 2: whenT is 90 minutes the passenger demand is 9710 while whenT is 30 minutes the demand is 5990. It can be seen that under different recovery time the absolute quantity of stranded passengers cannot reflect the actual evacuation efficiency. Therefore, we look into an indicator:evacuation efficiency factor. Define evacuation efficiency factor as the proportion of the number of passengers who have got on board before recovery time to total passenger flows. Evacuation efficiency factor is given by:(20)η=1-ΦΛ×100%In Equation (20), η indicates evacuation efficiency factor, Φ=∑i∈NLiF represents the total number of stranded passengers, and Λ=∑i∈N∑t∈[0,T]λi(t) denotes the total passenger flows.Figure13 presents the variation of evacuation efficiency factor with different fleet size. The horizontal axis represents fleet size and four curves represent evacuation efficiency factors under different recovery time. As the fleet size increased, η also increased. For example, when recovery time was 90 minutes and the fleet size was 30 vehicles, the corresponding η was only 77.4%, while when the fleet size increased to 60, η reached 100%. In addition, when the recovery time was less than 60 minutes, the evacuation efficiency factor was significantly lower than that of longer recovery time at the same fleet size. For example, when the recovery time was 30 minutes, even if the fleet size increased to 100, it was still unlikely to evacuate all passengers. When there were 60 available buses, η reached nearly 90%. It was unnecessary for transit agencies to dispatch numerous buses.Figure 13
Performance of evacuation efficiency factor with varying bus fleet size.


## 6. Conclusions

Considering dynamic passenger flow demands and recovery time, we formulated an optimization-based model to provide bus bridging services with two objective functions, one that minimized total waiting time and the number of stranded passengers and one that minimized the total number of dispatched buses. We solved the multi-objective model with NSGA-II algorithm. A case study on Shanghai Metro Line 9 was conducted finally. We can draw some conclusions as follows.(a) A comparison with the standard bridging plan was carried out. The results show that the proposed model can significantly reduce total waiting time and the number of stranded passengers especially at the downstream stations. Due to the node-to-node bus bridging mode, more passengers can board buses than those in the standard bridging plan. The proposed model achieves a more equitable distribution of passenger condition between stations.(b) Sensitivity analysis of fleet size under different recovery time was conducted. It was found that as the fleet size increased, average waiting time and the number of stranded passengers showed a decreasing trend, but when the fleet size reached a certain value, for instance, 70 in the case study, the decline was not significant. Similar analysis will facilitate transit agencies to determine suitable fleet size.(c) Evacuation efficiency under different recovery time was evaluated. It was found that as the fleet size increased, the evacuation efficiency also increased. When recovery time was smaller than 60 minutes, even if the fleet size increased to 100, it was still difficult to evacuate all passengers. The travel time of buses dispatched to disrupted stations accounted for a large proportion of the disruption duration, leading to limited evacuation efficiency. In conclusion, transit agencies should dispatch as many buses as possible under recovery time more than 60 minutes, and vice versa.Future research should focus on developing a more efficient algorithm applicable to real-world situations. Besides, since it is difficult to predict dynamic passenger flows under unexpected disruption, we assumed that passenger arrival follows a uniform distribution. We would like to develop a bus bridging optimization model under real-time dynamic passenger flows in the future.



---

*Source: 6965728-2019-07-24.xml*