# Flexible Bus Route Optimization for Multitarget Stations

Authors: Sun Ji-yang; Huang Jian-ling; Chen Yan-yan; Wei Pan-yi; Jia Jian-lin
Journal: Mathematical Problems in Engineering
 (2020)

---

## Abstract

This paper proposes a flexible bus route optimization model for efficient public city transportation systems based on multitarget stations. The model considers passenger demands, vehicle capacities, and transportation network and aims to solve the optimal route, minimizing the vehicles’ running time and the passengers’ travel time. A heuristic algorithm based on a gravity model is introduced to solve this NP-hard optimization problem. Simulation studies verify the effectiveness and practicality of the proposed model and algorithm. The results show that the total number of vehicles needed to complete the service is 17–21, the average travel time of each vehicle is 24.59 minutes, the solving time of 100 sets of data is within 25 seconds, and the average calculation time is 12.04 seconds. It can be seen that under the premise of real-time adjustment of connection planning time, the optimization model can satisfy the passenger’s dynamic demand to a greater extent, and effectively reduce the planning path error, shorten the distance and travel time of passengers, and the result is better than that of the flexible bus scheduling model which ignores the change of connection travel time.


---

## Body

## 1. Introduction

The concept of a flexible bus service system was originally proposed in 1976 by Flusberg M [1]. Koffman [2] classified flexible bus service systems for the first time in terms of line offsets, station offsets, demand response shuttles, demand response stations, section flexible buses, and regional flexible buses services. Although referred to the flexible bus service system, its plans, designs, and operations were more complex than the fixed one, it has not yet been used worldwide.Currently, there are relatively few research studies on flexible bus service systems especially on multiple flexible stations corresponding to one target station. By constructing a model [3, 4], the relationships between key parameters such as slack time [5], departure interval, and several bus routes are analyzed. For example, Lu et al. [6] proposed a three-stage model to find the nearest vehicle to serve passenger demands when many buses are operating in the target service area. The multibus route optimization scheme proposed by Liu and Yang [7] is based on a mixed integer programming model. Considering the space and time requirements of passengers to reach the central rail or bus station, the optimal bus service is determined. Pillac et al. [8] defined the concept of dynamic routes, solved the vehicle dynamic path problem, and obtained the optimal route. Based on the heuristic algorithm of an improved gravity model, Pan et al. [9] established a flexible bus route optimization and collaborative scheduling model to solve the single objective bus service problem. Alonso-Mora et al. [10] focused on dynamic high-capacity carpooling and designed many-to-one, flexible bus demand response strategies based on vehicle-demand analysis. Motivated by emerging transportation technologies and business modes, researchers devoted their efforts to a wide range of innovative mobility studies of the “many-to-one” mode, such as flexing service schedules for demand-adaptive hybrid transit [11], flexible mobility on demand transportation systems [12, 13], roundtrip car-sharing systems [14], and autonomous vehicle-sharing and reservation systems [15]. All the flexible bus connection modes involved in the above research studies are in the form of “many-to-one”, that is, multiple flexible stations corresponding to one target station. The case of multiple flexible sites corresponding to multiple target sites (the “many-to-many” pattern) has not been studied.To address both practical and theoretical challenges, this paper proposes an optimal flexible bus route scheduling model for multiobjective stations and considers the problem of station allocation in the route planning.


## 2. Problem Description and Modeling

### 2.1. Flexible Bus System Requirements under “Many-to-Many” Demand Mode

The flexible bus system is a demand-based transportation system, which can collect the travel needs of individual passengers and provide personalized transportation service [16, 17]. Compared with “many-to-one” bus feeder mode flexible bus system studied in Pan et al. [18] and Pan [19], the “many-to-many” mode studied in this paper has many merits and more flexibility. Its model construction and parameter selection need to consider various factors, such as passenger demand and operating cost.In this study, we focus on reducing operating costs of the vehicle operation enterprises and the time cost of passengers and improving the service quality of flexible bus systems. Then, we analyze the parameters and decision variables under the “many-to-many” condition (i.e., multiple flexible stations corresponding to multiple target sites), construct the objective function, and set boundary conditions to solve flexible bus route optimization problems for “many-to-many” modes.


### 2.2. Model Assumption

