郝 忠 娜

( 南京交通职业技术学院 运输管理系，江苏 南京 211188)

校车路径优化模型及算法研究

郝 忠 娜

( 南京交通职业技术学院 运输管理系，江苏 南京 211188)

以校车站点选择、学生群归属站点的划分以及车辆路径安排为研究对象，重点考虑了学生在车上的最大乘车时间、学生步行到候车站点的最大步行时间等约束条件，以车辆行程时间成本、学生乘车时间成本以及学生步行时间成本最小为目标建立数学规划模型。给出了解决这类问题的改进遗传算法，该算法通过启发式产生初始种群的优良个体，并针对模型特点设计带启发知识的遗传算子，提高寻优效率。实例分析表明，该方法可行，并且有比较显著的效果，能够有效地解决大规模的校车路径优化问题。

交通运输工程；校车路径；优化；数学规划模型；改进遗传算法

0 引 言

校车路径问题(School Bus Routing Problem, SBRP)主要包括站点选择、路径生成、校车时刻表的制定等问题[1]。根据校车派车车辆数，可以分为单校车路径问题和多校车路径问题。笔者针对单校车接学生到校的问题进行研究，其它更多问题可在此基础上进行扩展延伸。

校车路径问题是NP完全问题，对于小规模的应用问题，可以采用精确算法来解决。J. Riera-Ledesma等[2]针对校车路径问题，建立了集划分模型，并设计了BCP(Branch-and-Cut-and-Price)精确算法对模型进行求解。而对于大规模的问题，精确算法难以在合理的时间内得到最优解，因此，人们更多地研究采用各种智能算法来快速获取问题的满意解。……