# Optimal Integrated Model for Feeder Transit Route Design and Frequency-Setting Problem with Stop Selection

Authors: Ming Wei; Tao Liu; Bo Sun; Binbin Jing
Journal: Journal of Advanced Transportation
 (2020)

---

## Abstract

This study proposed a mathematical model for designing a feeder transit service for improving the service quality and accessibility of transportation hubs (such as airport and rail station). The proposed model featured an integrated framework, which simultaneously guided passengers to reach their nearest stops to get on and off the bus, designed routes to transport passengers from these selected pick-up stops to the transportation hubs, and calculated their departure frequencies. In particular, the maximum walking distance, the upper and lower limits of route frequencies, and the load factor rate of each route were fully accounted for in this study. The main objective of the proposed model was to simultaneously minimize the total walking, riding time, and waiting time of all passengers. As this study explored an NP-hard problem, a two-stage genetic algorithm combining the Dijkstra search method was further developed to yield metaoptimal solutions to the model within an acceptable time. Finally, a test instance in Chongqing City, China, demonstrated that the proposed model was an effective tool to generate a pedestrian, route, and operation plan; it reduced the total travel time, compared with the traditional model.


---

## Body

## 1. Introduction

Feeder transit system (FTS) aims at arranging access to vehicles located at different depots at all demand points and transporting residents from these selected pick-up stops to transportation hubs (rail station and airport, etc.). The FTS transit network, including a set of nodes (transportation hubs, bus stops, demand points, and depots) and links between them, is regarded as an effective tool to provide a better first/last mile service to and from the major fixed-route transit networks. Hence, a well-designed FTS transit network shifted transport demand from individual car traffic to public transport and further enhanced urban sustainability [1–3].Similar to conventional bus operation, route design and frequency setting are two key activities in FTS operation, where the former is the input data of the latter, and they affect each other. Several studies have analyzed the impact of frequencies under different route structures to meet the same passenger demand. Frequencies were increased to improve the level of service under hub-and-spoke route structures, while they were reduced in fully connected route structures. However, the majority of FTS have neglected an integrated operation of designing transit route structures and setting their frequencies [1, 4, 5]. Therefore, it is especially important to optimize a combination of FTS route design and frequency setting to reveal an optimal relationship between in-vehicle congestion and waiting time at bus stops.Another important observation was that most studies made an assumption of locations of demand points being pick-up stops and all stops being visited. In the real world, passengers at the demand point may walk to one of the nearby stops to get on and off the bus, and their choice behaviors are decided by routes with empty seats and shorter driving time. Selecting optimal stops in candidate routes as pick-up locations with an assignment of demand points is also key to designing FTS routes [6, 7]. Therefore, the integrated operation of transit route design and frequency setting with stop selection is now widely regarded as an effective tool to improve service efficiency and financial status.The main purpose of this study was to develop an integrated optimization framework for simultaneously coordinating the passenger boarding guidance, bus stop selection, feeder transit routing and frequency-setting process to trade off the total walking time from demand points to selected pick-up stops, total waiting time at selected pick-up stops, and total riding time from pick-up stops to the transportation hubs for all passengers. The study also focused on some research tasks as follows: (1) determination of the optimal design of FTS route and frequency with the assignment of all demand points to selected pick-up stops and (2) creation of a genetic algorithm- (GA-) based heuristic approach to efficiently find good solutions to such an NP-hard problem. Finally, a real-world test was performed to prove the applicability of the proposed model and algorithm.The remainder of this study is organized as follows: Section2 summarizes the related literature on FTS. Section 3 presents the methodology of the problem and provides a mathematical formulation for the integrated model. Section 4 presents a two-stage GA-based approach to resolve such a problem. Section 5 provides details of solutions and sensitivity analysis. Finally, Section 6 offers conclusions and future research directions.


## 2. Literature Review

At present, the FTS transit service has drawn great attention in the last few decades due to its convenience of first and last mile to link residential areas and transportation hubs in major fixed-route transit networks. Similar to the regular bus operation, route design and frequency setting are two key activities in improving the service level of operation cost, in-vehicle congestion, travel time, and waiting time at stops. Most previous studies optimized frequencies to generate a timetable based on an existing FTS route network. The integration of transit route structures and service frequencies could not maximize the operational efficiency of an FTS system. Hence, it is important to simultaneously coordinate the design process of these two activities in an FTS system to provide adequate feeder services from these origin places, where residents live or work, to transportation hubs (such as airport and rail station).Most previous studies on FTS route design mainly included two categories of approaches [8]: continuous analytical and discrete optimization. In the analytical approaches, optimal relationships between route spacing, stop spacing, and frequency could be found with an idealized FTS network structure based on a uniformly distributed demand in the study area [9–11]. Further, these approaches also optimized the stop locations and the route structures, and their headways by considering the time-dependent [12], space-dependent [13], and time-and-space-dependent demands [14–17]. However, these analytical methods have significant limitations in practical applications of FTS route design [8], because the two key model inputs were idealized FTS network structures and the demand was uniformly distributed.To overcome passenger demand endogeneity in a continuous analytical FTS, several discrete optimization approaches were considered to handle the FTS route design. First, this problem was decomposed into two sequential subproblems, which assigned stops to a route in the first stage and then determined the order of route by visiting the selected ones [18]. Second, a bilevel optimization model was built to achieve a user–operator equilibrium, where route structures were determined at first and the transit assignment was obtained [19]. Third, a nonlinear optimization model was built for passenger assignments and solved through heuristic algorithms [20]. However, some exact algorithms could only solve small-scale instances fast [18]. Advanced metaheuristics (e.g., GA) are commonly used to solve large-scale instances efficiently [2–4, 6, 7].In the FTS frequency setting, the number of trips for each route was determined to analyze the effect of frequency changes on the level of service. Their research ideas and methods were the same as those of regular bus operations. Early studies used analytical models [12, 21, 22] to set frequency based on a fixed demand-line assignment. These studies were later extended with consideration of uncertainty factors such as demand and riding/boarding/alighting times [3, 23]. For example, Verbas and Mahmassani [24, 25] extended the uncertain frequency-setting model with space–time changed demand. Besides, the design of frequency-setting decisions in short-turn and limited-stop routes was also presented to meet the uneven demand [16, 26, 27].In recent years, the integration of the regular bus route design and frequency setting has gained an ever-increasing interest. In early research studies, sequential approaches, bus route design considerations into the frequency setting, or vice versa did not guarantee a global optimal solution [28]. To avoid such disadvantages, the following approaches were used to handle the integration operation: (1) partial integrations, that is, the bus route design with consideration of frequency setting [29] and (2) complete integrations, that is, coordinated decisions of the two problems [30]. Complete integrated operations handle decisions of each subproblem and hence are much more complex than the subproblem [31]. Further, some exact and heuristic approaches were proposed to deal with large-scale problems [4, 5, 28–33].A review of literature on FTS revealed the following critical issues, which deserve further investigations:(1)
Although several studies proposed various integration operations of regular bus route design and frequency setting, few of them took them into account in FTS. The difference between them was the route structures and demand patterns (i.e., the transportation hub) [2, 4, 5, 28–31]. Therefore, this study was also very meaningful.(2)
Traditional FTS assumed that demand points were stops. People at demand points, where passengers live or work, can walk to one of the nearest stops to get on and off the bus. In such a case, an operation of integrated pedestrian guidance (from demand points to selected stops) and transit routing (from pick-up places to transportation hubs) can find an optimal relation between the walking and riding time of residents and the operation efficiency of vehicles [1, 6, 7, 34].(3)
Such integration of stop selection, transit routing, and frequency setting was a new research problem extending from an NP-hard vehicle route problem, and a novel heuristic algorithm was needed to efficiently resolve large-scale instances [8].


