Scheduling a Bus Fleet for Evacuation Planning Using Stop-Skipping Method

Abstract

Sudden passenger demand at a bus stop can lead to numerous passengers gathering at the stop, which can affect bus system operation. Bus system operators often deal with this problem by adopting peer-to-peer service, where empty buses are added to the fleet and dispatched directly to the stop where passengers are gathered (PG-stop). However, with this strategy, passengers at the PG-stop have a long waiting time to board a bus. Thus, this paper proposes a novel mathematical programming model to reduce the passenger waiting time at a bus stop. A more complete stop-skipping model that including four cases for passengers’ waiting time at bus stops is proposed in this study. The stop-skipping decision and fleet size are modeled as a dynamic program to obtain the optimal strategy that minimizes the passenger waiting time, and the optimization model is solved with an improved ant colony algorithm. The proposed strategy was implemented on a bus line in Harbin, China. The results show that, during the evacuation, using the stop-skipping strategy not only reduced the total waiting time for passengers but also decreased the proportion of passengers with a long waiting time (>6 min) at the stops. Compared with the habitual and peer-to-peer service strategies, the total waiting time for passengers is reduced by 31% and 23%, respectively. Additionally, the proportion of passengers with longer waiting time dropped to 43.19% by adopting the stop-skipping strategy, compared with 72.68% with the habitual strategy and 47.5% with the peer-to-peer service strategy.

Social events such as sports games, concerts, and other public events are frequently organized in many large cities around the world. These special events gather a large group of people within an urban area, which leads to a sudden increase in demand for urban transportation systems. A sustainable approach to meeting such sudden demand is required to avoid traffic congestion and pollution ( 1 , 2 ). Public transportation is key to resolving this issue because of its lower average road space and energy consumption than other transportation modes ( 1 , 3 , 4 ).

Evacuation planning is a recently blossoming field of research, and much attention has been paid to developing methods for computing plans to evacuate people ( 5 – 8 ). Many studies have focused on how to utilize public transportation efficiently for evacuation planning ( 5 , 9 – 11 ). Zhao et al. ( 5 ) proposed a round-trip evacuation model to reduce the total time cost for evacuees, including the in-bus trip time and waiting time at bus stops. Goerigk et al. ( 9 ) proposed an integrated model to minimize evacuation time. Their model can also provide shelter locations for people gathering during the evacuation. Rodrigues et al. ( 12 ) combined a public transportation smartcard with special event information and proposed a Bayesian additive model to predict the total number of trips to the special event areas. Pereira et al. ( 13 ) used the Internet as a source for special event information and developed a model to predict the arrival time of public transportation vehicles in special events. Lakshay and Bolia ( 6 ) proposed a bus-based evacuation plan for large-scale regional evacuation to make optimal use of limited resources within given constraints. They developed a mathematical model to provide emergency managers with the number of buses and bus sequence.

The main task of bus evacuation planning is to formulate a bus schedule with the goal of minimizing travel time. This goal is also a major objective in public transportation planning ( 14 , 15 ). This objective is subject to many constraints; different constraints lead to different control strategies. The stop-skipping strategy is an effective approach to reducing the passenger waiting time and has been studied for decades. Various strategies such as limited-stop bus service ( 16 , 17 ), “zonal” route design ( 18 – 20 ), and deadheading ( 20 – 23 ) have some similarities to stop-skipping ( 24 , 25 ). These strategies all allow service of some stops on the bus line, while other stops are skipped depending on the assumptions and constraints.

Jordan and Turnquist ( 19 ) formulated a dynamic programming model to select optimal zone structures and suggested that zone scheduling can improve both the reliability and average trip time. Eberlein et al. ( 26 ) minimized the passenger time cost in a bus system by formulating a simplified version of the optimal solution for when to dispatch vehicles and how many stops to skip. They then extended the solution to more general problems. Furth ( 22 ) developed a formula for determining the fleet size to meet a stop-skipping schedule and designed procedures to minimize the number of vehicles and passenger waiting time. Furth ( 18 ) extended the design of a zonal express service to a zonal local service in which inbound vehicles allow passengers to alight but not to board, while outbound vehicles allow passengers to board but not to alight. Application of this control strategy showed that it could considerably reduce the costs of the transportation agency. Ceder and Stern ( 21 ) developed a scheduling procedure to determine when and where vehicles can skip certain stops under garage and driver limitations. They based their scheduling procedure on the deficit function because of its visual nature. They designed an algorithm to offer passengers the effects on the schedule displayed on a computer monitor.

Many control strategies for bus schedules are available, but most are designed for habitual demand and evacuation during very large events (e.g., Olympic Games, World Cup competitions) and emergencies (e.g., hurricanes, floods, earthquakes). Systematic and effective public transportation planning for small- and medium-scale events has not been investigated in detail, even though such events can suddenly increase the passenger demand of public transportation systems. Bus schedules for habitual demand or large-scale and emergency evacuation are not suitable for medium- and small-scale events. Figure 1a shows the habitual demand strategy; extra empty buses are not dispatched, so this strategy cannot meet sudden increases in passenger demand. Figure 1b shows the peer-to-peer service strategy, which is often employed for very large events and emergencies. Several empty vehicles are dispatched from the depot to the stop where many passengers are gathered (PG-stop). Passengers need to wait at the PG-stop until the empty buses arrive, which is time-consuming.

Figure 1.

Illustration of three evacuation strategies at the “passengers-gathered” stop (PG-stop): (a) habitual, (b) peer-to-peer service, and (c) stop-skipping.

To bridge this gap, this study focused on developing a dynamic control strategy for a bus fleet to evacuate people gathered at stops after leaving medium- and small-scale social events. An optimization model was developed to minimize the waiting time for passengers at all bus line stops. Rather than dispatching empty vehicles directly to the PG-stop, a stop-skipping strategy was considered to dynamically control the buses already operating on the line (Figure 1c). To determine whether or not stops should be skipped, a novel formulation of stop-skipping patterns was developed while empty buses are added to the fleet to meet sudden increases in passenger demand. Stop-skipping means that for both buses added to the fleet and buses already operating on the line stops could be skipped, considering that during the high demand at the PG-stop a skipped stop could leave more seats for the passengers at the PG-stop and reduce their waiting time. However, a skipped stop will cause inconvenience to passengers at stops that are not PG-stops (NPG-stops) who therefore need be picked up by the empty buses added to the fleet. When deciding whether to skip stops, the waiting time for passengers at the PG-stop and the NPG-stops are both considered. Compared with existing studies, the control strategy developed in this study allows more flexible bus operation and evacuation. First, stop-skipping is allowed. Second, both currently opertating buses and the empty buses added temporarily were allowed to evacuate the passengers gathered at a PG-stop. In comparison, existing research on stop-skipping does not consider the sudden increase of passenger demand.

