# Shuttle Bus Rerouting and Rescheduling Problem considering Daily Demand Fluctuation

Authors: Yuqiang Wang; Pan Shang
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

In an urban shuttle system, shuttle buses need to pick up passengers waiting at predetermined stops according to their planned schedules (routes and timetables). However, in practice, passenger demand is unstable and has fluctuations, which means that passenger demand at a specific stop is likely to increase or decrease, causing low service quality, long passenger waiting times, and imbalanced utilization of bus capacity. Therefore, we introduce the shuttle bus rerouting and rescheduling strategy, based on which the operator can change the visited stops and arrival times of the shuttle buses and can operate backup buses to handle the passenger demand fluctuations. A three-dimensional space-time-state network is formulated to depict shuttle routes, timetables, and passenger-loading states, and the proposed problem can be formulated as a multicommodity network-flow optimization problem. To solve the model efficiently, we adopt the alternating direction method of multipliers (ADMM) decomposition method to decompose the original problem into several single shuttle routing subproblems. We test the model and algorithm in the 9-node network with three stops, and a larger scale Chicago sketch network is also adopted to demonstrate the effectiveness and efficiency of the proposed model and algorithm. The rerouting and rescheduling results for the Chicago case represent a 5.7% improvement relative to the results with the planned schedules.


---

## Body

## 1. Introduction

### 1.1. Motivation

With the development of the economy and cities, traffic congestion has become a serious phenomenon, and increasing attention is being paid to environmental traffic [1], so shuttle buses, which are also called buses in this paper, have become a major mode of commuting and travel mode for some citizens [2], for example, staff going to and from work, students going to and from school, and passengers going to and from airports. Many studies, such as Wang et al. [3]; Babaei and Rajabi-Bahaabadi [4]; Kim et al. [5] and Tong et al. [6], scheduled buses considering different situations, including traffic congestion, single destination, multiple destination, and customized bus service design, to generate well-designed bus routes and timetables and to improve service quality. To ensure security and comply with the traffic rules, the number of passengers must have an upper limit, which is called bus capacity. In addition, the bus capacity may decrease due to a specific time. For instance, during the epidemic caused by 2019-nCoV, government regulations limited the number of passengers a bus can carry to avoid contagion. In this context, shuttle bus rerouting and rescheduling must be implemented to reduce passenger density.In practice, public transportation systems are unstable and changeable due to unforeseen passenger flow. During the planning process, the operators determine the bus routes and shuttle bus timetable based on the average and estimated passenger flow to guarantee service. While the rerouting and rescheduling operation encounters oversaturated conditions because of the self-bus capacity limits and the capacity limits under specific policies, a temporary increase or decrease in passenger demand also affects bus schedules; in this case, if the bus follows the original routes, there must be some passengers that cannot board and some buses that have vacant seats leading to lower service quality and waste of capacity, respectively. Therefore, adjusting the original plan and generating rerouting and rescheduling strategies are important for addressing passenger demand fluctuation conditions when considering limited bus capacity. Figure1 shows the flowchart of the shuttle bus rerouting and rescheduling problem.Figure 1
Flowchart of the shuttle bus rerouting and rescheduling problem.


### 1.2. Literature Review

The bus/vehicle routing and timetable problem is based on the average demand of passengers or goods. The operators schedule the buses/vehicles to pick up the passengers or goods within or not within the time window, which is studied as vehicle routing problem with time window (VRPTW) or vehicle routing problem (VRP), respectively. Yu et al. [7] solved the VRP by an improved ant colony optimization which was a combination of the ant-weight strategy and a mutation operation. Ellegood et al. [8] proposed the continuous approximation models to evaluate the benefit of the mixed load school bus routes, and a semirural Missouri school district was adopted to test the model. Yao et al. [9] considered the VRPTW with time-dependent travel times. A space-time-state network-flow model is formulated to minimize the vehicle total costs, and the ADMM decomposition method was introduced to break the model symmetry and increase the quality of both primal and dual solution. Yan and Tang [10] proposed that previous studies scheduled buses with projected (or average) market share and demand, but passenger choice behaviors and uncertain market demands were used in this paper. Then, a nonlinear integer program and a solution algorithm were proposed and tested in Taiwan intercity operation. Ghilas et al. [11] studied the VRPTW to satisfy the demands. In order to solve the problem efficiently, an adaptive large neighborhood search heuristic algorithm was designed.However, in reality, the demand is not fixed, and the demand of some stops may increase or decrease unexpectedly. To provide high-quality service for users or operators when demand fluctuates, strategies such as the vehicle/bus rerouting and rescheduling are used. Moreover, traffic disruption can also have a significant influence on daily transportation, and the proposed strategies were also adopted in some studies. Cao and Ceder [2] proposed an approach to optimize the shuttle vehicle timetable and scheduling by using a skip-stop strategy considering real-time passenger demand in the single-depot bidirectional circle autonomous shuttle bus service route, which aimed to decrease the passenger total travel time and the number of shuttle buses in use. Liu et al. [12] proposed a model with three objectives that minimizes the total wait time, total in-vehicle time, and total operating time to generate an optimal stop-skipping plan or a deadhead plan. Then, a genetic algorithm incorporation Monte Carlo simulation was proposed to solve the model efficiently. Wang et al. [3] developed a bus rescheduling approach when traffic congestion occurred. The proposed approach generated vehicle timetables and rescheduled dynamically. Li and Ferguson [13] solved the vehicle rescheduling problem in disrupted transport network by augmenting the within-day replanning simulation model which means that the agents can adjust their day plans during a single day rather at the end of the day. Li et al. [14] proposed a vehicle rescheduling problem to minimize the operation delay for obtaining the optimal vehicle assignment and reassignment considering a single depot, and backup buses were used in this paper. Nikolić and Teodorović [15] found that one or more planned vehicle routes were not feasible when high demand emerged unexpectedly in some nodes. Then, a mathematical formulation of this problem was presented to reschedule vehicle routes by generating a new set of vehicle routes. In addition, Yin et al. [16], Bettinelli et al. [17], Espinosa-Aranda and García-Ródenas [18], Gao et al. [19], Altazin et al. [20], Niu et al. [21], and Zhu and Goverde [22] solved the problem of demand fluctuation or traffic disruption in the railway system, which can also provide suggestions for this paper.Table1 shows the comparison of the studies and this paper on vehicle/bus rerouting and rescheduling problem, including the objective of the model, the situation of the problem, and the solution algorithm. According to the previous studies, most of them considered the demand fluctuation from the aspect of the increasing demand, such as Nikolić and Teodorović [15], but this paper considers both the increasing and decreasing fluctuation demand, which is more realistic. Cao and Ceder [2], Liu et al. [12], Wang et al. [3], and Li et al. [14] solved the vehicle/bus rerouting and rescheduling problem without considering demand fluctuation. Besides, this paper introduces the state dimension in the space-time-state network to depict the number of real-time carrying passengers of the vehicle/bus, and this approach to demand is different from Cao and Ceder [2], Liu et al. [12], and Nikolić and Teodorović [15]. Furthermore, we design the ADMM-based decomposition method to improve the algorithm efficiency significantly, which was rarely used in the vehicle/bus rerouting and rescheduling problem.Table 1
Comparison of the previous studies and this paper on vehicle/bus rerouting and rescheduling.
StudyObjectiveSituationAlgorithmCao and Ceder [2]Minimize the total travel time and vehicle in useReal-time reschedulingGenetic algorithmLiu et al. [12]Minimizes the total wait time, total in-vehicle time, and total operating timeTraffic disruptionGenetic algorithmWang et al. [3]Minimize the operation costTraffic congestionGenetic algorithmLi et al. [14]Minimize the operation delayTraffic disruptionAuction-based algorithmNikolić and Teodorović [15]Minimize the transportation costDemand fluctuationBee colony optimization algorithmThis paperMinimize the total bus travel cost and the passenger delayDemand fluctuationADMM


### 1.3. Work and Structure of This Paper

In this paper, we aim to optimize the shuttle bus rerouting and rescheduling problem considering passenger demand fluctuation.The research works of this paper are as follows:(1)
In shuttle bus systems, considering passenger demand fluctuation, implementing original bus routes and timetables generated by average passenger demand may prevent passengers from boarding and leave some buses with vacant seats. Therefore, we propose the bus rerouting and rescheduling to adjust the bus routes and timetables and operate backup buses for increasing service quality and decreasing waste of capacity. The passengers waiting at their corresponding stops are rearranged optimally within the specific passenger boarding time window and arrive at the destination before the time limit.(2)
To solve the proposed model, we construct a three-dimensional space-time-state network based on the service network, where the space-time dimension depicts bus routes and timetables and the state dimension presents the number of passengers in real time. Then, the bus travel arcs, pick-up arcs, inbound arcs, outbound arcs, and drop-off arcs are built to describe bus operation, and the passenger pick-up time window and drop-off time window are also considered in the arcs. Based on this, we propose a time discretized multicommodity network-flow optimization model with side constraints for the shuttle bus rerouting and rescheduling problem. The passengers (as the users) waiting at each stop must be distributed to a specific bus (as the resource) and arrive at their destination optimally, and the buses must select a series of arcs with minimum cost.(3)
The proposed model is difficult to solve when applied to large-scale cases. Therefore, the alternating direction method of multipliers (ADMM) decomposition methods is adopted to relax the hard constraints (demand satisfaction constraint) into objectives. Because this technology introduces a quadratic term and leads to a nonlinear model, linearization technology is also used to linearize the quadratic term, and the original model can be decomposed into several space-time-state shortest-path-finding subproblems that can be solved by the designed dynamic programming algorithms. Finally, the proposed model and algorithm are applied to several cases to test their effectiveness and efficiency.The remainder of this paper is organized as follows. Section2 introduces the problem statement and the rerouting and rescheduling strategy based on the construction of the service network. Section 3 formulates the three-dimensional space-time-state network. A multicommodity flow optimization model for the shuttle bus rerouting and rescheduling problem is also built. Section 4 presents the alternating direction method of multipliers (ADMM) decomposition methods to solve the model efficiently. Section 5 optimizes a simple case with 15 nodes and a large-scale case based on a Chicago sketch road network using the proposed method. Section 6 concludes this paper.


## 1.1. Motivation

With the development of the economy and cities, traffic congestion has become a serious phenomenon, and increasing attention is being paid to environmental traffic [1], so shuttle buses, which are also called buses in this paper, have become a major mode of commuting and travel mode for some citizens [2], for example, staff going to and from work, students going to and from school, and passengers going to and from airports. Many studies, such as Wang et al. [3]; Babaei and Rajabi-Bahaabadi [4]; Kim et al. [5] and Tong et al. [6], scheduled buses considering different situations, including traffic congestion, single destination, multiple destination, and customized bus service design, to generate well-designed bus routes and timetables and to improve service quality. To ensure security and comply with the traffic rules, the number of passengers must have an upper limit, which is called bus capacity. In addition, the bus capacity may decrease due to a specific time. For instance, during the epidemic caused by 2019-nCoV, government regulations limited the number of passengers a bus can carry to avoid contagion. In this context, shuttle bus rerouting and rescheduling must be implemented to reduce passenger density.In practice, public transportation systems are unstable and changeable due to unforeseen passenger flow. During the planning process, the operators determine the bus routes and shuttle bus timetable based on the average and estimated passenger flow to guarantee service. While the rerouting and rescheduling operation encounters oversaturated conditions because of the self-bus capacity limits and the capacity limits under specific policies, a temporary increase or decrease in passenger demand also affects bus schedules; in this case, if the bus follows the original routes, there must be some passengers that cannot board and some buses that have vacant seats leading to lower service quality and waste of capacity, respectively. Therefore, adjusting the original plan and generating rerouting and rescheduling strategies are important for addressing passenger demand fluctuation conditions when considering limited bus capacity. Figure1 shows the flowchart of the shuttle bus rerouting and rescheduling problem.Figure 1
Flowchart of the shuttle bus rerouting and rescheduling problem.