## 3. Methodology

### 3.1. Research Framework

In the FTS model, demand points, where residents live or work, are not bus stops. Some stops are selected in candidate routes as pick-up locations visited by transit routes starting at depots and ending at transportation hubs (such as airport and rail station). Passengers at different demand points can get on and off at the same stop by walking some distance. Passengers at a demand point can choose one of the several nearby bus stops to get on and off the bus. The assignment of each demand point to one of the nearest stops is determined by the route capacity and the total travel time of passengers. The main purpose of this study was to propose an integrated optimization model for coordinating bus stop selection, feeder transit routing, and frequency-setting process, where some stops with their assigned demand points are first chosen as pick-up locations in candidate routes by considering some constraints such as maximum walking distance in the process of stop selection. Then, the feeder transit route design aims at determining the sequence of these vehicle nodes (i.e., pick-up locations, bus depots, and transportation hubs) visited by buses by satisfying some route constraints such as capacity, travel time, and mileage range limits. In the frequency-setting process, it finally optimizes the number of departure trips per hour to balance passenger waiting time and vehicle load rate. The key inputs of the proposed model were locations of demand points, stop candidate routes, and transportation hubs and depots. This was supplemented by data about walking distance matrix between demand points and stops as well as travel distance and time matrix between these vehicle nodes in the study area using an open GIS tool (Google or Baidu map) to reflect the real traffic status. A novel mixed-integer linear programming model was developed to find the optimal coupling between them to guide passengers of demand points to be quickly and comfortably transported from selected pick-up stops to their associated transportation hubs. The organization chart of the proposed framework is shown in Figure1.Figure 1
Organization chart of the proposed framework.A small FTS network consisting of one transportation hub (M), eight stop candidate routes (S1–S8), five demand points (C1–C5), and two bus depots (D1 and D2) was considered to better interpret the underlying principles of the proposed model and its scope, illustrated in Figure2. In the figure, the number around the circle denotes the number of people at the demand point and the number near the square is the number of people getting on and off the bus at the bus stop. The optimization process yielded an assignment of five demand points to four selected stops, described as S4 (C5); similarly, for other selected stops, they were described as S3 (C4), S2 (C3), and S1 (C1, C2). Considering S1 (C1, C2) for instance, the number of people getting on and off the bus at S1 was the sum of that of C1 and C2. Two feeder routes were then yielded as follows: route 1 was illustrated by [D3–S4–S3–M] and route 2 by [D2–S2–S1–M]. Once the route design was completed, the number of departure trips per hour was determined using the maximum and minimum departure frequency and the full-load rate. Considering route 1 as an example, its departure frequency was obtained by dividing its passenger capacity (i.e., 90 per/h) by the rated passenger load of the vehicle (i.e., 15 per/veh), that is, 90/15 = 6 veh/h.Figure 2
Typical example of the proposed model.The objective was to find the optimal design of the FTS route and frequency that simultaneously minimized the total walking time from demand points to selected stops, total waiting time at selected pick-up stops, and total travel time in vehicles of passengers from pick-up stops to transportation hubs for all passengers. The proposed methodology fitted well with real-life situations using the following assumptions:(1)
Each demand point must only be assigned to a selected stop, and each selected stop can only be covered once by one route.(2)
The real walking or travel distance/time matrix between these nodes in the traffic network is obtained from an Open GIS tool.(3)
By analyzing the signaling data of mobile phones, the number of passengers at each demand point in each period can be obtained. Also, it is assumed that the passengers arrive at the station evenly to get on and off the bus.


### 3.2. Model Formulation

#### 3.2.1. Notation

