# Dynamic Bus Scheduling of Multiple Routes Based on Joint Optimization of Departure Time and Speed

Authors: Yingxin Liu; Xinggang Luo; Shengping Cheng; Yang Yu; Jiafu Tang
Journal: Discrete Dynamics in Nature and Society
 (2021)

---

## Abstract

Dynamic bus scheduling is a rational solution to the urban traffic congestion problem. Most previous studies have considered a single bus line, and research on multiple bus lines remains limited. Departure schedules have been typically planned by making separate decisions regarding departure times. In this study, a joint optimization model of the bus departure time and speed scheduling is constructed for multiple routes, and a coevolutionary algorithm (CEA) is developed with the objective function of minimizing the total waiting time of passengers. Six bus lines are selected in Shenyang, with several transfer stations between them, as a typical case. Experiments are then conducted for high-, medium-, and low-intensity case of smooth, increasing and decreasing passenger flow. The results indicate that combining the scheduling departure time and speed produces better performances than when using only scheduling departure time. The total passengers waiting time of the genetic algorithm (GA) group was reduced by approximately 25%–30% when compared to the fixed speed group. The total passengers waiting time of the CEA group can be reduced by approximately 17%–24% when compared to that in the GA group, which also holds true for a multisegment convex passenger flow. The feasibility and efficiency of the constructed algorithm were demonstrated experimentally.


---

## Body

## 1. Introduction

The number of private cars produced and used in China has been increasing annually over the past few years due to rapid urbanization. Traffic congestion has become an increasingly serious problem, despite the numerous measures taken by the Chinese government to improve the traffic conditions [1]. The government advocates that individuals make use of green travel options to reduce traffic congestion and environmental pollution. The advantages offered by buses, in terms of passenger capacity, fuel consumption per capita, energy efficiency, and environmental protection, have demonstrated their efficiency as an effective solution for urban traffic problems. However, the current bus dispatching system in China adopts a static dispatch strategy to achieve the most accurate arrival time, and the daily bus dispatching strategy primarily follows a fixed schedule, which frequently tends to cause some problems, such as bus bunching and poor passenger travel experience with long waiting time. Owing to complex road conditions and fluctuating passenger flow, bus arrival times are often based on drivers’ experience, and their accuracy cannot be ensured, which tends to decrease the quality of the travel experience.Process control strategies are conventionally applied in the operation of public transportation, in which the bus operation plans are adjusted based on the actual daily status of the system. Dynamic bus dispatching in the control process is crucial in public transit because it dynamically determines the performance of the transit system [2]. Dynamic dispatching is a bus scheduling strategy based on the Internet of things (IoT) technology, which enables the monitoring and collection of a significant amount of real-time information in a timely manner, providing data for the implementation of dynamic buses. By design, the operating status of buses is adjusted to achieve their respective objectives based on real-time data.Extensive research has been conducted on dynamic buses to solve traffic congestion and reducing passenger waiting time, most of which had only focused on scheduling of departure time or on scheduling of speed for bus single line. However, relatively little research has thus far been conducted on the simultaneous scheduling of departure times and interstation speeds for multiroute scheduling.To avoid bus bunching, improve passengers’ bus travel experience, and reduce their waiting time, the study focuses on the joint optimization of the departure time and speed in the multiroute bus operation. A cooperative coevolutionary algorithm (CEA) is proposed to solve the joint optimization scheduling problem via a computational model designed to improve the departure time and speed of the multiroute bus systems. The transfer waiting time and speed controllability are considered, and the CEA is developed to solve the model. The main concept of the proposed model involves decomposing the complex problem into several subproblems, which are to be solved separately using suitable evolutionary algorithms, and subsequently, performing cooperative evaluation through the cooperation of multiple populations.The contributions of this study are summarized as follows: a computational model of the joint scheduling of departure time and speed for multiple bus lines is established. In this model, the shortest total waiting time including transfer waiting time is considered as the decision objective, the departure interval and the average speed between stations are considered as the decision variables, and the transfer phenomenon between multiple lines is considered.The CEA is developed based on a proposed coevolution mechanism; a suitable genetic algorithm (GA) is used to evolve the departure scheduling population and the speed scheduling population. During the evolution of departure scheduling and speed scheduling population, the current optimal speed and departure time are used to evaluate the evolved individuals and update the optimal departure time and speed.Simulation experiments are also carried out under different intensities and types of passenger flow distribution. Experimental results demonstrate that CEA exhibited better performance than GA in solving this problem.The remainder of this study is organized as follows: Section2 provides a review of relevant literature. Section 3 describes the problem, modeling assumptions, parameters, objective functions, constraint conditions, and model development. Section 4 presents the method used to solve the established mathematical model. Section 5 describes the numerical experiments and provides an analysis of the results. Finally, Section 6 presents the conclusions.


## 2. Literature Review

Bus scheduling methods are typically classified into two types: static or dynamic. Static bus scheduling is based on static information, such as scheduling of the vehicle and driver, and is mainly intended for scheduling before the initiation of the operation. In contrast, dynamic bus scheduling involves online adjustment and optimization of scheduling plan based on the latest time-varying information, which entails real-time control of the operation process. Owing to the various uncertainties in the bus system, the results of static scheduling can be adjusted based on real-time information, and the entire operation process can be monitored and optimized in dynamic bus scheduling. Representative control strategies include holding [3–11], skip-stop [12–19], short turnaround [20–24], travel restriction [23, 25–27], speed adjustment [28–31], and bus priority [32–35] strategies. Among these, holding, skip-stop, short turnaround, and travel restriction are station control strategies, and speed adjustment and bus priority are interstation control strategies. Furthermore, target lines studied can be broadly classified as single or multiple lines.


### 2.1. Single-Route Bus Dynamic Scheduling

Several studies have been conducted on single-route dynamic transit. In 1988, Van et al. [36] proposed an optimization method to determine the frequency of bus departures on a single route under elastic demand to optimize the maximization of the number of direct trips for specific fleet size, cost budget, and passenger assignment constraints. Leiva et al. [37] established a nonlinear optimization model to minimize the total costs incurred by firms and passengers. Xiuwen [38] optimized the total passenger waiting time at all stops by organizing the departure schedule and constructed a single-route departure-time scheduling model to minimize waiting time. Subsequently, Soto et al. [39] designed a two-layer optimization model by solving the bus-departure frequency and passenger assignment problems separately. Berrebi et al. [40] increased the departure frequency, stabilized the headway time spacing, avoided vehicles clustering at the same stop, and solved the model using inverse induction while minimizing passenger waiting time. Sun et al. [41] proposed a flexible timetable optimization method based on a hybrid vehicle size model to address demand fluctuations in bus transit operation, providing a new perspective to improve the level of regular bus service. Li et al. [42] presented a timetable optimization model with time-dependent passenger demand and travel time among stops. Most recently, Tang et al. [43] developed a new network-based methodology to optimize multiple operational strategies and to accommodate fluctuating passenger demand.


### 2.2. Multiroute Bus Dynamic Scheduling

The research conducted on multiple routes has been primarily focused on the transfer waiting times, which have not been addressed in the single-route studies. For instance, Li et al. [44] considered routes. Ibarra-Rojas and Munoz [45] considered bus operating speed and arrival time deviations and provided a collaborative schedule for overlapping intervals of multiroute bus operations using a GA. They additionally validated their approach using two local bus routes in Santiago, demonstrating that the arrival time of each was uniform when the schedule was beneficial for the passengers using multiroute buses. Shen and Du [46] aimed to minimize the total transfer waiting time of bus passengers by arranging the travel schedules of two routes using nonequally spaced departures to increase the number of interchangeable transfers between two bus lines at the transfer station and coordinate bus arrival times.Subsequently, Shuang and Weishi [47] designed a bus query system based on the least-number-of-transfers algorithm to minimize the number of transfers, and experimentally analyzed their designed system. Lu et al. [48] considered the impact of bus route interactions on passenger travel choices and proposed the coordinated scheduling of multiroute flexible buses in the urban periphery during off-peak hours. Zhou et al. [49] proposed a holding strategy based on two-bus cooperative control method. They conducted a simulation after the preliminary processing and analysis of the bus operation data of city of Foshan and compared the performance using three different scenarios to build a multibus cooperative control strategy.


### 2.3. Bus Speed Adjustment

In the bus speed adjustment process, the headway spacing is dynamically adjusted by adjusting the operating speed of the buses between stops. Daganzo and Pilachowski [28] proposed a speed-control strategy to obtain the appropriate spacing between the front and rear buses through a collaborative two-way approach and dynamically adjusted the operating speed of bus, effectively preventing vehicle aggregation. In addition, Chandrasekar et al. [29] proposed a control method based on controlling bus speed along a given route, the basic concept of which is similar to that of holding a bus at a stop. In other words, because the passengers cannot notice the reduction of the operating speed of the vehicle while running, controlling bus speeds can significantly reduce the unevenness of the time interval. Furthermore, He et al. [31] presented a new studied optimization method for the real-time scheduling of multiroute vehicles in bus hubs. They established a model to optimize the real-time scheduling of multiroute time and transfer passenger flow, along with an optimization objective function based on the minimum cost of the entire system. Li et al. [50] also developed an optimization model for the multiobjective scheduling problem of maximizing the social and corporate operational benefits of multiroute paratransit and designed a hybrid genetic-forbidden algorithm to solve this problem. Subsequently, Mazloumi et al. [51] developed a bus-scheduling scheme based on actual bus-line passenger flow data and used a GA and an ant-colony algorithm to solve the model. Le [52] presented a dynamic bus departure optimization method for multiroute buses considering both company and passenger interests under multivehicle conditions. Hernández et al. [8] proposed real-time scheduling of multiroute buses based on the presence of bus-only lanes on multiple routes, established a central dispatching center, determined the bus departure frequencies, and validated the results using two strategies to overcome the aforementioned drawbacks by adjusting the speeds of buses in dedicated bus lanes to stabilize the highly unstable bus lines, while reducing the waiting and traveling times of passengers. Deng et al. [30] proposed a real-time speed-control model with the objective of minimizing variations in bus headway and analyzed three cases of typical road infrastructure for bus lines.


## 2.1. Single-Route Bus Dynamic Scheduling

Several studies have been conducted on single-route dynamic transit. In 1988, Van et al. [36] proposed an optimization method to determine the frequency of bus departures on a single route under elastic demand to optimize the maximization of the number of direct trips for specific fleet size, cost budget, and passenger assignment constraints. Leiva et al. [37] established a nonlinear optimization model to minimize the total costs incurred by firms and passengers. Xiuwen [38] optimized the total passenger waiting time at all stops by organizing the departure schedule and constructed a single-route departure-time scheduling model to minimize waiting time. Subsequently, Soto et al. [39] designed a two-layer optimization model by solving the bus-departure frequency and passenger assignment problems separately. Berrebi et al. [40] increased the departure frequency, stabilized the headway time spacing, avoided vehicles clustering at the same stop, and solved the model using inverse induction while minimizing passenger waiting time. Sun et al. [41] proposed a flexible timetable optimization method based on a hybrid vehicle size model to address demand fluctuations in bus transit operation, providing a new perspective to improve the level of regular bus service. Li et al. [42] presented a timetable optimization model with time-dependent passenger demand and travel time among stops. Most recently, Tang et al. [43] developed a new network-based methodology to optimize multiple operational strategies and to accommodate fluctuating passenger demand.