## 1.2. Literature Review

The bus/vehicle routing and timetable problem is based on the average demand of passengers or goods. The operators schedule the buses/vehicles to pick up the passengers or goods within or not within the time window, which is studied as vehicle routing problem with time window (VRPTW) or vehicle routing problem (VRP), respectively. Yu et al. [7] solved the VRP by an improved ant colony optimization which was a combination of the ant-weight strategy and a mutation operation. Ellegood et al. [8] proposed the continuous approximation models to evaluate the benefit of the mixed load school bus routes, and a semirural Missouri school district was adopted to test the model. Yao et al. [9] considered the VRPTW with time-dependent travel times. A space-time-state network-flow model is formulated to minimize the vehicle total costs, and the ADMM decomposition method was introduced to break the model symmetry and increase the quality of both primal and dual solution. Yan and Tang [10] proposed that previous studies scheduled buses with projected (or average) market share and demand, but passenger choice behaviors and uncertain market demands were used in this paper. Then, a nonlinear integer program and a solution algorithm were proposed and tested in Taiwan intercity operation. Ghilas et al. [11] studied the VRPTW to satisfy the demands. In order to solve the problem efficiently, an adaptive large neighborhood search heuristic algorithm was designed.However, in reality, the demand is not fixed, and the demand of some stops may increase or decrease unexpectedly. To provide high-quality service for users or operators when demand fluctuates, strategies such as the vehicle/bus rerouting and rescheduling are used. Moreover, traffic disruption can also have a significant influence on daily transportation, and the proposed strategies were also adopted in some studies. Cao and Ceder [2] proposed an approach to optimize the shuttle vehicle timetable and scheduling by using a skip-stop strategy considering real-time passenger demand in the single-depot bidirectional circle autonomous shuttle bus service route, which aimed to decrease the passenger total travel time and the number of shuttle buses in use. Liu et al. [12] proposed a model with three objectives that minimizes the total wait time, total in-vehicle time, and total operating time to generate an optimal stop-skipping plan or a deadhead plan. Then, a genetic algorithm incorporation Monte Carlo simulation was proposed to solve the model efficiently. Wang et al. [3] developed a bus rescheduling approach when traffic congestion occurred. The proposed approach generated vehicle timetables and rescheduled dynamically. Li and Ferguson [13] solved the vehicle rescheduling problem in disrupted transport network by augmenting the within-day replanning simulation model which means that the agents can adjust their day plans during a single day rather at the end of the day. Li et al. [14] proposed a vehicle rescheduling problem to minimize the operation delay for obtaining the optimal vehicle assignment and reassignment considering a single depot, and backup buses were used in this paper. Nikolić and Teodorović [15] found that one or more planned vehicle routes were not feasible when high demand emerged unexpectedly in some nodes. Then, a mathematical formulation of this problem was presented to reschedule vehicle routes by generating a new set of vehicle routes. In addition, Yin et al. [16], Bettinelli et al. [17], Espinosa-Aranda and García-Ródenas [18], Gao et al. [19], Altazin et al. [20], Niu et al. [21], and Zhu and Goverde [22] solved the problem of demand fluctuation or traffic disruption in the railway system, which can also provide suggestions for this paper.Table1 shows the comparison of the studies and this paper on vehicle/bus rerouting and rescheduling problem, including the objective of the model, the situation of the problem, and the solution algorithm. According to the previous studies, most of them considered the demand fluctuation from the aspect of the increasing demand, such as Nikolić and Teodorović [15], but this paper considers both the increasing and decreasing fluctuation demand, which is more realistic. Cao and Ceder [2], Liu et al. [12], Wang et al. [3], and Li et al. [14] solved the vehicle/bus rerouting and rescheduling problem without considering demand fluctuation. Besides, this paper introduces the state dimension in the space-time-state network to depict the number of real-time carrying passengers of the vehicle/bus, and this approach to demand is different from Cao and Ceder [2], Liu et al. [12], and Nikolić and Teodorović [15]. Furthermore, we design the ADMM-based decomposition method to improve the algorithm efficiency significantly, which was rarely used in the vehicle/bus rerouting and rescheduling problem.Table 1
Comparison of the previous studies and this paper on vehicle/bus rerouting and rescheduling.
StudyObjectiveSituationAlgorithmCao and Ceder [2]Minimize the total travel time and vehicle in useReal-time reschedulingGenetic algorithmLiu et al. [12]Minimizes the total wait time, total in-vehicle time, and total operating timeTraffic disruptionGenetic algorithmWang et al. [3]Minimize the operation costTraffic congestionGenetic algorithmLi et al. [14]Minimize the operation delayTraffic disruptionAuction-based algorithmNikolić and Teodorović [15]Minimize the transportation costDemand fluctuationBee colony optimization algorithmThis paperMinimize the total bus travel cost and the passenger delayDemand fluctuationADMM


## 1.3. Work and Structure of This Paper

In this paper, we aim to optimize the shuttle bus rerouting and rescheduling problem considering passenger demand fluctuation.The research works of this paper are as follows:(1)
In shuttle bus systems, considering passenger demand fluctuation, implementing original bus routes and timetables generated by average passenger demand may prevent passengers from boarding and leave some buses with vacant seats. Therefore, we propose the bus rerouting and rescheduling to adjust the bus routes and timetables and operate backup buses for increasing service quality and decreasing waste of capacity. The passengers waiting at their corresponding stops are rearranged optimally within the specific passenger boarding time window and arrive at the destination before the time limit.(2)
To solve the proposed model, we construct a three-dimensional space-time-state network based on the service network, where the space-time dimension depicts bus routes and timetables and the state dimension presents the number of passengers in real time. Then, the bus travel arcs, pick-up arcs, inbound arcs, outbound arcs, and drop-off arcs are built to describe bus operation, and the passenger pick-up time window and drop-off time window are also considered in the arcs. Based on this, we propose a time discretized multicommodity network-flow optimization model with side constraints for the shuttle bus rerouting and rescheduling problem. The passengers (as the users) waiting at each stop must be distributed to a specific bus (as the resource) and arrive at their destination optimally, and the buses must select a series of arcs with minimum cost.(3)
The proposed model is difficult to solve when applied to large-scale cases. Therefore, the alternating direction method of multipliers (ADMM) decomposition methods is adopted to relax the hard constraints (demand satisfaction constraint) into objectives. Because this technology introduces a quadratic term and leads to a nonlinear model, linearization technology is also used to linearize the quadratic term, and the original model can be decomposed into several space-time-state shortest-path-finding subproblems that can be solved by the designed dynamic programming algorithms. Finally, the proposed model and algorithm are applied to several cases to test their effectiveness and efficiency.The remainder of this paper is organized as follows. Section2 introduces the problem statement and the rerouting and rescheduling strategy based on the construction of the service network. Section 3 formulates the three-dimensional space-time-state network. A multicommodity flow optimization model for the shuttle bus rerouting and rescheduling problem is also built. Section 4 presents the alternating direction method of multipliers (ADMM) decomposition methods to solve the model efficiently. Section 5 optimizes a simple case with 15 nodes and a large-scale case based on a Chicago sketch road network using the proposed method. Section 6 concludes this paper.


## 2. Problem Description

### 2.1. Service Network Construction for Shuttle Bus Rerouting and Rescheduling

In this section, we design a physical networkN,L for the urban shuttle bus system, where N is the node set and L is the link set. Each link can be defined as a direct link i,j∈L, which means that the bus can travel from node i∈N to node j∈N. To illustrate the network clearly, we take the example shown in Figure 2(a), which includes one bus depot node (node 7), one bus destination node (node 8), one backup bus depot node (node 9), six normal nodes (node 1–6), and three stops (stop 1–3) showed with triangles, and the passengers will wait for the shuttle buses at the stops. Considering that the physical network shown in Figure 2(a) only presents the structure of the network, the service process, such as picking up the passengers, cannot be depicted; therefore, we expand the physical network into the service network N,L, as shown in Figure 2(b). We transformed the stop in Figure 2(a) (stop 1) into a platform that includes the inbound link i,j∈Lin, pick-up link i,j∈Lp, outbound link i,j∈Lout, and drop-off link i,j∈Ld distinguished from the transportation link i,j∈Ltra, as shown in Figure 2(b), and an extra passenger pick-up time is introduced in the pick-up link, which means the travel time of the inbound link, pick-up link, and outbound link is larger than the travel time of corresponding transportation link. If there is some passenger demand between two normal nodes and the bus has vacant seats, then the bus will choose the platform (node 1 to node 12 to node 13 to node 3) to pick up the passengers. If there is some passenger demand between two normal nodes and the bus has no vacant seats, the bus will choose the transportation link (node 1 to node 3), and in addition, if there is no passenger demand, the bus will also choose the transportation link. For example, we set two buses to pick up the passengers at stop 1, stop 2, and stop 3, as shown in Figure 2(b). The node sequence of bus 1 is (7-2-10-11-5-1-12-13-3-8), and the node sequence of bus 2 is (7-2-4-14-15-3-8). The carrying state of the buses is also shown in Figure 2(b).Figure 2
The structure of the (a) physical network and (b) service network.
(a)(b)


### 2.2. Rerouting and Rescheduling Strategy to Deal with Daily Passenger Demand Fluctuations

Considering the passenger demand fluctuation, the average passenger demand may increase or decrease in a specific time, so some buses cannot carry any other passengers because of the saturated carrying capacity, and some buses may have more vacant seats compared to the planned scheme. Then, some stops may not need to be visited, and some stops may need other buses or extra buses to visit. Therefore, the rerouting and rescheduling strategy is presented to optimize the shuttle bus routes and timetable for higher service quality. Based on this, we present some examples to illustrate the advantages of the proposed methods.Figure3(a) shows the bus routes without any strategy and presents the stop plan and carrying state. Then, we set up two buses, and each bus carries at most three passengers. Buses 1 and 2 depart from the bus depot node and finally arrive at the bus destination node. During the entire travel process, the average passenger demand is satisfied through the planned schedule. However, passenger demand always fluctuates; if this happens, some passengers cannot be carried because of the limited capacity of each bus, leading to the worst service quality. For example, the passenger demand transforms from 1 to 2 at stop 1, from 2 to 1 at stop 2, and from 2 to 5 at stop 3. If the buses operate as scheduled, the satisfaction of passenger demand is shown in Figure 3(a); that is, four passengers at stop 3 cannot be carried and bus 2 has two vacant seats.Figure 3
The bus routes (a) without any strategy considering demand fluctuation and (b) with the rerouting and rescheduling strategy considering demand fluctuation.
(a)(b)In this paper, the operator can reroute the physical route of each bus to change their visited stops. In detail, when a bus reaches or will reach a full state (all seats are occupied) according to the planned schedule and passenger demand fluctuation, the bus can skip some stops and run to the following node, while the passengers waiting at the skipped stops can be picked up by the other unsaturated buses. As shown in Figure3(b), bus 1 can run directly from node 2 to node 1 instead of running from node 2 to node 5 to node 1, and then bus 1 picks up three passengers at stop 3 to finish the route. To pick up the passenger waiting at stop 1, which was skipped by bus 1, the operator should change the alternative route for bus 2 to visit stop 1.Considering that a large amount of passenger fluctuation may occur, the operator can reschedule the backup buses to satisfy the passenger demand. Backup buses are additional buses in the backup bus depot, and many studies, like Nikolić and Teodorović [15] and Li et al. [14], have adopted this method when demand fluctuations or unexpected disruptions occur at a specific time. In our study, the operator could directly reschedule additional backup buses with the operating cost from the backup bus depot node to pick up the temporarily increased passengers at the corresponding stops. As shown in Figure 3(b), bus 1 picks up three passengers at stop 3, but two passengers are left because of the limited capacity at stop 3. Then, an additional backup bus from the backup depot node can be scheduled to pick up the passenger waiting at stop 3.Table2 shows the result comparisons under no strategy and the proposed strategy. We set the travel time of each link, as shown in Table 3,, and the capacity of each bus is 3. Then, the bus travel cost can be calculated based on the node sequence, as shown in Figure 3. Moreover, we find that four passengers cannot be carried because of the limited capacity, leading to lower service quality, then two backup buses must be used to pick-up these passengers to satisfy the demand, and the added backup buses have an operating cost, which is set as 6. Based on this, the total cost without any strategy is 42, which is higher than the total cost of adopting the rerouting and rescheduling strategy.Table 2
Comparison between approaches with and without the strategy when considering fluctuating passenger demand.
SituationTravel costOperating cost of backup busesTotal costPlanned schedules301242Rerouting and rescheduling solution27633Table 3
The bus travel time of each link in the service network.
LinkTravel time(1, 2)3(1, 5)1(2, 1)3(2, 5)3(3, 1)3(3, 6)1(4, 2)3(4, 6)1(5, 1)1(5, 6)1(6, 3)1(7, 2)1(10, 11)2(12, 13)2(14, 15)2(1, 3)3(1, 12)1(2, 4)3(2, 10)1(3, 4)3(3, 8)1(4, 3)3(4, 14)1(5, 2)3(6, 5)1(6, 4)1(9, 1)1(11, 5)1(13, 3)1(15, 3)1