To facilitate the problem presentation of the proposed model, mathematical symbols of related parameters and variables are summarized in Table1.Table 1
Mathematical symbols in the FTS model.
Index:
i
Demand point
j
,
m
Vehicular node (depot, stop, and transportation hub) index
k
Route
Sets:
I
Set of demand points
K
Set of routes
N
Set of candidate stops
D
Set of depots
M
Set of transportation hubs
Parameters:
q
i
Number of persons at the demand pointsi during peak hours;∀i∈I
Q
Rated vehicle capacity
F
max
Maximum departure frequency
F
min
Minimum departure frequency
r
k
Load rate of routek
R
max
Maximum load rate
R
min
Minimum load rate
D
max
Maximum route length
T
min
Minimum travel time of feeder bus route
D
k
The total mileage of the routek visiting all vehicular nodes;∀k∈K
T
k
The total travel time of the routek visiting all vehicular nodes;∀k∈K
W
Maximum walking distance
v
Average walking speed
d
i
j
Map-based distance from rail stations, bus depots, and candidate route stop to demand pointi,j;∀i,j∈I∪M∪D∪N
t
i
j
Map-based distance from rail stations, bus depots, and candidate route stop to demand pointsi,j;∀i,j∈I∪M∪D∪N
H
Relatively large fixed value
Decision variables:
z
j
Whether the candidatej is selected as a feeder bus stop; ∀j∈N
h
i
j
Whether the demand pointi is assigned to a selected stop j;∀i∈I,∀j∈N
x
j
m
k
Whether a vehicular nodej precedes vehicular node m on the route k;∀k∈K,∀j∈N
f
k
Frequency of routek during peak hour
y
j
k
Whether the nodej is covered by the route k; ∀j∈I∪D∪M∪N, ∀k∈K
t
j
k
The travel time of the routek visiting vehicular node j;∀k∈K, ∀j∈I∪M∪D∪N
q
j
k
Number of persons at the vehicular nodej assigned to route k; ∀k∈K, ∀j∈I∪M∪D∪N
U
j
k
Auxiliary (real) variable for subtour elimination constraint in the route of busk; ∀k∈K


#### 3.2.2. Formulation

(1)
max
f
=
∑
∀
i
∈
I
∑
∀
j
∈
N
h
i
j
⋅
d
i
j
v
⋅
q
i
+
∑
∀
j
∈
M
∑
∀
k
∈
K
y
j
k
⋅
∑
∀
i
∈
I
h
i
j
⋅
q
i
⋅
T
k
−
t
j
k
+
60
f
k
/
2
,subjected to(2)hij≤zj,∀i∈I,∀j∈N,(3)∑∀j∈Nhij=1,∀i∈I,(4)hij⋅dij≤W,∀i∈I,∀j∈N,(5)yjk≤zj,∀k∈K,∀j∈N,(6)∑∀j∈Nyjk≥1,∀k∈K,(7)∑∀j∈Ixjmk=1,∀k∈K,∀m∈M,(8)∑∀j∈Nxmjk=0,∀k∈K,∀m∈M,(9)∑∀j∈Nxjmk=0,∀k∈K,∀m∈D,(10)∑∀j∈Nxmjk=1,∀k∈K,∀m∈D,(11)∑∀m∈N∪D∪Mxjmk=∑∀m∈N∪D∪Mxmjk=yjk,∀k∈K,∀j∈N,(12)Ujk−Umk+N∪D∪M⋅xjmk≥N∪D∪M−1,∀k∈K,∀j,m∈N∪D∪M,(13)tjk+tjm−1−xjmkH≤tmk,∀k∈K,∀j,m∈N∪D∪M,(14)tjk+tjm+1−xjmkH≥tmk,∀k∈K,∀j,m∈N∪D∪M,(15)qjk+∑∀i∈Ihij⋅qi−1−xjmkH≤qmk,∀k∈K,∀j,m∈N∪D∪M,(16)qjk+∑∀i∈Ihij⋅qi+1−xjmkH≥qmk,∀k∈K,∀j,m∈N∪D∪M,(17)Dk=∑∀j,m∈N∪D∪Mxjmkdjm≤Dmax,∀k∈K,(18)Tk=∑∀j,m∈N∪D∪Mxjmktjm≥Tmin,∀k∈K,(19)FMin≤fk≤FMax,∀k∈K,(20)RMin≤rk=∑∀j∈NqjkQ≤RMax,∀k∈K.Objective (1) aims at minimizing the total walking, riding, and waiting time of all passengers. Constraint (2) ensures that a demand point must be allocated to a selected stop. Constraint (3) ensures that each demand point must be assigned to a pick-up location. Constraint (4) ensures that the walking distance from each demand point to the bus stop is not less than the maximum allowable value. Constraint (5) ensures that each selected bus stop is covered by feeder buses. Constraint (6) ensures that each vehicle visits at least one selected stop. Constraints (7)–(10) are used for each route eventually starting from the depot and ending at the transportation hub. Constraint (11) indicates that each bus stop cannot be visited by two routes at the same time. Constraint (12) indicates that subtour elimination is met. Constraints (13) and (14) calculate the arrival time of the vehicle k visiting the current stop. Constraints (15) and (16) calculate the load capacity of adjacent stops visited by each route. Constraints (17) and (18) guarantee that travel mileage and time of each route should meet their upper and lower limits. Constraints (19) and (20) indicate that the frequency setting and load factor of each route must meet their minimum and maximum values.


## 3.1. Research Framework