The following assumptions are made for the establishment of the proposed model:(1)
The location of each station and the requirements of passenger reservation are all known(2)
After reservation, the time of each passenger intends to reach the target station is known(3)
The service time for passengers arriving at the station is constant(4)
The travel time for all shuttle bus traveling between the stations is known(5)
The capacity of the shuttle bus is known


### 2.3. Model Parameter

The definitions and descriptions of the model inputs and decision variables involved in the model are shown in Table1.Table 1
Model parameter.
Variable
Definitions and descriptions
Parameter type
H
Passenger demand station set
Set of integers
D
Target station set
Set of integers
K
Shuttle operation vehicle set
Set of integers
R
Passenger demand set
Set of integers
N
Total passenger demand,N≥0
Parameters
V
Shuttle fleet size,V≥0
Parameters
M
A large constant
Constant
T
t
Thetth departure time of the target station
Decision variables
p
r
Pick-up stationp for passenger demand r
Decision variables
T
r
The starting time of the target station for passenger demandr
Decision variables
c
i
j
The traveling time between stationi and station j
Decision variables
Q
k
The capacity of shuttle busk,QK≥0
Decision variables
X
r
k
t
If shuttle busk connects demand r to the target station at time t, Xrkt = 1; otherwise, Xrkt = 0
Decision variables
Y
i
j
k
If shuttle busk selects the link i,j as driving path, Yijk = 1; otherwise, Yijk = 0
Decision variables
a
r
The time when the shuttle bus reaches the demand point where the demandr is located
Decision variables
e
r
Time of passenger demandr reaches target station
Decision variables
U
i
k
Auxiliary variable, ensure that the driving path of the shuttle busk does not appear loop, i indicates the shuttle bus passing through the station, if shuttle bus k leaves station i, Uik = 0; if shuttle bus k arrives station i, Uik = 1
Auxiliary variable


### 2.4. Model Representation

To reduce operating costs of the vehicle operation enterprises and the time cost of passengers and improve the service quality of flexible bus systems, in this study, we chose vehicle operating time, passenger waiting time before boarding, and the difference between the actual and the expected arrival time of passengers as the main decision variables.Then, the scheduling optimization model needs to solve a nonlinear programming problem, as shown in equation (1), which should minimize the sum of the three decision variables, including vehicle operating time, passenger waiting time before boarding, and the difference between the actual and the expected arrival time of passengers:(1)min∑i∈H∪D∑j∈H∪D∑k∈KcijYijk+∑r∈Rar+∑r∈R∑k∈K∑tXrktTt−er.Equation (1) is the objective function. Within it, ∑i∈H∪D∑j∈H∪D∑k∈KcijYijk represents vehicle operating time, ar represents passenger waiting time before boarding, and ∑r∈R∑k∈K∑tXrktTt−er represents the difference between the actual and the expected arrival time of passengers. The boundary conditions are as follows:(2)∑j∈H∪D∑k∈KYijk≥1,∀i∈H,(3)∑j∈H∪D∑k∈KYijk≤V,∀i∈H,(4)∑i∈H∑k∈KYijk≤V,∀j∈D,(5)∑j∈H∪DYijk−∑p∈HYpik≥0,∀i∈H,k∈K,(6)Uik−Ujk+H×Yijk≤H−1,∀i,j∈H∪D,k∈K,(7)∑i∈H∑j∈DYijk≥1,∀k∈K,(8)∑i∈H∑j∈DYijk≤0,∀k∈K,(9)∑r∈R∑t∈TXrkt≤Qk,∀k∈K,(10)∑k∈K∑t∈TXrkt=1,∀r∈R,(11)∑m∈T/tXskm−1−XrktM≤0,∀r,s∈R,∀k∈K,∀t∈T,(12)∑r∈R∑k∈K∑t∈tXrkt=N,(13)ar+cprps−as+YprpskM≤M,∀r,s∈R,∀k∈K,(14)as−ar−cprps+YprpskM≤M,∀r,s∈R,∀k∈K,(15)ar+cprj−as+YprpskM≤M,∀r∈R,∀k∈K,∀j∈D,(16)as−ar−cprj+YprpskM≤M,∀r∈R,∀k∈K,∀j∈D,(17)er≤∑k∈K∑t∈TXrktTt,∀r∈R.Constraints (2) and (3) indicate that for any demand point, at least one bus is available for service and at most V bus is available. Constraint (4) ensures that at most v vehicles participate in operation services. Constraint (5) indicates that except the first demand point of each vehicle, for every other demand point being serviced, the number of entering vehicles should be equal to the ones that are driven out. Constraint (6) is to avoid loops in the driving path. Constraints (7) and (8) ensure that every passenger will be transported to the final destination. Constraint (9) ensures that the capacity of each shuttle bus will not overtake its rated capacity to guarantee service levels. Constraint (10) indicates that any demand can only be served by one bus. Constraint (11) indicates that a shuttle bus can only serve a passenger at a departure time of a target station. Constraint (12) guarantees all demand serviced equal to the known amount of reservation required. Constraints (13) and (14) indicate that if two stations are serviced by a transfer vehicle, the arrival time of the demand in the next station should be equal to the sum of the arrival time of the demand in the last demand point and the travel times between two demand points. Constraints (15) and (16) indicate that the time of the passenger at the last demand station of the shuttle bus arriving at the target station should be equal to the time that the vehicle reached the demand point and the travel time between the two demand points. Constraint (17) ensures that the time of vehicle arriving at the target station is not later than the departure time.


