# Vehicle-Scheduling Model for Operation Based on Single-Depot

Authors: Jing Teng; Shuang Jin; Xiongfei Lai; Sijin Chen
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

Centralized assigning of bus running between multiple lines can save operation cost of transit agency. As more big transit terminals can serve for multiple bus lines being established, coordinating the operation of these lines’ vehicles becomes more economical and perspective. This paper proposed a vehicle-scheduling model for multiple lines which share vehicle resource together and service based on the same terminal. The optimization goal is to minimize the number of vehicles while considering reducing the invalid operation time under the constraint of timetable schemes and matching time for vehicle crossing two lines. A case in Ningbo city, China, was conducted to compare the performance of the cross-line schedules with the original schedules assigning vehicles within respective lines. The optimized schedules can reduce 7.14% vehicles in need while meeting the timetable schemes of all bus lines, which indicated that the proposed model is suitable for operation practice.


---

## Body

## 1. Introduction

Vehicle-schedule is an important production plan for transit agency which assigns vehicle trips according to timetable. The quality of the vehicle-schedule is mainly shown with the number of vehicles which means that fewer vehicles used usually need lower cost. Traditionally, a vehicle only runs within a single line and could not be swapped to the other line. The average service headway of a bus line per hour usually varies in a day to meet the fluctuation of passenger demand, and the number of vehicles equipped with a bus line depends on the average departure headway in peak hour. Therefore, there are often some vehicles being surplus in off-peak hour. Comparatively, the cross-line operation mode assigning vehicles to multiple lines could save the number of vehicles and especially could be feasible to the lines whose distributions of passenger demands are staggered complementary. In addition, the cross-line scheduling can promote the efficiency of human resources and vehicle maintenance facilities. With the informatization of public transportation industry, many transit agencies have set up control centers, which have the requirement of centrally and economically dispatching vehicle resource [1]. The cross-line operation mode has a good prospect for development.The vehicle-scheduling of cross-line operation mode is a research hotspot in applied mathematics. It could be divided into two categories: single-depot vehicle-scheduling (SDVS) and multidepot vehicle-scheduling (MDVS). The difference between them is whether the vehicle resource is assigned from single-depot to multiple lines or assigned from multiple depots to multiple lines. SDVS problem gets more attention than MDVS from the view of applicability.Bodin and Golden in 1981 presented that SDVS problem could be solved by two-phase method when setting the optimization goal as minimizing empty vehicle trip time. However, as adding the line operation time as a constraint, this problem becomes an NP hard problem and needs heuristic algorithm to solve it [2]. In 2008, Ren et al.introduced Tabu Search algorithm into genetic algorithm to solve the optimization model with the target of minimizing passenger waiting time and operating cost. This algorithm is validated that the proposed algorithm is more efficient than standard genetic algorithm, which was ever an effective method to solve the problem of bus dispatching [3]. In 2012, Wei set the model with the goal of maximizing the utilization rate of vehicles and the constraints of schedule reliability. The model was solved through the heuristic algorithm with genetic algorithm, ant colony algorithm, and particle swarm optimization algorithm. The result indicated that operational cost and reliability have the direct proportional relationship [4].MDVS is more complicated than SDVS and most of the research results are theoretical. Bertossi stated that the MDVS is an NP problem. In 1981, Ceder and Stern set up timetable compensation function based on the difference of actual arrival time and timetable. This method could establish the connection of the arrival time of each vehicle and start time of its first subsequent vehicle. But this method was not suitable for solving large-scale problems [5]. In 1990, Lamatsch proposed a time-space network method to solve multiproduct matching problem [6]. In the same year, Mesquita and Paixao solved a problem of multidepot vehicle-scheduling problem as a multiproduct matching problem and proposed a network flow calculation method. The problem involved two cases: 2 depots with 250 trips and 3 depots with 200 trips [7]. In 1997, Lobel modified Forbes model and successfully solved a problem in Germany with 49 depots and 25000 runs and optimized thirteen million variables through the column generation technique of Lagrange pricing method to adjust linear slack time problem with multiple depots. However, his method did not consider the constraint of line operation time [8]. In 2009, Mao and Li solved transit vehicle scheduling through the general fixed job sorting algorithm, which could improve the utilization of vehicles. But the method increased the dwell time in the depot greatly [9]. In 2011, Naumann et al. presented a new robust stochastic programming method through adjusting the fixed slack time between two adjacent trips to reduce the total expected cost. This model enhanced the computation complexity so that it is only suitable for small- and medium-sized vehicle-scheduling problem [10].As the enterprise’s operation requires high applicability, MDVS is difficult to guarantee the reliability of implementation. Relatively, SDVS is easier to manage, especially when more lines service the same terminal, because it can reduce vehicle’s invalid dwelling time for matching two trips and is convenient for the passengers to transfer through the vehicle when crossing between lines. The majority of research results widely set up nonlinear multiobject models for SDVS and adopt heuristic algorithms. In consideration of the efficiency and reliability, most of the SDVS models and algorithms cannot be applied in practice. After reviewing the previous research, this paper puts forward a method of using fixed job sorting algorithm which belongs to deterministic algorithm to solve SDVS.


## 2. Problem Description

Figure1 shows the cross-line operation mode based on a terminal in this paper.Figure 1
The cross-line operation mode based on a terminal.The background of this operation mode is as follows.(1)
There are many bus terminals or intermodal transit terminals established or being planned in big cities; transit-oriented development especially based on terminals has become one tendency of urban planning in developing countries, such as China.
(2)
Laying out bus transit network based on terminals is beneficial for fleet management and maintenance and is also convenient for transferring organization of passenger flow.
(3)
Many terminals are located among functional areas to exchange passengers. Some of the lines could connect residential zones, and some could connect commercial zones or industrial zones. The peak time of the passenger volume of these lines is staggered. The transport capabilities required for these lines are complementary.
(4)
It is much easier for crew-scheduling based on the SDVS vehicle-scheduling than based on MDVS.Minimizing the total number of vehicles used is set as a single optimization target in this paper. Some previous researches [11] still considered another target of balancing the kilometers of all the vehicles running in a day. After the investigation of six transit agencies in China, we found that the target can be omitted because continuous rolling of the vehicles’ work during a period such as one month can easily balance the kilometers of all the vehicles. Therefore, this paper did not take the target into the objective function.The timetable schemes of each of the bus lines which set the average headway or frequency in each hour are considered as known and optimized based on passenger demands in this paper. The vehicle-scheduling results must get the trips to fit the timetable scheme of each line. Every vehicle will carry out a trip chain no matter being within one line or crossing several lines. The following constraints of the vehicle-scheduling need be confirmed.(1)
Every trip of the timetable is executed.
(2)
Each bus can only conduct one trip at the same time.
(3)
Each trip can only be conducted by one bus.
(4)
The connecting time of two consecutive trips run by one vehicle must meet the minimal dwell time in the terminal which is ruled according to the basic operation works.


## 3. Model Building

There is a premise to be stated before proposing the model that the cross-lines are equipped and run with the same type of buses in order to ensure all vehicles can serve for different bus lines.


### 3.1. The Mathematical Symbols

LetR
¯
=
{
R
j
∣
j
=
1,2
,
…
,
n
} be the set of cross-lines, in which j is the serial number of bus lines and n is the number of the bus lines to be optimized in vehicle-scheduling.LetJ
¯
=
{
J
j
t
∣
j
=
1,2
,
…
,
n
,
t
=
1,2
,
…
,
y
j
} be the set of the whole trips departed from the terminal. J
j
t means the tth trip of Line j. y
j is the number of Line j’s trips in a day.LetP
¯
=
{
P
k
∣
k
=
1,2
,
…
,
m
} be the set of vehicles, in which k is the serial number of vehicles and m is the total number of vehicles.Lett
d
j
t be J
j
t’s departure time from the terminal and let t
a
j
t be J
j
t’s arrival time (the time back the terminal), which are determined by timetables.Lett
j
t
′ and t
j
t
′′ be the upgoing running time and the downgoing running time.Lett
t
j
t
′ and t
t
j
t
′′ be the dwell times of vehicle in origin station and end station.LetT
j
t be the operational time of the trip t of the bus line j; T
j
t
=
t
j
t
′
+
t
t
j
t
′
+
t
j
t
′′
+
t
t
j
t
′′ and usually t
t
j
t
′
+
t
t
j
t
′′
=
15
%
T
j
t.LetG
i
s be the necessary time dwelling in the terminal for a vehicle connecting two consecutive trips J
i
s and J
j
t. G
i
s is mainly affected by the first trip J
i
s. Generally, its value ranges about 10
%
T
i
s
≤
G
i
s
≤
15
%
T
i
s.


### 3.2. Model Formation