### 2.3. Problem Statement

In order to mitigate the effect of the demand fluctuation, the rerouting and rescheduling strategy are proposed and corresponding to the adjustment of the bus routes and the operation of the backup buses, respectively. The proposed service networkN,L is the basis of the rerouting and rescheduling problem. Each shuttle bus v∈V departs from the depot node or backup bus depot node ov∈N, then picks up the passengers at a stop, and finally arrives at the destination node dv∈N. Therefore, we consider the shuttle bus rerouting and rescheduling problem as a single destination problem, for example, a company commuting bus, school bus, and airport shuttle bus. We set the average passenger demand of the pick-up link i,j∈Lp as ni,j and the fluctuation in passenger demand as Δni,j. If Δni,j>0, the passenger demand increases; if Δni,j=0, the passenger demand does not change; and if Δni,j<0, the passenger demand decreases. Therefore, the passenger demand is ni,j+Δni,j when fluctuation occurs. The passenger demand of each pick-up link must be met by the shuttle buses at the bus arrival time si,j as determined by the planned timetable, and actually si,j presents the earliest arrival time of shuttle bus and the latest arrival time of passenger at pick-up link. Finally, the passengers will be dropped off before the time limit, such as the class bell time. However, because of the demand fluctuation, the passengers cannot be picked up punctually according to the adjusted timetable, and there must be a latest pick-up time ei,j for shuttle buses. Then, the pick-up time window si,j,ei,j is determined, which indicates that the passengers must be picked up within the pick-up time window si,j,ei,j. Moreover, the passengers will be preferentially assigned to the unsaturated bus which arrives earlier and within the pick-up time window si,j,ei,j. Considering that the carrying capacity of each bus is limited because of security and traffic rules, we assume that the number of maximum passengers is capv for each bus v, which denotes that the number of passengers in the bus cannot exceed capv. Therefore, we propose that the shuttle bus rerouting and rescheduling strategy can be adopted to improve service quality and minimize operating costs and passenger delay within a limited bus capacity. Figure 4 presents an example to describe the relationship between buses and passengers.Figure 4
The description of the relationship between buses and passengers.To summarize, the inputs of this paper are (1) the physical network, (2) the planned shuttle bus routes and timetable, (3) the fluctuation in passenger demand at each stop, (4) the OD of passenger demand, (5) the earliest arrival time of shuttle bus and the latest arrival time of passenger at pick-up link and the arrival time limit of each passenger, and (6) the planning horizon and several basic parameters, such as the cost of each arc and backup bus. The outputs of this paper are (1) the bus routes and (2) the bus timetable.


## 2.1. Service Network Construction for Shuttle Bus Rerouting and Rescheduling

In this section, we design a physical networkN,L for the urban shuttle bus system, where N is the node set and L is the link set. Each link can be defined as a direct link i,j∈L, which means that the bus can travel from node i∈N to node j∈N. To illustrate the network clearly, we take the example shown in Figure 2(a), which includes one bus depot node (node 7), one bus destination node (node 8), one backup bus depot node (node 9), six normal nodes (node 1–6), and three stops (stop 1–3) showed with triangles, and the passengers will wait for the shuttle buses at the stops. Considering that the physical network shown in Figure 2(a) only presents the structure of the network, the service process, such as picking up the passengers, cannot be depicted; therefore, we expand the physical network into the service network N,L, as shown in Figure 2(b). We transformed the stop in Figure 2(a) (stop 1) into a platform that includes the inbound link i,j∈Lin, pick-up link i,j∈Lp, outbound link i,j∈Lout, and drop-off link i,j∈Ld distinguished from the transportation link i,j∈Ltra, as shown in Figure 2(b), and an extra passenger pick-up time is introduced in the pick-up link, which means the travel time of the inbound link, pick-up link, and outbound link is larger than the travel time of corresponding transportation link. If there is some passenger demand between two normal nodes and the bus has vacant seats, then the bus will choose the platform (node 1 to node 12 to node 13 to node 3) to pick up the passengers. If there is some passenger demand between two normal nodes and the bus has no vacant seats, the bus will choose the transportation link (node 1 to node 3), and in addition, if there is no passenger demand, the bus will also choose the transportation link. For example, we set two buses to pick up the passengers at stop 1, stop 2, and stop 3, as shown in Figure 2(b). The node sequence of bus 1 is (7-2-10-11-5-1-12-13-3-8), and the node sequence of bus 2 is (7-2-4-14-15-3-8). The carrying state of the buses is also shown in Figure 2(b).Figure 2
The structure of the (a) physical network and (b) service network.
(a)(b)


## 2.2. Rerouting and Rescheduling Strategy to Deal with Daily Passenger Demand Fluctuations

Considering the passenger demand fluctuation, the average passenger demand may increase or decrease in a specific time, so some buses cannot carry any other passengers because of the saturated carrying capacity, and some buses may have more vacant seats compared to the planned scheme. Then, some stops may not need to be visited, and some stops may need other buses or extra buses to visit. Therefore, the rerouting and rescheduling strategy is presented to optimize the shuttle bus routes and timetable for higher service quality. Based on this, we present some examples to illustrate the advantages of the proposed methods.Figure3(a) shows the bus routes without any strategy and presents the stop plan and carrying state. Then, we set up two buses, and each bus carries at most three passengers. Buses 1 and 2 depart from the bus depot node and finally arrive at the bus destination node. During the entire travel process, the average passenger demand is satisfied through the planned schedule. However, passenger demand always fluctuates; if this happens, some passengers cannot be carried because of the limited capacity of each bus, leading to the worst service quality. For example, the passenger demand transforms from 1 to 2 at stop 1, from 2 to 1 at stop 2, and from 2 to 5 at stop 3. If the buses operate as scheduled, the satisfaction of passenger demand is shown in Figure 3(a); that is, four passengers at stop 3 cannot be carried and bus 2 has two vacant seats.Figure 3
The bus routes (a) without any strategy considering demand fluctuation and (b) with the rerouting and rescheduling strategy considering demand fluctuation.
(a)(b)In this paper, the operator can reroute the physical route of each bus to change their visited stops. In detail, when a bus reaches or will reach a full state (all seats are occupied) according to the planned schedule and passenger demand fluctuation, the bus can skip some stops and run to the following node, while the passengers waiting at the skipped stops can be picked up by the other unsaturated buses. As shown in Figure3(b), bus 1 can run directly from node 2 to node 1 instead of running from node 2 to node 5 to node 1, and then bus 1 picks up three passengers at stop 3 to finish the route. To pick up the passenger waiting at stop 1, which was skipped by bus 1, the operator should change the alternative route for bus 2 to visit stop 1.Considering that a large amount of passenger fluctuation may occur, the operator can reschedule the backup buses to satisfy the passenger demand. Backup buses are additional buses in the backup bus depot, and many studies, like Nikolić and Teodorović [15] and Li et al. [14], have adopted this method when demand fluctuations or unexpected disruptions occur at a specific time. In our study, the operator could directly reschedule additional backup buses with the operating cost from the backup bus depot node to pick up the temporarily increased passengers at the corresponding stops. As shown in Figure 3(b), bus 1 picks up three passengers at stop 3, but two passengers are left because of the limited capacity at stop 3. Then, an additional backup bus from the backup depot node can be scheduled to pick up the passenger waiting at stop 3.Table2 shows the result comparisons under no strategy and the proposed strategy. We set the travel time of each link, as shown in Table 3,, and the capacity of each bus is 3. Then, the bus travel cost can be calculated based on the node sequence, as shown in Figure 3. Moreover, we find that four passengers cannot be carried because of the limited capacity, leading to lower service quality, then two backup buses must be used to pick-up these passengers to satisfy the demand, and the added backup buses have an operating cost, which is set as 6. Based on this, the total cost without any strategy is 42, which is higher than the total cost of adopting the rerouting and rescheduling strategy.Table 2
Comparison between approaches with and without the strategy when considering fluctuating passenger demand.
SituationTravel costOperating cost of backup busesTotal costPlanned schedules301242Rerouting and rescheduling solution27633Table 3
The bus travel time of each link in the service network.
LinkTravel time(1, 2)3(1, 5)1(2, 1)3(2, 5)3(3, 1)3(3, 6)1(4, 2)3(4, 6)1(5, 1)1(5, 6)1(6, 3)1(7, 2)1(10, 11)2(12, 13)2(14, 15)2(1, 3)3(1, 12)1(2, 4)3(2, 10)1(3, 4)3(3, 8)1(4, 3)3(4, 14)1(5, 2)3(6, 5)1(6, 4)1(9, 1)1(11, 5)1(13, 3)1(15, 3)1


## 2.3. Problem Statement

In order to mitigate the effect of the demand fluctuation, the rerouting and rescheduling strategy are proposed and corresponding to the adjustment of the bus routes and the operation of the backup buses, respectively. The proposed service networkN,L is the basis of the rerouting and rescheduling problem. Each shuttle bus v∈V departs from the depot node or backup bus depot node ov∈N, then picks up the passengers at a stop, and finally arrives at the destination node dv∈N. Therefore, we consider the shuttle bus rerouting and rescheduling problem as a single destination problem, for example, a company commuting bus, school bus, and airport shuttle bus. We set the average passenger demand of the pick-up link i,j∈Lp as ni,j and the fluctuation in passenger demand as Δni,j. If Δni,j>0, the passenger demand increases; if Δni,j=0, the passenger demand does not change; and if Δni,j<0, the passenger demand decreases. Therefore, the passenger demand is ni,j+Δni,j when fluctuation occurs. The passenger demand of each pick-up link must be met by the shuttle buses at the bus arrival time si,j as determined by the planned timetable, and actually si,j presents the earliest arrival time of shuttle bus and the latest arrival time of passenger at pick-up link. Finally, the passengers will be dropped off before the time limit, such as the class bell time. However, because of the demand fluctuation, the passengers cannot be picked up punctually according to the adjusted timetable, and there must be a latest pick-up time ei,j for shuttle buses. Then, the pick-up time window si,j,ei,j is determined, which indicates that the passengers must be picked up within the pick-up time window si,j,ei,j. Moreover, the passengers will be preferentially assigned to the unsaturated bus which arrives earlier and within the pick-up time window si,j,ei,j. Considering that the carrying capacity of each bus is limited because of security and traffic rules, we assume that the number of maximum passengers is capv for each bus v, which denotes that the number of passengers in the bus cannot exceed capv. Therefore, we propose that the shuttle bus rerouting and rescheduling strategy can be adopted to improve service quality and minimize operating costs and passenger delay within a limited bus capacity. Figure 4 presents an example to describe the relationship between buses and passengers.Figure 4
The description of the relationship between buses and passengers.To summarize, the inputs of this paper are (1) the physical network, (2) the planned shuttle bus routes and timetable, (3) the fluctuation in passenger demand at each stop, (4) the OD of passenger demand, (5) the earliest arrival time of shuttle bus and the latest arrival time of passenger at pick-up link and the arrival time limit of each passenger, and (6) the planning horizon and several basic parameters, such as the cost of each arc and backup bus. The outputs of this paper are (1) the bus routes and (2) the bus timetable.