## 2.2. Multiroute Bus Dynamic Scheduling

The research conducted on multiple routes has been primarily focused on the transfer waiting times, which have not been addressed in the single-route studies. For instance, Li et al. [44] considered routes. Ibarra-Rojas and Munoz [45] considered bus operating speed and arrival time deviations and provided a collaborative schedule for overlapping intervals of multiroute bus operations using a GA. They additionally validated their approach using two local bus routes in Santiago, demonstrating that the arrival time of each was uniform when the schedule was beneficial for the passengers using multiroute buses. Shen and Du [46] aimed to minimize the total transfer waiting time of bus passengers by arranging the travel schedules of two routes using nonequally spaced departures to increase the number of interchangeable transfers between two bus lines at the transfer station and coordinate bus arrival times.Subsequently, Shuang and Weishi [47] designed a bus query system based on the least-number-of-transfers algorithm to minimize the number of transfers, and experimentally analyzed their designed system. Lu et al. [48] considered the impact of bus route interactions on passenger travel choices and proposed the coordinated scheduling of multiroute flexible buses in the urban periphery during off-peak hours. Zhou et al. [49] proposed a holding strategy based on two-bus cooperative control method. They conducted a simulation after the preliminary processing and analysis of the bus operation data of city of Foshan and compared the performance using three different scenarios to build a multibus cooperative control strategy.


## 2.3. Bus Speed Adjustment

In the bus speed adjustment process, the headway spacing is dynamically adjusted by adjusting the operating speed of the buses between stops. Daganzo and Pilachowski [28] proposed a speed-control strategy to obtain the appropriate spacing between the front and rear buses through a collaborative two-way approach and dynamically adjusted the operating speed of bus, effectively preventing vehicle aggregation. In addition, Chandrasekar et al. [29] proposed a control method based on controlling bus speed along a given route, the basic concept of which is similar to that of holding a bus at a stop. In other words, because the passengers cannot notice the reduction of the operating speed of the vehicle while running, controlling bus speeds can significantly reduce the unevenness of the time interval. Furthermore, He et al. [31] presented a new studied optimization method for the real-time scheduling of multiroute vehicles in bus hubs. They established a model to optimize the real-time scheduling of multiroute time and transfer passenger flow, along with an optimization objective function based on the minimum cost of the entire system. Li et al. [50] also developed an optimization model for the multiobjective scheduling problem of maximizing the social and corporate operational benefits of multiroute paratransit and designed a hybrid genetic-forbidden algorithm to solve this problem. Subsequently, Mazloumi et al. [51] developed a bus-scheduling scheme based on actual bus-line passenger flow data and used a GA and an ant-colony algorithm to solve the model. Le [52] presented a dynamic bus departure optimization method for multiroute buses considering both company and passenger interests under multivehicle conditions. Hernández et al. [8] proposed real-time scheduling of multiroute buses based on the presence of bus-only lanes on multiple routes, established a central dispatching center, determined the bus departure frequencies, and validated the results using two strategies to overcome the aforementioned drawbacks by adjusting the speeds of buses in dedicated bus lanes to stabilize the highly unstable bus lines, while reducing the waiting and traveling times of passengers. Deng et al. [30] proposed a real-time speed-control model with the objective of minimizing variations in bus headway and analyzed three cases of typical road infrastructure for bus lines.


## 3. Joint Optimization Model for Multiline Departure Time and Speed Scheduling

### 3.1. Problem Description

Figure1 illustrates the multiple bus lines considered in this study, indicating that a single line can be considered as a special type of a multiline bus. If transference between lines is not considered, the problem is identical to that of single lines, where single lines can be used as the objects of a study of the departure descriptions.Figure 1
Schematic of multiple bus lines.The departure plan of one bus line is considered as a sample for analysis, as shown in Figure2. Consequently, line p is considered for analysis, and the travel direction of the vehicle is set as indicated by the arrow where the bus stop numbers on the line range from 1 to NPS, that is, the line has a total of NPS stops. The vehicles on the right side of the dashed vertical line are those that have begun traveling on the bus line (not necessarily on the site), the number of which ranges from 1 NpD. The vehicles on the left side of the dotted vertical line are those waiting to depart from the terminal center and are denoted by numbers ranging from NpD+1 to NpD+NpF, with a total number of NpF. After vehicle NpD departs from the first station, the road condition and passenger information are collected, and the departure times of the subsequent NpF vehicles and the speeds between the stations are replanned to determine the optimal departure time and interstation speed until the next vehicle departs at the newly determined departure time, which is called a planning cycle. At the beginning of each planning cycle, that is, after the departure of vehicle NpD+1, the following NpD buses will be in a new planning cycle for the optimal solution to ensure that the planning cycle continues to roll forward with time.Figure 2
Operation diagram of the departure of a single bus.


### 3.2. Assumptions

The following assumptions were made to establish a joint scheduling optimization model for bus-departure time and speed for multiple routes. These assumptions were previously made in several studies [2, 12, 26, 29].(1)
All buses in the area are of the same type, that is, they carry the same number of passengers and exhibit the same level of performance.(2)
There are no traffic accidents.(3)
The times required for passengers to board and deboard are equal.(4)
Buses must stop at each station, slow down to enter the station, and accelerate when leaving the station. If there are no passengers at the station, the stopping time is the sum of the inbound time during deceleration and outbound time during acceleration. If there are passengers, the stopping time is the sum of the inbound time during decelerating, outbound time during accelerating, and passenger boarding and deboarding times.(5)
Buses belonging to the same line cannot overtake one another.(6)
The planned departure time of the last bus must be a fixed value.(7)
Bus-station passenger-flow and vehicle speed are monitored with equipment including a camera and GPS. The passenger flow in the current situation can be predicted based on historical passenger flow information, and the function of each station passenger flow over time can be derived.


### 3.3. Intermediate Variables

Because there are vehicles on the road at the beginning of the planning cycle, it is assumed that real-time information corresponding to these moving vehicles is available for the decision-making process.At the beginning of the planning cycle, the number of passengers in a moving vehicle can be obtained using the IoT (the data were generated through simulation in the calculation experiment). The number of passengers in the bus at this time can be initialized as given below:(1)Npijon=Npinow−on,p=1,2,…,N,i=1,…,NpD,j=Npilast+1.When the bus arrives at the next stop and departs, the number of passengers is equal to the original number of passengers along with the number of passengers boarding at that stop minus the number of passengers deboarding at that stop, as shown in (2):(2)Npijon=Npij−1on+Npij−1debus,p=1,2,…,N,i=1,2,…,NpD+NPF,j=Npilast+2,…,NpS.For simplicity, it is assumed that the rate of passengers deboarding at all stations is known. The number of passengers deboarding is given as follows:(3)Npijdebus=γpjNpijon,p=1,2,…,N,i=1,2,…,NpD+NpF,j=1,2,…,NpS−1.As the bus capacity is limited, the number of passengers onboard becomes equal to the number of passengers waiting at the station when the capacity is sufficient, as shown in (4). However, when the capacity is insufficient, some passengers are left behind, and the number of passengers on board is equal to the maximum capacity minus the original number of passengers, plus the number of passengers deboarding, as shown in (5).(4)Npijboard=Npijwait,p=1,2,…,N,i=1,…,NpD+NpF,j=1,2,…,NpS−1,(5)Npijboard=C−Npijon+Npijdebus,p=1,2,…,N,i=1,…,NpD+NpF,j=1,2,…,NpS−1.For a bus running at the beginning of the planning cycle, the number of waiting passengers at a given stop can be calculated as follows:(6)Npijwait=Npjnow_wait+∫0Tpijafpjtdt+∑q=1N∑m=1NqDNqpmm′Zpqimjm′≥0Zpqi−1mjm′<0,p=1,…,N,i=1,…,NpD,j=1,…,NpS−1,m′=Spqj.The first term on the right-hand side of (6) represents the number of passengers waiting at station j on route p at the start of the planning cycle. The second term refers to the number of passengers arriving at station j during the period from the start of the planning cycle until the bus arrives at station j. Finally, the third term represents the number of passengers transferring to station j on route p from other routes. Essentially, for a bus moving at the beginning of the planning cycle, the number of passengers waiting at the next station when it arrives at that station is the sum of the number of passengers at that station in the initial state plus the number of passengers who arrive before the bus travels to that station and those who are transferring from other lines.For buses that have not yet departed at the beginning of the planning cycle, the number of waiting passengers at stopj is equal to the sum of the number of new arrivals from the previous bus leaving that stop until the bus arrives at stop j and the number of passengers left behind by the previous bus and those from other routes transferring at that stop.(7)Npijwait=∫Tpi−1jaTpijafpjtdt+∑q=1N∑m=1NqDNqpmm′Zpqimjm′≥0Zpqi−1mjm′<0+Npi−1jwait−Npi−1jboard,p=1,…,N,i=NpD+1,…,NpD+NpF,j=1,…,NpS−1;m′=Spqj.As with the calculation of the number of passengers deboarding, the number of transferring passengers can be assumed to be a certain ratio of the deboarding passengers, for simplicity.(8)Npqij=μpqijγpjNpijon,p,q=1,2,…,N,i=1,2,…,NpD+NpF,j∈Spq.The arrival time of a bus at each stop is also divided into two cases. The first case is the arrival time at the next stop of a vehicle, which is running at the beginning of the planning cycle, and is related to its location at the beginning.(9)Tpija=Dpj−DpinowVpij,p=1,2,…,N,i=1,2,…,NpD,j=Npilast+1.The second case is that the time decided at which each vehicle should arrive at each station can be calculated from the departure time of the vehicle from the previous station and the travel time of the vehicle between the two stations.(10)Tpija=Tpij−1+DpjVpij,p=1,2,…,N,i=1,2,…,NpD+NpF,j=Npilast+2,…,NpS.Unlike in the single-route case, the transfer waiting time for transferring passengers must also be considered in the multiple-route case. The calculation formula is as follows:(11)Tpqijwait=minj=1Zpqijmm′≥0NpD+NpFZpqijmm′,p,q=1,…,N,i=1,…,NpD+NpF,m∈Spq;m′=Spqm.In (11), Zpqijmm′≥0 implies that a passenger can transfer from station j to a station online q using vehicle i on line p only when this parameter is nonnegative. The first vehicle to arrive at that station is vehicle m.Zpqijmm′ can be calculated as follows:(12)Zpqijmm′=Tqmm′−Tpija−Tpijwalk,p,q=1,…,N,i,m=1,…,NpD+NpF,j∈Spq,m′=Spqj.The departure time of a bus can be derived from its arrival time and the time taken by passengers to board and deboard the bus.(13)Tpij=Tpija+TboardmaxNpijboard,γpjNpijon,p=1,2,...,N,i=1,2,…,NpD+NpF,j=Npilast+2,…,NpS−1.The waiting time of passengers who missed the last bus in the planning cycle is assumed to be the average waiting time of all passengers who boarded at the previous stations because the arrival time of the next bus is not known.(14)Tpavg_w=∑j=1NpS−1TpNpD+NpFj−TpNpD+NpF−1jNpS−1,p=1,2,…,N.For adjacent buses, the departure time at the first stop must be controlled such that it remains between the maximum and minimum departure intervals.(15)Hmin≤Tpi1−Tpi−11≤Hmax,p=1,2,…,N,i=NpD+1,…,NpD+NpF.During the operation of the vehicle, adjustments must be made to ensure that the headway of adjacent vehicles is always between the maximum and minimum headways, eliminating the bus-gathering phenomenon.(16)Hmin≤Hpij−Hpi−1j≤Hmax,p=1,2,…,N,i=2,…,NpD+NpF,j=1,…,NpS−1.In addition, the speed must be maintained between the maximum and minimum speeds specified by each line.(17)Vmin≤Vpij≤Vmax,p=1,2,…,N,i=1,2,…,NpD+NpF,j=1,…,NpS−1.