With the above mathematical symbols, the model of vehicle-scheduling was built in this section.(1)
Decision variableX
i
s
,
j
t
k is expressed as follows:(1)
X
i
s
,
j
t
k
=
1
,
after
conducting
trip
J
i
s
,
the
vehicle
P
k
conducts
trip
J
j
t
;
0
,
otherwise
.
(2)
Objective function is expressed as follows:
the number of vehicles, running all of the trips, isZ:(2)
Z
=
P
k
∣
∑
i
=
1
n
∑
s
=
1
y
i
∑
j
=
1
n
+
1
∑
t
=
1
y
j
X
i
s
,
j
t
k
≥
1
,
∀
k
.
Among them,X
i
s
,
(
n
+
1
)
t
k expresses that vehicle would not conduct any trip task after conducting trip J
i
s. Therefore, according to the principle of minimizing the number of vehicles, the objective function could be expressed as follows:(3)
min
⁡
Z
=
P
k
∣
∑
i
=
1
n
∑
s
=
1
y
i
∑
j
=
1
n
+
1
∑
t
=
1
y
j
X
i
s
,
j
t
k
≥
1
,
∀
k
.
(3)
A vehicle can only conduct one trip at the same time, and then a vehicle can only conduct a follow-up tripJ
j
t after conducting trip J
i
s. That is to say, there is a “value of 1” in the decision variable sequence X
i
s
,
j
t
k for the given parameter k and parameter i
s at most: (4)
∑
j
=
1
n
+
1
∑
t
=
1
y
j
X
i
s
,
j
t
k
≤
1
,
∀
k
,
i
,
s
.
(4)
Similarly, a vehicle can only conduct a consecutive tripJ
i
s before conducting trip J
j
t. That is to say, there is a “value of 1” in the decision variable sequence X
i
s
,
j
t
k for the given parameter k and parameter j
t at most:(5)
∑
i
=
1
n
+
1
∑
s
=
1
y
i
X
i
s
,
j
t
k
≤
1
,
∀
k
,
j
,
t
.
(5)
According to the principle that each trip can only be conducted by one vehicle, it can conclude that there is a “value of 1” in the decision variable sequenceX
i
s
,
j
t
k for the given parameter J
i
s:(6)
∑
k
=
1
m
∑
j
=
1
n
+
1
∑
t
=
1
y
j
X
i
s
,
j
t
k
=
1
,
∀
i
,
s
.
(6)
Letβ
k
j
t be the matching function: (7)
β
k
j
t
=
0
,
the
vehicle
P
k
is
matched
with
the
trip
J
j
t
;
1
,
otherwise
.
Therefore, according to the principle that a vehicle should be matched with a trip, the equivalent condition of∑
k
=
1
m
∑
j
=
1
n
+
1
∑
t
=
1
y
j
X
i
s
,
j
t
k
=
1 is that the vehicle P
k is matched with the trip J
j
t:(8)
∑
j
=
1
n
+
1
∑
t
=
1
y
j
X
i
s
,
j
t
k
+
β
k
j
t
≤
1
,
∀
k
,
i
,
s
.
(7)
The value of the matching functionβ
k
j
t is calculated as follows:
according to the principle that the time for a vehicle connecting two consecutive tripsJ
i
s and J
j
t cannot be smaller than G
i
s, we could get the formulation as follows:(9)
t
d
j
t
X
i
s
,
j
t
k
≥
t
a
i
s
+
G
i
s
X
i
s
,
j
t
k
,
∀
k
,
i
,
s
,
j
,
t
.
If the above equation holds, thenβ
k
j
t
=
0; otherwise, β
k
j
t
=
1.


## 3.1. The Mathematical Symbols

LetR
¯
=
{
R
j
∣
j
=
1,2
,
…
,
n
} be the set of cross-lines, in which j is the serial number of bus lines and n is the number of the bus lines to be optimized in vehicle-scheduling.LetJ
¯
=
{
J
j
t
∣
j
=
1,2
,
…
,
n
,
t
=
1,2
,
…
,
y
j
} be the set of the whole trips departed from the terminal. J
j
t means the tth trip of Line j. y
j is the number of Line j’s trips in a day.LetP
¯
=
{
P
k
∣
k
=
1,2
,
…
,
m
} be the set of vehicles, in which k is the serial number of vehicles and m is the total number of vehicles.Lett
d
j
t be J
j
t’s departure time from the terminal and let t
a
j
t be J
j
t’s arrival time (the time back the terminal), which are determined by timetables.Lett
j
t
′ and t
j
t
′′ be the upgoing running time and the downgoing running time.Lett
t
j
t
′ and t
t
j
t
′′ be the dwell times of vehicle in origin station and end station.LetT
j
t be the operational time of the trip t of the bus line j; T
j
t
=
t
j
t
′
+
t
t
j
t
′
+
t
j
t
′′
+
t
t
j
t
′′ and usually t
t
j
t
′
+
t
t
j
t
′′
=
15
%
T
j
t.LetG
i
s be the necessary time dwelling in the terminal for a vehicle connecting two consecutive trips J
i
s and J
j
t. G
i
s is mainly affected by the first trip J
i
s. Generally, its value ranges about 10
%
T
i
s
≤
G
i
s
≤
15
%
T
i
s.


## 3.2. Model Formation

With the above mathematical symbols, the model of vehicle-scheduling was built in this section.(1)
Decision variableX
i
s
,
j
t
k is expressed as follows:(1)
X
i
s
,
j
t
k
=
1
,
after
conducting
trip
J
i
s
,
the
vehicle
P
k
conducts
trip
J
j
t
;
0
,
otherwise
.
(2)
Objective function is expressed as follows:
the number of vehicles, running all of the trips, isZ:(2)
Z
=
P
k
∣
∑
i
=
1
n
∑
s
=
1
y
i
∑
j
=
1
n
+
1
∑
t
=
1
y
j
X
i
s
,
j
t
k
≥
1
,
∀
k
.
Among them,X
i
s
,
(
n
+
1
)
t
k expresses that vehicle would not conduct any trip task after conducting trip J
i
s. Therefore, according to the principle of minimizing the number of vehicles, the objective function could be expressed as follows:(3)
min
⁡
Z
=
P
k
∣
∑
i
=
1
n
∑
s
=
1
y
i
∑
j
=
1
n
+
1
∑
t
=
1
y
j
X
i
s
,
j
t
k
≥
1
,
∀
k
.
(3)
A vehicle can only conduct one trip at the same time, and then a vehicle can only conduct a follow-up tripJ
j
t after conducting trip J
i
s. That is to say, there is a “value of 1” in the decision variable sequence X
i
s
,
j
t
k for the given parameter k and parameter i
s at most: (4)
∑
j
=
1
n
+
1
∑
t
=
1
y
j
X
i
s
,
j
t
k
≤
1
,
∀
k
,
i
,
s
.
(4)
Similarly, a vehicle can only conduct a consecutive tripJ
i
s before conducting trip J
j
t. That is to say, there is a “value of 1” in the decision variable sequence X
i
s
,
j
t
k for the given parameter k and parameter j
t at most:(5)
∑
i
=
1
n
+
1
∑
s
=
1
y
i
X
i
s
,
j
t
k
≤
1
,
∀
k
,
j
,
t
.
(5)
According to the principle that each trip can only be conducted by one vehicle, it can conclude that there is a “value of 1” in the decision variable sequenceX
i
s
,
j
t
k for the given parameter J
i
s:(6)
∑
k
=
1
m
∑
j
=
1
n
+
1
∑
t
=
1
y
j
X
i
s
,
j
t
k
=
1
,
∀
i
,
s
.
(6)
Letβ
k
j
t be the matching function: (7)
β
k
j
t
=
0
,
the
vehicle
P
k
is
matched
with
the
trip
J
j
t
;
1
,
otherwise
.
Therefore, according to the principle that a vehicle should be matched with a trip, the equivalent condition of∑
k
=
1
m
∑
j
=
1
n
+
1
∑
t
=
1
y
j
X
i
s
,
j
t
k
=
1 is that the vehicle P
k is matched with the trip J
j
t:(8)
∑
j
=
1
n
+
1
∑
t
=
1
y
j
X
i
s
,
j
t
k
+
β
k
j
t
≤
1
,
∀
k
,
i
,
s
.
(7)
The value of the matching functionβ
k
j
t is calculated as follows:
according to the principle that the time for a vehicle connecting two consecutive tripsJ
i
s and J
j
t cannot be smaller than G
i
s, we could get the formulation as follows:(9)
t
d
j
t
X
i
s
,
j
t
k
≥
t
a
i
s
+
G
i
s
X
i
s
,
j
t
k
,
∀
k
,
i
,
s
,
j
,
t
.
If the above equation holds, thenβ
k
j
t
=
0; otherwise, β
k
j
t
=
1.


## 4. Algorithm Design

### 4.1. Fixed Job Sorting Theory

The description of fixed job sorting algorithm: letJ
=
{
J
j
∣
j
=
1,2
,
…
,
n
} be the set of jobs, in which n is the number of jobs. And the jobs in this paper correspond to bus trips. Let P
=
{
P
k
∣
k
=
1,2
,
…
,
m
} be the set of processors, in which m is the number of processors. The processors in this paper correspond to bus vehicles. Each processor can process no more than one job at the same time, and each job can be processed by no more than one processor at the same time. In addition, once a job begins to be processed, it cannot be broken off until completion of the processing. Let t
d
j be the departure time of the fixed processing and let t
a
j be the arrival time of the fixed processing for a job. There is a mapping function of P
→
J between a processor and a job. That is to say, there is a subset S
k
∈
J belonging to all P
k
∈
P. And a processor P
k could process every job belonging to S
k. The key is to find a schedule to minimize the total number of processors, and all of the jobs could be processed through the mapping relationship. According to the marking method in sorting theory, the algorithm could be denoted as follows:(10)
P
m
∣
Fixed
Job
,
P
⟶
J
Mapping
∣
max
⁡
z
=
∑
k
∑
j
Y
k
j
,where P
m is the number of processors, Y
k
j
=
1 expresses that a processor P
k conducts job J
j, Y
k
j
=
0 expresses that a processor P
k does not conduct job J
j, and max
⁡
z
=
∑
k
∑
j
Y
k
j denotes the maximal number of jobs would be conducted by processors. That is to say, each job could be assigned with a processor.