The optimization model is an NP-hard problem (i.e. The complexity class of decision problems in our model that are harder than those that can be solved by a nondeterministic Turing machine in polynomial time), and it is difficult to find an exact solution. Thus, the ant colony (AC) algorithm was adopted to solve the model, and the proposed stop-skipping strategy was applied to a bus line in a Chinese city as a case study to compare its performance with those of traditional strategies when the passenger demand suddenly increases.

The remainder of this study is organized as follows. The next section introduces the mathematical formulation of the stop-skipping problem. The third section describes the algorithm for solving the optimized mathematical model. The fourth section presents the case study to validate the proposed mathematical model. The final section provides concluding remarks and future research directions.

Bus Operating Methodology

The bus operating methodology for meeting sudden passenger demand during medium- and small-scale events is presented here. First, the waiting times for passengers at the PG-stop and NPG-stops were formulated. The waiting time for passengers at the PG-stop depends on the number of buses that are added to the fleet and the capacity of a bus. This can be used to determine the number of buses that need to be added to the fleet. Depending on the stop-skipping decisions between two successive NPG-stops, the waiting time for passengers at NPG-stops has four cases. These four cases can be integrated into an equation with decision variables. The stop-skipping strategy is based on modeling the bus operation process as an optimization problem, where the objective is to minimize the waiting time for all passengers. This requires considering several constraints.

Notation

Consider a bus line J containing a set $N_{j}$ of bus stops. In the literature, a bus line is usually treated as a bidirectional closed loop. To illustrate the stop-skipping strategy for meeting sudden passenger demand, without loss of generality, only one direction of the bus line is considered here. Let $N_{v}$ denote the set of operating buses along one direction of the bus line $J$ . Each bus is indexed by $v_{i}$ for $i \in N_{v}$ . Let $s^{*} \in N_{j}$ be a representative stop where many passengers gather. Passengers arrive at stop $s_{a} \in N_{j}$ heading to $s_{b} \in N_{j}$ randomly over time; this is denoted by the function $λ_{s_{a}, s_{b}} (t)$ . The notation used in this paper is given below:

s: index for bus stops on line J: $s = 1, 2, 3, \dots, S$

$s^{*}$ : PG-stop; $1 \leq s^{*} < S$

v : index of buses operating on line J

$A_{s}^{v}$ : arrival time of bus v at stop s

$D_{s}^{v}$ : departure time of bus v at stop s

$θ_{s_{a}, s_{b}}^{v}$ : number of passengers waiting for bus v at stop $s_{a}$ and about to alight at stop $s_{b}$ .

$η_{s_{b}, s_{a}}^{v}$ : number of passengers alighting bus v at stop $s_{b}$ from $s_{a}$ (in the situation where the origin–destination [OD] pairs are known, this term can be formulated by the OD between stops)

$λ_{s_{a}, s_{b}} (t)$ : arrival rate function of passengers traveling from stop $s_{a}$ to stop $s_{b}$

$m_{s}$ : number of gathered passengers at stop $s^{*}$ intending to take the bus on line J and alight at stop s: $s > s^{*}$

$Ω_{v}$ : bus capacity

$β_{0}^{v}$ : number of passengers in the bus v at time $t_{0}$

$α_{0}^{v}$ : index of bus v that first reaches the stop after time $t_{0}$