### 3.4. Model Construction

In this study, minimization of the total waiting time of passengers is considered as the objective function. This problem can be defined as follows:(18)MinF=Tfirst+Tleft+Ttrans,s. t.(19)Hmin≤Tpij−Tpij−1≤Hmax,p=1,2,…,N,i=1,2,…,NpD+NpF,j=2,…,NpS,(20)Vmin≤Vpij≤Vmax,p=1,2,…,N,i=1,2,…,NpD+NpF,j=1,…,NpS−1,(21)Tpij−Tpi−1j≥0,p=1,2,…,N,i=1,2,…,NpD+NpF,j=1,…,NpS−1.In (18), F is the total waiting time for all passengers, which is divided into three parts.The total waiting time,Tfirst, spent waiting for the first bus, where the integral is approximated by differentiating into rectangles of minimal width:(22)Tfirst=∑p=1N∑i=2NpD+NpF∑j=1NpS∫Tpi−1jTpijTpij−tfpjtdt.The total waiting time of stranded passengers waiting for subsequent vehicles,Tleft, is expressed as follows:(23)Tleft=∑p=1N∑i=2NpD+NpF∑j=1NpSNpijleftTpij−Tpi−1j+∑p=1N∑j=1NpSTpavg_wNpNpD+NpFjleft.The waiting time for transfer passengers,Ttrans, is obtained as follows:(24)Ttrans=∑p=1N∑q=1N∑i=1NpD+NpF∑j∈SpqSpq+NpqijTpqijwait.Here, |Spq|+indicates that the value of Spq is 1 when there is at least one element in the set |Spq|+, that is, when there is a commutation from lines p to q and is 0 otherwise. In addition, (19) and (20) represent the maximum and minimum constraints that need to be met by the departure interval and speed, respectively, and (21) indicates that the same line buses are not allowed to overtake one another.


## 3.1. Problem Description

Figure1 illustrates the multiple bus lines considered in this study, indicating that a single line can be considered as a special type of a multiline bus. If transference between lines is not considered, the problem is identical to that of single lines, where single lines can be used as the objects of a study of the departure descriptions.Figure 1
Schematic of multiple bus lines.The departure plan of one bus line is considered as a sample for analysis, as shown in Figure2. Consequently, line p is considered for analysis, and the travel direction of the vehicle is set as indicated by the arrow where the bus stop numbers on the line range from 1 to NPS, that is, the line has a total of NPS stops. The vehicles on the right side of the dashed vertical line are those that have begun traveling on the bus line (not necessarily on the site), the number of which ranges from 1 NpD. The vehicles on the left side of the dotted vertical line are those waiting to depart from the terminal center and are denoted by numbers ranging from NpD+1 to NpD+NpF, with a total number of NpF. After vehicle NpD departs from the first station, the road condition and passenger information are collected, and the departure times of the subsequent NpF vehicles and the speeds between the stations are replanned to determine the optimal departure time and interstation speed until the next vehicle departs at the newly determined departure time, which is called a planning cycle. At the beginning of each planning cycle, that is, after the departure of vehicle NpD+1, the following NpD buses will be in a new planning cycle for the optimal solution to ensure that the planning cycle continues to roll forward with time.Figure 2
Operation diagram of the departure of a single bus.


## 3.2. Assumptions

The following assumptions were made to establish a joint scheduling optimization model for bus-departure time and speed for multiple routes. These assumptions were previously made in several studies [2, 12, 26, 29].(1)
All buses in the area are of the same type, that is, they carry the same number of passengers and exhibit the same level of performance.(2)
There are no traffic accidents.(3)
The times required for passengers to board and deboard are equal.(4)
Buses must stop at each station, slow down to enter the station, and accelerate when leaving the station. If there are no passengers at the station, the stopping time is the sum of the inbound time during deceleration and outbound time during acceleration. If there are passengers, the stopping time is the sum of the inbound time during decelerating, outbound time during accelerating, and passenger boarding and deboarding times.(5)
Buses belonging to the same line cannot overtake one another.(6)
The planned departure time of the last bus must be a fixed value.(7)
Bus-station passenger-flow and vehicle speed are monitored with equipment including a camera and GPS. The passenger flow in the current situation can be predicted based on historical passenger flow information, and the function of each station passenger flow over time can be derived.


## 3.3. Intermediate Variables

Because there are vehicles on the road at the beginning of the planning cycle, it is assumed that real-time information corresponding to these moving vehicles is available for the decision-making process.At the beginning of the planning cycle, the number of passengers in a moving vehicle can be obtained using the IoT (the data were generated through simulation in the calculation experiment). The number of passengers in the bus at this time can be initialized as given below:(1)Npijon=Npinow−on,p=1,2,…,N,i=1,…,NpD,j=Npilast+1.When the bus arrives at the next stop and departs, the number of passengers is equal to the original number of passengers along with the number of passengers boarding at that stop minus the number of passengers deboarding at that stop, as shown in (2):(2)Npijon=Npij−1on+Npij−1debus,p=1,2,…,N,i=1,2,…,NpD+NPF,j=Npilast+2,…,NpS.For simplicity, it is assumed that the rate of passengers deboarding at all stations is known. The number of passengers deboarding is given as follows:(3)Npijdebus=γpjNpijon,p=1,2,…,N,i=1,2,…,NpD+NpF,j=1,2,…,NpS−1.As the bus capacity is limited, the number of passengers onboard becomes equal to the number of passengers waiting at the station when the capacity is sufficient, as shown in (4). However, when the capacity is insufficient, some passengers are left behind, and the number of passengers on board is equal to the maximum capacity minus the original number of passengers, plus the number of passengers deboarding, as shown in (5).(4)Npijboard=Npijwait,p=1,2,…,N,i=1,…,NpD+NpF,j=1,2,…,NpS−1,(5)Npijboard=C−Npijon+Npijdebus,p=1,2,…,N,i=1,…,NpD+NpF,j=1,2,…,NpS−1.For a bus running at the beginning of the planning cycle, the number of waiting passengers at a given stop can be calculated as follows:(6)Npijwait=Npjnow_wait+∫0Tpijafpjtdt+∑q=1N∑m=1NqDNqpmm′Zpqimjm′≥0Zpqi−1mjm′<0,p=1,…,N,i=1,…,NpD,j=1,…,NpS−1,m′=Spqj.The first term on the right-hand side of (6) represents the number of passengers waiting at station j on route p at the start of the planning cycle. The second term refers to the number of passengers arriving at station j during the period from the start of the planning cycle until the bus arrives at station j. Finally, the third term represents the number of passengers transferring to station j on route p from other routes. Essentially, for a bus moving at the beginning of the planning cycle, the number of passengers waiting at the next station when it arrives at that station is the sum of the number of passengers at that station in the initial state plus the number of passengers who arrive before the bus travels to that station and those who are transferring from other lines.For buses that have not yet departed at the beginning of the planning cycle, the number of waiting passengers at stopj is equal to the sum of the number of new arrivals from the previous bus leaving that stop until the bus arrives at stop j and the number of passengers left behind by the previous bus and those from other routes transferring at that stop.(7)Npijwait=∫Tpi−1jaTpijafpjtdt+∑q=1N∑m=1NqDNqpmm′Zpqimjm′≥0Zpqi−1mjm′<0+Npi−1jwait−Npi−1jboard,p=1,…,N,i=NpD+1,…,NpD+NpF,j=1,…,NpS−1;m′=Spqj.As with the calculation of the number of passengers deboarding, the number of transferring passengers can be assumed to be a certain ratio of the deboarding passengers, for simplicity.(8)Npqij=μpqijγpjNpijon,p,q=1,2,…,N,i=1,2,…,NpD+NpF,j∈Spq.The arrival time of a bus at each stop is also divided into two cases. The first case is the arrival time at the next stop of a vehicle, which is running at the beginning of the planning cycle, and is related to its location at the beginning.(9)Tpija=Dpj−DpinowVpij,p=1,2,…,N,i=1,2,…,NpD,j=Npilast+1.The second case is that the time decided at which each vehicle should arrive at each station can be calculated from the departure time of the vehicle from the previous station and the travel time of the vehicle between the two stations.(10)Tpija=Tpij−1+DpjVpij,p=1,2,…,N,i=1,2,…,NpD+NpF,j=Npilast+2,…,NpS.Unlike in the single-route case, the transfer waiting time for transferring passengers must also be considered in the multiple-route case. The calculation formula is as follows:(11)Tpqijwait=minj=1Zpqijmm′≥0NpD+NpFZpqijmm′,p,q=1,…,N,i=1,…,NpD+NpF,m∈Spq;m′=Spqm.In (11), Zpqijmm′≥0 implies that a passenger can transfer from station j to a station online q using vehicle i on line p only when this parameter is nonnegative. The first vehicle to arrive at that station is vehicle m.Zpqijmm′ can be calculated as follows:(12)Zpqijmm′=Tqmm′−Tpija−Tpijwalk,p,q=1,…,N,i,m=1,…,NpD+NpF,j∈Spq,m′=Spqj.The departure time of a bus can be derived from its arrival time and the time taken by passengers to board and deboard the bus.(13)Tpij=Tpija+TboardmaxNpijboard,γpjNpijon,p=1,2,...,N,i=1,2,…,NpD+NpF,j=Npilast+2,…,NpS−1.The waiting time of passengers who missed the last bus in the planning cycle is assumed to be the average waiting time of all passengers who boarded at the previous stations because the arrival time of the next bus is not known.(14)Tpavg_w=∑j=1NpS−1TpNpD+NpFj−TpNpD+NpF−1jNpS−1,p=1,2,…,N.For adjacent buses, the departure time at the first stop must be controlled such that it remains between the maximum and minimum departure intervals.(15)Hmin≤Tpi1−Tpi−11≤Hmax,p=1,2,…,N,i=NpD+1,…,NpD+NpF.During the operation of the vehicle, adjustments must be made to ensure that the headway of adjacent vehicles is always between the maximum and minimum headways, eliminating the bus-gathering phenomenon.(16)Hmin≤Hpij−Hpi−1j≤Hmax,p=1,2,…,N,i=2,…,NpD+NpF,j=1,…,NpS−1.In addition, the speed must be maintained between the maximum and minimum speeds specified by each line.(17)Vmin≤Vpij≤Vmax,p=1,2,…,N,i=1,2,…,NpD+NpF,j=1,…,NpS−1.