### 4.2. Algorithm Design

The general fixed job sorting algorithm is based on first in first out (FIFO) rule to dispatch bus vehicles [9]. This paper adopts a modified fixed job sorting algorithm that the dispatching rule will assign the vehicle to conduct the trip with earlier departure time when it conforms to the requirement of minimum consecutive time in the depot, which can reduce the total operating time by compressing dwelling time in terminal.In order to describe this algorithm further, the trip is defined asJob
(
j
t
):(11)
Job
j
t
=
p
,
Trip
J
j
t
conducted
by
bus
P
p
p
=
1,2
,
…
,
m
,
0
,
Unfinished
Trip
.LetP
e
¯
=
{
P
p
∣
p
=
1
,
…
,
m
e
,
m
e
<
m
} be the set of all dwelling buses in terminal, in which m
e refers to the amount of the dwelling buses. For each dwelling bus P
p
∈
P
e
¯, which can execute trip J
j
t, the interval between the departure time of J
j
t and P
k’s arrival time of last trip must be longer than the necessary consecutive time G
i
s. Therefore, for the next trip J
j
t, a variable E can be defined as(12)
E
=
t
d
j
t
X
i
s
,
j
t
k
-
t
a
i
s
+
G
i
s
X
i
s
,
j
t
k
∀
k
,
i
,
s
,
j
,
t
.Here the priority of the bus to be dispatched for the next trip is determined by the value ofPro
(
p
). Pro
(
p
) is the set of the sequence numbers depending on E. Pro
p
=
1
,
…
,
m
e
,
m
e maps the vehicle with the biggest value of E.Hereβ
k
j
t can be explained as(13)
β
k
j
t
=
0
,
Bus
P
k
is
conducting
trip
J
j
t
,
1
,
otherwise
.Algorithm logic is shown as in Figure2.Figure 2
Algorithm logic diagram.Algorithm process is as follows.(1)
The departure of each bus will generate a dispatching eventz
i which will be sorted by time series as z
1
≤
z
2
≤
⋯
≤
z
n. Initializing P
e
¯, Pro
(
p
) and Counter
=
0.
(2)
z
x
∈
(
z
1
,
…
,
z
n
) is defined as the departure event; the corresponding trip is J
j
t; then search P
k
∈
P
e
¯ which conforms to the constraints below:(14)
β
k
j
t
=
0
,
Pro
k
=
min
⁡
Pro
p
∣
k
∈
P
e
¯
.
IfP
k
∈
P
e
¯ exists, then renew Job
(
j
t
)
=
k, m
e
=
m
e
-
1, P
e
¯
=
P
e
¯
-
{
P
k
}. Consider P
p
∈
P and Pro
(
p
)
>
Pro
(
k
). Renew Pro
(
p
)
=
Pro
(
p
)
-
1. Otherwise, renew(15)
Job
j
t
=
0
,
Counter
=
Counter
+
1
.
Considerz
y
∈
(
z
1
,
…
,
z
n
), supposing z
y
+
t
′
i
s
+
t
t
i
s
′
+
t
i
s
′′ as the finish event of trip J
i
s, and then(16)
m
e
=
m
e
+
1
,
P
e
¯
=
P
e
¯
+
P
p
∣
p
=
Job
i
s
,
Pro
Job
i
s
=
m
e
.
(3)
Renewk
=
k
+
1. If k
≤
n, the process returns to step (
2
); otherwise, output Job
(
j
t
), j
t
=
1,2
,
…
,
n, Counter.


## 4.1. Fixed Job Sorting Theory

The description of fixed job sorting algorithm: letJ
=
{
J
j
∣
j
=
1,2
,
…
,
n
} be the set of jobs, in which n is the number of jobs. And the jobs in this paper correspond to bus trips. Let P
=
{
P
k
∣
k
=
1,2
,
…
,
m
} be the set of processors, in which m is the number of processors. The processors in this paper correspond to bus vehicles. Each processor can process no more than one job at the same time, and each job can be processed by no more than one processor at the same time. In addition, once a job begins to be processed, it cannot be broken off until completion of the processing. Let t
d
j be the departure time of the fixed processing and let t
a
j be the arrival time of the fixed processing for a job. There is a mapping function of P
→
J between a processor and a job. That is to say, there is a subset S
k
∈
J belonging to all P
k
∈
P. And a processor P
k could process every job belonging to S
k. The key is to find a schedule to minimize the total number of processors, and all of the jobs could be processed through the mapping relationship. According to the marking method in sorting theory, the algorithm could be denoted as follows:(10)
P
m
∣
Fixed
Job
,
P
⟶
J
Mapping
∣
max
⁡
z
=
∑
k
∑
j
Y
k
j
,where P
m is the number of processors, Y
k
j
=
1 expresses that a processor P
k conducts job J
j, Y
k
j
=
0 expresses that a processor P
k does not conduct job J
j, and max
⁡
z
=
∑
k
∑
j
Y
k
j denotes the maximal number of jobs would be conducted by processors. That is to say, each job could be assigned with a processor.


## 4.2. Algorithm Design

The general fixed job sorting algorithm is based on first in first out (FIFO) rule to dispatch bus vehicles [9]. This paper adopts a modified fixed job sorting algorithm that the dispatching rule will assign the vehicle to conduct the trip with earlier departure time when it conforms to the requirement of minimum consecutive time in the depot, which can reduce the total operating time by compressing dwelling time in terminal.In order to describe this algorithm further, the trip is defined asJob
(
j
t
):(11)
Job
j
t
=
p
,
Trip
J
j
t
conducted
by
bus
P
p
p
=
1,2
,
…
,
m
,
0
,
Unfinished
Trip
.LetP
e
¯
=
{
P
p
∣
p
=
1
,
…
,
m
e
,
m
e
<
m
} be the set of all dwelling buses in terminal, in which m
e refers to the amount of the dwelling buses. For each dwelling bus P
p
∈
P
e
¯, which can execute trip J
j
t, the interval between the departure time of J
j
t and P
k’s arrival time of last trip must be longer than the necessary consecutive time G
i
s. Therefore, for the next trip J
j
t, a variable E can be defined as(12)
E
=
t
d
j
t
X
i
s
,
j
t
k
-
t
a
i
s
+
G
i
s
X
i
s
,
j
t
k
∀
k
,
i
,
s
,
j
,
t
.Here the priority of the bus to be dispatched for the next trip is determined by the value ofPro
(
p
). Pro
(
p
) is the set of the sequence numbers depending on E. Pro
p
=
1
,
…
,
m
e
,
m
e maps the vehicle with the biggest value of E.Hereβ
k
j
t can be explained as(13)
β
k
j
t
=
0
,
Bus
P
k
is
conducting
trip
J
j
t
,
1
,
otherwise
.Algorithm logic is shown as in Figure2.Figure 2
Algorithm logic diagram.Algorithm process is as follows.(1)
The departure of each bus will generate a dispatching eventz
i which will be sorted by time series as z
1
≤
z
2
≤
⋯
≤
z
n. Initializing P
e
¯, Pro
(
p
) and Counter
=
0.
(2)
z
x
∈
(
z
1
,
…
,
z
n
) is defined as the departure event; the corresponding trip is J
j
t; then search P
k
∈
P
e
¯ which conforms to the constraints below:(14)
β
k
j
t
=
0
,
Pro
k
=
min
⁡
Pro
p
∣
k
∈
P
e
¯
.
IfP
k
∈
P
e
¯ exists, then renew Job
(
j
t
)
=
k, m
e
=
m
e
-
1, P
e
¯
=
P
e
¯
-
{
P
k
}. Consider P
p
∈
P and Pro
(
p
)
>
Pro
(
k
). Renew Pro
(
p
)
=
Pro
(
p
)
-
1. Otherwise, renew(15)
Job
j
t
=
0
,
Counter
=
Counter
+
1
.
Considerz
y
∈
(
z
1
,
…
,
z
n
), supposing z
y
+
t
′
i
s
+
t
t
i
s
′
+
t
i
s
′′ as the finish event of trip J
i
s, and then(16)
m
e
=
m
e
+
1
,
P
e
¯
=
P
e
¯
+
P
p
∣
p
=
Job
i
s
,
Pro
Job
i
s
=
m
e
.
(3)
Renewk
=
k
+
1. If k
≤
n, the process returns to step (
2
); otherwise, output Job
(
j
t
), j
t
=
1,2
,
…
,
n, Counter.


## 5. Case Study

### 5.1. Overview of Case

