Solving Multi-objective School Bus Routing Problem Using An Improved NSGA-II Algorithm

This paper deals with multi-objective school bus routing problem, which includes route balance, total number of school buses and total travel distance optimization objectives. An improved non-dominated sorting genetic algorithm (NSGA-II) is proposed to solve this problem. First, the definition of measurement indicator that denotes the degree of route balance is given based on the analysis of the solved problem. And then, the multi-objective optimization function is provided. In the proposed algorithm, the individuals are obtained by using the tournament selection, sequential crossover and inverse mutation. The 2-opt neighborhood operator is adopted to improve the best individuals obtained in each iteration. At the same time, the route selection rule based on the degree of route balance is applied to select the final optimal solution set. The solution with better balance degree will be taken as the best solution. Finally, some benchmark instances are used to test the effectiveness of proposed algorithm. The results reveal that the proposed algorithm outperforms the standard NSGA-II and Multi-objective Evolutionary Algorithm(MOEA). The experimental results also show that our algorithm has good stability.