## 3.4. Model Construction

In this study, minimization of the total waiting time of passengers is considered as the objective function. This problem can be defined as follows:(18)MinF=Tfirst+Tleft+Ttrans,s. t.(19)Hmin≤Tpij−Tpij−1≤Hmax,p=1,2,…,N,i=1,2,…,NpD+NpF,j=2,…,NpS,(20)Vmin≤Vpij≤Vmax,p=1,2,…,N,i=1,2,…,NpD+NpF,j=1,…,NpS−1,(21)Tpij−Tpi−1j≥0,p=1,2,…,N,i=1,2,…,NpD+NpF,j=1,…,NpS−1.In (18), F is the total waiting time for all passengers, which is divided into three parts.The total waiting time,Tfirst, spent waiting for the first bus, where the integral is approximated by differentiating into rectangles of minimal width:(22)Tfirst=∑p=1N∑i=2NpD+NpF∑j=1NpS∫Tpi−1jTpijTpij−tfpjtdt.The total waiting time of stranded passengers waiting for subsequent vehicles,Tleft, is expressed as follows:(23)Tleft=∑p=1N∑i=2NpD+NpF∑j=1NpSNpijleftTpij−Tpi−1j+∑p=1N∑j=1NpSTpavg_wNpNpD+NpFjleft.The waiting time for transfer passengers,Ttrans, is obtained as follows:(24)Ttrans=∑p=1N∑q=1N∑i=1NpD+NpF∑j∈SpqSpq+NpqijTpqijwait.Here, |Spq|+indicates that the value of Spq is 1 when there is at least one element in the set |Spq|+, that is, when there is a commutation from lines p to q and is 0 otherwise. In addition, (19) and (20) represent the maximum and minimum constraints that need to be met by the departure interval and speed, respectively, and (21) indicates that the same line buses are not allowed to overtake one another.


## 4. Algorithm for Departure Time and Speed Scheduling of Multiple Lines

The optimization problem associated with dynamic dispatching is NP-HARD, and the excessive solution space makes most of the solutions obtained by exact algorithms impractical. Intelligent algorithms can effectively solve this problem, among which GAs are widely used in major fields because of their efficient global search abilities and wide scalability. Therefore, a suitable GA was first applied to solve the problem according to the model characteristics as a comparison experiment; then, a suitable CEA was designed to solve the problem according to the characteristics of the model in this study.


### 4.1. GA for Departure Time and Speed Scheduling of Multiple Lines

#### 4.1.1. Chromosome Code

Based on the mathematical model given above, the solution of this model can be divided into two parts. One is the departure moment of each bus at the first station in minutes, and the other is the average speed of the vehicle traveling between the stations in kilometers per hour. Integer coding was used based on the decision variables. Furthermore, the departure moment was converted into a departure interval to simplify the coding process, and the coded chromosome genes are shown in Figure3.Figure 3
GA chromosome map.In Figure3, the interval from H111 to H1NPF1 represents the departure interval between the first bus determined to start on the first route in the planning to the NPF th bus at the first stop. The subsequent interval from V111 to V1N1FN1S represents the travel speeds of the first vehicle to be decided on the first route through the NPF th bus at all stops.Each subsequent line is coded similar to the first line, that is, the firstNpF gene bits indicate the departure interval between the vehicle to be determined and the previous bus at the first stop. The NpS gene bits indicate the average speed of the first vehicle to be determined between the stops. Then the NpS gene bits indicate the average speed of the second vehicle to be decided between the stops, and so on up to the NpF th vehicle.


#### 4.1.2. Chromosome Crossover and Mutations

The chromosome crossover and mutation operations are used to generate new offspring. The crossover operation involves seeking superiority from an excellent parent base, and mutation introduces the possibility of breaking the local superiority. Uniform crossover and single-point random variation are employed for the intersite speed in the proposed model. In the crossover operation, the two individuals to be crossed are first selected. A 0-1 mask, which is equal in length to the chromosome, is then generated, where the gene position corresponding to the mask 1 is the gene position to be crossed and the gene position of the speed part is directly exchanged to generate the offspring. The mutation operation is similar to the crossover operation, that is, the mutant individuals are first selected, a 0-1 mask of equal length is generated, and the gene position corresponding to 1 is subjected to the mutation operation, which is set to be replaced directly with other valid random values.Because of hypothesis (6) in Section 3.2, the crossover variation operation applied to the vehicle speed part is no longer suitable for the genetic position of the departure moment part. For example, if the total departure interval is 40, the fourth gene position of two chromosomes [8–12] undergoes crossover operation to generate two daughter chromosomes [8–12]. The total departure interval of the first daughter chromosome is 38, whereas the total departure interval of the second daughter chromosome is 42, which does not satisfy hypothesis (6). Further improvement is required in the crossover operation because there is a high probability of generating spent chromosomes when using the same crossover operator as the vehicle speed part.The crossover operator for the departure interval gene in the proposed method is a combination of three approaches: multipoint, uniform, and arithmetic crossover. After selecting two chromosomes that require crossover, a 0-1 mask is generated and two-by-two matching is performed for all gene sites that require crossover operation. Therefore, totals ofX1old,Y1old and X2old,Y2old genes in the two parent chromosomes require crossover. Equations (25)–(28) are used to generate new offspring gene loci values:(25)X1new=X2old×X1old+Y1oldX2old+Y2old,(26)Y1new=Y2old×X1old+Y1oldX2old+Y2old,(27)X2new=X1old×X2old+Y2oldX1old+Y1old,(28)Y2new=Y1old×X2old+Y2oldX1old+Y1old.Here,X1old and Y1old are paired genes on the first parent chromosome, X2old and Y2old are paired genes on the second parent chromosome, X1new and Y1new are paired genes of the first newly generated offspring, X2new and Y2new are paired genes of the second newly generated offspring, and the offspring are produced using this operator. Figure 4 shows an example of the new crossover operator, where the parent is guaranteed to be a valid chromosome.Figure 4
Schematic diagram of chromosome crossover.Similar to the crossover operator, the random variation operator also requires improvement as it primarily generates subchromosomes that do not satisfy hypothesis (6). Once again, the mutation operation for the genetic part of the departure interval is first generated as a 0-1 mask of the same length, and the part with a mask of 1 is the gene locus that requires mutation. All gene positions requiring mutation are also paired, and if there is a single position remaining at the end, the gene position with mask 0 is randomly matched for pairing. For all paired genes, one gene is randomly changed to another value similar to the speed section, and the paired genes are incremented or decremented based on the difference between the locus value and the original value, ensuring that the mutated chromosome is also valid. As shown in Figure 5, one gene position performs a plus-one operation and the other gene position paired with it performs a minus-one operation.Figure 5
Schematic diagram of chromosome variation.


#### 4.1.3. Strategy Selection

A classical roulette wheel selection strategy is used in the proposed method. However, since the optimization objective requires the minimization the total waiting time of the passengers, it is necessary first to convert the fitness values of all individuals as shown below:(29)Fnew=Fmax−Fold+ηFmax−Fmin+η.Here,Fmax and Fmin are the maximum and minimum fitness values in the current population, respectively; Fold and Fnew are the fitness values before and after individual conversion; and η is a minimal value preventing the denominator value from being zero when the maximum and minimum fitness values are equal. After conversion using (29), the smaller the fitness value before conversion, the larger the new fitness value after conversion. The general roulette selection method can thus be employed for selection. After the conversion, the selection probability of each chromosome is obtained using (30), and the cumulative probability can be calculated using (31):(30)Pi=Finew∑i=1NFinew,(31)pisum=∑k=1iPknew.During the selection, a random number,x, is randomly generated between 0 and 1, and an individual, i, is selected when Pi−1sum≤x≤Pisum. This process is repeated until the required number of individuals has been selected.


### 4.2. CEA for Joint Departure Time and Speed Scheduling of Multiple Lines

The CEAs have been widely applied in various fields [53–61] and can be mainly classified into the CEAs using population, individual, algorithm, operation, parameter, and strategy cooperation. A population CEA was employed in this study. This type of CEA is mainly used to realize coevolutionary searching indirectly through mutual evaluation between populations.The main concept involves decomposing the complex problem into several subproblems, which can be solved using various suitable algorithms. Cooperation with multiple populations is performed to achieve cooperative evaluation. The multiroute bus departure time and speed scheduling are decomposed into two subpopulations: departure and speed scheduling, based on the decision variables. The two populations affect each other and are interdependent; together, a departure scheduling solution and speed scheduling solution form a complete solution. Therefore, an optimal solution of the opposite type is required to evaluate the individual dispatcher or individual speed dispatcher; that is, the evolutionary process of one algorithm requires the assistance of the optimal solution generated by the other algorithm. The two algorithms alternate to ensure that the departure and speed scheduling continuously converge to produce optimality.Figure6 depicts the flow of the CEA and synergistic mechanism. Because the evaluation requires parameters pertaining to both the speed and departure moment, the departure moment is thus necessary to evolve the speed population (step 2), to ensure that the current optimal departure moment is sequentially combined with all of the evolved individuals in the speed scheduling population, and to form a complete solution to calculate the fitness value. The application of this method ensures that the individuals in the speed-scheduling population and those generating the next generation speed population can be evaluated. If the current speed population evolves to produce individuals with a better speed than the current optimal speed, the current optimal speed is updated (step 3). Similarly, the departure time population is evolved, the current optimal speed is utilized to assist the evolution of the departure-time population, and the current optimal departure time is updated after evolution (steps 4–6). This process is repeated until the termination condition is reached.Figure 6
Diagram of coevolution.Figure7 shows a flowchart of the coevolution process.Figure 7
Coevolution flow chart.The CEA employed in this study contains two subpopulations: departure time scheduling population and vehicle speed scheduling population, which are resolved using their respective evolutionary algorithms. The two subpopulations and their evolutionary algorithms are described below:(1)
Design of Genetic Evolutionary Algorithm for Vehicle Speed Scheduling Subpopulation. The evolutionary car speed scheduling population uses a GA, which includes the crossover, mutation, selection, and other operations. The variation operator with uniform crossover and single-point exchange is used to generate offspring, and the roulette wheel is subsequently applied to select individuals from the population. Integer coding is used for the speed population, where each gene position represents a value of speed. Figure8 illustrates the chromosome design.In Figure8, V111 is the travel speed of the first decision vehicle of the first line between the first stop and stop 1. N1S−1 gene bits indicate the average travel speed of vehicle 1 of the first line decision between stops. This quantity is followed by the average speed of the second vehicle to be determined between each stop on the first line, until the average speeds of all vehicles on the first line between stops have been determined. The second through p-th lines have the same design structure as the first line.A simple uniform crossover approach is utilized for the crossover operator because only the maximum and minimum driving speeds are guaranteed. Hence, the crossover operator first selects two individuals to be crossed then generates a 0-1 mask of equal length, and the two individuals corresponding to the gene position with mask 1 are exchanged. The variation operator takes a single point of variation; that is, the gene at the gene locus selected for variation is randomly replaced with another gene that meets the requirement. The roulette wheel selection method is used, where each parent and offspring are selected together, and only a specific number of individuals survive each generation until a sufficient number of generations have been considered to reach convergence.(2)
Genetic Evolutionary Algorithm Design for the Departure Scheduling Subpopulation. The GA used for the evolutionary departure time scheduling subpopulation remains the same, where the decision variables are first coded for simplicity and the departure times are converted into departure intervals for evolution. Each gene position represents the departure interval from the previous vehicle. Figure9 illustrates the chromosome design.Figure 8
Chromosome design of the bus speed population.Figure 9
Chromosome design of the population during departure.As shown in Figure9, H111 represents the departure interval between the first bus to be determined to start on the first line and the previous bus that has already left and H121 represents the departure interval between these buses. The first N1F genes are the departure intervals between all vehicles to be determined to start on the first bus line and the previous bus at the first stop. The subsequent N2F genes are the departure intervals between the vehicles to be determined to start on the second bus line at the first stop, and all designs of all subsequent lines are consistent with that of the first line.The crossover and variation operators adopt the crossover mode and variation mode, respectively, of the chromosome of the departure interval part discussed in Section3.1. Finally, the roulette wheel is used to select the evolved offspring individuals.