## 2.1. Flexible Bus System Requirements under “Many-to-Many” Demand Mode

The flexible bus system is a demand-based transportation system, which can collect the travel needs of individual passengers and provide personalized transportation service [16, 17]. Compared with “many-to-one” bus feeder mode flexible bus system studied in Pan et al. [18] and Pan [19], the “many-to-many” mode studied in this paper has many merits and more flexibility. Its model construction and parameter selection need to consider various factors, such as passenger demand and operating cost.In this study, we focus on reducing operating costs of the vehicle operation enterprises and the time cost of passengers and improving the service quality of flexible bus systems. Then, we analyze the parameters and decision variables under the “many-to-many” condition (i.e., multiple flexible stations corresponding to multiple target sites), construct the objective function, and set boundary conditions to solve flexible bus route optimization problems for “many-to-many” modes.


## 2.2. Model Assumption

The following assumptions are made for the establishment of the proposed model:(1)
The location of each station and the requirements of passenger reservation are all known(2)
After reservation, the time of each passenger intends to reach the target station is known(3)
The service time for passengers arriving at the station is constant(4)
The travel time for all shuttle bus traveling between the stations is known(5)
The capacity of the shuttle bus is known


## 2.3. Model Parameter

The definitions and descriptions of the model inputs and decision variables involved in the model are shown in Table1.Table 1
Model parameter.
Variable
Definitions and descriptions
Parameter type
H
Passenger demand station set
Set of integers
D
Target station set
Set of integers
K
Shuttle operation vehicle set
Set of integers
R
Passenger demand set
Set of integers
N
Total passenger demand,N≥0
Parameters
V
Shuttle fleet size,V≥0
Parameters
M
A large constant
Constant
T
t
Thetth departure time of the target station
Decision variables
p
r
Pick-up stationp for passenger demand r
Decision variables
T
r
The starting time of the target station for passenger demandr
Decision variables
c
i
j
The traveling time between stationi and station j
Decision variables
Q
k
The capacity of shuttle busk,QK≥0
Decision variables
X
r
k
t
If shuttle busk connects demand r to the target station at time t, Xrkt = 1; otherwise, Xrkt = 0
Decision variables
Y
i
j
k
If shuttle busk selects the link i,j as driving path, Yijk = 1; otherwise, Yijk = 0
Decision variables
a
r
The time when the shuttle bus reaches the demand point where the demandr is located
Decision variables
e
r
Time of passenger demandr reaches target station
Decision variables
U
i
k
Auxiliary variable, ensure that the driving path of the shuttle busk does not appear loop, i indicates the shuttle bus passing through the station, if shuttle bus k leaves station i, Uik = 0; if shuttle bus k arrives station i, Uik = 1
Auxiliary variable


## 2.4. Model Representation