In the FTS model, demand points, where residents live or work, are not bus stops. Some stops are selected in candidate routes as pick-up locations visited by transit routes starting at depots and ending at transportation hubs (such as airport and rail station). Passengers at different demand points can get on and off at the same stop by walking some distance. Passengers at a demand point can choose one of the several nearby bus stops to get on and off the bus. The assignment of each demand point to one of the nearest stops is determined by the route capacity and the total travel time of passengers. The main purpose of this study was to propose an integrated optimization model for coordinating bus stop selection, feeder transit routing, and frequency-setting process, where some stops with their assigned demand points are first chosen as pick-up locations in candidate routes by considering some constraints such as maximum walking distance in the process of stop selection. Then, the feeder transit route design aims at determining the sequence of these vehicle nodes (i.e., pick-up locations, bus depots, and transportation hubs) visited by buses by satisfying some route constraints such as capacity, travel time, and mileage range limits. In the frequency-setting process, it finally optimizes the number of departure trips per hour to balance passenger waiting time and vehicle load rate. The key inputs of the proposed model were locations of demand points, stop candidate routes, and transportation hubs and depots. This was supplemented by data about walking distance matrix between demand points and stops as well as travel distance and time matrix between these vehicle nodes in the study area using an open GIS tool (Google or Baidu map) to reflect the real traffic status. A novel mixed-integer linear programming model was developed to find the optimal coupling between them to guide passengers of demand points to be quickly and comfortably transported from selected pick-up stops to their associated transportation hubs. The organization chart of the proposed framework is shown in Figure1.Figure 1
Organization chart of the proposed framework.A small FTS network consisting of one transportation hub (M), eight stop candidate routes (S1–S8), five demand points (C1–C5), and two bus depots (D1 and D2) was considered to better interpret the underlying principles of the proposed model and its scope, illustrated in Figure2. In the figure, the number around the circle denotes the number of people at the demand point and the number near the square is the number of people getting on and off the bus at the bus stop. The optimization process yielded an assignment of five demand points to four selected stops, described as S4 (C5); similarly, for other selected stops, they were described as S3 (C4), S2 (C3), and S1 (C1, C2). Considering S1 (C1, C2) for instance, the number of people getting on and off the bus at S1 was the sum of that of C1 and C2. Two feeder routes were then yielded as follows: route 1 was illustrated by [D3–S4–S3–M] and route 2 by [D2–S2–S1–M]. Once the route design was completed, the number of departure trips per hour was determined using the maximum and minimum departure frequency and the full-load rate. Considering route 1 as an example, its departure frequency was obtained by dividing its passenger capacity (i.e., 90 per/h) by the rated passenger load of the vehicle (i.e., 15 per/veh), that is, 90/15 = 6 veh/h.Figure 2
Typical example of the proposed model.The objective was to find the optimal design of the FTS route and frequency that simultaneously minimized the total walking time from demand points to selected stops, total waiting time at selected pick-up stops, and total travel time in vehicles of passengers from pick-up stops to transportation hubs for all passengers. The proposed methodology fitted well with real-life situations using the following assumptions:(1)
Each demand point must only be assigned to a selected stop, and each selected stop can only be covered once by one route.(2)
The real walking or travel distance/time matrix between these nodes in the traffic network is obtained from an Open GIS tool.(3)
By analyzing the signaling data of mobile phones, the number of passengers at each demand point in each period can be obtained. Also, it is assumed that the passengers arrive at the station evenly to get on and off the bus.


## 3.2. Model Formulation

### 3.2.1. Notation

To facilitate the problem presentation of the proposed model, mathematical symbols of related parameters and variables are summarized in Table1.Table 1
Mathematical symbols in the FTS model.
Index:
i
Demand point
j
,
m
Vehicular node (depot, stop, and transportation hub) index
k
Route
Sets:
I
Set of demand points
K
Set of routes
N
Set of candidate stops
D
Set of depots
M
Set of transportation hubs
Parameters:
q
i
Number of persons at the demand pointsi during peak hours;∀i∈I
Q
Rated vehicle capacity
F
max
Maximum departure frequency
F
min
Minimum departure frequency
r
k
Load rate of routek
R
max
Maximum load rate
R
min
Minimum load rate
D
max
Maximum route length
T
min
Minimum travel time of feeder bus route
D
k
The total mileage of the routek visiting all vehicular nodes;∀k∈K
T
k
The total travel time of the routek visiting all vehicular nodes;∀k∈K
W
Maximum walking distance
v
Average walking speed
d
i
j
Map-based distance from rail stations, bus depots, and candidate route stop to demand pointi,j;∀i,j∈I∪M∪D∪N
t
i
j
Map-based distance from rail stations, bus depots, and candidate route stop to demand pointsi,j;∀i,j∈I∪M∪D∪N
H
Relatively large fixed value
Decision variables:
z
j
Whether the candidatej is selected as a feeder bus stop; ∀j∈N
h
i
j
Whether the demand pointi is assigned to a selected stop j;∀i∈I,∀j∈N
x
j
m
k
Whether a vehicular nodej precedes vehicular node m on the route k;∀k∈K,∀j∈N
f
k
Frequency of routek during peak hour
y
j
k
Whether the nodej is covered by the route k; ∀j∈I∪D∪M∪N, ∀k∈K
t
j
k
The travel time of the routek visiting vehicular node j;∀k∈K, ∀j∈I∪M∪D∪N
q
j
k
Number of persons at the vehicular nodej assigned to route k; ∀k∈K, ∀j∈I∪M∪D∪N
U
j
k
Auxiliary (real) variable for subtour elimination constraint in the route of busk; ∀k∈K


### 3.2.2. Formulation

(1)
max
f
=
∑
∀
i
∈
I
∑
∀
j
∈
N
h
i
j
⋅
d
i
j
v
⋅
q
i
+
∑
∀
j
∈
M
∑
∀
k
∈
K
y
j
k
⋅
∑
∀
i
∈
I
h
i
j
⋅
q
i
⋅
T
k
−
t
j
k
+
60
f
k
/
2
,subjected to(2)hij≤zj,∀i∈I,∀j∈N,(3)∑∀j∈Nhij=1,∀i∈I,(4)hij⋅dij≤W,∀i∈I,∀j∈N,(5)yjk≤zj,∀k∈K,∀j∈N,(6)∑∀j∈Nyjk≥1,∀k∈K,(7)∑∀j∈Ixjmk=1,∀k∈K,∀m∈M,(8)∑∀j∈Nxmjk=0,∀k∈K,∀m∈M,(9)∑∀j∈Nxjmk=0,∀k∈K,∀m∈D,(10)∑∀j∈Nxmjk=1,∀k∈K,∀m∈D,(11)∑∀m∈N∪D∪Mxjmk=∑∀m∈N∪D∪Mxmjk=yjk,∀k∈K,∀j∈N,(12)Ujk−Umk+N∪D∪M⋅xjmk≥N∪D∪M−1,∀k∈K,∀j,m∈N∪D∪M,(13)tjk+tjm−1−xjmkH≤tmk,∀k∈K,∀j,m∈N∪D∪M,(14)tjk+tjm+1−xjmkH≥tmk,∀k∈K,∀j,m∈N∪D∪M,(15)qjk+∑∀i∈Ihij⋅qi−1−xjmkH≤qmk,∀k∈K,∀j,m∈N∪D∪M,(16)qjk+∑∀i∈Ihij⋅qi+1−xjmkH≥qmk,∀k∈K,∀j,m∈N∪D∪M,(17)Dk=∑∀j,m∈N∪D∪Mxjmkdjm≤Dmax,∀k∈K,(18)Tk=∑∀j,m∈N∪D∪Mxjmktjm≥Tmin,∀k∈K,(19)FMin≤fk≤FMax,∀k∈K,(20)RMin≤rk=∑∀j∈NqjkQ≤RMax,∀k∈K.Objective (1) aims at minimizing the total walking, riding, and waiting time of all passengers. Constraint (2) ensures that a demand point must be allocated to a selected stop. Constraint (3) ensures that each demand point must be assigned to a pick-up location. Constraint (4) ensures that the walking distance from each demand point to the bus stop is not less than the maximum allowable value. Constraint (5) ensures that each selected bus stop is covered by feeder buses. Constraint (6) ensures that each vehicle visits at least one selected stop. Constraints (7)–(10) are used for each route eventually starting from the depot and ending at the transportation hub. Constraint (11) indicates that each bus stop cannot be visited by two routes at the same time. Constraint (12) indicates that subtour elimination is met. Constraints (13) and (14) calculate the arrival time of the vehicle k visiting the current stop. Constraints (15) and (16) calculate the load capacity of adjacent stops visited by each route. Constraints (17) and (18) guarantee that travel mileage and time of each route should meet their upper and lower limits. Constraints (19) and (20) indicate that the frequency setting and load factor of each route must meet their minimum and maximum values.


