Research On Single Line Bus Scheduling Problem Based On Hybrid Heuristic Algorithm

In recent years, with the speeding up of urbanization process, urban traffic problems are becoming more and more serious. In order to alleviate the traffic pressure in the city, we need to develop intelligent transportation and improve the operating efficiency and service quality of public transportation system. Bus scheduling problem, as one of the key issues in the intelligent transportation, has significant impact on the operation level and service quality of the public transportation system.The bus scheduling problem is a complex combinatorial optimization problem. Due to the complexity of the problem, the current bus scheduling model also has some problems, and so the problems currently modeled are not very suitable for the actual situation; at the same time, current bus scheduling algorithm is relatively simple, and intelligent optimization algorithms are commonly used like genetic algorithm etc., while the study on hybrid heuristic algorithm is not so much.Based on the above, we present a combined scheduling model of Normal scheduling and Zone scheduling with separate departure frequency for upline and downline. The model can deal the problem of uneven passenger flow between different sections and in both directions, and in order to make the model more general to adapt to various passenger flow demand, we improve the model by allowing the Zone scheduling not start from the first station. At the same time, the particle swarm algorithm and the pattern search algorithm are combined as a hybrid heuristic algorithm. Particle swarm optimization algorithm has a good performance in many complex NP-hard problems, but it can be premature convergence;pattern search algorithm has a strong ability of local search. Therefore, combining them to design a hybrid heuristic algorithm is reasonable.Finally, we perform an experiment on a real public transportation data set from Bengbu. The experimental results show that both the hybrid heuristic algorithm and the mixed bus scheduling model are effective.