## 3. Space-Time-State Network Representation and the Optimization Model

### 3.1. Space-Time-State Network Representation

To express and solve the problem easily, a three-dimensional space-time-state network introduced in Shang et al. [23] and Mahmoudi and Zhou [24] is formulated to depict the bus routes, timetable and carrying states. Based on the service network presented in Section 2, we introduce the time dimension and the node i that can be expanded into vertex i,t, where t∈1,2,…,T′, the travel link i,j can be expanded into arc i,j,t,s denoting a bus traveling from node i at time t to node j at time s, and travel time is s−t. Then, the state dimension is also introduced to depict the bus carrying state, and vertex i,t can be expanded into vertex i,t,w, where w depicts the number of carrying passengers in the bus at node i at time t. It should be noted that the value of w in the depot node and destination node is 0; we call these states the initial state wo and the final state wd, and the value of w cannot exceed the bus capacity. Accordingly, arc i,j,t,s can be expanded into i,j,t,s.w,w′∈A, denoting that the bus travels from node i at time t with w passengers to node j at time s with w′ passengers. Figure 5(a) shows the space-time-state network of bus 1 with the planned schedule presented in Section 2.1. Then, the rerouting strategy is adopted, and the adjusted space-time-state network of bus 1 is shown in Figure 5(b). We find that stop 1 is skipped by bus 1. In order to depict the bus routes precisely and clearly, we constructed six kinds of arcs:(1)
Transportation arcsi,j,t,s,w,w∈Atra: For arcs without passenger demand, the passenger carrying state in i,t is equal to the passenger carrying state in j,s(2)
Inbound arcsi,j,t,s,w,w∈Ain: Arcs entering the pick-up arcs(3)
Pick-up arcsi,j,t,s,w,w′∈Ap: Arcs with passenger demand, buses will carry w′−w passengers in pick-up arcs, and an extra pick-up time is included in the pick-up arcs travel time s−t(4)
Outbound arcsi,j,t,s,w,w∈Aout: Arcs departing from the pick-up arcs(5)
Bus waiting arcsi,j,t,t+1,w,w∈Ain: Arcs for bus waiting at the bus depot and destination(6)
Drop-off arcsi,j,t,s,w,wd∈Ad: Arcs connecting to the destination node for buses dropping off the passengers, and the carrying state decreases from w to 0Figure 5
The space-time-state network of bus 1: (a) planned schedule and (b) rerouting and rescheduling solution.
(a)(b)Table4 shows the indices, sets, parameters, and variables used in this paper.Table 4
Notations used in this paper.
NotationsDefinitionIndicesi,jIndex of nodes in the service network,i,j∈Ni,jIndex of links in the service network,i,j∈Lt,s,t′,s′Index of time intervals,t,s,t′,s′∈Tw,w′Index of passenger carrying state,w,w′∈Wi,t,wIndex of vertices in space-time-state networkvIndex of buses,v∈Va,i,j,t,s,w,w′Index of arcs in the space-time-state network,a,i,j,t,s,w,w′∈ASetsNSet of nodes in the service networkLSet of links in the service networkTSet of time intervals in the study time horizonVSet of busesVnSet of normal busesVbSet of backup busesASet of arcs in the space-time-state networkWSet of states in the space-time-state networkLin,Lp,Lout,Ltra,LdSet of inbound links, pick-up links, outbound links, transportation links, and drop-off links in the physical network,Lin,Lp,Lout,Ltra,Ld⊂L, respectively.Ain,Ap,Aout,Atra,AdSet of inbound arcs, pick-up arcs, outbound arcs, transportation arcs, and drop-off arcs in the space-time-state network,Ain,Ap,Aout,Atra,Ad⊂A, respectively.Parametersni,jThe average passenger demand at pick-up linklΔni,jThe passenger demand fluctuation at pick-up linklovThe origin of shuttle busvdvThe destination of shuttle busvDEPvThe departure time of shuttle busv at the depot nodeARRvThe arrival time of shuttle busv at the destination nodewoThe initial state of a shuttle buswdThe final state of a shuttle busT′The time horizon of the space-time-state networkTTeThe latest bus arrival time at destinationTTaThe earliest bus arrival time at destinationsi,j,ei,jThe pick-up time window in the pick-up linki,j∈LpcapvThe capacity of busvci,j,t,s,w,w′Cost of arci,j,t,s,w,w′ci,j,t,s,w,w′vCost of busv in arc i,j,t,s,w,w′πThe operating cost of backup busesπ′The cost of the unused backup busesVariablesxi,j,t,s,w,w′vIf arci,j,t,s,w,w′ is selected by bus v = 1; otherwise, v = 0


### 3.2. Details in the Space-Time-State Network Construction

#### 3.2.1. Passenger Pick-Up Activities and Time Windows

In the shuttle bus system, the passengers should be picked up at the scheduled timesi,j. However, because of the demand fluctuation and considering traffic delays, the bus may not arrive at the stop on time. Then, we set the latest picking up time ei,j denoting that the passengers must be picked up before ei,j. In detail, if there is passenger demand ni,j+Δni,j at the pick-up links, the passengers must be picked up within the time window si,j,ei,j, which implies that the start time of the pick-up arc i,j,t,s,w,w′∈Ap must be within the time window si,j,ei,j or si,j≤t≤ei,j. The number of carried passengers increases, reflected by w′>w. For example, in Figure 5(b), the demand time window at stop 3 is 6,8, so bus 1 selects the pick-up arc 12,13,7,8,0,3.


#### 3.2.2. Passenger Drop-Off Activities and Time Windows

In this paper, we solve a single destination problem by the rerouting and rescheduling strategy in a shuttle bus system. Passengers should arrive at the same destination before the arrival time limitTTe, such as the class bell time and clock-in time in the network. In addition, considering passenger feelings and the actual situation, the passenger should not arrive at the destination too early, so an earliest arrival time TTa at the destination is also set. In detail, the bus should finish travel within the time window TTa,TTe, which implies that the end time s of the drop-off arc i,j,t,s,w,wd∈Ad is within the time window TTa,TTe, which is TTe≤s≤TTa. In addition, passengers are dropped off in the drop-off arc; accordingly, the value of the end carrying state w′ transforms to wd=0. For instance, in Figure 5(b), we set the earliest arrival time TTa,=10 and the time limit TTe=12, and then the drop-off arc 3,8,10,11,3,0 is selected.


#### 3.2.3. Shuttle Bus Capacity

Bus capacity is an important element in transportation optimization. Some studies, such as Szeto and Jiang [25], consider the bus capacity as a soft constraint, which means that passengers can stand when all seats are occupied. Some studies, such as Mahmoudi and Zhou [24], consider the bus capacity as a hard constraint, which means that passengers cannot enter the bus when all seats are occupied. In this paper, considering security and service quality, we hold the latter constraint. The capacity of each bus v is capv, and the carrying state w,w′ can never be larger than capv, or w,w′≤capv. For example, in Figure 5(b), bus 1 can carry three passengers at most, so the remaining passengers at stop 3 are carried by backup bus 1 instead of bus 1.


#### 3.2.4. Backup Bus Scheduling Cost and Penalty of Unsatisfied Demand

In the shuttle bus system, the average passenger demand may fluctuate, and some passengers may fail to enter the bus because of the limited capacity. Therefore, in order to satisfy all the passenger demand, the backup buses should be used to pick up the remaining passengers. Considering that scheduling new backup buses will add operating costs, we setπ to denote the operating cost for each backup bus. Corresponding to the backup bus cost in the space-time-state network, we set the arc cost that connects the backup bus depot as π, as shown in equation (1a). Once arc ov,j,DEPv,s,wo,wd is selected, the backup bus attaches an operation cost π. To provide feasible rerouting and rescheduling results, we build a dummy arc ov,dv,DEPv,ARRv,wo,wd for each shuttle backup bus v∈Vb, which means that the backup bus v∈Vb is not operated when the dummy arc is selected, and the value of the cov,dv,DEPv,ARRv,wo,wd denotes the cost of the backup bus which is not used shown in equation (1b).(1a)cov,j,DEPv,s,wo,wd=πv∈Vb.(1b)cov,dv,DEPv,ARRv,wo,wd=π′v∈Vb.Moreover, to ensure the passenger service quality, a penalty is applied for passengers who cannot enter the bus. In this paper, for practicality, we assume that all passengers require service. When the existing buses have no vacant seats and there are also a certain number of passengers remaining at their stops, a backup bus will operate to pick up the remaining passengers regardless of the number of remaining passengers at each stop, so the penalty of unsatisfied demand is unified with the backup bus operating cost.


#### 3.2.5. Deviation from the Planned Schedules

In the shuttle bus rerouting and rescheduling problem, the shuttle bus may be late when the travel route is changed. Therefore, in this paper, we introduce the deviation between the rescheduled and planned timetable into the objective to minimize the passenger waiting time. The arc cost isci,j,t,s,w,w′ when the arc is not the pick-up arc, and the arc cost is ci,j,t,s,w,w′ with the deviation t−sl when the selected arc is the pick-up arc which is(2)ci,j,t,s,w,w′v=ci,j,t,s,w,w′i,j,t,s,w,w′∉Aporxi,j,t,s,w,w′v=0,ci,j,t,s,w,w′+t−si,ji,j,t,s,w,w′∈Api,j∈Lp,xi,j,t,s,w,w′v=1.


### 3.3. Model Formulation

According to the space-time-state network, the bus routes, bus timetable, and bus carrying state can be presented. To increase the bus service quality and decrease the passenger travel time, we formulate a multicommodity network-flow programming model in the shuttle bus rerouting and rescheduling problem.


#### 3.3.1. Objective Function

The objective of the proposed model is to minimize the total bus travel cost and the passenger delay, as shown in equation (3). The bus departure time xi,j,t,s,w,w′v×t is always after the scheduled time si,j when pick-up arc i,j,t,s,w,w′∈Ap is selected because the bus cannot pick-up the passengers at pick-up link i,j when the bus departs before si,j. Therefore, the passenger delay term xi,j,t,s,w,w′vt−si,j is always larger than 0:(3)minO=∑v∈V∑i,j,t,s,w,w′∈Axi,j,t,s,w,w′v×ci,j,t,s,w,w′v.


#### 3.3.2. Bus Flow Balance Constraint

The shuttle bus should be generated from its originov,DEPv,woin the space-time-state network which can be presented as(4)∑i,j,t,s,w,w′∈Axi,j,t,s,w,w′v=1i=ov,t=DEPv,w=wo,w′∈W∀v∈V.The shuttle bus should end the trip at its destinationdv,ARRv,wd, in the space-time-state network which can be presented as(5)∑i,j,t,s,w,w′∈Axi,j,t,s,w,w′v=1j=dv,s=ARRv,w∈W,w′=wd∀v∈V.The bus flow should be balanced at the intermediate vertexi,t,w, which means that the number of entering buses is equal to the number of departing buses at i,t,w shown in equation (6). Therefore, equations (4)–(6) show the bus flow balance constraint, which is also introduced in the studies of Shang et al. [26] and Wang et al. [27] as(6)∑j,s,w′xi,j,t,s,w,w'v−∑j′,s′,w'′xj′,i,s′,t,w'′,wv=0i,t,w∉ov,DEPv,wo,dv,ARRv,wd,∀v∈V.