## 3.2.1. Notation

To facilitate the problem presentation of the proposed model, mathematical symbols of related parameters and variables are summarized in Table1.Table 1
Mathematical symbols in the FTS model.
Index:
i
Demand point
j
,
m
Vehicular node (depot, stop, and transportation hub) index
k
Route
Sets:
I
Set of demand points
K
Set of routes
N
Set of candidate stops
D
Set of depots
M
Set of transportation hubs
Parameters:
q
i
Number of persons at the demand pointsi during peak hours;∀i∈I
Q
Rated vehicle capacity
F
max
Maximum departure frequency
F
min
Minimum departure frequency
r
k
Load rate of routek
R
max
Maximum load rate
R
min
Minimum load rate
D
max
Maximum route length
T
min
Minimum travel time of feeder bus route
D
k
The total mileage of the routek visiting all vehicular nodes;∀k∈K
T
k
The total travel time of the routek visiting all vehicular nodes;∀k∈K
W
Maximum walking distance
v
Average walking speed
d
i
j
Map-based distance from rail stations, bus depots, and candidate route stop to demand pointi,j;∀i,j∈I∪M∪D∪N
t
i
j
Map-based distance from rail stations, bus depots, and candidate route stop to demand pointsi,j;∀i,j∈I∪M∪D∪N
H
Relatively large fixed value
Decision variables:
z
j
Whether the candidatej is selected as a feeder bus stop; ∀j∈N
h
i
j
Whether the demand pointi is assigned to a selected stop j;∀i∈I,∀j∈N
x
j
m
k
Whether a vehicular nodej precedes vehicular node m on the route k;∀k∈K,∀j∈N
f
k
Frequency of routek during peak hour
y
j
k
Whether the nodej is covered by the route k; ∀j∈I∪D∪M∪N, ∀k∈K
t
j
k
The travel time of the routek visiting vehicular node j;∀k∈K, ∀j∈I∪M∪D∪N
q
j
k
Number of persons at the vehicular nodej assigned to route k; ∀k∈K, ∀j∈I∪M∪D∪N
U
j
k
Auxiliary (real) variable for subtour elimination constraint in the route of busk; ∀k∈K


## 3.2.2. Formulation

(1)
max
f
=
∑
∀
i
∈
I
∑
∀
j
∈
N
h
i
j
⋅
d
i
j
v
⋅
q
i
+
∑
∀
j
∈
M
∑
∀
k
∈
K
y
j
k
⋅
∑
∀
i
∈
I
h
i
j
⋅
q
i
⋅
T
k
−
t
j
k
+
60
f
k
/
2
,subjected to(2)hij≤zj,∀i∈I,∀j∈N,(3)∑∀j∈Nhij=1,∀i∈I,(4)hij⋅dij≤W,∀i∈I,∀j∈N,(5)yjk≤zj,∀k∈K,∀j∈N,(6)∑∀j∈Nyjk≥1,∀k∈K,(7)∑∀j∈Ixjmk=1,∀k∈K,∀m∈M,(8)∑∀j∈Nxmjk=0,∀k∈K,∀m∈M,(9)∑∀j∈Nxjmk=0,∀k∈K,∀m∈D,(10)∑∀j∈Nxmjk=1,∀k∈K,∀m∈D,(11)∑∀m∈N∪D∪Mxjmk=∑∀m∈N∪D∪Mxmjk=yjk,∀k∈K,∀j∈N,(12)Ujk−Umk+N∪D∪M⋅xjmk≥N∪D∪M−1,∀k∈K,∀j,m∈N∪D∪M,(13)tjk+tjm−1−xjmkH≤tmk,∀k∈K,∀j,m∈N∪D∪M,(14)tjk+tjm+1−xjmkH≥tmk,∀k∈K,∀j,m∈N∪D∪M,(15)qjk+∑∀i∈Ihij⋅qi−1−xjmkH≤qmk,∀k∈K,∀j,m∈N∪D∪M,(16)qjk+∑∀i∈Ihij⋅qi+1−xjmkH≥qmk,∀k∈K,∀j,m∈N∪D∪M,(17)Dk=∑∀j,m∈N∪D∪Mxjmkdjm≤Dmax,∀k∈K,(18)Tk=∑∀j,m∈N∪D∪Mxjmktjm≥Tmin,∀k∈K,(19)FMin≤fk≤FMax,∀k∈K,(20)RMin≤rk=∑∀j∈NqjkQ≤RMax,∀k∈K.Objective (1) aims at minimizing the total walking, riding, and waiting time of all passengers. Constraint (2) ensures that a demand point must be allocated to a selected stop. Constraint (3) ensures that each demand point must be assigned to a pick-up location. Constraint (4) ensures that the walking distance from each demand point to the bus stop is not less than the maximum allowable value. Constraint (5) ensures that each selected bus stop is covered by feeder buses. Constraint (6) ensures that each vehicle visits at least one selected stop. Constraints (7)–(10) are used for each route eventually starting from the depot and ending at the transportation hub. Constraint (11) indicates that each bus stop cannot be visited by two routes at the same time. Constraint (12) indicates that subtour elimination is met. Constraints (13) and (14) calculate the arrival time of the vehicle k visiting the current stop. Constraints (15) and (16) calculate the load capacity of adjacent stops visited by each route. Constraints (17) and (18) guarantee that travel mileage and time of each route should meet their upper and lower limits. Constraints (19) and (20) indicate that the frequency setting and load factor of each route must meet their minimum and maximum values.


