1. Introduction
In society, urban traffic problems are becoming more and more serious, which greatly reduces travel efficiency and transportation efficiency, and also causes varying degrees of economic losses. It is of great significance to do a good job in bus scheduling to improve the traffic environment, improve the travel conditions of citizens, and improve the economic and social benefits of bus companies. Bus schedule is the core of the basic work, he is according to the change in passenger flow and specific operating conditions and other conditions, the arrangement of different vehicle organization schemes [1].
Public transport is a necessary system to support the basic operation of a city and a necessary means to solve traffic problems [1]. Public transport is a necessary system to support the basic operation of a city. Public transport is the main force of urban passenger transport and the corresponding measure of sustainable development. At present, in the actual operation process of public transportation, there are often some problems to be optimized. For example, a series of problems such as a high empty load rate during low peak hours, unreasonable line design, and unstable departure time will lead to the rise of operating costs to a certain extent. At the same time, it is necessary that the needs of passengers should also be taken into account. For example, the peak hour load rate is too high, the passenger waiting time is too long, and the transfer rate is high. These problems will affect the satisfaction rate of passengers with public transport to a certain extent, thus reducing the attractiveness of public transport [2].
This paper aims to summarize the application status of some main algorithms in the process of bus scheduling optimization. First of all, the existing bus scheduling problems are summarized and the concept that the model can only be very close to reality and cannot be completely regarded as the actual situation is given. Then the common algorithms to solve the bus scheduling problem: genetic algorithm and other intelligent algorithms are introduced and analyzed, and then the research status is summarized, the limitations of the research are found, and finally further research prospects are discussed.
2. Description of scheduling problem
Bus scheduling is a multi-objective optimization problem that requires comprehensive consideration of operating costs and passenger satisfaction. It is susceptible to complex external factors and has randomness. In the process of building the model and solving the algorithm, it is impossible to take all the factors into account, and some prerequisites must be made to rationalize the constraints in order to achieve a stable simulation environment [3]. Assumptions are as follows:
The impact of external factors such as bad weather, car operation failure and traffic jam on bus operations is not considered.
Ignore the uncontrollable time of passengers getting on and off and getting on and off once.
Bus drivers strictly observe the departure time and arrive at each station on time.
The bus travels at a constant speed and is not affected by stimuli such as bus acceleration, deceleration, or even congestion.
Without considering other intangible factors that affect passenger satisfaction, only waiting time is used to measure bus service satisfaction.
It is assumed that the passenger flow within the departure time follows a certain mathematical distribution law.
The existing data can fully reflect the relationship between passenger travel time and bus operating costs.
Uniform bus model, the same passenger capacity, and uniform ticket price.
Buses will be provided for dispatch.
The unit time spent by the passenger and the unit operating cost of the bus is fixed.
3. Methods
The use of intelligent optimization algorithms to solve the bus scheduling problem has been widely concerned by scholars at home and abroad, and most of the applications are genetic algorithms. Therefore, this section will analyze the genetic algorithm and other intelligent algorithms from two aspects.
3.1. Genetic Algorithm (GA)
The genetic algorithm is a highly parallel random search algorithm proposed by J.Holland. It uses the replication and cross-mutation ability of simulated chromosomes to continuously generate new space, and continuously uses constraints to screen until it finds the optimal value that meets the most conditions. [4] Genetic algorithm has a simple structure and good global search ability, so it is widely used in scheduling problems. Strong information parallel processing ability, large randomness, strong scalability, and other advantages. The general steps are as follows:
Set the initial population (solution space), including all possible solution cases.
Design the fitness function and evaluate whether the scheme is reasonable.
Select and continuously screen unqualified schemes.
Mutation operators are designed to generate new solutions.
Generate a new population.
Check whether the condition is met. If so, continue; Otherwise, it returns to step 2 for iteration.
Output optimization results.
Some in the literature are directly solved using traditional genetic algorithms, and some are mixed with genetic algorithms and other algorithms. The specific description is as follows.
3.1.1 Traditional genetic algorithm. The traditional genetic algorithm is the basic algorithm to optimize the bus scheduling mechanism. Tan Hua [5] used the algorithm to start from the operation peak and peak time, and at the same time, the load factor was greater than or equal to 60% as the constraint condition and established an optimization model that was easy to solve. The calculation is performed using the basic solution steps mentioned above. In particular, real coding is used here, and operator selection roulette selection operator, arithmetic crossover operator, and uniform mutation operator are the mainstream operators. A bus line in Nanning city is taken as the optimization practice target. First of all, the changes in the daily average ridership, frequency, number of stops, departure time, ticket price, and opening and closing time of the line are clarified. The running time is then divided into flat peak time and peak time. Finally, the main parameters of the algorithm are determined: crossover probability, mutation probability, the maximum number of iterations and weighting coefficient. The model is useful for real-time bus scheduling.
Tao Ye [6] improved the traditional genetic algorithm and established the objective function of average cost and loss, and the rest were the same. Here, credit enhancement is added to the screening mechanism, adaptive changes are made in the screening stage, the mechanism is relaxed in the early stage of screening, and the mechanism is strict in the late stage of screening. Different screening mechanisms bring the final calculation closer to the optimal value. This paper takes a bus dispatching in Lhasa as an example. It can be seen from the application results that the improved algorithm saves 10% of the operating cost of the company and improves passenger satisfaction by 10%. It can be seen that its reference significance.
3.1.2 Single-parent Genetic Algorithm. Single-parent GA is a simplification of GA: the crossover operator is eliminated, the diversity of the initial population is not required, and the computational efficiency is greatly improved [7]. Yao Chun and Li Maojun [8] briefly described the steps of the single-parent genetic algorithm, which is different from the sixth step above and changed to reinsertion: selecting a certain proportion of new individuals to replace the new individuals with the lowest fitness in the offspring. Lidu compares the single-parent genetic algorithm with the traditional genetic algorithm through simulation and finds that the convergence speed and optimal value of the single-parent genetic algorithm are obviously affected by the traditional algorithm. But simulations are not meant to show that this is also the case, after all, we listed some utopian environments, which may be the reason why single-parent genetic algorithms are rarely used to optimize bus scheduling problems.
3.1.3 Tabu Search Genetic Algorithm. The tabu search algorithm proposed by Glover et al. has a strong local search capability, which can make up for the shortcomings of GA and greatly improve the ability to obtain the optimal solution [4]. Different from the traditional GA, the proposed algorithm needs to set the tabu length and construct the search neighborhood to avoid the dilemma of local optimum. The optimal solution is selected as the tabu object each time, and the tabu is broken when the fitness of the tabu object is less than the recorded fitness. Yang Min et al. [9] used this algorithm to solve the scheduling optimization problem of the hybrid electric bus fleet. The goal is to reduce operating costs and protect the environment. During the analysis, it was found that its accuracy improved by 12% compared to GA.
3.1.4 non-dominated sorting Genetic Algorithm (NSGA) algorithm. Based on hierarchical implementation operation, the NSGA algorithm is usually used to solve Pareto frontier solutions, which have the advantages of diverse non-dominant solutions, high computational efficiency, good robustness, and good convergence of optimal solutions. The shared fitness of the algorithm is conducive to maintaining diversity and preventing premature convergence [1]. Song Xiaopeng et al. [10] used the NSGA algorithm to solve the optimization problem of the two objectives of the cost of the bus company and the cost of passengers waiting for the bus. At the same time, considering the delay problem of signal lights, it is found that there is an interaction between bus departure interval and signal control. By applying the algorithm to five representative bus lines in Jiaozuo City, Henan Province, the optimization of the bus load rate and signal light control problem is successfully solved.
3.1.5 parallel mutation differential evolution algorithm (PMDE). The parallel mutation differential evolution algorithm divides the population into two populations of the same size according to the fitness value of the individuals and assigns them different mutation strategies respectively. During the algorithm operation, the two strategies are executed in parallel, and at the same time, the excellent individuals in the excellent population participate in the individual mutation of the poor population, so as to accelerate the convergence, and the overall performance is significantly better than that of the comparison algorithm. Ding Xianyong and Li Yuzhen [11] studied the algorithm from the perspective of passengers' ride loss. Then, the effectiveness of PMDE is demonstrated, and the optimal solution is obtained by dividing the operating time into 15 periods in hours, setting the maximum and minimum departure intervals, etc.
3.2. Differential bacterial foraging algorithm
Differential bacterial foraging is an algorithmic model that simulates bacterial reproduction. His update is by inversion and swimming, requiring the variable: chemotactic step length. Some individuals also need to migrate randomly, so the number and probability of migration need to be calculated. Liu Qin [12] optimized the scheduling of 10 stations and determined the cost of vehicles per kilometer, the time consumption of passengers per minute and other conditions. Then, by modifying the position of the traditional calculation, the corresponding passenger flow of each station at each time can be calculated, which shows the effectiveness and rationality of the algorithm.
3.3. Dual particle swarm optimization algorithm
Particle Swarm Optimization is an algorithm developed by Kennedy and Eberhart to model the predation behavior of flocks of birds. The idea is that the instances individually search for the optimal solution in the current space and then iterate, updating the optimal solution found by themselves and the optimal solution found by the group during the iteration [13]. These two factors will affect the accuracy and convergence speed of the algorithm. By introducing a generalized central particle and narrow central ion, it is a double-center PSO algorithm, which improves the sum precision of the convergence element. Zhu et al. [14] improved the algorithm, which no longer standardized the movement route of particles, and improved the search range and global extremum. The optimization algorithm is used to better solve the problem of vehicle operation limitation of electric buses under load limitation.
4. Limitations and prospects
At present, most of the models of bus scheduling optimization problems are similar, and they all take the minimum operating cost and the maximum passenger satisfaction as the objective equation. But most of the algorithms used by these algorithms evolved from biological algorithms. The limiting conditions are determined by dividing the population, and the suitable population is constantly searched, and the optimal solution is finally iterated. Scholars constantly update existing algorithms and improve convergence speed and screening conditions to make the results closer to the optimal solution [2].
But with the development of the scientific and technological network, is not enough to improve the algorithm theory. The gap between the model and reality is risky just to improve the accuracy of the algorithm. Therefore, we should find a solution to the real-time scheduling problem while studying to improve the accuracy of the algorithm. Using real-time data instead of preset or survey data, through the transmission of real-time data, timely solve the distribution and scheduling problem, which can greatly alleviate the traffic problem [15]. This method is more flexible and reduces error to a certain extent, so it is more practical. It is not possible at all times to fully take into account the circumstances encountered by each region, or even by each bus line. However, it also has certain disadvantages, such as signal stability, data transmission, computing power, and so on.
In the future, there will inevitably be more modes of bus schedules, such as dynamic scheduling, online scheduling and real-time scheduling, and at the same time, the optimization objectives will inevitably increase. In addition, with the development of The Times, personalized demand has become more and more complex, which makes the actual transportation environment such as actual operating conditions and passenger demand more and more complex [9]. Traditional oil-burning vehicles are constantly being updated, and the emerging oil-electric integration and even pure tram scheduling problems are also under development. The conflict between the charging problem and scheduling, and how to solve the emergency situation in the transportation process is a very real problem. This is all the more proof of the need for real-time problem-solving. Therefore, more complex factors should be taken into account in the design process of the model, which has strong practical significance for practical application.
5. Conclusion
For the bus scheduling problem, the goal of optimization is to minimize the operating cost of the bus company and maximize the satisfaction of passengers. According to the research of scholars, it is obtained that bus operation and scheduling usually adopt the establishment of a single-objective or multi-objective linear programming optimization model, then select the appropriate algorithm for continuous iterative optimization, and finally obtain the relatively optimized solution. In this process, it is necessary to strictly screen decision variables and various indicators of bus operators to ensure the practical significance of the model. This paper summarizes and analyzes the application of algorithms for bus scheduling problems, and compares the differences between different algorithms in bus scheduling problems. Different algorithms can be applied separately or they can be implemented but the models are similar, they just use different algorithms to converge. At the same time, the algorithm is constantly improved to improve its accuracy of the algorithm.