Two tested bus lines, Line 9 and Line 519 in Ningbo, China, are shown below, which share the identical terminal—Gymnasium Station. The layout of the bus lines is shown as in Figure3.Figure 3
The layout of Line 9 and Line 519 in Ningbo city, China.The running time of Line 9 is 51 min. The normal time for vehicles dwelling at the terminal accounts for 15% of the running time and should not be less than 10%. There are totally 126 trips conducted by 18 vehicles every day and the time of vehicle departing from the terminal in existing timetable is shown in Table1.Table 1
The time of vehicle departing from the terminal in existing timetable (Line 9).
Bus number
The departure time of Line 9 in Gymnasium Station
1
6:00
(
1
)
8:00
(
25
)
10:00
(
48
)
12:00
(
66
)
14:00
(
83
)
16:00
(
106
)
18:00
(
134
)
20:00
(
157
)
22:00
(
174
)
2
6:07
(
2
)
8:08
(
27
)
10:10
(
49
)
12:10
(
67
)
14:08
(
84
)
16:07
(
108
)
18:06
(
135
)
20:10
(
158
)
3
6:14
(
3
)
8:16
(
29
)
10:20
(
51
)
12:20
(
69
)
14:24
(
87
)
16:21
(
112
)
18:18
(
138
)
20:20
(
160
)
4
6:21
(
4
)
8:24
(
30
)
16:28
(
113
)
18:25
(
139
)
5
6:28
(
5
)
14:16
(
86
)
16:14
(
110
)
18:12
(
137
)
6
6:35
(
6
)
8:32
(
32
)
10:30
(
52
)
12:30
(
70
)
14:32
(
89
)
16:35
(
115
)
18:32
(
141
)
20:30
(
161
)
22:15
(
175
)
7
6:42
(
7
)
8:40
(
33
)
10:40
(
54
)
12:40
(
71
)
14:40
(
90
)
16:42
(
117
)
18:39
(
142
)
20:40
(
163
)
8
6:49
(
8
)
8:48
(
35
)
10:50
(
55
)
12:50
(
73
)
14:48
(
91
)
16:49
(
118
)
18:46
(
143
)
20:50
(
164
)
22:30
(
177
)
9
6:56
(
10
)
8:56
(
36
)
11:00
(
57
)
13:00
(
74
)
15:04
(
94
)
17:03
(
121
)
19:00
(
146
)
21:00
(
165
)
22:45
(
179
)
10
7:03
(
12
)
9:04
(
38
)
17:24
(
126
)
19:21
(
150
)
11
7:10
(
13
)
9:12
(
39
)
11:10
(
58
)
13:10
(
76
)
15:12
(
96
)
17:10
(
123
)
19:07
(
147
)
21:10
(
167
)
12
7:17
(
15
)
9:20
(
41
)
11:20
(
60
)
13:20
(
77
)
15:20
(
97
)
17:17
(
124
)
19:14
(
148
)
21:20
(
168
)
13
7:24
(
17
)
14:56
(
93
)
16:56
(
120
)
18:53
(
144
)
14
7:30
(
18
)
9:28
(
42
)
11:30
(
61
)
13:30
(
78
)
15:28
(
99
)
17:30
(
127
)
19:27
(
151
)
21:30
(
170
)
15
7:36
(
20
)
9:36
(
44
)
11:40
(
63
)
13:40
(
80
)
15:44
(
103
)
17:42
(
130
)
19:39
(
153
)
21:40
(
171
)
16
7:42
(
21
)
9:44
(
45
)
17:48
(
131
)
19:46
(
155
)
17
7:48
(
23
)
15:36
(
101
)
17:36
(
129
)
19:33
(
152
)
18
7:54
(
24
)
9:52
(
47
)
11:50
(
64
)
13:50
(
81
)
15:52
(
105
)
17:54
(
133
)
19:53
(
156
)
21:50
(
172
)
Note. The subscript in each cell is according to the time sequence of the timetables of Line 9 and timetables of Line 519.Similarly, the running time of Line 519 is 42 min. Therefore, the normal time for vehicles dwelling at the terminal is 8 min while the minimum dwelling time cannot be less than 5 min. There are 54 trips conducted by 10 vehicles every day and the time of vehicle departing from the terminal in the existing timetable is shown in Table2.Table 2
The time of vehicle departing from the terminal in existing timetable (Line 519).
Bus number
The departure time of Line 519 in Gymnasium Station
1
6:50
(
9
)
8:30
(
31
)
10:10
(
50
)
11:50
(
65
)
13:30
(
79
)
15:10
(
95
)
16:50
(
119
)
18:30
(
140
)
20:10
(
159
)
21:50
(
173
)
2
7:00
(
11
)
8:45
(
34
)
10:30
(
53
)
12:15
(
68
)
14:10
(
85
)
15:50
(
104
)
3
7:10
(
14
)
13:50
(
82
)
15:30
(
100
)
17:20
(
125
)
4
7:20
(
16
)
9:00
(
37
)
10:50
(
56
)
12:40
(
72
)
14:30
(
88
)
16:10
(
109
)
5
7:30
(
19
)
9:15
(
40
)
15:20
(
98
)
17:05
(
122
)
18:55
(
145
)
20:35
(
162
)
22:15
(
176
)
6
7:45
(
22
)
9:30
(
43
)
11:10
(
59
)
13:05
(
75
)
14:50
(
92
)
16:30
(
114
)
7
8:00
(
26
)
9:50
(
46
)
11:30
(
62
)
15:40
(
102
)
17:35
(
128
)
19:20
(
149
)
21:00
(
166
)
22:40
(
178
)
8
8:15
(
28
)
16:00
(
107
)
17:50
(
132
)
19:45
(
154
)
21:25
(
169
)
23:05
(
180
)
9
16:20
(
111
)
18:10
(
136
)
10
16:40
(
116
)
Note. The subscript in each cell is according to the time sequence of the timetables of Line 9 and Line 519.The total trips and vehicles of two lines are shown in Table3.Table 3
The total number of trips and vehicles.
Bus line
The total number of trips
The total number of vehicles
Line 9
126
18
Line 519
54
10
Total
180
28


### 5.2. The Optimized Vehicle-Schedule