## 4.1. GA for Departure Time and Speed Scheduling of Multiple Lines

### 4.1.1. Chromosome Code

Based on the mathematical model given above, the solution of this model can be divided into two parts. One is the departure moment of each bus at the first station in minutes, and the other is the average speed of the vehicle traveling between the stations in kilometers per hour. Integer coding was used based on the decision variables. Furthermore, the departure moment was converted into a departure interval to simplify the coding process, and the coded chromosome genes are shown in Figure3.Figure 3
GA chromosome map.In Figure3, the interval from H111 to H1NPF1 represents the departure interval between the first bus determined to start on the first route in the planning to the NPF th bus at the first stop. The subsequent interval from V111 to V1N1FN1S represents the travel speeds of the first vehicle to be decided on the first route through the NPF th bus at all stops.Each subsequent line is coded similar to the first line, that is, the firstNpF gene bits indicate the departure interval between the vehicle to be determined and the previous bus at the first stop. The NpS gene bits indicate the average speed of the first vehicle to be determined between the stops. Then the NpS gene bits indicate the average speed of the second vehicle to be decided between the stops, and so on up to the NpF th vehicle.


### 4.1.2. Chromosome Crossover and Mutations

The chromosome crossover and mutation operations are used to generate new offspring. The crossover operation involves seeking superiority from an excellent parent base, and mutation introduces the possibility of breaking the local superiority. Uniform crossover and single-point random variation are employed for the intersite speed in the proposed model. In the crossover operation, the two individuals to be crossed are first selected. A 0-1 mask, which is equal in length to the chromosome, is then generated, where the gene position corresponding to the mask 1 is the gene position to be crossed and the gene position of the speed part is directly exchanged to generate the offspring. The mutation operation is similar to the crossover operation, that is, the mutant individuals are first selected, a 0-1 mask of equal length is generated, and the gene position corresponding to 1 is subjected to the mutation operation, which is set to be replaced directly with other valid random values.Because of hypothesis (6) in Section 3.2, the crossover variation operation applied to the vehicle speed part is no longer suitable for the genetic position of the departure moment part. For example, if the total departure interval is 40, the fourth gene position of two chromosomes [8–12] undergoes crossover operation to generate two daughter chromosomes [8–12]. The total departure interval of the first daughter chromosome is 38, whereas the total departure interval of the second daughter chromosome is 42, which does not satisfy hypothesis (6). Further improvement is required in the crossover operation because there is a high probability of generating spent chromosomes when using the same crossover operator as the vehicle speed part.The crossover operator for the departure interval gene in the proposed method is a combination of three approaches: multipoint, uniform, and arithmetic crossover. After selecting two chromosomes that require crossover, a 0-1 mask is generated and two-by-two matching is performed for all gene sites that require crossover operation. Therefore, totals ofX1old,Y1old and X2old,Y2old genes in the two parent chromosomes require crossover. Equations (25)–(28) are used to generate new offspring gene loci values:(25)X1new=X2old×X1old+Y1oldX2old+Y2old,(26)Y1new=Y2old×X1old+Y1oldX2old+Y2old,(27)X2new=X1old×X2old+Y2oldX1old+Y1old,(28)Y2new=Y1old×X2old+Y2oldX1old+Y1old.Here,X1old and Y1old are paired genes on the first parent chromosome, X2old and Y2old are paired genes on the second parent chromosome, X1new and Y1new are paired genes of the first newly generated offspring, X2new and Y2new are paired genes of the second newly generated offspring, and the offspring are produced using this operator. Figure 4 shows an example of the new crossover operator, where the parent is guaranteed to be a valid chromosome.Figure 4
Schematic diagram of chromosome crossover.Similar to the crossover operator, the random variation operator also requires improvement as it primarily generates subchromosomes that do not satisfy hypothesis (6). Once again, the mutation operation for the genetic part of the departure interval is first generated as a 0-1 mask of the same length, and the part with a mask of 1 is the gene locus that requires mutation. All gene positions requiring mutation are also paired, and if there is a single position remaining at the end, the gene position with mask 0 is randomly matched for pairing. For all paired genes, one gene is randomly changed to another value similar to the speed section, and the paired genes are incremented or decremented based on the difference between the locus value and the original value, ensuring that the mutated chromosome is also valid. As shown in Figure 5, one gene position performs a plus-one operation and the other gene position paired with it performs a minus-one operation.Figure 5
Schematic diagram of chromosome variation.


### 4.1.3. Strategy Selection

A classical roulette wheel selection strategy is used in the proposed method. However, since the optimization objective requires the minimization the total waiting time of the passengers, it is necessary first to convert the fitness values of all individuals as shown below:(29)Fnew=Fmax−Fold+ηFmax−Fmin+η.Here,Fmax and Fmin are the maximum and minimum fitness values in the current population, respectively; Fold and Fnew are the fitness values before and after individual conversion; and η is a minimal value preventing the denominator value from being zero when the maximum and minimum fitness values are equal. After conversion using (29), the smaller the fitness value before conversion, the larger the new fitness value after conversion. The general roulette selection method can thus be employed for selection. After the conversion, the selection probability of each chromosome is obtained using (30), and the cumulative probability can be calculated using (31):(30)Pi=Finew∑i=1NFinew,(31)pisum=∑k=1iPknew.During the selection, a random number,x, is randomly generated between 0 and 1, and an individual, i, is selected when Pi−1sum≤x≤Pisum. This process is repeated until the required number of individuals has been selected.


## 4.1.1. Chromosome Code

Based on the mathematical model given above, the solution of this model can be divided into two parts. One is the departure moment of each bus at the first station in minutes, and the other is the average speed of the vehicle traveling between the stations in kilometers per hour. Integer coding was used based on the decision variables. Furthermore, the departure moment was converted into a departure interval to simplify the coding process, and the coded chromosome genes are shown in Figure3.Figure 3
GA chromosome map.In Figure3, the interval from H111 to H1NPF1 represents the departure interval between the first bus determined to start on the first route in the planning to the NPF th bus at the first stop. The subsequent interval from V111 to V1N1FN1S represents the travel speeds of the first vehicle to be decided on the first route through the NPF th bus at all stops.Each subsequent line is coded similar to the first line, that is, the firstNpF gene bits indicate the departure interval between the vehicle to be determined and the previous bus at the first stop. The NpS gene bits indicate the average speed of the first vehicle to be determined between the stops. Then the NpS gene bits indicate the average speed of the second vehicle to be decided between the stops, and so on up to the NpF th vehicle.


## 4.1.2. Chromosome Crossover and Mutations

The chromosome crossover and mutation operations are used to generate new offspring. The crossover operation involves seeking superiority from an excellent parent base, and mutation introduces the possibility of breaking the local superiority. Uniform crossover and single-point random variation are employed for the intersite speed in the proposed model. In the crossover operation, the two individuals to be crossed are first selected. A 0-1 mask, which is equal in length to the chromosome, is then generated, where the gene position corresponding to the mask 1 is the gene position to be crossed and the gene position of the speed part is directly exchanged to generate the offspring. The mutation operation is similar to the crossover operation, that is, the mutant individuals are first selected, a 0-1 mask of equal length is generated, and the gene position corresponding to 1 is subjected to the mutation operation, which is set to be replaced directly with other valid random values.Because of hypothesis (6) in Section 3.2, the crossover variation operation applied to the vehicle speed part is no longer suitable for the genetic position of the departure moment part. For example, if the total departure interval is 40, the fourth gene position of two chromosomes [8–12] undergoes crossover operation to generate two daughter chromosomes [8–12]. The total departure interval of the first daughter chromosome is 38, whereas the total departure interval of the second daughter chromosome is 42, which does not satisfy hypothesis (6). Further improvement is required in the crossover operation because there is a high probability of generating spent chromosomes when using the same crossover operator as the vehicle speed part.The crossover operator for the departure interval gene in the proposed method is a combination of three approaches: multipoint, uniform, and arithmetic crossover. After selecting two chromosomes that require crossover, a 0-1 mask is generated and two-by-two matching is performed for all gene sites that require crossover operation. Therefore, totals ofX1old,Y1old and X2old,Y2old genes in the two parent chromosomes require crossover. Equations (25)–(28) are used to generate new offspring gene loci values:(25)X1new=X2old×X1old+Y1oldX2old+Y2old,(26)Y1new=Y2old×X1old+Y1oldX2old+Y2old,(27)X2new=X1old×X2old+Y2oldX1old+Y1old,(28)Y2new=Y1old×X2old+Y2oldX1old+Y1old.Here,X1old and Y1old are paired genes on the first parent chromosome, X2old and Y2old are paired genes on the second parent chromosome, X1new and Y1new are paired genes of the first newly generated offspring, X2new and Y2new are paired genes of the second newly generated offspring, and the offspring are produced using this operator. Figure 4 shows an example of the new crossover operator, where the parent is guaranteed to be a valid chromosome.Figure 4
Schematic diagram of chromosome crossover.Similar to the crossover operator, the random variation operator also requires improvement as it primarily generates subchromosomes that do not satisfy hypothesis (6). Once again, the mutation operation for the genetic part of the departure interval is first generated as a 0-1 mask of the same length, and the part with a mask of 1 is the gene locus that requires mutation. All gene positions requiring mutation are also paired, and if there is a single position remaining at the end, the gene position with mask 0 is randomly matched for pairing. For all paired genes, one gene is randomly changed to another value similar to the speed section, and the paired genes are incremented or decremented based on the difference between the locus value and the original value, ensuring that the mutated chromosome is also valid. As shown in Figure 5, one gene position performs a plus-one operation and the other gene position paired with it performs a minus-one operation.Figure 5
Schematic diagram of chromosome variation.