To reduce operating costs of the vehicle operation enterprises and the time cost of passengers and improve the service quality of flexible bus systems, in this study, we chose vehicle operating time, passenger waiting time before boarding, and the difference between the actual and the expected arrival time of passengers as the main decision variables.Then, the scheduling optimization model needs to solve a nonlinear programming problem, as shown in equation (1), which should minimize the sum of the three decision variables, including vehicle operating time, passenger waiting time before boarding, and the difference between the actual and the expected arrival time of passengers:(1)min∑i∈H∪D∑j∈H∪D∑k∈KcijYijk+∑r∈Rar+∑r∈R∑k∈K∑tXrktTt−er.Equation (1) is the objective function. Within it, ∑i∈H∪D∑j∈H∪D∑k∈KcijYijk represents vehicle operating time, ar represents passenger waiting time before boarding, and ∑r∈R∑k∈K∑tXrktTt−er represents the difference between the actual and the expected arrival time of passengers. The boundary conditions are as follows:(2)∑j∈H∪D∑k∈KYijk≥1,∀i∈H,(3)∑j∈H∪D∑k∈KYijk≤V,∀i∈H,(4)∑i∈H∑k∈KYijk≤V,∀j∈D,(5)∑j∈H∪DYijk−∑p∈HYpik≥0,∀i∈H,k∈K,(6)Uik−Ujk+H×Yijk≤H−1,∀i,j∈H∪D,k∈K,(7)∑i∈H∑j∈DYijk≥1,∀k∈K,(8)∑i∈H∑j∈DYijk≤0,∀k∈K,(9)∑r∈R∑t∈TXrkt≤Qk,∀k∈K,(10)∑k∈K∑t∈TXrkt=1,∀r∈R,(11)∑m∈T/tXskm−1−XrktM≤0,∀r,s∈R,∀k∈K,∀t∈T,(12)∑r∈R∑k∈K∑t∈tXrkt=N,(13)ar+cprps−as+YprpskM≤M,∀r,s∈R,∀k∈K,(14)as−ar−cprps+YprpskM≤M,∀r,s∈R,∀k∈K,(15)ar+cprj−as+YprpskM≤M,∀r∈R,∀k∈K,∀j∈D,(16)as−ar−cprj+YprpskM≤M,∀r∈R,∀k∈K,∀j∈D,(17)er≤∑k∈K∑t∈TXrktTt,∀r∈R.Constraints (2) and (3) indicate that for any demand point, at least one bus is available for service and at most V bus is available. Constraint (4) ensures that at most v vehicles participate in operation services. Constraint (5) indicates that except the first demand point of each vehicle, for every other demand point being serviced, the number of entering vehicles should be equal to the ones that are driven out. Constraint (6) is to avoid loops in the driving path. Constraints (7) and (8) ensure that every passenger will be transported to the final destination. Constraint (9) ensures that the capacity of each shuttle bus will not overtake its rated capacity to guarantee service levels. Constraint (10) indicates that any demand can only be served by one bus. Constraint (11) indicates that a shuttle bus can only serve a passenger at a departure time of a target station. Constraint (12) guarantees all demand serviced equal to the known amount of reservation required. Constraints (13) and (14) indicate that if two stations are serviced by a transfer vehicle, the arrival time of the demand in the next station should be equal to the sum of the arrival time of the demand in the last demand point and the travel times between two demand points. Constraints (15) and (16) indicate that the time of the passenger at the last demand station of the shuttle bus arriving at the target station should be equal to the time that the vehicle reached the demand point and the travel time between the two demand points. Constraint (17) ensures that the time of vehicle arriving at the target station is not later than the departure time.


## 3. Model Solving

The flexible bus route optimization scheduling problem for multitarget stations proposed in this paper is an NP-hard problem. Compared with the “many-to-one” shuttle bus mode, the burden of computation will increase exponentially as the scale of the problem expands. Therefore, this type of problem is usually solved by heuristic algorithms that can guarantee both computation speed and accuracy. In this paper, a heuristic algorithm based on a gravity model is proposed. Firstly, a superior initial solution is generated based on the gravity model, then the optimization algorithm between routes and within routes is used to improve the route, respectively, and then the final route is obtained. The specific steps are as follows.


### 3.1. Passenger Travel Reservation and Demand Distribution