With the modified fixed job sorting algorithm, the cross-line vehicle-schedule can be quickly gotten and all the trips are burdened with 26 vehicles. Compared with the operation mode of single line, the method could reduce 2 vehicles which occupy 7.1% of the existing vehicle number. Table4 shows the trip chains of the 26 vehicles in a day. Figure 4 is the operation diagram of the two bus lines under cross-line operation mode.Table 4
The 26-vehicle operation diagram.
Bus label
Trip chain
P
1
J
(
1
)
,
J
(
25
)
,
J
(
48
)
,
J
(
66
)
,
J
(
83
)
,
J
(
106
)
P
2
J
(
2
)
,
J
(
27
)
,
J
(
49
)
,
J
(
68
)
,
J
(
85
)
,
J
(
105
)
,
J
(
132
)
,
J
(
155
)
P
3
J
(
3
)
,
J
(
28
)
,
J
(
51
)
,
J
(
69
)
,
J
(
89
)
,
J
(
114
)
,
J
(
136
)
P
4
J
(
4
)
,
J
(
30
)
,
J
(
93
)
,
J
(
120
)
,
J
(
144
)
,
J
(
164
)
P
5
J
(
5
)
,
J
(
103
)
,
J
(
130
)
,
J
(
153
)
P
6
J
7
,
J
33
,
J
98
,
J
122
,
J
145, J
(
175
)
P
7
J
(
9
)
,
J
(
31
)
,
J
(
50
)
,
J
(
86
)
,
J
(
110
)
,
J
(
137
)
,
J
(
159
)
,
J
(
173
)
P
8
J
(
10
)
,
J
(
36
)
,
J
(
56
)
,
J
(
70
)
,
J
(
88
)
,
J
(
108
)
,
J
(
135
)
P
9
J
6
,
J
32
,
J
53
,
J
67
,
J
84
,
J
109
,
J
131
,
J
154
,
J
(
171
)
P
10
J
(
12
)
,
J
(
37
)
,
J
(
54
)
,
J
(
72
)
,
J
(
87
)
,
J
(
112
)
,
J
(
138
)
,
J
(
160
)
P
11
J
(
8
)
,
J
(
107
)
,
J
(
133
)
,
J
(
156
)
,
J
(
172
)
P
12
J
(
14
)
,
J
(
35
)
,
J
(
55
)
,
J
(
75
)
,
J
(
92
)
,
J
(
113
)
,
J
(
139
)
P
13
J
(
15
)
,
J
(
40
)
,
J
(
57
)
,
J
(
74
)
,
J
(
94
)
,
J
(
121
)
,
J
(
146
)
,
J
(
166
),
J
(
178
)
P
14
J
(
11
)
,
J
(
34
)
,
J
(
52
)
,
J
(
71
)
,
J
(
90
)
,
J
(
116
)
P
15
J
(
17
)
,
J
(
111
)
,
J
(
134
)
,
J
(
157
)
,
J
(
174
)
P
16
J
(
13
)
,
J
(
41
)
,
J
(
60
)
,
J
(
77
)
,
J
(
97
)
,
J
(
125
)
P
17
J
(
18
)
,
J
(
42
)
,
J
(
61
)
,
J
(
78
)
,
J
(
99
)
,
J
(
129
)
,
J
(
152
)
,
J
(
170
)
P
18
J
(
20
)
,
J
(
44
)
,
J
(
63
)
,
J
(
80
)
,
J
(
102
)
,
J
(
124
)
,
J
(
148
)
P
19
J
(
16
)
,
J
(
38
)
,
J
(
101
)
,
J
(
128
)
,
J
(
149
)
,
J
(
166
)
P
20
J
(
21
)
,
J
(
45
)
,
J
(
64
)
,
J
(
82
)
,
J
(
100
)
,
J
(
126
)
,
J
(
150
)
,
J
(
168
)
P
21
J
(
23
)
,
J
(
46
)
,
J
(
62
)
,
J
(
77
)
,
J
(
96
)
,
J
(
123
)
,
J
(
147
)
,
J
(
167
)
P
22
J
19
,
J
39
,
J
59
,
J
73
,
J
91
,
J
119
,
J
140,
J
158
,
J
(
176
)
P
23
J
(
24
)
,
J
(
47
)
,
J
(
65
)
,
J
(
79
)
,
J
(
95
)
,
J
(
118
)
,
J
(
143
)
P
24
J
(
26
)
,
J
(
115
)
,
J
(
141
)
,
J
(
161
)
,
J
(
177
)
P
25
J
22
,
J
43
,
J
58
,
J
81
,
J
104
,
J
127
,
J
151,
J
(
169
)
,
J
(
180
)
P
26
J
(
29
)
,
J
(
117
)
,
J
(
153
)
,
J
(
163
)
,
J
(
179
)Figure 4
Vehicle operation diagram (all kinds of vehicles are represented by different colors).Table5 shows the optimized cross-line vehicle-schedule in Gymnasium Station. It is known that during the transition phase from peak period to off-peak period, the transport capacity offered in peak period will be cut away to fit with off-peak transport demand. With the modified fixed job sorting algorithm, some vehicles could get a long nonservice interval (the bold italic font parts in Table 5) and others continue operating efficiently, which is beneficial for making the work plan of repairing and maintaining vehicles while rolling vehicles to execute the vehicle schedule. During the long nonservice interval, vehicles will exit operation and the bold italic font parts do not belong to the operating time, so the modified method can reduce the total operating time of the vehicles. In this case, through optimization, the total dwelling time at the terminal of 26 buses conducting 180 round trips is 1409 min. The average interval between two consecutive trips is 7.9 min.Table 5
The optimized cross-line vehicle-schedule of the Gymnasium Station terminal.
Bus
D.T.1
A.T.1
S.T.1.
D.T.2
A.T.2
S.T.2
D.T.3
A.T.3
S.T.3
D.T.4
A.T.4
S.T.4
D.T.5
A.T.5
S.T.5
D.T.6
A.T.6
S.T.6
D.T.7
A.T.7
S.T.7
D.T.7
A.T.7
S.T.7
D.T.7
A.T.7
7
6:50
8:22
8
8:30
10:02
8
10:10
11:42
Nonservice time
14:16
16:07
7
16:14
18:05
7
18:12
20:03
7
20:10
21:42
8
21:50
23:22
9
6:35
8:26
6
8:32
10:23
7
10:30
12:02
8
12:10
14:01
7
14:08
15:59
11
16:10
17:42
6
17:48
19:39
6
19:45
21:17
23
21:40
23:31
11
6:49
8:40
Nonservice time
16:00
17:32
22
17:54
19:45
8
19:53
21:44
6
21:50
23:41
22
7:30
9:02
10
9:12
11:03
7
11:10
12:42
8
12:50
14:41
7
14:48
16:39
11
16:50
18:22
8
18:30
20:02
8
20:10
22:01
14
22:15
23:47
15
7:24
9:15
Nonservice time
16:20
17:52
8
18:00
19:51
9
20:00
21:51
9
22:00
23:51
6
6:42
8:33
7
8:40
10:31
Nonservice time
15:20
16:52
13
17:05
18:37
18
18:55
20:27
8
20:35
22:07
8
22:15
0:06
13
7:17
9:08
7
9:15
10:47
13
11:00
12:51
9
13:00
14:51
13
15:04
16:55
8
17:03
18:54
6
19:00
20:51
9
21:00
22:32
8
22:40
0:12
24
8:00
9:32
Nonservice time
16:35
18:26
6
18:32
20:23
7
20:30
22:21
9
22:30
0:21
26
8:16
10:07
Nonservice time
16:42
18:33
6
18:39
20:30
10
20:40
22:31
14
22:45
0:36
25
7:45
9:17
13
9:30
11:02
8
11:10
13:01
41
13:50
15:41
9
15:50
17:22
8
17:30
19:21
6
19:27
21:18
7
21:25
22:57
8
23:05
0:37
2
6:07
7:58
10
8:08
9:59
11
10:10
12:01
14
12:15
13:47
13
14:10
15:42
10
15:52
17:43
7
17:50
19:22
24
19:46
21:37
Nonservice time
10
7:03
8:54
6
9:00
10:32
8
10:40
12:31
9
12:40
14:12
12
14:24
16:15
6
16:21
18:12
6
18:18
20:09
11
20:20
22:11
Nonservice time
4
6:21
8:12
12
8:24
10:15
Nonservice time
14:56
16:47
9
16:56
18:47
6
18:53
20:44
6
20:50
22:41
Nonservice time
19
7:20
8:52
12
9:04
10:55
Nonservicetime
15:36
17:27
8
17:35
19:07
13
19:20
20:52
8
21:00
22:51
Nonservice time
21
7:48
9:39
11
9:50
11:22
8
11:30
13:02
8
13:10
15:01
11
15:12
17:03
7
17:10
19:01
6
19:07
20:58
12
21:10
23:01
Nonservice time
20
7:42
9:33
11
9:44
11:35
15
11:50
13:41
9
13:50
15:22
8
15:30
17:02
22
17:24
19:15
6
19:21
21:12
8
21:20
23:11
Nonservicetime
17
7:30
9:21
7
9:28
11:19
11
11:30
13:21
9
13:30
15:21
7
15:28
17:19
17
17:36
19:27
6
19:33
21:24
6
21:30
23:21
Nonservice time
3
6:14
8:05
10
8:15
9:47
33
10:20
12:11
9
12:20
14:11
13
14:32
16:23
7
16:30
18:02
8
18:10
19:42
Nonservice time
8
6:56
8:47
9
8:56
10:47
13
10:50
12:22
8
12:30
14:21
9
14:30
16:02
5
16:07
17:58
8
18:06
19:57
Nonservice time
12
7:10
8:42
8
8:48
10:39
11
10:50
12:41
24
13:05
14:37
13
14:50
16:22
6
16:28
18:19
6
18:25
20:16
Nonservice time
23
7:54
9:45
7
9:52
11:43
7
11:50
13:22
8
13:30
15:02
8
15:10
16:42
7
16:49
18:40
6
18:46
20:37
Nonservice time
18
7:36
9:27
9
9:36
11:27
13
11:40
13:31
9
13:40
15:31
9
15:40
17:12
5
17:17
19:08
6
19:14
21:05
Nonservice time
5
6:28
8:19
Nonservice time
15:44
17:35
7
17:42
19:33
6
19:39
21:30
Nonservice time
1
6:00
7:51
9
8:00
9:51
9
10:00
11:51
9
12:00
13:51
9
14:00
15:51
9
16:00
17:51
Nonservice time
14
7:00
8:32
13
8:45
10:17
13
10:30
12:21
19
12:40
14:31
9
14:40
16:31
9
16:40
18:12
Nonservice time
16
7:10
9:01
19
9:20
11:11
9
11:20
13:11
9
13:20
15:11
9
15:20
17:11
9
17:20
18:52
Nonservice time
D.T., A.T., and S.T. are the abbreviations of departure time, arrival time, and dwelling time; the unit of S.T. is min.In comparison, the general fixed job sorting algorithm selects the bus vehicle to fit a connective trip based on first in first out (FIFO) rule. During the transition phase from peak period to off-peak period the vehicles that arrived earlier have to continue conducting the subsequent trips and the total vehicles’ extended dwelling time in terminal cannot be concentrated on part vehicles and then cannot be utilized for vehicle maintenance or other purposes, so the time is idle but still belongs to operating time. Table6 shows the general cross-line vehicle-schedule based on first in first out (FIFO) rule in Gymnasium Station.Table 6
The general cross-line vehicle-schedule based on first in first out (FIFO) rule in Gymnasium Station.
Bus
D.T.1
A.T.1
S.T.1
D.T.2
A.T.2
S.T.2
D.T.3
A.T.3
S.T.3
D.T.4
A.T.4
S.T.4
D.T.5
A.T.5
S.T.5
D.T.6
A.T.6
S.T.6
D.T.7
A.T.7
1
6:00
7:51
9
8:00
9:51
49
10:40
12:31
79
13:50
15:22
38
16:00
17:51
9
18:00
19:51
39
20:30
22:21
2
6:07
7:58
10
8:08
9:59
51
10:50
12:41
69
13:50
15:41
26
16:07
17:58
12
18:10
19:42
28
20:10
21:42
3
6:14
8:05
10
8:15
9:47
43
10:30
12:21
69
13:30
15:21
31
15:52
17:43
11
17:54
19:45
35
20:20
22:11
4
6:21
8:12
12
8:24
10:15
45
11:00
12:51
77
14:08
15:59
21
16:20
17:52
14
18:06
19:57
38
20:35
22:07
5
6:28
8:19
11
8:30
10:02
48
10:50
12:22
78
13:40
15:31
29
16:00
17:32
16
17:48
19:39
31
20:10
22:01
6
6:35
8:26
14
8:40
10:31
49
11:20
13:11
73
14:24
16:15
15
16:30
18:02
10
18:12
20:03
47
20:50
22:41
7
6:42
8:33
15
8:48
10:39
51
11:30
13:21
69
14:30
16:02
19
16:21
18:12
13
18:25
20:16
44
21:00
22:32
8
6:49
8:40
16
8:56
10:47
53
11:40
13:31
69
14:40
16:31
11
16:42
18:33
20
18:53
20:44
56
21:40
23:31
9
6:50
8:22
10
8:32
10:23
47
11:10
13:01
69
14:10
15:42
28
16:10
17:42
8
17:50
19:22
38
20:00
21:51
10
6:56
8:47
17
9:04
10:55
55
11:50
13:41
67
14:48
16:39
10
16:49
18:40
20
19:00
20:51
59
21:50
23:41
11
7:00
8:32
13
8:45
10:17
53
11:10
12:42
78
14:00
15:51
23
16:14
18:05
13
18:18
20:09
51
21:00
22:51
12
7:03
8:54
21
9:15
10:47
63
11:50
13:22
70
14:32
16:23
17
16:40
18:12
18
18:30
20:02
38
20:40
22:31
13
7:10
9:01
19
9:20
11:11
64
12:15
13:47
63
14:50
16:22
13
16:35
18:26
20
18:46
20:37
53
21:30
23:21
14
7:10
8:42
18
9:00
10:32
58
11:30
13:02
74
14:16
16:07
21
16:28
18:19
13
18:32
20:23
47
21:10
23:01
15
7:17
9:08
22
9:30
11:02
58
12:00
13:51
65
14:56
16:47
9
16:56
18:47
20
19:07
20:58
62
22:00
23:51
16
7:20
8:52
20
9:12
11:03
67
12:10
14:01
63
15:04
16:55
10
17:05
18:37
18
18:55
20:27
53
21:20
23:11
17
7:24
9:15
21
9:36
11:27
73
12:40
14:12
60
15:12
17:03
14
17:17
19:08
25
19:33
21:24
81
22:45
0:36
18
7:30
9:21
29
9:50
11:22
68
12:30
14:21
59
15:20
17:11
9
17:20
18:52
22
19:14
21:05
70
22:15
0:06
19
7:30
9:02
26
9:28
11:19
61
12:20
14:11
59
15:10
16:42
8
16:50
18:22
17
18:39
20:30
55
21:25
22:57
20
7:36
9:27
25
9:52
11:43
77
13:00
14:51
45
15:36
17:27
9
17:36
19:27
19
19:46
21:37
Nonservice time
21
7:42
9:33
37
10:10
12:01
69
13:10
15:01
39
15:40
17:12
12
17:24
19:15
24
19:39
21:30
95
23:05
0:37
22
7:45
9:17
27
9:44
11:35
65
12:40
14:31
49
15:20
16:52
11
17:03
18:54
26
19:20
20:52
58
21:50
23:22
23
7:48
9:39
31
10:10
11:42
68
12:50
14:41
49
15:30
17:02
8
17:10
19:01
20
19:21
21:12
63
22:15
23:47
24
7:54
9:45
35
10:20
12:11
79
13:30
15:02
42
15:44
17:35
7
17:42
19:33
20
19:53
21:44
Nonservice time
25
8:00
9:32
28
10:00
11:51
74
13:05
14:37
51
15:28
17:19
11
17:30
19:21
24
19:45
21:17
73
22:30
0:21
26
8:16
10:07
23
10:30
12:02
78
13:20
15:11
39
15:50
17:22
13
17:35
19:07
20
19:27
21:18
82
22:40
0:12
D.T., A.T., and S.T. are the abbreviations of departure time, arrival time, and dwelling time; the unit of S.T. is min.In this case, with the general fixed job sorting algorithm, the total number of vehicles optimized is still 26 buses, but the total dwelling time at the terminal is 5880 min and the average interval between two consecutive trips is 32.7 min. That is the reason why we modify the general fixed job sorting algorithm. Figure5 shows the comparison of two circumstances.Figure 5
The comparison of the average intervals between two consecutive trips of two circumstances.