## 4.1.3. Strategy Selection

A classical roulette wheel selection strategy is used in the proposed method. However, since the optimization objective requires the minimization the total waiting time of the passengers, it is necessary first to convert the fitness values of all individuals as shown below:(29)Fnew=Fmax−Fold+ηFmax−Fmin+η.Here,Fmax and Fmin are the maximum and minimum fitness values in the current population, respectively; Fold and Fnew are the fitness values before and after individual conversion; and η is a minimal value preventing the denominator value from being zero when the maximum and minimum fitness values are equal. After conversion using (29), the smaller the fitness value before conversion, the larger the new fitness value after conversion. The general roulette selection method can thus be employed for selection. After the conversion, the selection probability of each chromosome is obtained using (30), and the cumulative probability can be calculated using (31):(30)Pi=Finew∑i=1NFinew,(31)pisum=∑k=1iPknew.During the selection, a random number,x, is randomly generated between 0 and 1, and an individual, i, is selected when Pi−1sum≤x≤Pisum. This process is repeated until the required number of individuals has been selected.


## 4.2. CEA for Joint Departure Time and Speed Scheduling of Multiple Lines

The CEAs have been widely applied in various fields [53–61] and can be mainly classified into the CEAs using population, individual, algorithm, operation, parameter, and strategy cooperation. A population CEA was employed in this study. This type of CEA is mainly used to realize coevolutionary searching indirectly through mutual evaluation between populations.The main concept involves decomposing the complex problem into several subproblems, which can be solved using various suitable algorithms. Cooperation with multiple populations is performed to achieve cooperative evaluation. The multiroute bus departure time and speed scheduling are decomposed into two subpopulations: departure and speed scheduling, based on the decision variables. The two populations affect each other and are interdependent; together, a departure scheduling solution and speed scheduling solution form a complete solution. Therefore, an optimal solution of the opposite type is required to evaluate the individual dispatcher or individual speed dispatcher; that is, the evolutionary process of one algorithm requires the assistance of the optimal solution generated by the other algorithm. The two algorithms alternate to ensure that the departure and speed scheduling continuously converge to produce optimality.Figure6 depicts the flow of the CEA and synergistic mechanism. Because the evaluation requires parameters pertaining to both the speed and departure moment, the departure moment is thus necessary to evolve the speed population (step 2), to ensure that the current optimal departure moment is sequentially combined with all of the evolved individuals in the speed scheduling population, and to form a complete solution to calculate the fitness value. The application of this method ensures that the individuals in the speed-scheduling population and those generating the next generation speed population can be evaluated. If the current speed population evolves to produce individuals with a better speed than the current optimal speed, the current optimal speed is updated (step 3). Similarly, the departure time population is evolved, the current optimal speed is utilized to assist the evolution of the departure-time population, and the current optimal departure time is updated after evolution (steps 4–6). This process is repeated until the termination condition is reached.Figure 6
Diagram of coevolution.Figure7 shows a flowchart of the coevolution process.Figure 7
Coevolution flow chart.The CEA employed in this study contains two subpopulations: departure time scheduling population and vehicle speed scheduling population, which are resolved using their respective evolutionary algorithms. The two subpopulations and their evolutionary algorithms are described below:(1)
Design of Genetic Evolutionary Algorithm for Vehicle Speed Scheduling Subpopulation. The evolutionary car speed scheduling population uses a GA, which includes the crossover, mutation, selection, and other operations. The variation operator with uniform crossover and single-point exchange is used to generate offspring, and the roulette wheel is subsequently applied to select individuals from the population. Integer coding is used for the speed population, where each gene position represents a value of speed. Figure8 illustrates the chromosome design.In Figure8, V111 is the travel speed of the first decision vehicle of the first line between the first stop and stop 1. N1S−1 gene bits indicate the average travel speed of vehicle 1 of the first line decision between stops. This quantity is followed by the average speed of the second vehicle to be determined between each stop on the first line, until the average speeds of all vehicles on the first line between stops have been determined. The second through p-th lines have the same design structure as the first line.A simple uniform crossover approach is utilized for the crossover operator because only the maximum and minimum driving speeds are guaranteed. Hence, the crossover operator first selects two individuals to be crossed then generates a 0-1 mask of equal length, and the two individuals corresponding to the gene position with mask 1 are exchanged. The variation operator takes a single point of variation; that is, the gene at the gene locus selected for variation is randomly replaced with another gene that meets the requirement. The roulette wheel selection method is used, where each parent and offspring are selected together, and only a specific number of individuals survive each generation until a sufficient number of generations have been considered to reach convergence.(2)
Genetic Evolutionary Algorithm Design for the Departure Scheduling Subpopulation. The GA used for the evolutionary departure time scheduling subpopulation remains the same, where the decision variables are first coded for simplicity and the departure times are converted into departure intervals for evolution. Each gene position represents the departure interval from the previous vehicle. Figure9 illustrates the chromosome design.Figure 8
Chromosome design of the bus speed population.Figure 9
Chromosome design of the population during departure.As shown in Figure9, H111 represents the departure interval between the first bus to be determined to start on the first line and the previous bus that has already left and H121 represents the departure interval between these buses. The first N1F genes are the departure intervals between all vehicles to be determined to start on the first bus line and the previous bus at the first stop. The subsequent N2F genes are the departure intervals between the vehicles to be determined to start on the second bus line at the first stop, and all designs of all subsequent lines are consistent with that of the first line.The crossover and variation operators adopt the crossover mode and variation mode, respectively, of the chromosome of the departure interval part discussed in Section3.1. Finally, the roulette wheel is used to select the evolved offspring individuals.


## 5. Numerical Experiments

All numerical experiments in this study were performed on an Intel Core(TM) i7-8700 processor 3.19 GHz computer with 8 GB of RAM and the Windows 10 operating system. Six bus lines in Shenyang were selected as typical cases for the scheduling problem. Figure1 depicts the distribution of the lines, and Table 1 provides the corresponding details. There are several interchange stations between the six lines. The eighth station of the first line can be transferred to the seventh station of the fourth line, the 14th station can be transferred to the eighth station of the fifth line, and the 18th station can be transferred to the 15th station of the sixth line. Meanwhile, the 10th station of the second line can be transferred to the 16th station of the fourth line, the 16th station can be transferred to the 15th station of the fifth line, and the 19th station of the third line can be transferred to the sixth station of the sixth line.Table 1
Information about each bus line.
First lineSecond lineThird lineFourth lineFifth lineSixth lineNumber of seats232635232132Capacity353540353540Full length (km)1315.154012.6713.2515.6Because a significant amount of real-time information is required to solve the scheduling problem, it is necessary to first perform an initial state simulation. The real-time information includes the locations of the vehicles running on the line at the beginning of the planning-time window, the number of passengers waiting at each station, and the number of passengers in each running vehicle. A simulation using the C# language was employed in this study to obtain these data. The subsequent optimization algorithm read these simulation data for optimization, and experimental analyses performed under different passenger flow conditions are presented in the following subsections. The fixed vehicle speed part was considered to be 18 km/h, as used in the multiroute dynamic scheduling study performed by Sun and Hickman [12]; the maximum number of iterations in the simple GA was 100; the crossover rate was 0.8; the variation rate was 0.1; and the maximum number of iterations in the joint optimization was 100. Here, the crossover and variation rates of the two subpopulations are consistent with those in the simple GA.


### 5.1. Smooth Passenger-Flow Case Design and Analysis

Smooth passenger flow mainly occurs during daytime, and the passenger flow concentrated between morning and evening peaks. During this period, the passenger flow is roughly as shown in Figure10, which depicts a flat state, and the passenger arrival rate per unit time remains constant.Figure 10
Passenger arrival rate in the case of smooth flow.The experiment is carried out under this kind of passenger flow, and the planned time ranges from 10 AM to 1 PM. The experiment is conducted for three types of gentle passenger-flow conditions: high, medium, and low. After sufficient analysis of the actual passenger-flow data, the corresponding passenger arrival rate of each period is set, as shown in Table2. The curve of the passenger-flow arrival rate in this period can be obtained from Table 2, as shown in Figure 11.Table 2
Corresponding passenger arrival rate of each time period under smooth passenger flow.
Passenger-flow intensityTime10:0010:3011:0011:3012:0012:3013:00High1.111.021.201.181.181.151.12Medium0.760.780.810.780.840.820.79Low0.500.530.540.550.510.490.51Figure 11
Smooth passenger arrival rate.The parameters of the GA are as follows: the crossover rate is 0.8, the mutation rate is 0.1, and the number of individuals per generation is 30. A single-solution 800-generation graph of the multiline departure time and speed scheduling model, using the GA under the low-intensity passenger-flow model, is shown in Figure12. The solution results are observed to gradually converge within approximately 105 generations, and there is no significant improvement in the evolution performance after that. The evolution performance of the model is improved significantly considering the optimization performance and the solution time, and the termination condition of the algorithm is set as the maximum convergence algebra of iteration termination reaches 100.Figure 12
Evolutionary iteration diagram of GA.The results of typical experiments under the three intensity types of the smooth passenger flow case are shown in Tables3, 4, and 5. The experiment is divided into three sections. The data of the fixed speed group represents the results of using the GA to evolve the departure interval under the condition of fixed speed. The data of the GA group are the results of using GA to evolve multiline departure time and speed scheduling, and the data of the coevolution group are the results of using the CEA to evolve departure time and speed scheduling. The rate of the GA group represents the improvement rate of the waiting time when compared to the fixed speed group, and the improvement rate of the CEA when compared to the GA group.Table 3
Experimental results of high intensity of smooth passenger flow.
Target value-passengers waiting time (min)Fixed speedGACEA14078163293112522622416799299713236970341278828107523506343868942612622365305417948293368256303640463129468224591374213042873622412558409686330073234296942188332441224557010412800315976256620Average value411254.9301723.4244078.2Promotion rate—26.63%%19.10%%Table 4
Experimental results of medium intensity of smooth passenger flow.
Target value-passenger waiting time (min)Fixed speedGACEA11777601303971072062180,617108,388100,9963174,444125,02798,4034174,040124,354103,8885186,236123,67299,2906170,812124,710112,4037187,451134,979113,5298173,692130,351101,1619184,302123,42293,46610168,757124,60599,938Average value177,811.1124,990.5103,028Promotion rate—29.70%%17.50%%Table 5
Experimental results of low intensity of smooth passenger flow.
Target value-passenger waiting time (min)Fixed speedGACEA15745742986368742604873986437021361060385013885646130039176368915592133545635144660794396413739876062243900353648585644157433951960583381253382910591784126937076Average value59925.840049.236240.4Promotion rate—25.98%%18.29%%The promotion rate in the last row of Table3, 4, and 5 is the promotion after considering the average value of 10 groups of data for comparison to avoid the probability of intelligent algorithm solution. It may be observed from the comparison that combination of the scheduling departure time and speed presents better results than when scheduling departure time alone. The total waiting time of passengers can be reduced by approximately 20%–30%, and the optimization effect is more significant.By analyzing the optimization results of the GA and CEA groups, it may be observed that the results obtained by the intelligent algorithm are volatile. However, the optimal solution obtained by the CEA was better than that of the GA under various intensities of smooth passenger flow. When compared to the average value, the optimization performance of the CEA was improved by approximately 15%–20% in the case of smooth passenger flow.


