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

摘要

随着我国社会经济的发展，为中小学学生提供校车服务及保障校车安全成为我国义务教育面临的新问题。科学地安排和组织校车运行不但能减少学生乘车时间，而且还会减少校车的运行成本。本文假设车场与学校的位置不一致，所有校车均从同一车场出发，最终到达学校，即将单个学校校车线路问题抽象为开放式车辆路径问题(OVRP）。设计元启发式算法框架求解：先利用改进的节约算法在全局范围内产生初始解，再利用四种局部交换策略的模拟退火算法进行改进。针对有457 名学生、160个站点、8条线路和100个随机模拟停车场的案例，测试结果表明本算法是有效的。与ArcGIS 10 VRP相比，93%的情形能够优化出总距离更短的线路方案，且计算效率有明显的提高。