#### 3.3.3. Demand Satisfaction Constraint

The passenger demandni,j+Δni,j must be met in the pick-up arc i,j,t,s,w,w′∈Ap by a specific bus, which can be shown as equation (7), in the space-time-state network. It should be noted that the pick-up arcs i,j,t,s,w,w′ are only built when si,j≤t≤ei,j, which guarantees the passengers can only be carried within the pick-up time window as(7)∑v∈V∑i,j,t,s,w,w′∈Apxi,j,t,s,w,w′v×w′−w=ni,j+Δni,j∀i,j∈Lp.


#### 3.3.4. Binary Variable Definition

A binary variable is shown in equation (8); if bus v selects arc i,j,t,s,w,w′, xi,j,t,s,w,w′v=1; otherwise, xi,j,t,s,w,w′v=0.(8)xi,j,t,s,w,w′v∈0,1∀i,j,t,s,w,w′∈A,∀v∈V.


## 3.1. Space-Time-State Network Representation

To express and solve the problem easily, a three-dimensional space-time-state network introduced in Shang et al. [23] and Mahmoudi and Zhou [24] is formulated to depict the bus routes, timetable and carrying states. Based on the service network presented in Section 2, we introduce the time dimension and the node i that can be expanded into vertex i,t, where t∈1,2,…,T′, the travel link i,j can be expanded into arc i,j,t,s denoting a bus traveling from node i at time t to node j at time s, and travel time is s−t. Then, the state dimension is also introduced to depict the bus carrying state, and vertex i,t can be expanded into vertex i,t,w, where w depicts the number of carrying passengers in the bus at node i at time t. It should be noted that the value of w in the depot node and destination node is 0; we call these states the initial state wo and the final state wd, and the value of w cannot exceed the bus capacity. Accordingly, arc i,j,t,s can be expanded into i,j,t,s.w,w′∈A, denoting that the bus travels from node i at time t with w passengers to node j at time s with w′ passengers. Figure 5(a) shows the space-time-state network of bus 1 with the planned schedule presented in Section 2.1. Then, the rerouting strategy is adopted, and the adjusted space-time-state network of bus 1 is shown in Figure 5(b). We find that stop 1 is skipped by bus 1. In order to depict the bus routes precisely and clearly, we constructed six kinds of arcs:(1)
Transportation arcsi,j,t,s,w,w∈Atra: For arcs without passenger demand, the passenger carrying state in i,t is equal to the passenger carrying state in j,s(2)
Inbound arcsi,j,t,s,w,w∈Ain: Arcs entering the pick-up arcs(3)
Pick-up arcsi,j,t,s,w,w′∈Ap: Arcs with passenger demand, buses will carry w′−w passengers in pick-up arcs, and an extra pick-up time is included in the pick-up arcs travel time s−t(4)
Outbound arcsi,j,t,s,w,w∈Aout: Arcs departing from the pick-up arcs(5)
Bus waiting arcsi,j,t,t+1,w,w∈Ain: Arcs for bus waiting at the bus depot and destination(6)
Drop-off arcsi,j,t,s,w,wd∈Ad: Arcs connecting to the destination node for buses dropping off the passengers, and the carrying state decreases from w to 0Figure 5
The space-time-state network of bus 1: (a) planned schedule and (b) rerouting and rescheduling solution.
(a)(b)Table4 shows the indices, sets, parameters, and variables used in this paper.Table 4
Notations used in this paper.
NotationsDefinitionIndicesi,jIndex of nodes in the service network,i,j∈Ni,jIndex of links in the service network,i,j∈Lt,s,t′,s′Index of time intervals,t,s,t′,s′∈Tw,w′Index of passenger carrying state,w,w′∈Wi,t,wIndex of vertices in space-time-state networkvIndex of buses,v∈Va,i,j,t,s,w,w′Index of arcs in the space-time-state network,a,i,j,t,s,w,w′∈ASetsNSet of nodes in the service networkLSet of links in the service networkTSet of time intervals in the study time horizonVSet of busesVnSet of normal busesVbSet of backup busesASet of arcs in the space-time-state networkWSet of states in the space-time-state networkLin,Lp,Lout,Ltra,LdSet of inbound links, pick-up links, outbound links, transportation links, and drop-off links in the physical network,Lin,Lp,Lout,Ltra,Ld⊂L, respectively.Ain,Ap,Aout,Atra,AdSet of inbound arcs, pick-up arcs, outbound arcs, transportation arcs, and drop-off arcs in the space-time-state network,Ain,Ap,Aout,Atra,Ad⊂A, respectively.Parametersni,jThe average passenger demand at pick-up linklΔni,jThe passenger demand fluctuation at pick-up linklovThe origin of shuttle busvdvThe destination of shuttle busvDEPvThe departure time of shuttle busv at the depot nodeARRvThe arrival time of shuttle busv at the destination nodewoThe initial state of a shuttle buswdThe final state of a shuttle busT′The time horizon of the space-time-state networkTTeThe latest bus arrival time at destinationTTaThe earliest bus arrival time at destinationsi,j,ei,jThe pick-up time window in the pick-up linki,j∈LpcapvThe capacity of busvci,j,t,s,w,w′Cost of arci,j,t,s,w,w′ci,j,t,s,w,w′vCost of busv in arc i,j,t,s,w,w′πThe operating cost of backup busesπ′The cost of the unused backup busesVariablesxi,j,t,s,w,w′vIf arci,j,t,s,w,w′ is selected by bus v = 1; otherwise, v = 0


## 3.2. Details in the Space-Time-State Network Construction

### 3.2.1. Passenger Pick-Up Activities and Time Windows

In the shuttle bus system, the passengers should be picked up at the scheduled timesi,j. However, because of the demand fluctuation and considering traffic delays, the bus may not arrive at the stop on time. Then, we set the latest picking up time ei,j denoting that the passengers must be picked up before ei,j. In detail, if there is passenger demand ni,j+Δni,j at the pick-up links, the passengers must be picked up within the time window si,j,ei,j, which implies that the start time of the pick-up arc i,j,t,s,w,w′∈Ap must be within the time window si,j,ei,j or si,j≤t≤ei,j. The number of carried passengers increases, reflected by w′>w. For example, in Figure 5(b), the demand time window at stop 3 is 6,8, so bus 1 selects the pick-up arc 12,13,7,8,0,3.


### 3.2.2. Passenger Drop-Off Activities and Time Windows

In this paper, we solve a single destination problem by the rerouting and rescheduling strategy in a shuttle bus system. Passengers should arrive at the same destination before the arrival time limitTTe, such as the class bell time and clock-in time in the network. In addition, considering passenger feelings and the actual situation, the passenger should not arrive at the destination too early, so an earliest arrival time TTa at the destination is also set. In detail, the bus should finish travel within the time window TTa,TTe, which implies that the end time s of the drop-off arc i,j,t,s,w,wd∈Ad is within the time window TTa,TTe, which is TTe≤s≤TTa. In addition, passengers are dropped off in the drop-off arc; accordingly, the value of the end carrying state w′ transforms to wd=0. For instance, in Figure 5(b), we set the earliest arrival time TTa,=10 and the time limit TTe=12, and then the drop-off arc 3,8,10,11,3,0 is selected.


### 3.2.3. Shuttle Bus Capacity

Bus capacity is an important element in transportation optimization. Some studies, such as Szeto and Jiang [25], consider the bus capacity as a soft constraint, which means that passengers can stand when all seats are occupied. Some studies, such as Mahmoudi and Zhou [24], consider the bus capacity as a hard constraint, which means that passengers cannot enter the bus when all seats are occupied. In this paper, considering security and service quality, we hold the latter constraint. The capacity of each bus v is capv, and the carrying state w,w′ can never be larger than capv, or w,w′≤capv. For example, in Figure 5(b), bus 1 can carry three passengers at most, so the remaining passengers at stop 3 are carried by backup bus 1 instead of bus 1.


### 3.2.4. Backup Bus Scheduling Cost and Penalty of Unsatisfied Demand

In the shuttle bus system, the average passenger demand may fluctuate, and some passengers may fail to enter the bus because of the limited capacity. Therefore, in order to satisfy all the passenger demand, the backup buses should be used to pick up the remaining passengers. Considering that scheduling new backup buses will add operating costs, we setπ to denote the operating cost for each backup bus. Corresponding to the backup bus cost in the space-time-state network, we set the arc cost that connects the backup bus depot as π, as shown in equation (1a). Once arc ov,j,DEPv,s,wo,wd is selected, the backup bus attaches an operation cost π. To provide feasible rerouting and rescheduling results, we build a dummy arc ov,dv,DEPv,ARRv,wo,wd for each shuttle backup bus v∈Vb, which means that the backup bus v∈Vb is not operated when the dummy arc is selected, and the value of the cov,dv,DEPv,ARRv,wo,wd denotes the cost of the backup bus which is not used shown in equation (1b).(1a)cov,j,DEPv,s,wo,wd=πv∈Vb.(1b)cov,dv,DEPv,ARRv,wo,wd=π′v∈Vb.Moreover, to ensure the passenger service quality, a penalty is applied for passengers who cannot enter the bus. In this paper, for practicality, we assume that all passengers require service. When the existing buses have no vacant seats and there are also a certain number of passengers remaining at their stops, a backup bus will operate to pick up the remaining passengers regardless of the number of remaining passengers at each stop, so the penalty of unsatisfied demand is unified with the backup bus operating cost.


### 3.2.5. Deviation from the Planned Schedules

In the shuttle bus rerouting and rescheduling problem, the shuttle bus may be late when the travel route is changed. Therefore, in this paper, we introduce the deviation between the rescheduled and planned timetable into the objective to minimize the passenger waiting time. The arc cost isci,j,t,s,w,w′ when the arc is not the pick-up arc, and the arc cost is ci,j,t,s,w,w′ with the deviation t−sl when the selected arc is the pick-up arc which is(2)ci,j,t,s,w,w′v=ci,j,t,s,w,w′i,j,t,s,w,w′∉Aporxi,j,t,s,w,w′v=0,ci,j,t,s,w,w′+t−si,ji,j,t,s,w,w′∈Api,j∈Lp,xi,j,t,s,w,w′v=1.


## 3.2.1. Passenger Pick-Up Activities and Time Windows

In the shuttle bus system, the passengers should be picked up at the scheduled timesi,j. However, because of the demand fluctuation and considering traffic delays, the bus may not arrive at the stop on time. Then, we set the latest picking up time ei,j denoting that the passengers must be picked up before ei,j. In detail, if there is passenger demand ni,j+Δni,j at the pick-up links, the passengers must be picked up within the time window si,j,ei,j, which implies that the start time of the pick-up arc i,j,t,s,w,w′∈Ap must be within the time window si,j,ei,j or si,j≤t≤ei,j. The number of carried passengers increases, reflected by w′>w. For example, in Figure 5(b), the demand time window at stop 3 is 6,8, so bus 1 selects the pick-up arc 12,13,7,8,0,3.


## 3.2.2. Passenger Drop-Off Activities and Time Windows

In this paper, we solve a single destination problem by the rerouting and rescheduling strategy in a shuttle bus system. Passengers should arrive at the same destination before the arrival time limitTTe, such as the class bell time and clock-in time in the network. In addition, considering passenger feelings and the actual situation, the passenger should not arrive at the destination too early, so an earliest arrival time TTa at the destination is also set. In detail, the bus should finish travel within the time window TTa,TTe, which implies that the end time s of the drop-off arc i,j,t,s,w,wd∈Ad is within the time window TTa,TTe, which is TTe≤s≤TTa. In addition, passengers are dropped off in the drop-off arc; accordingly, the value of the end carrying state w′ transforms to wd=0. For instance, in Figure 5(b), we set the earliest arrival time TTa,=10 and the time limit TTe=12, and then the drop-off arc 3,8,10,11,3,0 is selected.


