Memetic algorithm based electric bus scheduling approach

• 1、School of Cyberspace Security, Beijing University of Posts and Telecommunications, Beijing 100876
• 2、School of Computing, Beijing University of Posts and Telecommunications, Beijing 100876

Abstract：Electric buses are widely adopted by public transportation companies because of their low noise, stable driving, and zero emissions.Aiming at electric bus scheduling problem, this paper proposes a cultural genetic algorithm based vehicle scheduling approach. First, initial individual generation algorithms are devised to construct the initial population, to maintain the population diversity and ensure the quality of initial individuals. Then, a crossover operation for the bus scheduling problem is designed to perform global search. Furthermore, three kinds of neighborhood search operators are improved, and combiMemetic algorMemetic algorithm based electric bus scheduling approachithm based electric bus scheduling approachned with the existing neighborhood search operators to perform local search. An evaluation function based on vehicle blocks is devised to guide the neighborhood search operators to search. In order to balance the search efficiency and solution quality, a method combining three different insertion operations is constructed for neighborhood search. The approach is applied to three actual bus lines in Qingdao city. Experimental results show that compared with the manual scheduling scheme, the approach can reduce 1-7 vehicles and increase the average vehicle utilization rate of 6.2%-14.4%. The approach has high computational efficiency, and its running time is less than 15 seconds. Key words bus scheduling; electric bus scheduling; memetic algorithm; neighborhood search

Keywords： bus scheduling electric bus scheduling memetic algorithm neighborhood search