校车路径问题元启发算法设计与GIS集成.pdf

1、为中小学生提供校车服务是我国义务教育发展的必然要求。然而,规划校车路径是校车运行管理中的一个难题。合理的校车路径规划,既能减少所需校车数量,又可缩短校车运行里程,从而节省校车运营服务成本。本文尝试建立校车路径问题(School Bus Routing Problem,SBRP)数学模型,设计元启发算法进行路径优化,并将优化算法集成在GIS中,为校车路径规划提供软件工具。
　　因SBRP本质上属于车辆路径问题(VRP)范畴,本文借鉴

2、VRP模型和算法,针对校车停车场不在学校的实际情况,选择开放 VRP模型构建SBRP优化模型。模型中,以校车运行总路径长度最短为目标,以校车容量、学生最长乘车时间等为限制条件。模型优化算法流程如下:建立模型,构造初始解,在模拟退火元启发框架中利用 VRP邻域交换算子优化路径,通过C++程序设计实现优化算法。为验证本算法的有效性和计算效率,利用模拟数据进行算法测试,并与ArcGIS网络分析模块中VRP工具优化结果进行比较。最后,在GIS中

3、设计校车路径规划工具。在ArcGIS10中管理学校、停车场、学生乘车站点、交通网络等地理数据,基于Geoprocessing框架设计规划工具。利用Python程序设计实现工具参数设置、模型参数计算、模型建模、优化模块调用、优化结果可视化等功能。并用一所初级中学作为测试实例进行校车路径规划。
　　实验结果表明:使用模拟退火元启发算法解决校车问题是可行的。从多个初始解进行优化的模拟退火算法与ArcGIS中添加禁忌算法的VRP求解算法相