### 5.2. Increasing Passenger-Flow Case Design and Analysis

Increasing passenger flow distributions mainly occur during the first half of the morning peak, when passengers are commuting to work, and the first half of the evening peak, when passengers are returning home. An approximation of the passenger flow in this case is shown in Figure13, where the passenger arrival rate at the station increases with time.Figure 13
Increasing passenger arrival rate.The first half of the morning peak (from 7 AM to 9 AM) is selected for the experiment of increasing passenger flow, and three passenger flow models of high, medium, and low intensities are designed for the experiment. The specific details of these models are shown in Table6. The arrival rate curve of the increasing passengers flow is shown in Figure 14.Table 6
Corresponding passenger arrival rate of each time period under increasing passenger flow.
Passenger flow intensityTime7:007:207:408:008:208:409:00High1.021.141.231.351.431.501.56Medium0.750.810.890.981.061.101.15Low0.470.530.590.630.690.750.81Figure 14
Increasing passenger arrival rate.Similarly, to verify the effect of single dispatching departure time, simultaneous dispatching departure time and vehicle speed under the increasing passenger flow, as well as the solution performance of the CEA, several groups of experiments are performed and analyzed according to the passenger flow curve in Figure 14, and the experimental results are shown in Tables 7, 8, 9.Table 7
Experimental results of high intensity of increasing passenger flow.
Target value-passenger waiting time (min)Fixed speedGACEA16194034574483374332621726434936319820359833841333836389346048114229333511165622212402986314802660189945799833748775950974393723220758612457428577320092964136544219835054610627986459302351753Average value614529.4435908.8336901.7Promotion rate—29.07%%22.71%%Table 8
Experimental results of medium intensity of increasing passenger flow.
Target value-passenger waiting time (min)Fixed speedGACEA13454132451161747542343683243755207487334616323707817333643598882583631817765329022245019190673634546223723717353173423162507111927078342426238049190411935372923558917769310360498248547180253Average value346860243946.4184262.1Promotion rate—29.67%%24.46%%Table 9
Experimental results of low intensity of increasing passenger flow.
Target value of passenger waiting time (min)Fixed speedGACEA1135615103686706092135510981257288931387791067807955241371319343583193514218395030686306136735950306706171375549533879632813824810000882094914193798200702111014582610104675338Average value138951.898778.674920.9Promotion rate—28.91%%24.15%%By analyzing the results in Tables7, 8, and 9, between the fixed speed group and the GA group, the total passenger waiting time can be reduced by approximately 30% and the optimization effect is more significant compared with the experimental results under smooth passenger flow. Based on the analysis of the optimization results of the GA and CEA groups, the promotion rate of the CEA under the increasing passenger flow model also exhibited a better optimization performance than that of the GA, and the total waiting time of the passengers was be reduced by approximately 20%–25%.These results show that the strategy of scheduling departure time and vehicle speed simultaneously is more effective in solving the bus scheduling under conditions of increasing passenger flow distribution.


### 5.3. Decreasing Passenger-Flow Case Design and Analysis

Decreasing passenger-flow distributions mainly occur during the second halves of the morning and evening peak periods, when the passenger flow is roughly as shown in Figure15, and the passenger arrival rate at the waiting stations decreases with time.Figure 15
Decreasing passenger arrival rate.The second half of the simulated evening peak (6 PM to 8 PM) is selected for the experiment on the decreasing passenger flow, and the passenger flow of high, medium, and low intensities are also designed for the experiment. The specific experimental details of the descending-type passenger flow are shown in Table10. The arrival rate curve of increasing passengers flow is shown in Figure 16. The experimental details of the decreasing passenger flow are shown in Tables 11, 12, and 13.Table 10
Corresponding passenger arrival rate of each time period under decreasing passenger flow.
Passenger flow intensityTime18:0018:2018:4019:0019:2019:4020:00High1.321.251.191.101.051.020.99Medium0.950.900.870.830.790.750.69Low0.640.600.580.530.450.470.44Figure 16
Decreasing passenger arrival rate.Table 11
Experimental results of high intensity of decreasing passenger flow.
Target value-passengers waiting time (min)Fixed speedGACEA1384838258389232515238526726727622081133868652535592032514379500271737223164539732126667720963863931002833062339437380272824282380118360,147283881219424936944926407621807310370599256232234111Average value380721.3268756.1223294.1Promotion rate—29.41%%17.29%%Table 12
Experimental results of medium intensity of decreasing passenger flow.
Target value-passenger waiting time (min)Fixed speedGACEA15287739418318202513764180430618353501392583355145403340272378925545493890735229654696383363222675386038165303218525713834729951953876381462918510524783815432763Average value53381.739080.732355.6Promotion rate—26.79%%17.21%%Table 13
Experimental results of low intensity of decreasing passenger flow.
Target value-passenger waiting time (min)Fixed speedGACEA1183279121557887522187986119809109355317654411680310092641833671166369901051845481200441049576182440120053840537183701122068101596818255911952010449691831071246271003241018058312850798304Average value182811.4120962.499177.3Promotion rate—33.83%%18.01%%By analyzing the experimental data in Tables11, 12, and 13, the experimental results of the descending passenger flow distribution were found to be consistent with the experimental results of the smooth and increasing passenger-flow distribution. The total waiting time of passengers was reduced by approximately 25%–35%, and the overall optimization effect is relatively significant. The optimization effect of low intensity passenger flow was particularly significant.Based on the analysis of the optimization results of the GA and CEA groups, the promotion rate of the CEA under decreasing passenger flow has also exhibited a better optimization performance than that of the GA. Furthermore, the total waiting time of passengers can be reduced by approximately 15%–20%, which is roughly consistent with the optimization effect under smooth passenger flow.


### 5.4. Multisegment Convex Passenger-Flow Case Design and Analysis

The schematic of multisegment convex passenger flow is shown in Figure17. The passenger flow is generally distributed in the morning and evening travel peaks or when a large-scale event or celebration is held at a certain location, resulting in a surge of passengers for a period. The multisegment convex passenger flow designed in this study is an ideal model, which is a combination of the previous three types of passenger flow. The case simulates the passenger-flow curve between 7:00 AM and 10:00 AM, and the specific passenger flow data are shown in Table 14. According to the data in Table 14, several groups of experiments were conducted, and the experimental results are shown in Table 15.Figure 17
Multisegment convex passenger arrival rate.Table 14
Multisegment convex passenger-flow data table.
Time7:007:207:408:008:20Arrival rate0.420.420.550.550.74Time8:409:009:209:4010:00Arrival rate0.740.60.60.480.48Table 15
Experimental results of multisegment convex passenger flow.
Target value-passengers waiting time (mins)Fixed speedGACEA12350811617431310972227444158880135318323599815259812354842354591569321113865227460152687125302622839715817810699572359241533011299098223026164859124952922790016614412645810220927176650128033Average value229761.6160197.2124299.8Promotion rate—30.27%%22.41%%Similarly, as shown in Table15, the total waiting time of passengers was reduced by approximately 30%. Hence, we conclude that combining scheduling departure time and vehicle speed forms a better bus scheduling strategy, which can reduce the waiting time of passengers by approximately 30% compared with scheduling departure time alone.By analyzing the optimization results of the GA and CEA groups, the promotion rate in Table15 of the CEA under the passenger-flow models demonstrated a better optimization performance than that of the GA, and the total waiting time of passengers was reduced by approximately 20%.Several experiments have verified that the strategy of scheduling the departure time and speed simultaneously is suitable for bus scheduling. Moreover, the CEA demonstrated a suitable good optimization effect in a variety of different passenger flow models. Compared with GA, the optimization performance of each passenger flow model can be improved by at least 10%, up to a maximum of 25%.


## 5.1. Smooth Passenger-Flow Case Design and Analysis

Smooth passenger flow mainly occurs during daytime, and the passenger flow concentrated between morning and evening peaks. During this period, the passenger flow is roughly as shown in Figure10, which depicts a flat state, and the passenger arrival rate per unit time remains constant.Figure 10
Passenger arrival rate in the case of smooth flow.The experiment is carried out under this kind of passenger flow, and the planned time ranges from 10 AM to 1 PM. The experiment is conducted for three types of gentle passenger-flow conditions: high, medium, and low. After sufficient analysis of the actual passenger-flow data, the corresponding passenger arrival rate of each period is set, as shown in Table2. The curve of the passenger-flow arrival rate in this period can be obtained from Table 2, as shown in Figure 11.Table 2
Corresponding passenger arrival rate of each time period under smooth passenger flow.
Passenger-flow intensityTime10:0010:3011:0011:3012:0012:3013:00High1.111.021.201.181.181.151.12Medium0.760.780.810.780.840.820.79Low0.500.530.540.550.510.490.51Figure 11
Smooth passenger arrival rate.The parameters of the GA are as follows: the crossover rate is 0.8, the mutation rate is 0.1, and the number of individuals per generation is 30. A single-solution 800-generation graph of the multiline departure time and speed scheduling model, using the GA under the low-intensity passenger-flow model, is shown in Figure12. The solution results are observed to gradually converge within approximately 105 generations, and there is no significant improvement in the evolution performance after that. The evolution performance of the model is improved significantly considering the optimization performance and the solution time, and the termination condition of the algorithm is set as the maximum convergence algebra of iteration termination reaches 100.Figure 12
Evolutionary iteration diagram of GA.The results of typical experiments under the three intensity types of the smooth passenger flow case are shown in Tables3, 4, and 5. The experiment is divided into three sections. The data of the fixed speed group represents the results of using the GA to evolve the departure interval under the condition of fixed speed. The data of the GA group are the results of using GA to evolve multiline departure time and speed scheduling, and the data of the coevolution group are the results of using the CEA to evolve departure time and speed scheduling. The rate of the GA group represents the improvement rate of the waiting time when compared to the fixed speed group, and the improvement rate of the CEA when compared to the GA group.Table 3
Experimental results of high intensity of smooth passenger flow.
Target value-passengers waiting time (min)Fixed speedGACEA14078163293112522622416799299713236970341278828107523506343868942612622365305417948293368256303640463129468224591374213042873622412558409686330073234296942188332441224557010412800315976256620Average value411254.9301723.4244078.2Promotion rate—26.63%%19.10%%Table 4
Experimental results of medium intensity of smooth passenger flow.
Target value-passenger waiting time (min)Fixed speedGACEA11777601303971072062180,617108,388100,9963174,444125,02798,4034174,040124,354103,8885186,236123,67299,2906170,812124,710112,4037187,451134,979113,5298173,692130,351101,1619184,302123,42293,46610168,757124,60599,938Average value177,811.1124,990.5103,028Promotion rate—29.70%%17.50%%Table 5
Experimental results of low intensity of smooth passenger flow.
Target value-passenger waiting time (min)Fixed speedGACEA15745742986368742604873986437021361060385013885646130039176368915592133545635144660794396413739876062243900353648585644157433951960583381253382910591784126937076Average value59925.840049.236240.4Promotion rate—25.98%%18.29%%The promotion rate in the last row of Table3, 4, and 5 is the promotion after considering the average value of 10 groups of data for comparison to avoid the probability of intelligent algorithm solution. It may be observed from the comparison that combination of the scheduling departure time and speed presents better results than when scheduling departure time alone. The total waiting time of passengers can be reduced by approximately 20%–30%, and the optimization effect is more significant.By analyzing the optimization results of the GA and CEA groups, it may be observed that the results obtained by the intelligent algorithm are volatile. However, the optimal solution obtained by the CEA was better than that of the GA under various intensities of smooth passenger flow. When compared to the average value, the optimization performance of the CEA was improved by approximately 15%–20% in the case of smooth passenger flow.