## 4. Solution Method

This model involves four core variables, includingzj,hij,xjmk, and fk, where hij decides zj. Obviously, demand point i can be assigned to route k according to hij and xjmk. Hence, a two-stage GA-based heuristic approach [7, 35, 36] was developed to solve this problem.In the first stage, GA was used to allocate all demand points to different routes and calculate their departure frequencies according to the passenger flow of each route, where the total waiting time of passengers at stops in the objective function was determined.In the second stage, the greedy algorithm and the Dijkstra algorithm were embedded in GA, where demand points were assigned to selected stops, and feeder routes were designed to visit these selected stops. Through these two operations, the total walking time and riding time of all passengers at demand points in the objective function were also determined.


### 4.1. GA in the First Stage

The chromosome of solution to the problem was represented by a two-dimensional vectorU=U1,U2, where each element ui in U1=u1,u2,…,uI, being a natural number in 1, 2, ..., K, denotes a route ui visiting the demand point i (i = 1, 2, …, I); each element uk in U2=uI+1,uI+2,…,uI+K, being a real number, denotes departure frequency of the route k (k = 1, 2, …, K). For example, a chromosome vector U = {11221245} of two routes and six demand points could be coded as follows: route 1 visits demand points 1, 2, and 5; route 2 visits demand point 3, 4, and 6; and the departure frequencies of the two routes are 4 and 5, respectively.A randomly generated chromosome may not comply with the partial constraint. To evaluate the quality of chromosomes, the fitness function is designed using penalty functions to eliminate infeasible solutions from the population in the process of evolution.(21)F=f+H⋅∑∀k∈Kmax∑∀i,j∈N∪D∪Mxijkdij−Dmax,0+max∑∀i,j∈N∪D∪Mxijktij−Tmin,0+H⋅maxfk−Fmax,0+maxFmin−fk,0+H⋅max∑∀j∈NqjkQ−Rmax,0+maxRmin−∑∀j∈NqjkQ,0.Figure3 details the evolutionary process of the GA. A given number of solutions were randomly generated in the initial population. Note that the departure frequency of the route could be obtained to determine the part of the evaluation fitness function. A specific heuristic at the second stage was embedded in this first-stage algorithm to obtain the assignment of each demand point to one of the nearest stops and route visiting stops to determine the rest of the evaluation fitness function. After evaluating the fitness values of these solutions, a certain number of offspring were generated from parents using the roulette-wheel selection method. To generate a better solution, single-point crossover and mutation operators were then adopted to exchange genes of any two individuals, or the genes of the individuals themselves to prevent the same genes in individual chromosome from appearing on next population. The algorithm was stopped until a preset maximal number was met.Figure 3
Flowchart of the GA-based two-stage algorithm.


### 4.2. Greedy and Dijkstra Algorithm in the Second Stage

In the first stage, all demand points were assigned to different routes. If the assignment of each demand point to one of the nearest stops and a sequence of stops along with designed routes were determined, a complete solution could be obtained.In this section, a stop would be selected for each demand point based on the principle of minimization of walking distance, that is,hij=jminpi⋅dij/v,∀i∈I, ∀j∈N. In such a case, the Dijkstra algorithm (seen from references 6 and 7) was implemented to search the shortest route dispatching from a depot to the transportation hub so as to order the sequence of selected stops for the route, that is, xjmk.


### 4.3. Numerical Example

#### 4.3.1. Example Description and Data Preparation

An FTS network, consisting of 5 depots (D1–D1), 25 demand points (P1–P25), 42 candidate stops (S1–S42), and 1 transportation hub (M), was used in the case study to prove the effectiveness of models and algorithms. The travel information of all passengers is shown in Table2. The main inputs of this study were as follows:(i)
Number of routes: 3(ii)
Capacity of a vehicle: 35 per(iii)
Maximum travel time of each route: 30 min(iv)
Minimum length of each route: 4 km(v)
Minimum and maximum hourly departure frequencies: 5 and 10(vi)
Minimum and maximum load factor: 0.7 and 1.2(vii)
Walking speedv = 110 m/min(vii)
Parameters of the hybrid algorithm: iteration times, 100; chromosome number, 500; crossover rate, 0.9; and mutation rate, 0.1Table 2
Information of all demand points.
No.
q
i
P1
21
P2
36
P3
40
P4
63
P5
18
P6
32
P7
17
P8
24
P9
24
P10
16
P11
23
P12
27
P13
13
P14
32
P15
40
P16
36
P17
17
P18
35
P19
23
P20
48
P21
42
P22
35
P23
42
P24
40
P25
35


## 4.1. GA in the First Stage

The chromosome of solution to the problem was represented by a two-dimensional vectorU=U1,U2, where each element ui in U1=u1,u2,…,uI, being a natural number in 1, 2, ..., K, denotes a route ui visiting the demand point i (i = 1, 2, …, I); each element uk in U2=uI+1,uI+2,…,uI+K, being a real number, denotes departure frequency of the route k (k = 1, 2, …, K). For example, a chromosome vector U = {11221245} of two routes and six demand points could be coded as follows: route 1 visits demand points 1, 2, and 5; route 2 visits demand point 3, 4, and 6; and the departure frequencies of the two routes are 4 and 5, respectively.A randomly generated chromosome may not comply with the partial constraint. To evaluate the quality of chromosomes, the fitness function is designed using penalty functions to eliminate infeasible solutions from the population in the process of evolution.(21)F=f+H⋅∑∀k∈Kmax∑∀i,j∈N∪D∪Mxijkdij−Dmax,0+max∑∀i,j∈N∪D∪Mxijktij−Tmin,0+H⋅maxfk−Fmax,0+maxFmin−fk,0+H⋅max∑∀j∈NqjkQ−Rmax,0+maxRmin−∑∀j∈NqjkQ,0.Figure3 details the evolutionary process of the GA. A given number of solutions were randomly generated in the initial population. Note that the departure frequency of the route could be obtained to determine the part of the evaluation fitness function. A specific heuristic at the second stage was embedded in this first-stage algorithm to obtain the assignment of each demand point to one of the nearest stops and route visiting stops to determine the rest of the evaluation fitness function. After evaluating the fitness values of these solutions, a certain number of offspring were generated from parents using the roulette-wheel selection method. To generate a better solution, single-point crossover and mutation operators were then adopted to exchange genes of any two individuals, or the genes of the individuals themselves to prevent the same genes in individual chromosome from appearing on next population. The algorithm was stopped until a preset maximal number was met.Figure 3
Flowchart of the GA-based two-stage algorithm.