## 5.1. Overview of Case

Two tested bus lines, Line 9 and Line 519 in Ningbo, China, are shown below, which share the identical terminal—Gymnasium Station. The layout of the bus lines is shown as in Figure3.Figure 3
The layout of Line 9 and Line 519 in Ningbo city, China.The running time of Line 9 is 51 min. The normal time for vehicles dwelling at the terminal accounts for 15% of the running time and should not be less than 10%. There are totally 126 trips conducted by 18 vehicles every day and the time of vehicle departing from the terminal in existing timetable is shown in Table1.Table 1
The time of vehicle departing from the terminal in existing timetable (Line 9).
Bus number
The departure time of Line 9 in Gymnasium Station
1
6:00
(
1
)
8:00
(
25
)
10:00
(
48
)
12:00
(
66
)
14:00
(
83
)
16:00
(
106
)
18:00
(
134
)
20:00
(
157
)
22:00
(
174
)
2
6:07
(
2
)
8:08
(
27
)
10:10
(
49
)
12:10
(
67
)
14:08
(
84
)
16:07
(
108
)
18:06
(
135
)
20:10
(
158
)
3
6:14
(
3
)
8:16
(
29
)
10:20
(
51
)
12:20
(
69
)
14:24
(
87
)
16:21
(
112
)
18:18
(
138
)
20:20
(
160
)
4
6:21
(
4
)
8:24
(
30
)
16:28
(
113
)
18:25
(
139
)
5
6:28
(
5
)
14:16
(
86
)
16:14
(
110
)
18:12
(
137
)
6
6:35
(
6
)
8:32
(
32
)
10:30
(
52
)
12:30
(
70
)
14:32
(
89
)
16:35
(
115
)
18:32
(
141
)
20:30
(
161
)
22:15
(
175
)
7
6:42
(
7
)
8:40
(
33
)
10:40
(
54
)
12:40
(
71
)
14:40
(
90
)
16:42
(
117
)
18:39
(
142
)
20:40
(
163
)
8
6:49
(
8
)
8:48
(
35
)
10:50
(
55
)
12:50
(
73
)
14:48
(
91
)
16:49
(
118
)
18:46
(
143
)
20:50
(
164
)
22:30
(
177
)
9
6:56
(
10
)
8:56
(
36
)
11:00
(
57
)
13:00
(
74
)
15:04
(
94
)
17:03
(
121
)
19:00
(
146
)
21:00
(
165
)
22:45
(
179
)
10
7:03
(
12
)
9:04
(
38
)
17:24
(
126
)
19:21
(
150
)
11
7:10
(
13
)
9:12
(
39
)
11:10
(
58
)
13:10
(
76
)
15:12
(
96
)
17:10
(
123
)
19:07
(
147
)
21:10
(
167
)
12
7:17
(
15
)
9:20
(
41
)
11:20
(
60
)
13:20
(
77
)
15:20
(
97
)
17:17
(
124
)
19:14
(
148
)
21:20
(
168
)
13
7:24
(
17
)
14:56
(
93
)
16:56
(
120
)
18:53
(
144
)
14
7:30
(
18
)
9:28
(
42
)
11:30
(
61
)
13:30
(
78
)
15:28
(
99
)
17:30
(
127
)
19:27
(
151
)
21:30
(
170
)
15
7:36
(
20
)
9:36
(
44
)
11:40
(
63
)
13:40
(
80
)
15:44
(
103
)
17:42
(
130
)
19:39
(
153
)
21:40
(
171
)
16
7:42
(
21
)
9:44
(
45
)
17:48
(
131
)
19:46
(
155
)
17
7:48
(
23
)
15:36
(
101
)
17:36
(
129
)
19:33
(
152
)
18
7:54
(
24
)
9:52
(
47
)
11:50
(
64
)
13:50
(
81
)
15:52
(
105
)
17:54
(
133
)
19:53
(
156
)
21:50
(
172
)
Note. The subscript in each cell is according to the time sequence of the timetables of Line 9 and timetables of Line 519.Similarly, the running time of Line 519 is 42 min. Therefore, the normal time for vehicles dwelling at the terminal is 8 min while the minimum dwelling time cannot be less than 5 min. There are 54 trips conducted by 10 vehicles every day and the time of vehicle departing from the terminal in the existing timetable is shown in Table2.Table 2
The time of vehicle departing from the terminal in existing timetable (Line 519).
Bus number
The departure time of Line 519 in Gymnasium Station
1
6:50
(
9
)
8:30
(
31
)
10:10
(
50
)
11:50
(
65
)
13:30
(
79
)
15:10
(
95
)
16:50
(
119
)
18:30
(
140
)
20:10
(
159
)
21:50
(
173
)
2
7:00
(
11
)
8:45
(
34
)
10:30
(
53
)
12:15
(
68
)
14:10
(
85
)
15:50
(
104
)
3
7:10
(
14
)
13:50
(
82
)
15:30
(
100
)
17:20
(
125
)
4
7:20
(
16
)
9:00
(
37
)
10:50
(
56
)
12:40
(
72
)
14:30
(
88
)
16:10
(
109
)
5
7:30
(
19
)
9:15
(
40
)
15:20
(
98
)
17:05
(
122
)
18:55
(
145
)
20:35
(
162
)
22:15
(
176
)
6
7:45
(
22
)
9:30
(
43
)
11:10
(
59
)
13:05
(
75
)
14:50
(
92
)
16:30
(
114
)
7
8:00
(
26
)
9:50
(
46
)
11:30
(
62
)
15:40
(
102
)
17:35
(
128
)
19:20
(
149
)
21:00
(
166
)
22:40
(
178
)
8
8:15
(
28
)
16:00
(
107
)
17:50
(
132
)
19:45
(
154
)
21:25
(
169
)
23:05
(
180
)
9
16:20
(
111
)
18:10
(
136
)
10
16:40
(
116
)
Note. The subscript in each cell is according to the time sequence of the timetables of Line 9 and Line 519.The total trips and vehicles of two lines are shown in Table3.Table 3
The total number of trips and vehicles.
Bus line
The total number of trips
The total number of vehicles
Line 9
126
18
Line 519
54
10
Total
180
28


