论文部分内容阅读
为中小学生提供校车服务是我国义务教育发展的必然要求。然而，规划校车路径是校车运行管理中的一个难题。合理的校车路径规划，既能减少所需校车数量，又可缩短校车运行里程，从而节省校车运营服务成本。本文尝试建立校车路径问题（School BusRouting Problem，SBRP）数学模型，设计元启发算法进行路径优化，并将优化算法集成在GIS中，为校车路径规划提供软件工具。因SBRP本质上属于车辆路径问题（VRP）范畴，本文借鉴VRP模型和算法，针对校车停车场不在学校的实际情况，选择开放VRP模型构建SBRP优化模型。模型中，以校车运行总路径长度最短为目标，以校车容量、学生最长乘车时间等为限制条件。模型优化算法流程如下：建立模型，构造初始解，在模拟退火元启发框架中利用VRP邻域交换算子优化路径，通过C++程序设计实现优化算法。为验证本算法的有效性和计算效率，利用模拟数据进行算法测试，并与ArcGIS网络分析模块中VRP工具优化结果进行比较。最后，在GIS中设计校车路径规划工具。在ArcGIS10中管理学校、停车场、学生乘车站点、交通网络等地理数据，基于Geoprocessing框架设计规划工具。利用Python程序设计实现工具参数设置、模型参数计算、模型建模、优化模块调用、优化结果可视化等功能。并用一所初级中学作为测试实例进行校车路径规划。实验结果表明：使用模拟退火元启发算法解决校车问题是可行的。从多个初始解进行优化的模拟退火算法与ArcGIS中添加禁忌算法的VRP求解算法相比，解的质量有所提高。本文算法数据结构设计简单，占用内存少，在针对校车路径规划方面表现出明显的优势；且将通过ArcGIS网络分析功能算出的OD距离矩阵作为算法输入项，提高了对实际问题的处理能力。通过工具箱输入相关参数之后，能够快速的找到近似最优的校车安排方案，并且进行了可视化的输出，使规划者对规划方案有直观认知。