A genetic algorithm with trip-adjustment strategy for multi-depot electric bus scheduling problems

Bus scheduling problem is vital to ensure service quality and save operational cost. Electric bus scheduling problem is difficult to solve because of vehicles' limited driving range and charging requirements. This article investigates the multi-depot electric bus scheduling problem (MD-EBSP). A genetic algorithm with trip-adjustment strategy (GA-TAS) is proposed for the MD-EBSP. Firstly, a genetic algorithm (GA) with three crossover operators and seven mutation operators is devised to find a set of solutions. In each generation, a randomly selected crossover (mutation) operator is used to update the individuals. The solutions found by the GA are further improved by a trip-adjustment strategy (TAS) to obtain the final solution. The GA-TAS is compared with an adaptive large neighbourhood search method, a heuristic procedure, and experience-based scheduling schemes on seven problem instances. Experiments show that the GA-TAS outperforms comparative approaches on a number of vehicle and balancing vehicle driving tasks.