## 5.2. The Optimized Vehicle-Schedule

With the modified fixed job sorting algorithm, the cross-line vehicle-schedule can be quickly gotten and all the trips are burdened with 26 vehicles. Compared with the operation mode of single line, the method could reduce 2 vehicles which occupy 7.1% of the existing vehicle number. Table4 shows the trip chains of the 26 vehicles in a day. Figure 4 is the operation diagram of the two bus lines under cross-line operation mode.Table 4
The 26-vehicle operation diagram.
Bus label
Trip chain
P
1
J
(
1
)
,
J
(
25
)
,
J
(
48
)
,
J
(
66
)
,
J
(
83
)
,
J
(
106
)
P
2
J
(
2
)
,
J
(
27
)
,
J
(
49
)
,
J
(
68
)
,
J
(
85
)
,
J
(
105
)
,
J
(
132
)
,
J
(
155
)
P
3
J
(
3
)
,
J
(
28
)
,
J
(
51
)
,
J
(
69
)
,
J
(
89
)
,
J
(
114
)
,
J
(
136
)
P
4
J
(
4
)
,
J
(
30
)
,
J
(
93
)
,
J
(
120
)
,
J
(
144
)
,
J
(
164
)
P
5
J
(
5
)
,
J
(
103
)
,
J
(
130
)
,
J
(
153
)
P
6
J
7
,
J
33
,
J
98
,
J
122
,
J
145, J
(
175
)
P
7
J
(
9
)
,
J
(
31
)
,
J
(
50
)
,
J
(
86
)
,
J
(
110
)
,
J
(
137
)
,
J
(
159
)
,
J
(
173
)
P
8
J
(
10
)
,
J
(
36
)
,
J
(
56
)
,
J
(
70
)
,
J
(
88
)
,
J
(
108
)
,
J
(
135
)
P
9
J
6
,
J
32
,
J
53
,
J
67
,
J
84
,
J
109
,
J
131
,
J
154
,
J
(
171
)
P
10
J
(
12
)
,
J
(
37
)
,
J
(
54
)
,
J
(
72
)
,
J
(
87
)
,
J
(
112
)
,
J
(
138
)
,
J
(
160
)
P
11
J
(
8
)
,
J
(
107
)
,
J
(
133
)
,
J
(
156
)
,
J
(
172
)
P
12
J
(
14
)
,
J
(
35
)
,
J
(
55
)
,
J
(
75
)
,
J
(
92
)
,
J
(
113
)
,
J
(
139
)
P
13
J
(
15
)
,
J
(
40
)
,
J
(
57
)
,
J
(
74
)
,
J
(
94
)
,
J
(
121
)
,
J
(
146
)
,
J
(
166
),
J
(
178
)
P
14
J
(
11
)
,
J
(
34
)
,
J
(
52
)
,
J
(
71
)
,
J
(
90
)
,
J
(
116
)
P
15
J
(
17
)
,
J
(
111
)
,
J
(
134
)
,
J
(
157
)
,
J
(
174
)
P
16
J
(
13
)
,
J
(
41
)
,
J
(
60
)
,
J
(
77
)
,
J
(
97
)
,
J
(
125
)
P
17
J
(
18
)
,
J
(
42
)
,
J
(
61
)
,
J
(
78
)
,
J
(
99
)
,
J
(
129
)
,
J
(
152
)
,
J
(
170
)
P
18
J
(
20
)
,
J
(
44
)
,
J
(
63
)
,
J
(
80
)
,
J
(
102
)
,
J
(
124
)
,
J
(
148
)
P
19
J
(
16
)
,
J
(
38
)
,
J
(
101
)
,
J
(
128
)
,
J
(
149
)
,
J
(
166
)
P
20
J
(
21
)
,
J
(
45
)
,
J
(
64
)
,
J
(
82
)
,
J
(
100
)
,
J
(
126
)
,
J
(
150
)
,
J
(
168
)
P
21
J
(
23
)
,
J
(
46
)
,
J
(
62
)
,
J
(
77
)
,
J
(
96
)
,
J
(
123
)
,
J
(
147
)
,
J
(
167
)
P
22
J
19
,
J
39
,
J
59
,
J
73
,
J
91
,
J
119
,
J
140,
J
158
,
J
(
176
)
P
23
J
(
24
)
,
J
(
47
)
,
J
(
65
)
,
J
(
79
)
,
J
(
95
)
,
J
(
118
)
,
J
(
143
)
P
24
J
(
26
)
,
J
(
115
)
,
J
(
141
)
,
J
(
161
)
,
J
(
177
)
P
25
J
22
,
J
43
,
J
58
,
J
81
,
J
104
,
J
127
,
J
151,
J
(
169
)
,
J
(
180
)
P
26
J
(
29
)
,
J
(
117
)
,
J
(
153
)
,
J
(
163
)
,
J
(
179
)Figure 4
Vehicle operation diagram (all kinds of vehicles are represented by different colors).Table5 shows the optimized cross-line vehicle-schedule in Gymnasium Station. It is known that during the transition phase from peak period to off-peak period, the transport capacity offered in peak period will be cut away to fit with off-peak transport demand. With the modified fixed job sorting algorithm, some vehicles could get a long nonservice interval (the bold italic font parts in Table 5) and others continue operating efficiently, which is beneficial for making the work plan of repairing and maintaining vehicles while rolling vehicles to execute the vehicle schedule. During the long nonservice interval, vehicles will exit operation and the bold italic font parts do not belong to the operating time, so the modified method can reduce the total operating time of the vehicles. In this case, through optimization, the total dwelling time at the terminal of 26 buses conducting 180 round trips is 1409 min. The average interval between two consecutive trips is 7.9 min.Table 5
The optimized cross-line vehicle-schedule of the Gymnasium Station terminal.
Bus
D.T.1
A.T.1
S.T.1.
D.T.2
A.T.2
S.T.2
D.T.3
A.T.3
S.T.3
D.T.4
A.T.4
S.T.4
D.T.5
A.T.5
S.T.5
D.T.6
A.T.6
S.T.6
D.T.7
A.T.7
S.T.7
D.T.7
A.T.7
S.T.7
D.T.7
A.T.7
7
6:50
8:22
8
8:30
10:02
8
10:10
11:42
Nonservice time
14:16
16:07
7
16:14
18:05
7
18:12
20:03
7
20:10
21:42
8
21:50
23:22
9
6:35
8:26
6
8:32
10:23
7
10:30
12:02
8
12:10
14:01
7
14:08
15:59
11
16:10
17:42
6
17:48
19:39
6
19:45
21:17
23
21:40
23:31
11
6:49
8:40
Nonservice time
16:00
17:32
22
17:54
19:45
8
19:53
21:44
6
21:50
23:41
22
7:30
9:02
10
9:12
11:03
7
11:10
12:42
8
12:50
14:41
7
14:48
16:39
11
16:50
18:22
8
18:30
20:02
8
20:10
22:01
14
22:15
23:47
15
7:24
9:15
Nonservice time
16:20
17:52
8
18:00
19:51
9
20:00
21:51
9
22:00
23:51
6
6:42
8:33
7
8:40
10:31
Nonservice time
15:20
16:52
13
17:05
18:37
18
18:55
20:27
8
20:35
22:07
8
22:15
0:06
13
7:17
9:08
7
9:15
10:47
13
11:00
12:51
9
13:00
14:51
13
15:04
16:55
8
17:03
18:54
6
19:00
20:51
9
21:00
22:32
8
22:40
0:12
24
8:00
9:32
Nonservice time
16:35
18:26
6
18:32
20:23
7
20:30
22:21
9
22:30
0:21
26
8:16
10:07
Nonservice time
16:42
18:33
6
18:39
20:30
10
20:40
22:31
14
22:45
0:36
25
7:45
9:17
13
9:30
11:02
8
11:10
13:01
41
13:50
15:41
9
15:50
17:22
8
17:30
19:21
6
19:27
21:18
7
21:25
22:57
8
23:05
0:37
2
6:07
7:58
10
8:08
9:59
11
10:10
12:01
14
12:15
13:47
13
14:10
15:42
10
15:52
17:43
7
17:50
19:22
24
19:46
21:37
Nonservice time
10
7:03
8:54
6
9:00
10:32
8
10:40
12:31
9
12:40
14:12
12
14:24
16:15
6
16:21
18:12
6
18:18
20:09
11
20:20
22:11
Nonservice time
4
6:21
8:12
12
8:24
10:15
Nonservice time
14:56
16:47
9
16:56
18:47
6
18:53
20:44
6
20:50
22:41
Nonservice time
19
7:20
8:52
12
9:04
10:55
Nonservicetime
15:36
17:27
8
17:35
19:07
13
19:20
20:52
8
21:00
22:51
Nonservice time
21
7:48
9:39
11
9:50
11:22
8
11:30
13:02
8
13:10
15:01
11
15:12
17:03
7
17:10
19:01
6
19:07
20:58
12
21:10
23:01
Nonservice time
20
7:42
9:33
11
9:44
11:35
15
11:50
13:41
9
13:50
15:22
8
15:30
17:02
22
17:24
19:15
6
19:21
21:12
8
21:20
23:11
Nonservicetime
17
7:30
9:21
7
9:28
11:19
11
11:30
13:21
9
13:30
15:21
7
15:28
17:19
17
17:36
19:27
6
19:33
21:24
6
21:30
23:21
Nonservice time
3
6:14
8:05
10
8:15
9:47
33
10:20
12:11
9
12:20
14:11
13
14:32
16:23
7
16:30
18:02
8
18:10
19:42
Nonservice time
8
6:56
8:47
9
8:56
10:47
13
10:50
12:22
8
12:30
14:21
9
14:30
16:02
5
16:07
17:58
8
18:06
19:57
Nonservice time
12
7:10
8:42
8
8:48
10:39
11
10:50
12:41
24
13:05
14:37
13
14:50
16:22
6
16:28
18:19
6
18:25
20:16
Nonservice time
23
7:54
9:45
7
9:52
11:43
7
11:50
13:22
8
13:30
15:02
8
15:10
16:42
7
16:49
18:40
6
18:46
20:37
Nonservice time
18
7:36
9:27
9
9:36
11:27
13
11:40
13:31
9
13:40
15:31
9
15:40
17:12
5
17:17
19:08
6
19:14
21:05
Nonservice time
5
6:28
8:19
Nonservice time
15:44
17:35
7
17:42
19:33
6
19:39
21:30
Nonservice time
1
6:00
7:51
9
8:00
9:51
9
10:00
11:51
9
12:00
13:51
9
14:00
15:51
9
16:00
17:51
Nonservice time
14
7:00
8:32
13
8:45
10:17
13
10:30
12:21
19
12:40
14:31
9
14:40
16:31
9
16:40
18:12
Nonservice time
16
7:10
9:01
19
9:20
11:11
9
11:20
13:11
9
13:20
15:11
9
15:20
17:11
9
17:20
18:52
Nonservice time
D.T., A.T., and S.T. are the abbreviations of departure time, arrival time, and dwelling time; the unit of S.T. is min.In comparison, the general fixed job sorting algorithm selects the bus vehicle to fit a connective trip based on first in first out (FIFO) rule. During the transition phase from peak period to off-peak period the vehicles that arrived earlier have to continue conducting the subsequent trips and the total vehicles’ extended dwelling time in terminal cannot be concentrated on part vehicles and then cannot be utilized for vehicle maintenance or other purposes, so the time is idle but still belongs to operating time. Table6 shows the general cross-line vehicle-schedule based on first in first out (FIFO) rule in Gymnasium Station.Table 6
The general cross-line vehicle-schedule based on first in first out (FIFO) rule in Gymnasium Station.
Bus
D.T.1
A.T.1
S.T.1
D.T.2
A.T.2
S.T.2
D.T.3
A.T.3
S.T.3
D.T.4
A.T.4
S.T.4
D.T.5
A.T.5
S.T.5
D.T.6
A.T.6
S.T.6
D.T.7
A.T.7
1
6:00
7:51
9
8:00
9:51
49
10:40
12:31
79
13:50
15:22
38
16:00
17:51
9
18:00
19:51
39
20:30
22:21
2
6:07
7:58
10
8:08
9:59
51
10:50
12:41
69
13:50
15:41
26
16:07
17:58
12
18:10
19:42
28
20:10
21:42
3
6:14
8:05
10
8:15
9:47
43
10:30
12:21
69
13:30
15:21
31
15:52
17:43
11
17:54
19:45
35
20:20
22:11
4
6:21
8:12
12
8:24
10:15
45
11:00
12:51
77
14:08
15:59
21
16:20
17:52
14
18:06
19:57
38
20:35
22:07
5
6:28
8:19
11
8:30
10:02
48
10:50
12:22
78
13:40
15:31
29
16:00
17:32
16
17:48
19:39
31
20:10
22:01
6
6:35
8:26
14
8:40
10:31
49
11:20
13:11
73
14:24
16:15
15
16:30
18:02
10
18:12
20:03
47
20:50
22:41
7
6:42
8:33
15
8:48
10:39
51
11:30
13:21
69
14:30
16:02
19
16:21
18:12
13
18:25
20:16
44
21:00
22:32
8
6:49
8:40
16
8:56
10:47
53
11:40
13:31
69
14:40
16:31
11
16:42
18:33
20
18:53
20:44
56
21:40
23:31
9
6:50
8:22
10
8:32
10:23
47
11:10
13:01
69
14:10
15:42
28
16:10
17:42
8
17:50
19:22
38
20:00
21:51
10
6:56
8:47
17
9:04
10:55
55
11:50
13:41
67
14:48
16:39
10
16:49
18:40
20
19:00
20:51
59
21:50
23:41
11
7:00
8:32
13
8:45
10:17
53
11:10
12:42
78
14:00
15:51
23
16:14
18:05
13
18:18
20:09
51
21:00
22:51
12
7:03
8:54
21
9:15
10:47
63
11:50
13:22
70
14:32
16:23
17
16:40
18:12
18
18:30
20:02
38
20:40
22:31
13
7:10
9:01
19
9:20
11:11
64
12:15
13:47
63
14:50
16:22
13
16:35
18:26
20
18:46
20:37
53
21:30
23:21
14
7:10
8:42
18
9:00
10:32
58
11:30
13:02
74
14:16
16:07
21
16:28
18:19
13
18:32
20:23
47
21:10
23:01
15
7:17
9:08
22
9:30
11:02
58
12:00
13:51
65
14:56
16:47
9
16:56
18:47
20
19:07
20:58
62
22:00
23:51
16
7:20
8:52
20
9:12
11:03
67
12:10
14:01
63
15:04
16:55
10
17:05
18:37
18
18:55
20:27
53
21:20
23:11
17
7:24
9:15
21
9:36
11:27
73
12:40
14:12
60
15:12
17:03
14
17:17
19:08
25
19:33
21:24
81
22:45
0:36
18
7:30
9:21
29
9:50
11:22
68
12:30
14:21
59
15:20
17:11
9
17:20
18:52
22
19:14
21:05
70
22:15
0:06
19
7:30
9:02
26
9:28
11:19
61
12:20
14:11
59
15:10
16:42
8
16:50
18:22
17
18:39
20:30
55
21:25
22:57
20
7:36
9:27
25
9:52
11:43
77
13:00
14:51
45
15:36
17:27
9
17:36
19:27
19
19:46
21:37
Nonservice time
21
7:42
9:33
37
10:10
12:01
69
13:10
15:01
39
15:40
17:12
12
17:24
19:15
24
19:39
21:30
95
23:05
0:37
22
7:45
9:17
27
9:44
11:35
65
12:40
14:31
49
15:20
16:52
11
17:03
18:54
26
19:20
20:52
58
21:50
23:22
23
7:48
9:39
31
10:10
11:42
68
12:50
14:41
49
15:30
17:02
8
17:10
19:01
20
19:21
21:12
63
22:15
23:47
24
7:54
9:45
35
10:20
12:11
79
13:30
15:02
42
15:44
17:35
7
17:42
19:33
20
19:53
21:44
Nonservice time
25
8:00
9:32
28
10:00
11:51
74
13:05
14:37
51
15:28
17:19
11
17:30
19:21
24
19:45
21:17
73
22:30
0:21
26
8:16
10:07
23
10:30
12:02
78
13:20
15:11
39
15:50
17:22
13
17:35
19:07
20
19:27
21:18
82
22:40
0:12
D.T., A.T., and S.T. are the abbreviations of departure time, arrival time, and dwelling time; the unit of S.T. is min.In this case, with the general fixed job sorting algorithm, the total number of vehicles optimized is still 26 buses, but the total dwelling time at the terminal is 5880 min and the average interval between two consecutive trips is 32.7 min. That is the reason why we modify the general fixed job sorting algorithm. Figure5 shows the comparison of two circumstances.Figure 5
The comparison of the average intervals between two consecutive trips of two circumstances.


## 6. Conclusion

This paper studied a model to optimize cross-line vehicle scheduling for single-depot, whose optimization goal is minimizing the total number of vehicles used. Setting the sole goal avoids the complexity and uncertainty of solving the multiobjective problem and still keeps availability. The modified fixed job sorting algorithm is designed, which can not only get the deterministic optimum solution to reduce total vehicle used but also save the vehicles’ operating time. The algorithm can be easily written into computer program and the computation time is short, which is feasible for application. In fact, the vehicle-scheduling method would not be limited in bus transit operation and could be generalized to the similar scenario of logistics transport.



---

*Source: 506794-2015-09-07.xml*