元启发式算法在校车路径规划中的应用

Application of Meta-heuristic Algorithm in School Bus Routing Problem

将单个学校校车路径问题抽象为开放式车辆路径问题,基于元启发式算法框架求解校车最优路径。假设所有校车从同一停车场出发,最终到达学校,首先利用改进的节约算法在全局范围内产生初始解,再用模拟退火算法通过4种局部交换策略获得最优解。100次模拟实验结果表明,在93%的情况下,改进后的元启发式算法框架比ArcGIS 10的VRP求解的最优路径总距离短,且计算效率明显提高。

When the school bus depot is not located in the school it serviced, the school bus routing problem(SBRP) can be modeled as open vehicle routing problem(OVRP). It was assumed that all the school bus were starting from the bus depot, visiting a number of stops, and ending at the school. In order to reduce the possibility of sinking into local optima, a meta-heuristic algorithm was used to get the shortest total travel distance for SBRP. First, a set of feasible solutions were generated using modified Clark-Wright saving-algorithm.Second, the initial solution was improved by a well-designed simulated annealing algorithm with four local exchange operators. The results show that the algorithm introduced in this paper is efficient and robust,and 93% solutions are better than those generated by VRP solver of ArcGIS 10.