## 3.2.3. Shuttle Bus Capacity

Bus capacity is an important element in transportation optimization. Some studies, such as Szeto and Jiang [25], consider the bus capacity as a soft constraint, which means that passengers can stand when all seats are occupied. Some studies, such as Mahmoudi and Zhou [24], consider the bus capacity as a hard constraint, which means that passengers cannot enter the bus when all seats are occupied. In this paper, considering security and service quality, we hold the latter constraint. The capacity of each bus v is capv, and the carrying state w,w′ can never be larger than capv, or w,w′≤capv. For example, in Figure 5(b), bus 1 can carry three passengers at most, so the remaining passengers at stop 3 are carried by backup bus 1 instead of bus 1.


## 3.2.4. Backup Bus Scheduling Cost and Penalty of Unsatisfied Demand

In the shuttle bus system, the average passenger demand may fluctuate, and some passengers may fail to enter the bus because of the limited capacity. Therefore, in order to satisfy all the passenger demand, the backup buses should be used to pick up the remaining passengers. Considering that scheduling new backup buses will add operating costs, we setπ to denote the operating cost for each backup bus. Corresponding to the backup bus cost in the space-time-state network, we set the arc cost that connects the backup bus depot as π, as shown in equation (1a). Once arc ov,j,DEPv,s,wo,wd is selected, the backup bus attaches an operation cost π. To provide feasible rerouting and rescheduling results, we build a dummy arc ov,dv,DEPv,ARRv,wo,wd for each shuttle backup bus v∈Vb, which means that the backup bus v∈Vb is not operated when the dummy arc is selected, and the value of the cov,dv,DEPv,ARRv,wo,wd denotes the cost of the backup bus which is not used shown in equation (1b).(1a)cov,j,DEPv,s,wo,wd=πv∈Vb.(1b)cov,dv,DEPv,ARRv,wo,wd=π′v∈Vb.Moreover, to ensure the passenger service quality, a penalty is applied for passengers who cannot enter the bus. In this paper, for practicality, we assume that all passengers require service. When the existing buses have no vacant seats and there are also a certain number of passengers remaining at their stops, a backup bus will operate to pick up the remaining passengers regardless of the number of remaining passengers at each stop, so the penalty of unsatisfied demand is unified with the backup bus operating cost.


## 3.2.5. Deviation from the Planned Schedules

In the shuttle bus rerouting and rescheduling problem, the shuttle bus may be late when the travel route is changed. Therefore, in this paper, we introduce the deviation between the rescheduled and planned timetable into the objective to minimize the passenger waiting time. The arc cost isci,j,t,s,w,w′ when the arc is not the pick-up arc, and the arc cost is ci,j,t,s,w,w′ with the deviation t−sl when the selected arc is the pick-up arc which is(2)ci,j,t,s,w,w′v=ci,j,t,s,w,w′i,j,t,s,w,w′∉Aporxi,j,t,s,w,w′v=0,ci,j,t,s,w,w′+t−si,ji,j,t,s,w,w′∈Api,j∈Lp,xi,j,t,s,w,w′v=1.


## 3.3. Model Formulation

According to the space-time-state network, the bus routes, bus timetable, and bus carrying state can be presented. To increase the bus service quality and decrease the passenger travel time, we formulate a multicommodity network-flow programming model in the shuttle bus rerouting and rescheduling problem.


### 3.3.1. Objective Function

The objective of the proposed model is to minimize the total bus travel cost and the passenger delay, as shown in equation (3). The bus departure time xi,j,t,s,w,w′v×t is always after the scheduled time si,j when pick-up arc i,j,t,s,w,w′∈Ap is selected because the bus cannot pick-up the passengers at pick-up link i,j when the bus departs before si,j. Therefore, the passenger delay term xi,j,t,s,w,w′vt−si,j is always larger than 0:(3)minO=∑v∈V∑i,j,t,s,w,w′∈Axi,j,t,s,w,w′v×ci,j,t,s,w,w′v.


### 3.3.2. Bus Flow Balance Constraint

The shuttle bus should be generated from its originov,DEPv,woin the space-time-state network which can be presented as(4)∑i,j,t,s,w,w′∈Axi,j,t,s,w,w′v=1i=ov,t=DEPv,w=wo,w′∈W∀v∈V.The shuttle bus should end the trip at its destinationdv,ARRv,wd, in the space-time-state network which can be presented as(5)∑i,j,t,s,w,w′∈Axi,j,t,s,w,w′v=1j=dv,s=ARRv,w∈W,w′=wd∀v∈V.The bus flow should be balanced at the intermediate vertexi,t,w, which means that the number of entering buses is equal to the number of departing buses at i,t,w shown in equation (6). Therefore, equations (4)–(6) show the bus flow balance constraint, which is also introduced in the studies of Shang et al. [26] and Wang et al. [27] as(6)∑j,s,w′xi,j,t,s,w,w'v−∑j′,s′,w'′xj′,i,s′,t,w'′,wv=0i,t,w∉ov,DEPv,wo,dv,ARRv,wd,∀v∈V.


### 3.3.3. Demand Satisfaction Constraint

The passenger demandni,j+Δni,j must be met in the pick-up arc i,j,t,s,w,w′∈Ap by a specific bus, which can be shown as equation (7), in the space-time-state network. It should be noted that the pick-up arcs i,j,t,s,w,w′ are only built when si,j≤t≤ei,j, which guarantees the passengers can only be carried within the pick-up time window as(7)∑v∈V∑i,j,t,s,w,w′∈Apxi,j,t,s,w,w′v×w′−w=ni,j+Δni,j∀i,j∈Lp.


### 3.3.4. Binary Variable Definition

A binary variable is shown in equation (8); if bus v selects arc i,j,t,s,w,w′, xi,j,t,s,w,w′v=1; otherwise, xi,j,t,s,w,w′v=0.(8)xi,j,t,s,w,w′v∈0,1∀i,j,t,s,w,w′∈A,∀v∈V.


## 3.3.1. Objective Function

The objective of the proposed model is to minimize the total bus travel cost and the passenger delay, as shown in equation (3). The bus departure time xi,j,t,s,w,w′v×t is always after the scheduled time si,j when pick-up arc i,j,t,s,w,w′∈Ap is selected because the bus cannot pick-up the passengers at pick-up link i,j when the bus departs before si,j. Therefore, the passenger delay term xi,j,t,s,w,w′vt−si,j is always larger than 0:(3)minO=∑v∈V∑i,j,t,s,w,w′∈Axi,j,t,s,w,w′v×ci,j,t,s,w,w′v.


## 3.3.2. Bus Flow Balance Constraint

The shuttle bus should be generated from its originov,DEPv,woin the space-time-state network which can be presented as(4)∑i,j,t,s,w,w′∈Axi,j,t,s,w,w′v=1i=ov,t=DEPv,w=wo,w′∈W∀v∈V.The shuttle bus should end the trip at its destinationdv,ARRv,wd, in the space-time-state network which can be presented as(5)∑i,j,t,s,w,w′∈Axi,j,t,s,w,w′v=1j=dv,s=ARRv,w∈W,w′=wd∀v∈V.The bus flow should be balanced at the intermediate vertexi,t,w, which means that the number of entering buses is equal to the number of departing buses at i,t,w shown in equation (6). Therefore, equations (4)–(6) show the bus flow balance constraint, which is also introduced in the studies of Shang et al. [26] and Wang et al. [27] as(6)∑j,s,w′xi,j,t,s,w,w'v−∑j′,s′,w'′xj′,i,s′,t,w'′,wv=0i,t,w∉ov,DEPv,wo,dv,ARRv,wd,∀v∈V.


## 3.3.3. Demand Satisfaction Constraint

The passenger demandni,j+Δni,j must be met in the pick-up arc i,j,t,s,w,w′∈Ap by a specific bus, which can be shown as equation (7), in the space-time-state network. It should be noted that the pick-up arcs i,j,t,s,w,w′ are only built when si,j≤t≤ei,j, which guarantees the passengers can only be carried within the pick-up time window as(7)∑v∈V∑i,j,t,s,w,w′∈Apxi,j,t,s,w,w′v×w′−w=ni,j+Δni,j∀i,j∈Lp.


## 3.3.4. Binary Variable Definition

A binary variable is shown in equation (8); if bus v selects arc i,j,t,s,w,w′, xi,j,t,s,w,w′v=1; otherwise, xi,j,t,s,w,w′v=0.(8)xi,j,t,s,w,w′v∈0,1∀i,j,t,s,w,w′∈A,∀v∈V.


## 4. Solution Approach