## 4.2. Greedy and Dijkstra Algorithm in the Second Stage

In the first stage, all demand points were assigned to different routes. If the assignment of each demand point to one of the nearest stops and a sequence of stops along with designed routes were determined, a complete solution could be obtained.In this section, a stop would be selected for each demand point based on the principle of minimization of walking distance, that is,hij=jminpi⋅dij/v,∀i∈I, ∀j∈N. In such a case, the Dijkstra algorithm (seen from references 6 and 7) was implemented to search the shortest route dispatching from a depot to the transportation hub so as to order the sequence of selected stops for the route, that is, xjmk.


## 4.3. Numerical Example

### 4.3.1. Example Description and Data Preparation

An FTS network, consisting of 5 depots (D1–D1), 25 demand points (P1–P25), 42 candidate stops (S1–S42), and 1 transportation hub (M), was used in the case study to prove the effectiveness of models and algorithms. The travel information of all passengers is shown in Table2. The main inputs of this study were as follows:(i)
Number of routes: 3(ii)
Capacity of a vehicle: 35 per(iii)
Maximum travel time of each route: 30 min(iv)
Minimum length of each route: 4 km(v)
Minimum and maximum hourly departure frequencies: 5 and 10(vi)
Minimum and maximum load factor: 0.7 and 1.2(vii)
Walking speedv = 110 m/min(vii)
Parameters of the hybrid algorithm: iteration times, 100; chromosome number, 500; crossover rate, 0.9; and mutation rate, 0.1Table 2
Information of all demand points.
No.
q
i
P1
21
P2
36
P3
40
P4
63
P5
18
P6
32
P7
17
P8
24
P9
24
P10
16
P11
23
P12
27
P13
13
P14
32
P15
40
P16
36
P17
17
P18
35
P19
23
P20
48
P21
42
P22
35
P23
42
P24
40
P25
35


## 4.3.1. Example Description and Data Preparation

An FTS network, consisting of 5 depots (D1–D1), 25 demand points (P1–P25), 42 candidate stops (S1–S42), and 1 transportation hub (M), was used in the case study to prove the effectiveness of models and algorithms. The travel information of all passengers is shown in Table2. The main inputs of this study were as follows:(i)
Number of routes: 3(ii)
Capacity of a vehicle: 35 per(iii)
Maximum travel time of each route: 30 min(iv)
Minimum length of each route: 4 km(v)
Minimum and maximum hourly departure frequencies: 5 and 10(vi)
Minimum and maximum load factor: 0.7 and 1.2(vii)
Walking speedv = 110 m/min(vii)
Parameters of the hybrid algorithm: iteration times, 100; chromosome number, 500; crossover rate, 0.9; and mutation rate, 0.1Table 2
Information of all demand points.
No.
q
i
P1
21
P2
36
P3
40
P4
63
P5
18
P6
32
P7
17
P8
24
P9
24
P10
16
P11
23
P12
27
P13
13
P14
32
P15
40
P16
36
P17
17
P18
35
P19
23
P20
48
P21
42
P22
35
P23
42
P24
40
P25
35


## 5. Results

The solution involves stop selection, pedestrian guidance, transit routing, and scheduling. Table3 details the assignment of all demand points to selected stops visited by three routes, which include the number of people getting on and off at a station and the walking distance between demand points and selected stops. Taking a selected stop S3 visited by the route R1 as an example, passengers at P3 and P12 get on at this place by walking 303.9 m and 244.9 m, respectively. Table 4 also details the routing and scheduling plans for these routes, which include the route length, running time, departure frequency, and load factor. Taking the route R1 as an example, the total number of passengers was 142 per/h, so the departure frequency was 5 veh/h, and the load rate was 0.81. A map-based graphical illustration of bus routing plans and passenger guidance is shown in Figure 4, where a yellow circle denotes the transportation hub, a red square denotes a depot, a blue dot denotes a stop, and a black dot denotes a demand point. The green dash line represents route 1, the red dash line represents route 2, and the blue dash line represents route 3. In addition to the bus route plan, the red solid lines between selected blue dots and all-black dots indicate the walking paths of passengers.Table 3
Assignment of all demand points to selected pick-up stops visited by routes.
Demand point
Selected stops
Number of persons
Assigned route
Walk distance (m)
P7
S3
44
R1
303.9
P12
244.9
P11
S6
23
111.3
P24
S34
40
73.7
P25
S22
35
106.9
P1
S11
21
R2
219.8
P2
S10
36
215.6
P3
S13
40
54.8
P4
S14
63
140.9
P5
S15
18
192
P6
S16
32
116.6
P8
S8
24
38.
P9
S7
24
175.5
P10
S5
16
145.3
P13
S4
45
439.7
P14
235.8
P15
S17
40
219.6
P16
S30
36
R3
188.4
P17
S24
17
78.9
P18
S26
35
66.2
P19
S41
71
106.7
P20
36.7
P21
S40
42
13.3
P22
S39
35
20
P23
S32
42
147.3Table 4
Optimal scheme for route design and frequency setting.
Route
Sequence of stops visited by routes
Frequencies
Load rate
Length (km)
Travel time (min)
R1
D1-S3-S6-S22-S34-M
5
0.81
12.0
25.6
R2
D2-S4-S5-S7-S8-S10-S11-S13-S14-S15-S16-S17-M
9
1.14
10.5
19.3
R3
D3-S24-S26-S30-S32-S39-S40-S41-M
9
0.88
9.9
24.5Figure 4
Roadmap of the optimal solution.Furthermore, Figure5 analyzes the difference in solution performance between the traditional and the proposed model under three routes. The walking distance of these two models remained unchanged due to the reasonable layout of demand points and stops. Compared with the traditional model, the total travel time in this study increased while the total waiting time decreased. As the increase in the former was less than the decrease in the latter, the objective value (i.e., total travel time) in this study was less than that of the traditional model. This was because this study considered the route design and departure frequency to pursue global optimization, avoiding local optimum of the traditional model, where first the route design is determined and then the departure frequency is calculated.Figure 5
Comparative analysis of the traditional and the proposed models under three routes.