$x_{s}$ : decision variable; $x_{s}^{v} = {\begin{matrix} 1 if stop s is skipped by bus v \\ 0 otherwise \end{matrix}$

The proposed model uses the following assumptions:

Passengers arrive at each stop to alight at another stop randomly over time.

Passengers waiting at a stop have equal opportunity to board the bus.

Except for the PG-stop, the bus does not reach its maximum capacity when it departs from a stop.

The bus running time between two adjacent stops is unchanged during the scheduling time.

Waiting Time for Passengers at NPG-Stops

For passengers who arrive at stop $s_{a}$ heading to stop $s_{b}$ before the departure time $D_{s_{a}}^{v}$ , their waiting time depends on whether stop $s_{a}$ and stop $s_{b}$ are skipped by bus v. If stop $s_{a}$ or stop $s_{b}$ is skipped by bus v, the passengers must wait for the next bus. Thus, the waiting time for passengers who arrive at stop $s_{a}$ between the departure times $D_{s_{a}}^{v - 1}$ and $D_{s_{a}}^{v}$ depends on the values of $x_{a}$ and $x_{b}$ : $\forall s_{b} \in [s_{a} + 1, S]; \forall v \in [1, N_{v}]$ for $s_{b} = s_{a} + 1, s_{a} + 2, \dots, S; v = 1, 2, 3, \dots, N_{v}$ . There are four cases for these decision variables, as presented below.

If $x_{s_{a}}^{v} = 0$ and $x_{s_{b}}^{v} = 0$ , then the passengers who arrive at stop $s_{a}$ between $D_{s_{a}}^{v - 1}$ and $D_{s_{a}}^{v}$ can board bus v, and their waiting time is given by

W_{1} = \int_{D_{s_{a}}^{v - 1}}^{D_{s_{a}}^{v}} λ_{s_{a}, s_{b}} (t) (D_{s_{a}}^{v} - t) d t .

(1)

If $x_{s_{a}}^{v} = 1$ and $x_{s_{b}}^{v} = 0$ , then the passengers who arrive at stop $s_{a}$ between $D_{s_{a}}^{v - 1}$ and $D_{s_{a}}^{v}$ cannot board bus v because it skips the stop. They have to wait for the next bus $v + 1$ . In this case, stops $s_{a}$ and $s_{b}$ must not be skipped by bus $v + 1$ (i.e., $x_{s_{a}}^{v + 1} = 0$ and $x_{s_{b}}^{v + 1} = 0$ ). The waiting time for these passengers is given by

W_{2} = \int_{D_{s_{a}}^{v - 1}}^{D_{s_{a}}^{v}} λ_{s_{a}, s_{b}} (t) (D_{s_{a}}^{v + 1} - t) d t

(2)

If $x_{s_{a}}^{v} = 0$ and $x_{s_{b}}^{v} = 1$ , then the passengers who arrive at stop $s_{a}$ between $D_{s_{a}}^{v - 1}$ and $D_{s_{a}}^{v}$ cannot alight from bus v at stop $s_{b}$ if they board at stop $s_{a}$ . Therefore, they have to wait for the next bus $v + 1$ . Stops $s_{a}$ and $s_{b}$ must not be skipped by bus $v + 1$ (i.e., $x_{s_{a}}^{v + 1} = 0$ and $x_{s_{b}}^{v + 1} = 0$ ). The waiting time for these passengers is given by

W_{3} = \int_{D_{s_{a}}^{v - 1}}^{D_{s_{a}}^{v}} λ_{s_{a}, s_{b}} (t) (D_{s_{a}}^{v + 1} - t) d t

(3)

If $x_{s_{a}}^{v} = 1$ and $x_{s_{b}}^{v} = 1$ , then the passengers who arrive at stop $s_{a}$ between $D_{s_{a}}^{v - 1}$ and $D_{s_{a}}^{v}$ cannot board bus v. Therefore, they have to wait for the next bus $v + 1$ . Stops $s_{a}$ and $s_{b}$ must not be skipped by bus $v + 1$ (i.e., $x_{s_{a}}^{v + 1} = 0$ and $x_{s_{b}}^{v + 1} = 0$ ). The waiting time for these passengers is given by

W_{4} = \int_{D_{s_{a}}^{v - 1}}^{D_{s_{a}}^{v}} λ_{s_{a}, s_{b}} (t) (D_{s_{a}}^{v + 1} - t) d t

(4)

To compute the waiting time for passengers at NPG-stops, the above four cases can be integrated into the following equation using decision variables:

\begin{matrix} W = \sum_{s_{b} = s_{a} + 1}^{S} {(1 - x_{s_{a}}^{v}) (1 - x_{s_{b}}^{v}) W_{1} + x_{s_{a}}^{v} (1 - x_{s_{b}}^{v}) W_{2} \\ + (1 - x_{s_{a}}^{v}) x_{s_{b}}^{v} W_{3} + x_{s_{a}}^{v} x_{s_{b}}^{v} W_{4}} \end{matrix}

(5)

The expressions for W₁–W₄ can be substituted into the above equation to obtain the waiting time of passengers who arrive at stop $s_{a}$ between the departure times $D_{s_{a}}^{v - 1}$ and $D_{s_{a}}^{v}$ :

\begin{matrix} W = \sum_{S_{b} = S_{a} + 1}^{S} {\begin{matrix} (1 - x_{s_{a}}^{v}) (1 - x_{s_{b}}^{v}) \int_{D_{s_{a}}^{v - 1}}^{D_{s_{a}}^{v}} λ_{s_{a}, s_{b}} (t) (D_{s_{a}}^{v} - t) d t + [x_{s_{a}}^{v} (1 - x_{s_{b}}^{v}) + \\ (1 - x_{s_{a}}^{v}) x_{s_{b}}^{v} + x_{s_{a}}^{v} x_{s_{b}}^{v}] \int_{D_{s_{a}}^{v - 1}}^{D_{s_{a}}^{v}} λ_{s_{a}, s_{b}} (t) (D_{s_{a}}^{v + 1} - t) d t \end{matrix}} \\ \forall s_{b} \in [s_{a} + 1, S], \forall v \in [1, N_{v}] \end{matrix}

(6)

Because $x_{s_{a}}^{v}$ and $x_{s_{b}}^{v}$ are 0–1 binary variables, the above equation can be replaced with

\begin{matrix} W = \sum_{S_{b} = S_{a} + 1}^{S} {\begin{matrix} (1 - x_{s_{a}}^{v}) (1 - x_{s_{b}}^{v}) \int_{D_{s_{a}}^{v - 1}}^{D_{s_{a}}^{v}} λ_{s_{a}, s_{b}} (t) (D_{s_{a}}^{v} - t) d t + \\ [(1 - x_{s_{a}}^{v}) x_{s_{b}}^{v} + x_{s_{a}}^{v}] \int_{D_{s_{a}}^{v - 1}}^{D_{s_{a}}^{v}} λ_{s_{a}, s_{b}} (t) (D_{s_{a}}^{v + 1} - t) d t \end{matrix}} \\ \forall s_{b} \in [s_{a} + 1, S], \forall v \in [1, N_{v}] \end{matrix}

(7)

The capacity of bus v that first reaches the stop after $t_{0}$ is given by $Ω_{v} - β_{0}^{v}$ . Passengers waiting at the stop include those who were unable to board the preceding bus because of the limited capacity. The number of passengers waiting at stop $s_{a}$ to alight at stop $s_{b}$ is given by

θ_{s_{a}, s_{b}}^{v} = l_{s_{a}, s_{b}}^{v} + \int_{D_{s_{a}}^{v - 1}}^{A_{s_{a}}^{v}} λ_{s_{a}, s_{b}} d t

(8)

l_{s_{a}, s_{b}}^{v} = {\begin{matrix} θ_{s_{a}, s_{b}}^{v - 1} - (Ω_{v - 1} - Ψ_{s_{a}}^{v - 1}), if θ_{s_{a}, s_{b}}^{v - 1} > (Ω_{v - 1} - Ψ_{s_{a}}^{v - 1}) \\ 0, otherwise \end{matrix}

(9)

H_{s_{a}}^{v} = A_{s_{a}}^{v} - D_{s_{a}}^{v - 1}

(10)

The number of passengers boarding bus v at stop $s_{a}$ is given by

{\hat{ϒ}}_{s_{a}}^{v} = {\begin{matrix} \sum_{s = s_{a} + 1,}^{S} θ_{s_{a}, s}^{v} & , if \sum_{s = s_{a} + 1,}^{S} θ_{s_{a}, s}^{v} < Ω_{v} - Ψ_{s_{a}}^{v} + η_{s_{a}}^{v} \\ Ω_{v} - Ψ_{s_{a}}^{v} + η_{s_{a}}^{v} & , if \sum_{s = s_{a} + 1,}^{S} θ_{s_{a}, s}^{v} > Ω_{v} - Ψ_{s_{a}}^{v} + η_{s_{a}}^{v} \end{matrix}

(11)

According to the assumptions of the proposed methodology, passengers waiting at the stop have equal opportunity to board the bus. Then, the actual number of passengers boarding bus v at stop $s_{a}$ to alight at stop $s_{b}$ is

{\hat{θ}}_{s_{a}, s_{b}}^{v} = \frac{{\hat{Θ}}_{s_{a}}^{v}}{\sum_{s = s_{a} + 1}^{S} θ_{s_{a}, s}^{v}} θ_{s_{a}, s_{b}}^{v}

(12)

The number of passengers alighting bus v at stop $s_{a}$ is given by

η_{s_{a}}^{v} = \sum_{s = 1}^{s_{a} - 1} {\hat{θ}}_{s, s_{a}}^{v}

(13)

The number of passengers in bus v when it arrives at stop $s_{a}$ is given by

Ψ_{s_{a}}^{v} = Ψ_{s_{a} - 1}^{v} - η_{s_{a} - 1}^{v} + {\hat{Θ}}_{s_{a} - 1}^{v}

(14)

The number of passengers who did not board the first bus v to arrive at stop $s_{a}$ because of limited capacity is given by

\sum_{s = s_{a} + 1,}^{S} θ_{s_{a}, s}^{v} - {\hat{Θ}}_{s_{a}}^{v}

(15)

The headway between bus $v - 1$ and bus v at stop s is the time gap between bus $v - 1$ leaving stop s and bus v arriving at s:

H_{s_{a}}^{v} = A_{s_{a}}^{v} - D_{s_{a}}^{v - 1}

(16)

The bus dwell time is given by

t_{s_{a}}^{v} = max (\sum_{s_{a} = 1}^{s_{b} - 1} {\hat{θ}}_{s_{a}, s_{b}}^{v} τ_{b}, \sum_{s_{b} = s_{a} + 1}^{S} {\hat{θ}}_{s_{a}, s_{b}}^{v} τ_{a})

(17)

$τ_{a}$ and $τ_{b}$ represent the average alighting and boarding time per passenger, respectively. The running time of bus v between stops $s_{i}$ and $s_{j}$ is given by

T_{s_{i}, s_{j}}^{v} = \frac{l_{s_{i}, s_{j}}}{spee d^{v}}

(18)

The time for bus v to arrive at and depart stop $s_{a}$ can be represented as

A_{s_{a}}^{v} = D_{s_{a} - 1}^{v} + T_{s_{a}}^{v}

(19)

D_{s_{a}}^{v} = A_{s_{a}}^{v} + t_{s_{a}}^{v}

(20)

For passengers who arrive at stop s after the departure time $D_{s}^{v - 1}$ , the tolerance for the waiting time is assumed to be $[D_{s}^{v - 1}, D_{s}^{v + 1}]$ . In other words, if they do not board the first bus to arrive at the stop (i.e., bus v), they must take the next bus to arrive at the stop (i.e., bus $v + 1$ ). For this reason, two successive buses are not allowed to skip the same stop. Therefore, the following constraint must be satisfied:

x_{s_{a}}^{v} + x_{s_{a}}^{v + 1} \leq 1

(21)

Waiting Time for Passengers at the PG-Stop

The arrival rate from PG-stop $s^{*}$ to other stops is larger than usual within a short time. Passengers arriving at stop $s^{*}$ during this time are evacuated by several buses. Which bus passengers can board depends on the load of buses arriving at this stop. To evacuate passengers at PG-stop $s^{*}$ , this stop cannot be skipped by any buses (i.e., $x_{s^{*}}^{v} = 0$ for $v = 1, 2, 3, \dots, N_{v}$ ).

Several buses should be added to the fleet to meet the passenger demand at PG-stop $s^{*}$ . If the added buses are run directly to the PG-stop, this would take a long time, and passengers at $s^{*}$ would complain. The number of buses that should be added to the fleet is given by

n_{e} = Γ (\frac{\sum_{s = s^{*} + 1}^{S} m_{s}}{Ω_{v}})

(22)

where $Γ ()$ represents the ceiling function.

The added buses are denoted by $N_{v} + 1, N_{v} + 2, \dots, N_{v} + n_{e}$ . These buses should skip the first few stops to avoid idle load and bus bunching at these stops (i.e., $x_{1}^{N_{v} + h} = 1$ and $x_{2}^{N_{v} + h} = 1$ , for $h = 1, 2, 3, \dots, n_{e}$ ). Passengers boarding bus v at stop $s^{*}$ have the waiting time $(D_{s^{*}}^{v} - t_{0}) (Ω_{v} - Ψ_{s^{*}}^{v})$ .

Optimization Model

The objective of the optimization model is to minimize the total waiting time for all passengers during the entire optimization horizon. There are two types of waiting times: for passengers at the PG-stop and for passengers at NPG-stops. The total waiting time for all passengers can be expressed by summing Equations 10–15. The waiting time for passengers at NPG-stops can then be expressed by the following summation, where stop $s_{a}$ and bus v represent the sets of all stops and buses:

Z_{1} = \sum_{v = 1}^{N_{v}} \sum_{s_{a} = 1}^{S - 1} \sum_{s_{b} = s_{a} + 1}^{S} {\begin{matrix} (1 - x_{s_{a}}^{v}) (1 - x_{s_{b}}^{v}) \int_{D_{s_{a}}^{v - 1}}^{D_{s_{a}}^{v}} λ_{s_{a}, s_{b}} (t) (D_{s_{a}}^{v} - t) d t + \\ [(1 - x_{s_{a}}^{v}) x_{s_{b}}^{v} + x_{s_{a}}^{v}] \int_{D_{s_{a}}^{v - 1}}^{D_{s_{a}}^{v}} λ_{s_{a}, s_{b}} (t) (D_{s_{a}}^{v + 1} - t) d t \end{matrix}}

(23)

The waiting time for passengers at the PG-stop is given by

Z_{2} = \sum_{v = 1}^{v^{*}} (D_{s^{*}}^{v} - t_{0}) (Ω_{v} - Ψ_{s^{*}}^{v})

(24)

where $v^{*}$ is the bus that has departed from PG-stop and all gathered passengers have been evacuated. In other words, the following inequality holds:

\sum_{v = 1}^{v^{*}} (Ω_{v} - Ψ_{s^{*}}^{v}) \geq \sum_{s = s^{*} + 1}^{S} m_{s}

(25)

Thus, the objective function for the proposed model is given by

min Z = Z_{1} + Z_{2}

(26)

Therefore, the stop-skipping strategy to meet sudden passenger demand can be formulated as follows:

\begin{matrix} min Z = \sum_{v = 1}^{N_{v}} \sum_{s_{a} = 1}^{S - 1} \sum_{s_{b} = s_{a} + 1}^{S} {\begin{matrix} (1 - x_{s_{a}}^{v}) (1 - x_{s_{b}}^{v}) \int_{D_{s_{a}}^{v - 1}}^{D_{s_{a}}^{v}} λ_{s_{a}, s_{b}} (t) (D_{s_{a}}^{v} - t) d t \\ + [(1 - x_{s_{a}}^{v}) x_{s_{b}}^{v} + x_{s_{a}}^{v}] \int_{D_{s_{a}}^{v - 1}}^{D_{s_{a}}^{v}} λ_{s_{a}, s_{b}} (t) (D_{s_{a}}^{v + 1} - t) d t \end{matrix}} \\ + \sum_{v = 1}^{v^{*}} (D_{s^{*}}^{v} - t_{0}) (Ω_{v} - Ψ_{s^{*}}^{v}) \end{matrix}

(27)

subject to Equations 1–14, 25, and the following constraints:

\begin{matrix} x_{s}^{v} \in {0, 1}, s = 1, 2, 3, \dots, s^{*} - 1, s^{*} + 1, \dots, S; \\ v = 1, 2, 3, \dots, N_{v} \end{matrix}

(28)

D_{s}^{v} < D_{s}^{v + 1}, s = 1, 2, 3, \dots, S; v = 1, 2, 3, \dots, N_{v} - 1

(29)

If x_{s}^{v} = 1, then t_{s}^{v} = 0

(30)

x_{s^{*}}^{v} = 0, for v = 1, 2, 3, \dots, N_{v}

(31)

Equation 29 establishes that buses cannot overtake each other. Equation 30 shows that, if bus v skips stop s, then the dwell time of bus v at stop s is zero. Equation 31 ensures that the PG-stop should not be skipped by any bus.

Solution Method

Ibarra-Rojas and Rios-Solis ( 27 ) proved that the bus timetabling problem they formulated is NP-hard and also the NP-hardness of the similar problems present in other literature, such as the related problems of Ceder and Tal ( 28 ) and Eranki ( 29 ). The bus scheduling problem in this study is similar to these problems and the proposed mathematical model is a mixed 0–1 integer programming model. The objective function is neither convex nor concave. Therefore, the problem in this study is an NP-hard problem. Finding an exact solution is difficult. The AC algorithm is used to solve this problem. However, the traditional version of this algorithm is typically computationally expensive. To enhance the search ability and convergence speed of the AC algorithm, a competition function was customized to combine with the algorithm.

Competition Function

Let $X (0)$ denote the initial solution of the problem, and $X (i)$ denote the i th iterative solution. The variables corresponding to $X (i)$ are ( $x_{1}, x_{2}, \dots, x_{n}$ ). For $j = 1, 2, \dots, n$ , updating $x_{j}$ obtains a new solution to the problem. Therefore, the problem has n possible new solutions, which are denoted by $X_{j} (i), j = 1, 2, \dots, n$ . The competition function $f_{c} (i, j)$ for the j th new solution of the i th iteration is

f_{c} (i, j) = {\begin{matrix} 0, & if (X_{j} (i) > X (i)) \\ \frac{X (i) - X_{j} (i)}{\sum_{k \in U} (X (i) - X_{k} (i))}, & otherwise \end{matrix}

(32)

where $U = {k | X (i) > X_{k} (i)}$ ,

Overall Solution Procedure

The above competition function is combined with the optimization model presented in the previous section for the solution algorithm. The steps are given below:

Initialize the algorithm parameters $τ_{j}$ and $Δ τ_{j}$ .

Set nc = 0, and randomly assign a set of 0–1 values to ants as the initial starting point. For each ant, search for the new status according to the state transition probability, which is given by:

P_{ij} = \frac{{[τ_{j}]}^{α} {[θ_{ij}]}^{β}}{\sum_{k} {[τ_{k}]}^{α} {[θ_{ik}]}^{β}}

(33)

where $τ_{j}$ is the trajectory and $θ_{ij} = Z_{j} - Z_{i}$ represents the difference for the combination of a different variable. $α$ is a coefficient that represents the importance of the trajectory. $β$ is a coefficient that represents the relative materiality of $θ_{ij}$ . Then, the objective value is calculated for every ant.

Growth and evolution take place according to the competition rules. Compute $f_{c} (i, j),$ for $j = 1, 2, \dots, n$ .

If $\exists j \in {1, 2, \dots, n}$ , then satisfy $f_{c} (i, j) > rand ()$ by letting

f_{c} (i, j^{*}) = max_{\begin{matrix} \begin{matrix} f_{c} (i, j) > rand () \end{matrix} \\ j = 1, 2, \dots, n \end{matrix}} f_{c} (i, j)

(34)

The best solution is $f_{c} (i, j^{*}) .$ Then, for any $j \in {1, 2, \dots, n} = 0$ , $f_{c} (i, j) < rand ()$ , record the best solution, and end the step.

Update the trajectory strength according to the pheromone concentration:

τ_{j}^{new} = ρ τ_{j}^{old} + \sum_{k} Δ τ_{j}^{k}

(35)

where $ρ \in [0, 1)$

Δ τ_{j}^{k} = {\begin{matrix} Q, if j is selected \\ 0, otherwise \end{matrix}

(36)

where Q is the quantity of the pheromone left by the previous ant.

Set $Δ τ_{j} = 0$ and $nc = nc + 1$ .

If $nc > n c_{\max}$ (where $n c_{\max}$ is the predetermined maximum number of iterations) or all solutions are identical, then stop and output the current best solution. Otherwise, $nc = nc + 1$ , and go to step 2.

Output the current solution.

Case Study

Data Preparation

For validation, the proposed mathematical model and algorithm were applied to a real-world bus route in Harbin City, China as a case study. The route contains 34 stops and is approximately 17 km long; the headway is 3 min at peak hour. A segment of the route overlaps with the subway. Figure 2 shows the route and stop locations.

Figure 2.

Bus line in Harbin, China used for the case study.

When an event occurs near a bus stop, many passengers must gather around the stop and need to evacuate via the buses. An event considered occurred at stop 23 during peak hour. Many passengers gathered at this stop and needed to be evacuated by buses. Table 1 presents information on the bus stops. The running times between successive stops were computed according to the distance and operating bus speed, and they are given in the table as well. At the beginning of the optimization, the buses on the line departed for the next stop in sequence. The following parameters were set: number of buses $N_{v} = 15$ , cruising speed $spee d^{v} =$ 30 km/h, and average boarding and alighting times of $τ_{a} = 4 s / person$ and $τ_{b} = 2 s / person$ , respectively. $Ω_{v}$ was set to 100. Passengers intending to alight at downstream stops were assumed to be evenly distributed among the stops throughout the optimization horizon. In other words, the rate of passengers boarding at one stop to alight at another stop was constant. The rate of passengers traveling from one stop to another can be obtained through an OD matrix survey.

Table 1.

Distance and Running Time between Adjacent Stops

Index (stop no.)	Stop	Distance (m)	Running time (s)	Index (stop no.)	Stop	Distance (m)	Running time (s)
1	YangMingTan Bridge South	0	0	18	HeXing Road	508	61
2	1st Road of QunLi	447	54	19	TongDa Street	487	59
3	BaoLi City	357	43	20	City Orthopedic Hospital	324	39
4	1st Road of QunLi	370	45	21	West Bridge	419	51
5	QunLi New City Community	565	68	22	HIT Campus	923	111
6	QunLi GuanJiang International	921	111	23	Harbin Railway Bureau	453	55
7	Harbin Concert Hall	808	97	24	Provincial Expo Center	374	45
8	Jingjiang East Road	577	70	25	QiuLin Company	805	97
9	Wangfujing Shopping Center	492	60	26	Children’s Park	686	83
10	QunLi Bus Terminal	439	53	27	GeXin Street	705	85
11	JinJiang Road	565	68	28	Provincial Archives	308	37
12	14 Middle School	629	76	29	XuanHua Street	342	42
13	GuXiang	766	92	30	LiZhi Street	261	32
14	GuXiang Street	541	65	31	ShiZi Street	571	69
15	Armed Police Hospital	644	78	32	HaiHe Road	433	52
16	DaFa Market	295	36	33	JianGongXinQu	184	23
17	47 Middle School	720	87	34	HIT 2nd Campus	391	47

Passenger Demand

The average arrival rate under common passenger demand at each stop is shown in Table 2. The Harbin Railway Bureau stop (stop 23) is shared by the bus line and subway line. In the case study, an emergency event occurred on the subway line around stop 23 and passengers on the subway needed to transfer to the bus line, which would cause a sudden increase in passenger demand. There are 150 passengers intending to transfer to the bus line at this point. The beginning of the optimization is denoted by $t_{0}$ . The bus load at $t_{0}$ was computed from the passenger arrival rate and bus schedule.

Table 2.

Average Arrival Rate at Each Stop (people per minute)

Bus stop	1	2	3	4	5	6	7	8	9	10	11	12
Arrive rate	2.33	2.67	3.00	2.67	2.67	2.33	3.00	2.67	2.00	2.67	2.67	1.67
Bus stop	13	14	15	16	17	18	19	20	21	22	23	24
Arrive rate	2.00	1.67	1.33	2.67	2.67	2.67	2.33	1.67	3.00	3.00	2.67	1.67
Bus stop	25	26	27	28	29	30	31	32	33	34	NA	NA
Arrive rate	1.67	0.67	0.67	0.00	0.33	0.33	0.33	0.00	0.00	0.00	NA	NA

Note: NA = not available.

Dynamic Control Strategies

Two strategies were considered to evacuate the passengers gathered at stop 23. The first was peer-to-peer service, in which empty buses are dispatched directly to the PG-stop. Two extra buses were required to evacuate the gathered passengers, and they were dispatched from the route terminus. The two buses were empty before they arrived at stop 23. When they departed, they were fully loaded unless no more passengers were waiting at the PG-stop. This study assumed that passengers could board the buses stochastically. The second was the proposed stop-skipping strategy described above. Empty buses were again needed, but instead of them being dispatched directly to the PG-stop, buses already operating on the line skipped certain stops to arrive at the PG-stop.

Computation Results

The stop-skipping problem on this numerical case is solved using the modified AC algorithm proposed above. The parameters of the algorithm were set to $α = 1, β = 1, ρ = 0.8, and Q = 100$ . The algorithm is coded in Python and implemented on a personal computer with Intel(R) Core(TM) i7-9750H CPU @2.60 GHz 2.59 GHz and 16.0 GB RAM. The computation took about 53 s. Compared with the evacuation time, the calculation time is very small and negligible. This modified AC algorithm is sound for solving the stop-skipping problem for evacuation planning.

To demonstrate the benefits of the proposed stop-skipping strategy, the time costs of three strategies were computed: (a) habitual (i.e., no control strategy), (b) peer-to-peer service, and (c) stop-skipping. Table 3 illustrates the passenger average waiting time for all stops with the three strategies. The stop-skipping strategy resulted in an average waiting time for all passengers of 111 s, while the habitual and peer-to-peer service strategies resulted in 162 s and 144 s, respectively. Thus, the stop-skipping strategy reduced the average waiting time for passengers.

Table 3.

Average Waiting Time for Each Strategy

Strategy	Average waiting time (s)
Habitual	162
Peer-to-peer service	144
Stop-skipping	111

To obtain an overview of the variations in the passenger waiting time with the three strategies, the waiting time at all stops on the bus line was tracked, as shown in Figure 3. The maximum waiting time for passengers at the PG-stop was approximately 230,000 s with the peer-to-peer service strategy. The minimum waiting time for passengers at the PG-stop was approximately 50,000 s with the proposed stop-skipping strategy. The proposed stop-skipping strategy drastically reduced the waiting time for passengers at the PG-stop compared with the other strategies. Unsurprisingly, the waiting time for passengers at other stops increased slightly. This is because when a bus skips a stop, the passengers at this stop have to wait for the next bus. The waiting time for passengers at the stops near the PG-stop changed greatly with the three strategies. The waiting times for passengers between stops 1 and 10 were very similar with the habitual and peer-to-peer service strategies. However, the waiting time for passengers at these stops decreased greatly with the stop-skipping strategy.

Figure 3.

Total waiting time for passengers at different stops with different strategies: (a) habitual, (b) peer-to-peer service, and (c) stop-skipping.

Figure 4 shows the average waiting time for all bus stops on the bus line under three different strategies. For the habitual strategy, passengers at waiting at stops before the PG-stop (stop 23) spend almost equal time waiting for a bus. Since most buses leave the PG-stop at maximum load, passengers waiting behind PG-stop have to wait longer time for a bus. The maximum wait time for passengers at PG-stop is 945 s. For the peer-to-peer strategy, the maximum passenger waiting time at PG-stop is up to 1,700 s, which is also the maximum waiting time for all passengers in the three strategies. Recall that bus headway in our case study was 3 min(180s), and the waiting time of passengers at the stop was half of the headway( 28 ). Therefore, the waiting time of passengers at all other stops in this strategy was 90 s. Therefore, under this strategy, the waiting time of passengers at other stops except PG-stop is 90 s. When the demand of the PG-stop suddenly increases, it will not affect passengers at other stops, and the passengers at the PG-stop must wait longer until the empty train arrives. For the stop-skipping strategy, the passengers who wait at stops before stop 7 spend less than 90 s waiting because of the empty buses added to the fleet, while those who are at the stops after it all endure waiting for a longer time. For the stop-skipping strategy, the waiting time of passengers stopping at the stop before the seventh stop is less than 90 s because of the empty buses added to the fleet, and the time for the stops after it will increase with the impact of the stop-skipping.

Figure 4.

Average waiting time for passengers at different stops with different strategies: (a) habitual, (b) peer-to-peer service, and (c) stop-skipping.

The waiting time distributions at all bus stops with the three different strategies were also explored. Table 4 presents the percentages of passengers waiting for six different time intervals. The stop-skipping strategy reduced the percentage of passengers that had to wait more than 10 min to board a bus. This is because this strategy adjusted the buses already operating on the line to skip certain stops to reach the PG-stop quickly and evacuate the passengers in a timely manner. However, it increased the percentages of passengers waiting for other time intervals compared with the habitual and peer-to-peer service strategies. With the stop-skipping strategy, the waiting time interval with the highest percentage of passengers was 4–6 min at all stops. Approximately half of the passengers waited 4–8 min. This is because some stops were skipped by the bus, and passengers who wanted to board or alight at these stops had to wait for the next bus. With the peer-to-peer service strategy, the vast majority of passengers waited less than 6 min or more than 10 min. In other words, almost no passengers had to wait 6–10 min. This indicates that this strategy divides passengers into two groups: those at the PG-stop and those at other stops. The passengers at the PG-stop had to wait more than 10 min, while passengers at other stops waited between 0 and 6 min. With the habitual strategy, more than 70% of passengers had to wait for more than 6 min. This is because some passengers could not board the bus because of limited capacity, so they had to wait for the next bus. The limited bus capacity is another reason why the waiting time was more than the headway. In summary, the stop-skipping strategy evacuated gathered passengers in a timely manner and reduced the waiting time at the PG-stop better than the other two strategies.

Table 4.

Percentage of Passengers for Each Waiting Interval with the Three Strategies

Strategy	% of passengers for each waiting interval
Strategy	0–2 min	2–4 min	4–6 min	6–8 min	8–10 min	>10 min
Habitual	6.75	8.21	12.36	24.85	21.35	26.48
Peer-to-peer service	21.36	19.06	12.08	2.45	0	45.05
Stop-skipping	16.93	13.57	26.31	23.17	15.67	4.35

Conclusions

In this paper, a dynamic bus control strategy based on stop-skipping was developed to evacuate gathered passengers when the passenger demand suddenly increases at a certain stop. The proposed strategy allows the agency to dispatch empty buses from the terminus to meet the sudden demand. However, instead of the empty buses being dispatched directly to the PG-stop, they start to pick up passengers from the first stop on the bus line. Meanwhile, buses already operating on the line skip certain stops to reach the PG-stop more quickly. Therefore, the proposed strategy requires the agency to decide the number of empty buses to dispatch and which stops on the bus line to skip.

The objective of the agency would be to evacuate passengers at the PG-stop as quickly as possible and minimize the waiting time for all passengers on the bus line. This problem was formulated into an optimization program and modified the AC algorithm to determine the optimal solution for stop-skipping. As a case study, the proposed strategy and solution algorithm were applied to a bus line with a PG-stop caused by an emergency event. Compared with the habitual and peer-to-peer service strategies, the proposed stop-skipping strategy reduced the total waiting time for all passengers at the different stops. Also, the benefit of the stop-skipping strategy in decreasing the percentage of passengers who had to wait more than 10 min was quantified. The proposed strategy not only reduced the total waiting time for all passengers but also decreased the proportion of passengers who had to wait more than 10 min. The proposed strategy also significantly reduced the waiting time for passengers at the PG-stop.

Footnotes

Author Contributions

The authors confirm contribution to the paper as follows: study conception and design: H. Zhao, S. Feng; data collection: H. Zhao; analysis and interpretation of results: H. Zhao, S. Feng, Y. Ci; draft manuscript preparation: H. Zhao, Y. Ci. All authors reviewed the results and approved the final version of the manuscript.

Declaration of Conflicting Interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This work is supported by the National Nature Science Foundation of China (No. 71771062).

ORCID iD

Hu Zhao

References

Tang

Ceder

A. A.

Y. E.

Liu

Operational Strategies for Single Bus Lines Using Network-Based Method. International Journal of Sustainable Transportation, Vol. 15, No. 557, 2020, pp. 1–13.

Shaheen

S. A.

Cohen

A. P.

Carsharing and Personal Vehicle Services: Worldwide Market Developments and Emerging Trends. International Journal of Sustainable Transportation, Vol. 7, No. 1, 2013, pp. 5–34.

Taylor

B. D.

Morris

E. A.

Public Transportation Objectives and Rider Demographics: Are Transit’s Priorities Poor Public Policy?

Transportation, Vol. 42, No. 2, 2014, pp. 347–367.

Dreier

Silveira

Khatiwada

Fonseca

K. V. O.

Nieweglowski

Schepanski

The Influence of Passenger Load, Driving Cycle, Fuel Price and Different Types of Buses on the Cost of Transport Service in the BRT System in Curitiba, Brazil. Transportation, Vol. 46, No. 6, 2018, pp. 2195–2242.

Zhao

Qian

W. W.

Shan

X. N.

A Round-Trip Bus Evacuation Model with Scheduling and Routing Planning. Transportation Research Part A: Policy and Practice, Vol. 137, 2020, pp. 285–300.

Lakshay Bolia

N. B.

Robust Scheduling for Large Scale Evacuation Planning. Socio-Economic Planning Sciences, Vol. 71, 2020, p. 100756.

Goerigk

Hamacher

H. W.

Kinscherff

Ranking Robustness and Its Application to Evacuation Planning. European Journal of Operational Research, Vol. 264, No. 3, 2018, pp. 837–846.

Ghasemi

Khalili-Damghani

Hafezalkotob

Raissi

Stochastic Optimization Model for Distribution and Evacuation Planning (A Case Study of Tehran Earthquake). Socio-Economic Planning Sciences, Vol. 71, 2020, p. 100745.

Goerigk

Grün

Heßler

Combining Bus Evacuation with Location Decisions: A Branch-and-Price Approach. Transportation Research Procedia, Vol. 2, 2014, pp. 783–791.

10.

Goerigk

Grün

Heßler

Branch and Bound Algorithms for the Bus Evacuation Problem. Computers and Operations Research, Vol. 40, No. 12, 2013, pp. 3010–3020.

11.

Goerigk

Deghdak

T’Kindt

A Two-Stage Robustness Approach to Evacuation Planning with Buses. Transportation Research Part B: Methodological, Vol. 78, 2015, pp. 66–82.

12.

Rodrigues

Borysov

S. S.

Ribeiro

Pereira

F. C.

A Bayesian Additive Model for Understanding Public Transport Usage in Special Events. IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 39, No. 11, 2017, pp. 2113–2126.

13.

Pereira

F. C.

Rodrigues

Ben-Akiva

Using Data from the Web to Predict Public Transport Arrivals under Special Events Scenarios. Journal of Intelligent Transportation Systems, Vol. 19, No. 3, 2015, pp. 273–288.

14.

Berrebi

S. J.

Watkins

K. E.

Laval

J. A.

A Real-Time Bus Dispatching Policy to Minimize Passenger Wait on a High Frequency Route. Transportation Research Part B-Methodological, Vol. 81, 2015, pp. 377–389.

15.

Liu

Ceder

Integrated Public Transport Timetable Synchronization and Vehicle Scheduling with Demand Assignment: A Bi-Objective Bi-Level Model Using Deficit Function Approach. Transportation Research Part B-Methodological, pp. 117, 2018, pp. 935–955.

16.

Chen

Liu

Zhu

Wang

Design of Limited-Stop Bus Service with Capacity Constraint and Stochastic Travel Time. Transportation Research Part E-Logistics and Transportation Review, Vol. 83, 2015, pp. 1–15.

17.

El-Geneidy

A. M.

Surprenant-Legault

Limited-Stop Bus Service: An Evaluation of an Implementation Strategy. Public Transport, Vol. 2, No. 4, 2010, pp. 291–306.

18.

Furth

P. G.

Zonal Route Design for Transit Corridors. Transportation Science, Vol. 20, No. 1, 1986, pp. 1–12.

19.

Jordan

W. C.

Turnquist

M. A.

Zone Scheduling of Bus Routes to Improve Service Reliability. Transportation Science, Vol. 13, No. 3, 1979, pp. 242–268.

20.

Ohlmann

J. W.

Fry

M. J.

Thomas

B. W.

Route Design for Lean Production Systems. Transportation Science, Vol. 42, No. 3, 2008, pp. 352–370.

21.

Ceder

Stern

H. I.

Deficit Function Bus Scheduling with Deadheading Trip Insertions for Fleet Size Reduction. Transportation Science, Vol. 15, No. 4, 1981, pp. 338–363.

22.

Furth

P. G.

Alternating Deadheading in Bus Route Operations. Transportation Science, Vol. 19, No. 1, pp. 13–28.

23.

Yang

Z. Z.

Real-Time Partway Deadheading Strategy Based on Transit Service Reliability Assessment. Transportation Research Part A-Policy and Practice, Vol. 46, No. 8, 2012, pp. 1265–1279.

24.

Liu

Yan

Bus Stop-Skipping Scheme with Random Travel Time. Transportation Research Part C-Emerging Technologies, Vol. 35, 2013, 46–56.

25.

Sun

Hickman

The Real-Time Stop-Skipping Problem. Journal of Intelligent Transportation Systems, Vol. 9, No. 2, 2005, pp. 91–109.

26.

Eberlein

X. J.

Wilson

N. H. M.

Barnhart

The Real-Time Deadheading Problem in Transit Operations Control. Transportation Research Part B-Methodological, Vol. 32, No. 2, 77–100.

27.

Ibarra-Rojas

O. J.

Rios-Solis

Y. A.

Synchronization of Bus Timetabling. Transportation Research Part B-Methodological, Vol. 46, No. 5, pp. 599–614.

28.

Ceder

Tal

Designing Synchonization into Bus Timetables. Transportation Research Record: Journal of the Transportation Research Board, 2001. 1760: 28–33.

29.

Eranki

A Model to Create Bus Timetables to Attain Maximum Synchronization Considering Waiting Times at Transfer Stops. Master thesis, University of South Florida, 2004.