First, the passenger travel reservation and demand distribution are completed as follows:Step 1: passengers make a travel appointment according to their travel needs. Each passenger transmits their information, such as the departure station, the target station, and the time expected to arrive, to the travel reservation platform.Step 2: the travel reservation platform clusters all passengers based on the target station and the expected arriving time of each passenger, according to the principle that the actual arrival time is not later than the passenger’s expectation.Step 3: according to the path generation results in2.2 and 2.3, combined with the arrival time of the shuttle bus, the average driving speed, the location of the passenger demand point, the number of passengers at each demand point, etc., the initial arrival time of shuttle bus at each demand point is estimated.Step 4: the initially estimated time of shuttle bus arriving at the demand point is sent to the passenger at the corresponding point, and the passenger will select whether to ride according to the rationality based on the arrival time of shuttle bus.


### 3.2. Generate Initial Vehicle Path Solution Based on Gravity Model

Based on the gravity model, the path search problem is transformed into a station selection iteration problem that is most attractive to the current station, so as to generate a feasible initial vehicle path solution. The gravitation between the two stations is defined as follows:(18)Fij=NiNjcij2.N
i is the number of passengers at the station i and cij is the travel time between station i and station j. If the value of Fij is large, the two stations have a large number of passengers and a small travel cost, which requires priority service, and the station j needs to be set to the next station of station i.In case a rated passenger capacity is known, the gravity model algorithm generates the initial path solution as follows:Step 1: determine the vehicle departure station. First,k=1, from the station with passengers on board, randomly picks one as the starting point for the vehicle.Step 2: judge whether there are still similar passengers who not served. If yes, skip to Step 3; otherwise, Step 5.Step 3: search for the next station. In the boarding station with similar passengers, find the stationX that is most attractive to the current station, try to drive in the station X into the route selection chain, calculate the number of passengers after the vehicle joins the station, and the time to reach the target station directly after joining the station X.Step 4: judge whether the route of the vehicle is reasonable after joining the stationX. If the current number of passengers served by the vehicle does not overtake the capacity Qk and the time to reach the target station does not overtake the time required by the passenger, take the station X as a new starting point and skip to Step 3; otherwise, Step 5.Step 5: judge whether all passengers are scheduled to serve. If there are still passengers not scheduled, dispatch the next bus,k=k+1 and jump to Step 1; otherwise, output all current initial paths and end the initial vehicle path solution generation algorithm based on the gravity model.


### 3.3. Vehicle Path Optimization Based on Station Equalization and Exchange

This section describes the path optimization algorithms between routes and within routes. Step 1 and Step 2 of the following algorithms all belong to the optimization between vehicle paths. During execution of Step 1 and Step 2, multigroups of feasible solutions may be searched. If only the current optimal set of solutions is saved during the search, then Step 3 is executed, and the final route result may not be optimal. Therefore, the algorithm will save all feasible solutions found by Step 1 and Step 2 and execute Step 3 for each feasible solution. Finally, review the objective functions of all route groups to find the final optimal solution.Step 1: First, the number of stations is balanced between vehicles that the time to serve the target station is equal to the time to reach the target station. Check if there is a gap between the number of vehicle service stations. If so, the number of stations on different routes will be balanced, and then the number of stations will be reasonably arranged on the premise for meeting the requirements of bus capacity and arrival time serve the target station is equal to the time to reach the target station. Check if there is a gap between the number of vehicle service stations. If so, the number of stations on different routes will be balanced, and then the number of stations will be reasonably arranged on the premise for meeting the requirements of bus capacity and arrival time.Step 2: try to optimize the path between vehicles that the time to serve the target station is equal to the time to reach the target station. It mainly uses the way of exchanging stations between two routes to search for better routes. Guarantee to meet the vehicle capacity and time to reach the target station.Step 3: it is the internal optimization for each bus route. Mainly in the same vehicle route, try to exchange the order of the two stations and evaluate whether the value of the objective function is reduced. Only if it is reduced, the station order is updated. After iterating a number of times, terminate the algorithm and output the final route result.After the abovementioned steps, it is ensured that passengers arrive at the target station as expected, the objective function of the model is optimized, the service time is shortened, the route of each vehicle is more reasonable, the operating cost is reduced, and the passenger's waiting time is reduced.


## 3.1. Passenger Travel Reservation and Demand Distribution