## 5.2. Increasing Passenger-Flow Case Design and Analysis

Increasing passenger flow distributions mainly occur during the first half of the morning peak, when passengers are commuting to work, and the first half of the evening peak, when passengers are returning home. An approximation of the passenger flow in this case is shown in Figure13, where the passenger arrival rate at the station increases with time.Figure 13
Increasing passenger arrival rate.The first half of the morning peak (from 7 AM to 9 AM) is selected for the experiment of increasing passenger flow, and three passenger flow models of high, medium, and low intensities are designed for the experiment. The specific details of these models are shown in Table6. The arrival rate curve of the increasing passengers flow is shown in Figure 14.Table 6
Corresponding passenger arrival rate of each time period under increasing passenger flow.
Passenger flow intensityTime7:007:207:408:008:208:409:00High1.021.141.231.351.431.501.56Medium0.750.810.890.981.061.101.15Low0.470.530.590.630.690.750.81Figure 14
Increasing passenger arrival rate.Similarly, to verify the effect of single dispatching departure time, simultaneous dispatching departure time and vehicle speed under the increasing passenger flow, as well as the solution performance of the CEA, several groups of experiments are performed and analyzed according to the passenger flow curve in Figure 14, and the experimental results are shown in Tables 7, 8, 9.Table 7
Experimental results of high intensity of increasing passenger flow.
Target value-passenger waiting time (min)Fixed speedGACEA16194034574483374332621726434936319820359833841333836389346048114229333511165622212402986314802660189945799833748775950974393723220758612457428577320092964136544219835054610627986459302351753Average value614529.4435908.8336901.7Promotion rate—29.07%%22.71%%Table 8
Experimental results of medium intensity of increasing passenger flow.
Target value-passenger waiting time (min)Fixed speedGACEA13454132451161747542343683243755207487334616323707817333643598882583631817765329022245019190673634546223723717353173423162507111927078342426238049190411935372923558917769310360498248547180253Average value346860243946.4184262.1Promotion rate—29.67%%24.46%%Table 9
Experimental results of low intensity of increasing passenger flow.
Target value of passenger waiting time (min)Fixed speedGACEA1135615103686706092135510981257288931387791067807955241371319343583193514218395030686306136735950306706171375549533879632813824810000882094914193798200702111014582610104675338Average value138951.898778.674920.9Promotion rate—28.91%%24.15%%By analyzing the results in Tables7, 8, and 9, between the fixed speed group and the GA group, the total passenger waiting time can be reduced by approximately 30% and the optimization effect is more significant compared with the experimental results under smooth passenger flow. Based on the analysis of the optimization results of the GA and CEA groups, the promotion rate of the CEA under the increasing passenger flow model also exhibited a better optimization performance than that of the GA, and the total waiting time of the passengers was be reduced by approximately 20%–25%.These results show that the strategy of scheduling departure time and vehicle speed simultaneously is more effective in solving the bus scheduling under conditions of increasing passenger flow distribution.


## 5.3. Decreasing Passenger-Flow Case Design and Analysis

Decreasing passenger-flow distributions mainly occur during the second halves of the morning and evening peak periods, when the passenger flow is roughly as shown in Figure15, and the passenger arrival rate at the waiting stations decreases with time.Figure 15
Decreasing passenger arrival rate.The second half of the simulated evening peak (6 PM to 8 PM) is selected for the experiment on the decreasing passenger flow, and the passenger flow of high, medium, and low intensities are also designed for the experiment. The specific experimental details of the descending-type passenger flow are shown in Table10. The arrival rate curve of increasing passengers flow is shown in Figure 16. The experimental details of the decreasing passenger flow are shown in Tables 11, 12, and 13.Table 10
Corresponding passenger arrival rate of each time period under decreasing passenger flow.
Passenger flow intensityTime18:0018:2018:4019:0019:2019:4020:00High1.321.251.191.101.051.020.99Medium0.950.900.870.830.790.750.69Low0.640.600.580.530.450.470.44Figure 16
Decreasing passenger arrival rate.Table 11
Experimental results of high intensity of decreasing passenger flow.
Target value-passengers waiting time (min)Fixed speedGACEA1384838258389232515238526726727622081133868652535592032514379500271737223164539732126667720963863931002833062339437380272824282380118360,147283881219424936944926407621807310370599256232234111Average value380721.3268756.1223294.1Promotion rate—29.41%%17.29%%Table 12
Experimental results of medium intensity of decreasing passenger flow.
Target value-passenger waiting time (min)Fixed speedGACEA15287739418318202513764180430618353501392583355145403340272378925545493890735229654696383363222675386038165303218525713834729951953876381462918510524783815432763Average value53381.739080.732355.6Promotion rate—26.79%%17.21%%Table 13
Experimental results of low intensity of decreasing passenger flow.
Target value-passenger waiting time (min)Fixed speedGACEA1183279121557887522187986119809109355317654411680310092641833671166369901051845481200441049576182440120053840537183701122068101596818255911952010449691831071246271003241018058312850798304Average value182811.4120962.499177.3Promotion rate—33.83%%18.01%%By analyzing the experimental data in Tables11, 12, and 13, the experimental results of the descending passenger flow distribution were found to be consistent with the experimental results of the smooth and increasing passenger-flow distribution. The total waiting time of passengers was reduced by approximately 25%–35%, and the overall optimization effect is relatively significant. The optimization effect of low intensity passenger flow was particularly significant.Based on the analysis of the optimization results of the GA and CEA groups, the promotion rate of the CEA under decreasing passenger flow has also exhibited a better optimization performance than that of the GA. Furthermore, the total waiting time of passengers can be reduced by approximately 15%–20%, which is roughly consistent with the optimization effect under smooth passenger flow.


## 5.4. Multisegment Convex Passenger-Flow Case Design and Analysis

The schematic of multisegment convex passenger flow is shown in Figure17. The passenger flow is generally distributed in the morning and evening travel peaks or when a large-scale event or celebration is held at a certain location, resulting in a surge of passengers for a period. The multisegment convex passenger flow designed in this study is an ideal model, which is a combination of the previous three types of passenger flow. The case simulates the passenger-flow curve between 7:00 AM and 10:00 AM, and the specific passenger flow data are shown in Table 14. According to the data in Table 14, several groups of experiments were conducted, and the experimental results are shown in Table 15.Figure 17
Multisegment convex passenger arrival rate.Table 14
Multisegment convex passenger-flow data table.
Time7:007:207:408:008:20Arrival rate0.420.420.550.550.74Time8:409:009:209:4010:00Arrival rate0.740.60.60.480.48Table 15
Experimental results of multisegment convex passenger flow.
Target value-passengers waiting time (mins)Fixed speedGACEA12350811617431310972227444158880135318323599815259812354842354591569321113865227460152687125302622839715817810699572359241533011299098223026164859124952922790016614412645810220927176650128033Average value229761.6160197.2124299.8Promotion rate—30.27%%22.41%%Similarly, as shown in Table15, the total waiting time of passengers was reduced by approximately 30%. Hence, we conclude that combining scheduling departure time and vehicle speed forms a better bus scheduling strategy, which can reduce the waiting time of passengers by approximately 30% compared with scheduling departure time alone.By analyzing the optimization results of the GA and CEA groups, the promotion rate in Table15 of the CEA under the passenger-flow models demonstrated a better optimization performance than that of the GA, and the total waiting time of passengers was reduced by approximately 20%.Several experiments have verified that the strategy of scheduling the departure time and speed simultaneously is suitable for bus scheduling. Moreover, the CEA demonstrated a suitable good optimization effect in a variety of different passenger flow models. Compared with GA, the optimization performance of each passenger flow model can be improved by at least 10%, up to a maximum of 25%.


## 6. Conclusion

In this study, a joint decision model has been constructed to simultaneously determine the departure time of vehicles on multiple bus lines and their driving speeds between stations, while considering the waiting times of passengers changing between lines. A suitable GA was developed for the optimize solution optimization; moreover, considering the characteristics of the two decision variables in the model, a CEA was developed to build departure time and speed scheduling populations according to the decision variables, in which each population is independent of the other and adopts different evolutionary algorithms for solution optimization. Numerous experiments were conducted to prove the feasibility and efficiency of the algorithms. The CEA provided superior solutions by scheduling both speed and departure time under different passenger-flow situations rather than by scheduling only departure time, reducing the total waiting time of passengers compared to that achievable using the GA.However, some factors were not accounted for in the study, such as the actual weather or sudden accidents, which will also affect road conditions and vehicle speed. In the future, we will consider adding conditions, such as weather and different sizes vehicle, to expand the applicability of the model. The present work mainly focuses on scheduling strategy for existing vehicles running on established lines. Some advanced methods have not been considered. Second-order sliding mode control (SOSM) design optimization methods are usually used in some vehicle power systems applications, such as eliminating state errors due to different vehicle parameters, achieving control performance and energy effects, and realizing the optimal control of the braking process [62–64]. We may consider vehicle system optimization and the application of SOSM control design in future research.



---

*Source: 4213837-2021-09-30.xml*