In this section, the alternating direction method of multipliers (ADMM) decomposition method is introduced to solve the proposed model. To simplify the description in our model, we use notationa instead of i,j,t,s,w,w′ in the space-time-state network. We introduce wa to show the state transition on the space-time-state arc i,j,t,s,w,w′, where wa=w′−w.The ADMM described in Yao et al. [9] and Zhang et al. [28] is the combination of augmented Lagrangian relaxation [29] and the block coordinate descent method. Augmented Lagrangian relaxation introduces a quadratic penalty term into the objective function based on Lagrangian relaxation [26]. Compared to Lagrangian relaxation, augmented Lagrangian relaxation can improve the model robustness and functional convexity. However, the quadratic penalty term leads to the nonlinearity of the model, so it is difficult to decompose the model into several independent subproblems. Then, we introduce the block coordinate descent method to update the variables sequentially in a block-by-block manner and make the quadratic penalty term linear. Furthermore, ADMM has the advantages of breaking the symmetry and strong convexity, and readers can refer to Yao et al. [9] for more details.The hard constraint demand satisfaction constraint in modelO shown in Section 3 leads to inefficiency when solving the large-scale case, so equation (9) shows the augmented Lagrangian model Oρ, which is a transformed model O by relaxing the demand satisfaction constraint (equation (7)) into the original objective (equation (3)), the Lagrangian multipliers λi,j are introduced, and the quadratic penalty multiplier ρ is also introduced to punish the objective when the constraint is not complied with. Then, we find that constraints (4)–(6) and (8) in model Oρ are independent of all buses, and the original bus routing problem can be decomposed into several shortest-path searching problems for each bus. However, a quadratic term ∑i,j∈Lp∑v∈V∑a∈Apxav×wa−ni,j−Δni,j2 can be found in the new objective Oρ; then, to linearize the quadratic term, we introduce γi,jv=ni,j+Δni,j−∑v′∈V|v∑a∈Apxav′×wa∀i,j∈Lp to denote the number of passengers serviced by buses other than bus v at pick-up link i,j∈Lp. The new model is shown in equation (10), and the quadratic term ∑a∈Apxav×wa−γi,jv2 can be reformulated, as shown in equation (11), because the γi,jv is constant and the binary variable xav is equal to 1 or 0, which can easily calculate the square xav2 as equal to 1 or 0. The detailed procedure of the proposed ADMM-based decomposition method is shown in Algorithm 1.Algorithm 1: ADMM-based decomposition method.
Input: The physical network and space-time-state network, the planned shuttle buses routes and timetable, the fluctuation in passenger demand at each stop, the OD of passenger demand, the departure time window and the arrival time limit of each passenger, the planning horizon, and several basic parameters such as the cost of each arc and backup bus.Output: The routing and timetable of each bus.Step 1: InitializationSet the current iteration numberg=0, Lagrangian multipliers λi,j, and penalty multipliers ρ, best lower bound LB∗=−∞, best upper bound UB∗=+∞, the maximum iteration number M and initialize the lower bound and upper bound solution x0lower, x0upper.Step 2: Solve the bus routes and timetable problems for each busFor each bus v∈V doUpdate arc costc∧av by equation (12)Use Algorithm2 to find the time-dependent least-cost paths for all the busesObtain the bus route and timetable results and the objective function value, and add the results into lower bound solutionxglowerEnd for each bus v∈VStep 3: Obtaining the best lower boundThe lower boundLBg at iteration g is the sum of two objective function values, then the best lower bound can be calculated as LB∗=maxLB∗,LBg.Step 4: Obtaining the best upper boundFind feasible initial solutionx0upper.Adopt the passenger-to-bus results in step 2:For each pick-up link i,j doIf the passenger is picked up by more than one bus, one of the buses is selected to pick up the passengers in pick-up linki,j.If the passenger is not picked up by any bus, a backup bus is selected to pick up him/her.End for each pick-up link i,jThen, update the upper bound solutionxgupper and the best upper bound can be updated as UB∗=minUB∗,UBgStep 5: Updating the Lagrangian multipliersUpdate the Lagrangian multipliers by subgradient method:λi,jg+1=max0,λi,jg+ρxav×wa−ni,j−Δni,jThe values of quadratic penalty multipliersρ are fixed in this paperStep 6: Termination conditionsIf current iterationg reaches the maximum iteration number presented before, terminate the algorithm; otherwise, go to Step 2.Algorithm 2: Time-dependent least-cost path algorithm in forward dynamic programming.
Input: The space-time-state network, the arc cost in the space-time-state network, the passenger time window si,j,ei,j, the bus travel time in each linkOutput: Bus routes and timetableFor each bus vStep 1: InitializationSet the label cost of the space-time-state vertexσi,t,w=+∞ and the space-time-state vertex predecessor predi,t,w=−1,−1,−1. The label cost σov,DEPv,0=0.Step 2: Label updating in forward dynamic programmingFor each time t doFor each pick-up link i,j doFor state w doCalculate downstream statew′ based on the possible state transition on link i,j at time t.Calculate arrive times=t+TTi,j,tIfσi,t,w+c^av≤σj,s,w′,σj,s,w′:=σi,t,w+c∧avThenpredj,s,w′=i,t,wEnd ifEnd for state wEnd for each pick-up link i,jEnd for each time tBack tracing the shortest space-time-state path for busvEnd for each bus vObjective function is(9)minOρ=∑v∈V∑a∈Acavxav+∑i,j∈Lpλi,j×∑v∈V∑a∈Apxav×wa−ni,j−Δni,j+ρ2×∑i,j∈Lp∑v∈V∑a∈Apxav×wa−ni,j−Δni,j2,subject to constraints (3)–(5) and (7) reformulation(10)minOρ=∑v∈V∑a∈Acavxav+∑i,j∈Lpλi,j×∑v∈V∑a∈Apxav×wa−ni,j−Δni,j+ρ2×∑i,j∈Lp∑a∈Apxav×wa−γi,jv2,(11)∑a∈Apxav×wa−γi,jv2=∑a∈Apxav×wa2−2×∑a∈Apxav×wa×γi,jv+γi,jv2=∑a∈Apxav×wa2−2×∑a∈Apxav×wa×γi,jv+γi,jv2=∑a∈Apxav×wa2−2wa×γi,jv+γi,jv2,subject to constraints (4)–(6) and (8).According to the model proposed above, we use the mathematical method to merge the similar items, and then the final model is shown in equation (12), where Q is the constant, and the calculation of the arc cost is also introduced. Constraints (4)–(6) and (8) are independent of all buses; therefore, model Oρv is a standard shortest-path searching problem for each bus v, which can be solved by the dynamic programming shown in Algorithm 2.(12)minOρv=∑a∈Ac∧avxav+Q,c^av=cav+λi,j×wa+ρ2×wa2−ρ×wa×γi,jv+ρ2×γi,jv2∀i,j∈Lp,∀v∈V,∀a∈Apcavotherwise,subject to constraints (4)–(6) and (8).In the modelOρ, γi,jv=ni,j+Δni,j−∑v′∈V|v∑a∈Apxav′×wais introduced to present the number of passengers serviced by buses other than bus v at pick-up link i,j. Therefore, we design the rolling update scheme shown in Figure 6 to solve the shuttle bus routing and timetable problem. The bus within the circle means the current optimizing bus v, and the buses within the rectangle mean the fixed buses v′∈V|v.Figure 6
The rolling update scheme of ADMM.


## 5. Numerical Experiments

### 5.1. Simple Cases

#### 5.1.1. Description

In this section, we design several simple experiments based on the service network in Section2.1 to illustrate the proposed model and algorithm. Table 5 presents the different demands that lead to different strategies. Situation 1 is the average demand as the baseline, and passenger demand fluctuation occurs in situation 2 and situation 3, and the difference between them is that planned shuttle buses can satisfy all the passengers in situation 2 and cannot satisfy all the passengers in situation 3. The Lagrangian multipliers for the four situations are set as 0.01, and the penalty multiplier ρ is set as 25. The capacity of each bus is set as 3, and at most three passengers can be carried in each bus. The bus travel time in each link is assumed to be constant and is shown in Table 3. The cost of each arc is equal to the corresponding travel time, and the operating cost of each backup bus is set as 10.Table 5
The demand of different situations.
SituationThe demand in each stopStop 1Stop 2Stop 3Situation 1122Situation 2222Situation 3251


#### 5.1.2. The Rerouting and Rescheduling Results and Discussion

According to the proposed model in Section3.3 and the proposed solution approach in Section 4, we can obtain the objective upper bound within 10 iterations, and the space-time-state networks of each bus in the three situations are shown as follows:(1)
Figures7(a) and 7(b) present the two buses’ space-time-state networks with average demand as the baseline.(2)
The rerouting strategy is adopted when the demand increases from 1 to 2 at stop 1, and bus 2 would change the route to pick-up the passengers at stop 1, as shown in Figure7(d).(3)
The rerouting and rescheduling strategy is adopted when the demand increases from 1 to 2 at stop 1, from 2 to 5 at stop 2 and decreases from 2 to 1 at stop 3. Then, bus 1 picks up two passengers at stop 2, as directly shown in Figure7(e), and bus 2 picks up two passengers at stop 1 and then picks up passengers at stop 3, as shown in Figure 7(f). The backup bus operates to pick up the remaining two passengers at stop 2, as shown in Figure 7(g).From the three situations’ results, the proposed approaches can provide expected rerouting and rescheduling programs with different types of passenger demand fluctuations. The operators can reroute the buses visiting stops and flexibly operate the backup bus.Figure 7
The space-time-state networks of shuttle bus rerouting and rescheduling results in three situations. (a) Bus 1 in situation 1. (b) Bus 2 in situation 1. (c) Bus 1 in situation 2. (d) Bus 2 in situation 2. (e) Bus 1 in situation 3. (f) Bus 2 in situation 3. (g) Backup bus in situation 3.
(a)(b)(c)(d)(e)(f)(g)


#### 5.1.3. Parameter Analysis between Backup Bus Cost and Penalty Multiplier

In this paper, we aim to reschedule the shuttle bus to improve the service quality when passenger demand fluctuation occurs, and the objective of the model is to minimize the total cost and passenger delay. As the number of passengers increases at a specific stop and the total passenger demand exceeds the total shuttle bus capacity, a backup bus with a fixed operating cost should be used to pick up the additional passengers. Then, we find that the value of penalty multiplierρ and the backup bus cost have an effect on the total carried passengers. When the penalty multiplier is not large enough, the backup bus would not operate to pick up the increasing passengers and select the dummy arc to arrive at the destination. When the backup bus operation cost is too large, the backup bus would also not operate to pick up the increasing passengers and select the dummy to arrive at the destination. Therefore, we test the effect of penalty multiplier ρ and the backup bus cost on the total carried passengers shown in Figures 8(a) and 8(b), respectively. We fix the backup bus cost as 10 first; it can be found that two passengers are not carried when ρ<25, and all the passengers can be picked up when ρ≥25. When we fix ρ=25, all the passenger demand can be satisfied with backup cost less than 11, and two passengers are not carried when the backup cost is larger than 11.Figure 8
(a) The effect ofρ on the total carried passengers when backup bus cost is 10. (b) The effect of backup bus cost on the total carried passengers when ρ=25.
(a)(b)


### 5.2. A Large-Scale Case Based on the Chicago Sketch Road Network

In this section, we test the proposed model and algorithm in the Chicago sketch road network, which is shown in Figure9, including 545 nodes and 2,176 links. The link travel time is set as the real data, which is the quotient of distance divided by the average speed.Figure 9
The structure of the Chicago road sketch network: (a) the planned shuttle bus lines and (b) the location of shuttle bus stops.
(a)(b)We assume that there is a company in the center of the city as presented in Figure9(a). The six planned lines shown in Figure 9(a) are scheduled to pick up the passengers at 16 stops, as shown in Figure 9(b). The clock-in time of the staff is 9:00, so the passengers waiting at each stop must arrive at the company before 9:00, and the earliest arrival time is set as 8:00. Considering that the maximum travel time from the depot to the destination is 81 minutes, the study period is set as 7:00–9:00, for a time horizon of 120 minutes, and we set the time interval to 1 minute. The bus capacity is 6, and the average passenger demand and fluctuation in passenger demand are shown in Table 6.Table 6
The average passenger demand and fluctuated passenger demand.
StopAverage passenger demandFluctuation in passenger demandStop 122Stop 222Stop 320Stop 422Stop 524Stop 622Stop 722Stop 824Stop 922Stop 1032Stop 1132Stop 1226Stop 1322Stop 1424Stop 1532Stop 1632According to the input introduced, we run the experiment on a PC (CPU: i7-7700HQ 2.80 GHZ with eight threads, 16 GB RAM). To present the advantages of the proposed approaches, we calculate the objective value without the proposed strategy first as the baseline objective value when passenger demand fluctuates. The baseline objective results are shown in Figure10, and the penalty of each unsatisfied demand is set as 15. Then, we adopt the shuttle bus rerouting and rescheduling strategy by the proposed model and algorithm to calculate the upper bound objective value. The operating cost of the backup bus is set as 20, the Lagrangian multiplier is initially set as 0.01, and the quadratic penalty multiplier is set as 30. The upper bound objective results of 15 iterations obtained within 753 s are also shown in Figure 10, and the best solution is obtained at iteration 10. As shown in Figure 10, there is a 5.7% improvement when the proposed approaches are adopted.Figure 10
Upper bound objective value and baseline objective value.The rerouting and rescheduling results are shown in Figure11. As the figure shows, the rerouting strategy is adopted in Line 1 and Line 3, Line 2 and Line 4, and Line 5 and Line 6 because some lines are too far, such as Line 3 and Line 5, which creates a large cost to pick up the remaining passengers from Line 3 to Line 5. In detail, bus 1 skips stop 3 shown in Figure 11(a), bus 2 skips stop 6 shown in Figure 11(b) and bus 5 skips stop 13 and 14 shown in Figure 11(c). Furthermore, the total passengers at stop 12, stop 13, and stop 14 is 12, which is far more than the bus capacity, so a backup bus (running on Line 7) from the backup bus depot must be used to pick up the remaining passengers on Line 5, as shown in Figure 11(d). In conclusion, based on the proposed strategy, model, and algorithm, the bus rerouting and rescheduling results can be obtained in a short time, and all the passengers can be picked up within their time window.Figure 11
The rerouting and rescheduling results in the Chicago road sketch network: (a) line 1 and line 3, (b) line 2 and line 4, (c) line 5 and line 6, and (d) line 7 (the backup bus line).
(a)(b)(c)(d)


## 5.1. Simple Cases

### 5.1.1. Description

In this section, we design several simple experiments based on the service network in Section2.1 to illustrate the proposed model and algorithm. Table 5 presents the different demands that lead to different strategies. Situation 1 is the average demand as the baseline, and passenger demand fluctuation occurs in situation 2 and situation 3, and the difference between them is that planned shuttle buses can satisfy all the passengers in situation 2 and cannot satisfy all the passengers in situation 3. The Lagrangian multipliers for the four situations are set as 0.01, and the penalty multiplier ρ is set as 25. The capacity of each bus is set as 3, and at most three passengers can be carried in each bus. The bus travel time in each link is assumed to be constant and is shown in Table 3. The cost of each arc is equal to the corresponding travel time, and the operating cost of each backup bus is set as 10.Table 5
The demand of different situations.
SituationThe demand in each stopStop 1Stop 2Stop 3Situation 1122Situation 2222Situation 3251