First, the passenger travel reservation and demand distribution are completed as follows:Step 1: passengers make a travel appointment according to their travel needs. Each passenger transmits their information, such as the departure station, the target station, and the time expected to arrive, to the travel reservation platform.Step 2: the travel reservation platform clusters all passengers based on the target station and the expected arriving time of each passenger, according to the principle that the actual arrival time is not later than the passenger’s expectation.Step 3: according to the path generation results in2.2 and 2.3, combined with the arrival time of the shuttle bus, the average driving speed, the location of the passenger demand point, the number of passengers at each demand point, etc., the initial arrival time of shuttle bus at each demand point is estimated.Step 4: the initially estimated time of shuttle bus arriving at the demand point is sent to the passenger at the corresponding point, and the passenger will select whether to ride according to the rationality based on the arrival time of shuttle bus.


## 3.2. Generate Initial Vehicle Path Solution Based on Gravity Model

Based on the gravity model, the path search problem is transformed into a station selection iteration problem that is most attractive to the current station, so as to generate a feasible initial vehicle path solution. The gravitation between the two stations is defined as follows:(18)Fij=NiNjcij2.N
i is the number of passengers at the station i and cij is the travel time between station i and station j. If the value of Fij is large, the two stations have a large number of passengers and a small travel cost, which requires priority service, and the station j needs to be set to the next station of station i.In case a rated passenger capacity is known, the gravity model algorithm generates the initial path solution as follows:Step 1: determine the vehicle departure station. First,k=1, from the station with passengers on board, randomly picks one as the starting point for the vehicle.Step 2: judge whether there are still similar passengers who not served. If yes, skip to Step 3; otherwise, Step 5.Step 3: search for the next station. In the boarding station with similar passengers, find the stationX that is most attractive to the current station, try to drive in the station X into the route selection chain, calculate the number of passengers after the vehicle joins the station, and the time to reach the target station directly after joining the station X.Step 4: judge whether the route of the vehicle is reasonable after joining the stationX. If the current number of passengers served by the vehicle does not overtake the capacity Qk and the time to reach the target station does not overtake the time required by the passenger, take the station X as a new starting point and skip to Step 3; otherwise, Step 5.Step 5: judge whether all passengers are scheduled to serve. If there are still passengers not scheduled, dispatch the next bus,k=k+1 and jump to Step 1; otherwise, output all current initial paths and end the initial vehicle path solution generation algorithm based on the gravity model.


## 3.3. Vehicle Path Optimization Based on Station Equalization and Exchange

This section describes the path optimization algorithms between routes and within routes. Step 1 and Step 2 of the following algorithms all belong to the optimization between vehicle paths. During execution of Step 1 and Step 2, multigroups of feasible solutions may be searched. If only the current optimal set of solutions is saved during the search, then Step 3 is executed, and the final route result may not be optimal. Therefore, the algorithm will save all feasible solutions found by Step 1 and Step 2 and execute Step 3 for each feasible solution. Finally, review the objective functions of all route groups to find the final optimal solution.Step 1: First, the number of stations is balanced between vehicles that the time to serve the target station is equal to the time to reach the target station. Check if there is a gap between the number of vehicle service stations. If so, the number of stations on different routes will be balanced, and then the number of stations will be reasonably arranged on the premise for meeting the requirements of bus capacity and arrival time serve the target station is equal to the time to reach the target station. Check if there is a gap between the number of vehicle service stations. If so, the number of stations on different routes will be balanced, and then the number of stations will be reasonably arranged on the premise for meeting the requirements of bus capacity and arrival time.Step 2: try to optimize the path between vehicles that the time to serve the target station is equal to the time to reach the target station. It mainly uses the way of exchanging stations between two routes to search for better routes. Guarantee to meet the vehicle capacity and time to reach the target station.Step 3: it is the internal optimization for each bus route. Mainly in the same vehicle route, try to exchange the order of the two stations and evaluate whether the value of the objective function is reduced. Only if it is reduced, the station order is updated. After iterating a number of times, terminate the algorithm and output the final route result.After the abovementioned steps, it is ensured that passengers arrive at the target station as expected, the objective function of the model is optimized, the service time is shortened, the route of each vehicle is more reasonable, the operating cost is reduced, and the passenger's waiting time is reduced.


## 4. Case Analysis