### 5.1. Sensitivity Analysis

Table5 also analyzes the influence of different routes on the model performance. The results are shown as follows:(1)
As each route started from the depot and returned to the transportation hub, the increase in the number of routes led to some invalid mileage and time, which increased the total travel distance and time of all routes. However, the total riding time of passengers gradually reduced.(2)
As the number of routes increased, the number of passengers in demand points visited by each route decreased, which led to a reduction in the departure frequency. In such a case, the waiting time of all passengers was gradually increased.(3)
With the increase in the number of routes, the total walking time of passengers remained unchanged because passengers tended to choose the nearest stops to get on and off the bus. Hence, the changing trend of the objective function was related to the decrease in the travel time of the passengers and the increase in the waiting time.Table 5
Comparison of model and algorithm performance under different routes.
Scenario
Objective (min)
Computation time (min)
Total riding time (min)
Total waiting time (min)
Total walking time (min)
Average load factor
Total frequency
Total route length (km)
Total route time (min)
Cplex
GA
Cplex
GA
3 routes
10230.3
9472.5
20.1
1.2
6717.8
1798.7
956.1
0.94
23
32.4
69.4
4 routes
9398.1
8621.8
126.3
1.6
5580.5
20851
956.1
0.74
30
33.1
73.8
5 routes
9557.2
8900.2
1514.6
1.9
4798.8
3145.3
956.1
0.74
30
35.7
76.0Besides, the difference in the solution quality between the proposed algorithm and the Cplex was within 10%, but the solution time greatly reduced, which proved the effectiveness of the algorithm.Finally, Figure6 further analyzes the difference in model performance between the traditional and the proposed models under different routes. Their waiting time reduced, and riding time increased. The results were consistent with those shown in Figure 5.Figure 6
Comparative analysis of the traditional and the proposed models under different routes.


## 5.1. Sensitivity Analysis

Table5 also analyzes the influence of different routes on the model performance. The results are shown as follows:(1)
As each route started from the depot and returned to the transportation hub, the increase in the number of routes led to some invalid mileage and time, which increased the total travel distance and time of all routes. However, the total riding time of passengers gradually reduced.(2)
As the number of routes increased, the number of passengers in demand points visited by each route decreased, which led to a reduction in the departure frequency. In such a case, the waiting time of all passengers was gradually increased.(3)
With the increase in the number of routes, the total walking time of passengers remained unchanged because passengers tended to choose the nearest stops to get on and off the bus. Hence, the changing trend of the objective function was related to the decrease in the travel time of the passengers and the increase in the waiting time.Table 5
Comparison of model and algorithm performance under different routes.
Scenario
Objective (min)
Computation time (min)
Total riding time (min)
Total waiting time (min)
Total walking time (min)
Average load factor
Total frequency
Total route length (km)
Total route time (min)
Cplex
GA
Cplex
GA
3 routes
10230.3
9472.5
20.1
1.2
6717.8
1798.7
956.1
0.94
23
32.4
69.4
4 routes
9398.1
8621.8
126.3
1.6
5580.5
20851
956.1
0.74
30
33.1
73.8
5 routes
9557.2
8900.2
1514.6
1.9
4798.8
3145.3
956.1
0.74
30
35.7
76.0Besides, the difference in the solution quality between the proposed algorithm and the Cplex was within 10%, but the solution time greatly reduced, which proved the effectiveness of the algorithm.Finally, Figure6 further analyzes the difference in model performance between the traditional and the proposed models under different routes. Their waiting time reduced, and riding time increased. The results were consistent with those shown in Figure 5.Figure 6
Comparative analysis of the traditional and the proposed models under different routes.


## 6. Conclusions

This study presented an integrated model for FTS to simultaneously coordinate stop selection, feeder transit routing, and frequency-setting process to trade off the operation efficiency. To solve such an NP-hard large-scale problem, a two-stage heuristic algorithm-based GA was further designed, where the assignment of all demand points to selected pick-up locations visited by different routes, as well as the determination of departure frequency, was obtained using GA in the first stage. In the second stage, the Dijkstra algorithm was embedded in the GA to calculate the shortest path for the vehicle visiting selected stops. A case study showed that the proposed model could save 0.34% of the total travel time for all residents, compared with the traditional model. The main reason was that the traditional model separated the line design from the departure frequency, which led to the departure frequency range and full-load level not affecting the design process of the route layout. In such a case, the passenger flow of each route might be unbalanced and the waiting time of some routes might increase. In order to validate the performance of developed heuristic algorithm, a comparison of CPLEX solutions and heuristic algorithm solutions in case of designing 3 routes, 4 routes, and 5 routes, respectively, the results suggested that the proposed algorithm can yield effective solutions to the proposed problem in an acceptable computation time. Furthermore, the increase in the number of routes led to the decrease in the travel time of the passengers and the increase in the waiting time.A reduction in the departure frequency of each route was also done.However, the premise of this study was that each demand point must be assigned to only a selected stop, which neglected the notion that travel needs were split and each group of passengers could choose a different stop to get on and off the bus when the number of passengers at the demand points exceeded the route capacity. Further, inferred OD table and travel time are static in this paper. In this sense, the problem considered here is that model uses a static representation of the pedestrian and vehicular network. Hence, it is worthwhile to extend the proposed model with a split travel demand and time-varying demand and travel times in future studies.



---

*Source: 6517248-2020-03-09.xml*