### 5.1.2. The Rerouting and Rescheduling Results and Discussion

According to the proposed model in Section3.3 and the proposed solution approach in Section 4, we can obtain the objective upper bound within 10 iterations, and the space-time-state networks of each bus in the three situations are shown as follows:(1)
Figures7(a) and 7(b) present the two buses’ space-time-state networks with average demand as the baseline.(2)
The rerouting strategy is adopted when the demand increases from 1 to 2 at stop 1, and bus 2 would change the route to pick-up the passengers at stop 1, as shown in Figure7(d).(3)
The rerouting and rescheduling strategy is adopted when the demand increases from 1 to 2 at stop 1, from 2 to 5 at stop 2 and decreases from 2 to 1 at stop 3. Then, bus 1 picks up two passengers at stop 2, as directly shown in Figure7(e), and bus 2 picks up two passengers at stop 1 and then picks up passengers at stop 3, as shown in Figure 7(f). The backup bus operates to pick up the remaining two passengers at stop 2, as shown in Figure 7(g).From the three situations’ results, the proposed approaches can provide expected rerouting and rescheduling programs with different types of passenger demand fluctuations. The operators can reroute the buses visiting stops and flexibly operate the backup bus.Figure 7
The space-time-state networks of shuttle bus rerouting and rescheduling results in three situations. (a) Bus 1 in situation 1. (b) Bus 2 in situation 1. (c) Bus 1 in situation 2. (d) Bus 2 in situation 2. (e) Bus 1 in situation 3. (f) Bus 2 in situation 3. (g) Backup bus in situation 3.
(a)(b)(c)(d)(e)(f)(g)


### 5.1.3. Parameter Analysis between Backup Bus Cost and Penalty Multiplier

In this paper, we aim to reschedule the shuttle bus to improve the service quality when passenger demand fluctuation occurs, and the objective of the model is to minimize the total cost and passenger delay. As the number of passengers increases at a specific stop and the total passenger demand exceeds the total shuttle bus capacity, a backup bus with a fixed operating cost should be used to pick up the additional passengers. Then, we find that the value of penalty multiplierρ and the backup bus cost have an effect on the total carried passengers. When the penalty multiplier is not large enough, the backup bus would not operate to pick up the increasing passengers and select the dummy arc to arrive at the destination. When the backup bus operation cost is too large, the backup bus would also not operate to pick up the increasing passengers and select the dummy to arrive at the destination. Therefore, we test the effect of penalty multiplier ρ and the backup bus cost on the total carried passengers shown in Figures 8(a) and 8(b), respectively. We fix the backup bus cost as 10 first; it can be found that two passengers are not carried when ρ<25, and all the passengers can be picked up when ρ≥25. When we fix ρ=25, all the passenger demand can be satisfied with backup cost less than 11, and two passengers are not carried when the backup cost is larger than 11.Figure 8
(a) The effect ofρ on the total carried passengers when backup bus cost is 10. (b) The effect of backup bus cost on the total carried passengers when ρ=25.
(a)(b)


## 5.1.1. Description

In this section, we design several simple experiments based on the service network in Section2.1 to illustrate the proposed model and algorithm. Table 5 presents the different demands that lead to different strategies. Situation 1 is the average demand as the baseline, and passenger demand fluctuation occurs in situation 2 and situation 3, and the difference between them is that planned shuttle buses can satisfy all the passengers in situation 2 and cannot satisfy all the passengers in situation 3. The Lagrangian multipliers for the four situations are set as 0.01, and the penalty multiplier ρ is set as 25. The capacity of each bus is set as 3, and at most three passengers can be carried in each bus. The bus travel time in each link is assumed to be constant and is shown in Table 3. The cost of each arc is equal to the corresponding travel time, and the operating cost of each backup bus is set as 10.Table 5
The demand of different situations.
SituationThe demand in each stopStop 1Stop 2Stop 3Situation 1122Situation 2222Situation 3251


## 5.1.2. The Rerouting and Rescheduling Results and Discussion

According to the proposed model in Section3.3 and the proposed solution approach in Section 4, we can obtain the objective upper bound within 10 iterations, and the space-time-state networks of each bus in the three situations are shown as follows:(1)
Figures7(a) and 7(b) present the two buses’ space-time-state networks with average demand as the baseline.(2)
The rerouting strategy is adopted when the demand increases from 1 to 2 at stop 1, and bus 2 would change the route to pick-up the passengers at stop 1, as shown in Figure7(d).(3)
The rerouting and rescheduling strategy is adopted when the demand increases from 1 to 2 at stop 1, from 2 to 5 at stop 2 and decreases from 2 to 1 at stop 3. Then, bus 1 picks up two passengers at stop 2, as directly shown in Figure7(e), and bus 2 picks up two passengers at stop 1 and then picks up passengers at stop 3, as shown in Figure 7(f). The backup bus operates to pick up the remaining two passengers at stop 2, as shown in Figure 7(g).From the three situations’ results, the proposed approaches can provide expected rerouting and rescheduling programs with different types of passenger demand fluctuations. The operators can reroute the buses visiting stops and flexibly operate the backup bus.Figure 7
The space-time-state networks of shuttle bus rerouting and rescheduling results in three situations. (a) Bus 1 in situation 1. (b) Bus 2 in situation 1. (c) Bus 1 in situation 2. (d) Bus 2 in situation 2. (e) Bus 1 in situation 3. (f) Bus 2 in situation 3. (g) Backup bus in situation 3.
(a)(b)(c)(d)(e)(f)(g)


## 5.1.3. Parameter Analysis between Backup Bus Cost and Penalty Multiplier

In this paper, we aim to reschedule the shuttle bus to improve the service quality when passenger demand fluctuation occurs, and the objective of the model is to minimize the total cost and passenger delay. As the number of passengers increases at a specific stop and the total passenger demand exceeds the total shuttle bus capacity, a backup bus with a fixed operating cost should be used to pick up the additional passengers. Then, we find that the value of penalty multiplierρ and the backup bus cost have an effect on the total carried passengers. When the penalty multiplier is not large enough, the backup bus would not operate to pick up the increasing passengers and select the dummy arc to arrive at the destination. When the backup bus operation cost is too large, the backup bus would also not operate to pick up the increasing passengers and select the dummy to arrive at the destination. Therefore, we test the effect of penalty multiplier ρ and the backup bus cost on the total carried passengers shown in Figures 8(a) and 8(b), respectively. We fix the backup bus cost as 10 first; it can be found that two passengers are not carried when ρ<25, and all the passengers can be picked up when ρ≥25. When we fix ρ=25, all the passenger demand can be satisfied with backup cost less than 11, and two passengers are not carried when the backup cost is larger than 11.Figure 8
(a) The effect ofρ on the total carried passengers when backup bus cost is 10. (b) The effect of backup bus cost on the total carried passengers when ρ=25.
(a)(b)


## 5.2. A Large-Scale Case Based on the Chicago Sketch Road Network

In this section, we test the proposed model and algorithm in the Chicago sketch road network, which is shown in Figure9, including 545 nodes and 2,176 links. The link travel time is set as the real data, which is the quotient of distance divided by the average speed.Figure 9
The structure of the Chicago road sketch network: (a) the planned shuttle bus lines and (b) the location of shuttle bus stops.
(a)(b)We assume that there is a company in the center of the city as presented in Figure9(a). The six planned lines shown in Figure 9(a) are scheduled to pick up the passengers at 16 stops, as shown in Figure 9(b). The clock-in time of the staff is 9:00, so the passengers waiting at each stop must arrive at the company before 9:00, and the earliest arrival time is set as 8:00. Considering that the maximum travel time from the depot to the destination is 81 minutes, the study period is set as 7:00–9:00, for a time horizon of 120 minutes, and we set the time interval to 1 minute. The bus capacity is 6, and the average passenger demand and fluctuation in passenger demand are shown in Table 6.Table 6
The average passenger demand and fluctuated passenger demand.
StopAverage passenger demandFluctuation in passenger demandStop 122Stop 222Stop 320Stop 422Stop 524Stop 622Stop 722Stop 824Stop 922Stop 1032Stop 1132Stop 1226Stop 1322Stop 1424Stop 1532Stop 1632According to the input introduced, we run the experiment on a PC (CPU: i7-7700HQ 2.80 GHZ with eight threads, 16 GB RAM). To present the advantages of the proposed approaches, we calculate the objective value without the proposed strategy first as the baseline objective value when passenger demand fluctuates. The baseline objective results are shown in Figure10, and the penalty of each unsatisfied demand is set as 15. Then, we adopt the shuttle bus rerouting and rescheduling strategy by the proposed model and algorithm to calculate the upper bound objective value. The operating cost of the backup bus is set as 20, the Lagrangian multiplier is initially set as 0.01, and the quadratic penalty multiplier is set as 30. The upper bound objective results of 15 iterations obtained within 753 s are also shown in Figure 10, and the best solution is obtained at iteration 10. As shown in Figure 10, there is a 5.7% improvement when the proposed approaches are adopted.Figure 10
Upper bound objective value and baseline objective value.The rerouting and rescheduling results are shown in Figure11. As the figure shows, the rerouting strategy is adopted in Line 1 and Line 3, Line 2 and Line 4, and Line 5 and Line 6 because some lines are too far, such as Line 3 and Line 5, which creates a large cost to pick up the remaining passengers from Line 3 to Line 5. In detail, bus 1 skips stop 3 shown in Figure 11(a), bus 2 skips stop 6 shown in Figure 11(b) and bus 5 skips stop 13 and 14 shown in Figure 11(c). Furthermore, the total passengers at stop 12, stop 13, and stop 14 is 12, which is far more than the bus capacity, so a backup bus (running on Line 7) from the backup bus depot must be used to pick up the remaining passengers on Line 5, as shown in Figure 11(d). In conclusion, based on the proposed strategy, model, and algorithm, the bus rerouting and rescheduling results can be obtained in a short time, and all the passengers can be picked up within their time window.Figure 11
The rerouting and rescheduling results in the Chicago road sketch network: (a) line 1 and line 3, (b) line 2 and line 4, (c) line 5 and line 6, and (d) line 7 (the backup bus line).
(a)(b)(c)(d)


## 6. Conclusions

In this paper, we study the shuttle bus rerouting and rescheduling problem. The operators schedule the shuttle bus based on the average passenger demand in the first stage. However, because the passenger demand fluctuates, passenger demand may increase at some stops and decrease at some stops, and the planned bus schedule cannot satisfy all the passengers, leading to unsatisfied passenger demand and vacant seats. To improve the service quality and decrease the capacity waste, we introduce the rerouting and rescheduling strategy to generate better routes and timetable. Then, we adopt the three-dimensional space-time-state network and an integer programming model to depict and optimize the proposed problem. The state dimension denotes the number of passengers carried by the bus in a specific time and node. Considering that the demand satisfaction constraint is a complex constraint, the ADMM-based decomposition method is adopted to break the model symmetry and improve efficiency. To test the effectiveness and efficiency of the proposed model and algorithm, a simple case network with 15 nodes is used, and the sensitivity analysis of backup bus cost and penalty multiplier is also measured. Finally, we test the proposed method in a large-scale case based on the Chicago sketch road network. Based on the input of the planned six lines, the rerouting and rescheduling results with passenger demand fluctuation can be generated within 783 s.In future studies, new strategies such as passenger transfer strategies can be integrated with the strategy in this paper, and multidestination problems can also be considered to expand the scope of application of the method. A more efficient least-cost path algorithm in forward dynamic programming will also be designed and adopted. [14].



---

*Source: 2917240-2022-10-21.xml*