The abovementioned model is solved for a small network to verify the accuracy and applicability of the proposed approach. The parameters of the model are shown in Tables2–4. Some input parameters of constant variables are given in Table 2. The passenger travel demands in all stations are listed in Table 3, and the travel time between each station is listed in Table 4 in the form of a matrix, where H is the demand point and D is the target station.Table 2
Constants and variables.
Variable name
Value of the variable
Number of demand points
15
Number of target stations
3
Vehicle rated passenger capacity
7
Fleet size (veh)
18
Expected arrival time (minute)
35/45/55Table 3
The demand at each demand point.
Passenger number
Departure station
Target station
Expected arrival time (minute)
Passenger number
Departure station
Target station
Expected arrival time (minute)
Passenger number
Departure station
Target station
Expected arrival time (minute)
1
1
1
35
31
1
2
35
61
1
3
35
2
1
1
45
32
1
2
55
62
1
3
55
3
2
1
35
33
2
2
55
63
1
3
55
4
2
1
45
34
2
2
35
64
2
3
35
5
2
1
55
35
3
2
55
65
2
3
55
6
3
1
35
36
3
2
35
66
3
3
35
7
3
1
55
37
3
2
45
67
3
3
45
8
4
1
35
38
4
2
35
68
4
3
35
9
5
1
35
39
5
2
35
69
5
3
35
10
5
1
45
40
5
2
45
70
5
3
45
11
5
1
45
41
5
2
55
71
5
3
55
12
5
1
55
42
6
2
55
72
5
3
55
13
6
1
45
43
6
2
35
73
6
3
35
14
6
1
55
44
6
2
45
74
6
3
45
15
7
1
35
45
7
2
35
75
7
3
35
16
7
1
45
46
7
2
55
76
7
3
55
17
7
1
55
47
8
2
55
77
8
3
55
18
8
1
35
48
8
2
35
78
8
3
35
19
8
1
55
49
8
2
45
79
8
3
45
20
9
1
45
50
9
2
45
80
9
3
45
21
10
1
35
51
10
2
45
81
10
3
45
22
10
1
55
52
10
2
55
82
10
3
55
23
11
1
45
53
11
2
45
83
11
3
45
24
11
1
55
54
12
2
55
84
12
3
55
25
12
1
35
55
12
2
35
85
12
3
35
26
12
1
45
56
12
2
55
86
12
3
55
27
13
1
35
57
13
2
35
87
13
3
35
28
14
1
35
58
14
2
45
88
14
3
45
29
14
1
35
59
15
2
45
89
15
3
45
30
15
1
55
60
15
2
45
90
15
3
45Table 4
The travel time matrix in the case study.
H1
H2
H3
H4
H5
H6
H7
H8
H9
H10
H11
H12
H13
H14
H15
D
1
D
2
D
3
H1
—
8
5
3
6
6
5
8
4
8
4
7
7
4
5
6
9
3
H2
6
—
9
6
7
9
5
5
5
3
3
7
5
5
5
3
7
5
H3
6
7
—
6
5
7
7
7
8
9
6
3
5
6
8
7
7
6
H4
3
4
9
—
3
6
4
8
4
7
3
4
9
5
3
5
4
4
H5
5
8
3
5
—
7
9
8
6
3
9
4
3
3
7
7
9
7
H6
4
8
6
7
5
—
4
4
3
7
4
7
5
4
7
6
6
8
H7
7
9
5
7
6
3
—
4
5
8
3
9
3
6
6
8
6
3
H8
4
6
6
9
5
5
3
—
7
3
7
8
5
3
7
3
9
3
H9
3
6
5
8
6
8
8
3
—
9
9
7
5
8
8
7
4
5
H10
9
8
5
8
4
4
5
7
9
—
7
3
3
5
3
8
3
9
H11
6
6
8
3
9
9
3
3
9
4
—
4
3
4
6
5
7
3
H12
3
8
3
9
9
8
8
7
6
6
3
—
3
9
8
5
5
8
H13
8
7
8
9
3
5
3
8
6
9
4
6
—
3
5
7
8
8
H14
4
5
8
8
9
7
3
8
6
8
5
7
4
—
6
8
7
5
H15
4
8
7
7
8
9
8
5
6
4
4
5
6
5
—
7
8
5
D
1
7
5
9
9
4
9
9
4
6
6
6
3
7
6
8
—
17
21
D
2
6
3
4
6
6
4
5
9
6
6
4
3
5
7
3
20
—
18
D
3
8
4
7
6
6
5
6
9
9
4
6
8
4
4
9
16
19
—The case is solved by using the heuristic algorithm proposed in this paper. The service path of each vehicle, the number of service passengers, and the objective function of each path are shown in Table5. 90 travel demands are all serviced, and the time for all passengers arriving at target stations meet the expectation.Table 5
Vehicle service path results.
Passenger number
Vehicle path
Number of passengers served
Expected arrival time (minute)
The target function value corresponding to the path
1
13-7-6-1-2-3-D1
1-1-1-1-1-1
35
104
2
4-8-12-5-D1
1-1-1-1
35
93
3
14-5-11-9-10-D1
2-1-1-1-1
45
140
4
6-8-3-15-D1
1-1-1-1
45
137
5
2-1-10-D1
1-2-1
55
180
6
7-12-5-11-D1
2-1-2-1
55
242
7
4-1-6-5-13-8-D2
1-1-1-1-1-1
35
108
8
3-12-7-2-D2
1-1-1-1
35
93
9
15-3-9-11-5-D2
2-1-1-1-1
45
139
10
10-14-6-8-D2
1-1-1-1
45
138
11
12-5-7-10-1-D2
2-1-1-1-1
55
198
12
6-2-3-8-D2
1-1-1-1
55
170
13
12-3-5-4-8-13-D3
1-1-1-1-1-1
35
111
14
6-7-1-2-D3
1-1-1-1
35
102
15
15-5-11-9-10-D3
2-1-1-1-1
45
136
16
8-14-3-6-D3
1-1-1-1
45
134
17
1-8-2-D3
2-1-1
55
185
18
5-12-7-10-D3
2-2-1-1
55
225The schematic diagram of vehicle routing results are shown in Figure1.Figure 1
The schematic diagram of vehicle routing results.According to the calculation results in Table5, Figure 2 shows the network topology of some vehicle driving paths. As Table 5 has a lot of contents, six groups of routes are selected and displayed according to the passenger destination, with D1 as the destination; we show the paths 14-5-11-9-10- D1 and 4-8-12-5- D1; D2 as the destination, and we show the paths 6-2-3-8-D2 and 4-1-6-5-13-8-D2; D3 as the destination, and we show the paths 15-5-11-9-10-D3 and 6-7-1-2-D3.Figure 2
The total travel time results of vehicles.To further verify the reliability of the algorithm, keep the existing constants and the network travel time matrix (i.e., Table3) unchanged, test 90 travel demands in 100 sets of randomly generated 30 demand points. The results show that, under the given conditions, all the 90 travel demands will be served, the number of service vehicles is 17–21, 84% of the total travel time of the vehicles is 400–500 minutes, and the average travel time per vehicle is 24.59 minutes. The test results are shown in Figures 1, 3, and 4.Figure 3
The total objective function results of vehicles.Figure 4
The calculation time results.As shown in Figure2, the travel time of the vehicle solved by the heuristic algorithm is stable. Even if there is a large uncertainty in the demand distribution, thanks to the robustness of the proposed model and algorithm, the final result is still reliable. Figure 3 shows that a major part of the total objective function value affected by the demand change is concentrated between 2600 and 2900. At the same time, it can be seen from Figure 4 that the solution time of all 100 sets of data is less than 25 seconds, and the average computation time is 12.04 seconds, which makes the proposed algorithm apply to the actual system, and vehicle path optimization and collaborative scheduling can be completed within a reasonably short time window for appointments and services.


## 5. Conclusion

In this paper, a flexible bus route optimization scheduling model for multitarget stations problem is studied, and a path planning and coordination scheduling model is established to minimize the sum of vehicle operating time, passenger waiting time before boarding, and the difference between the actual and the expected arrival time of passengers. Also, this paper proposes a heuristic algorithm based on a gravity model to effectively solve the path optimization scheduling model and is verified by examples. The results show that the model and algorithm can quickly solve the effective and reasonable vehicle service path in the vehicle scheduling process.Comparing to the studies about “many-to-one” flexible bus system, the “many-to-many” mode studied in this paper has more flexibility and practicability. We selected more parameters in modeling and considered more factors, such as passenger demand and operating cost to make our solution to be more nearing to the reality of the flexible bus system.



---

*Source: 7183465-2020-03-19.xml*