基于PDPTW邻域算子进行混载校车路线优化

摘要

为中小学校学生提供安全、高效的校车交通服务是教育主管部门的一项重要任务。允许某一区域内的校车混载多个学校的学生可以显著地减少校车数量，提升校车运营效率。混载校车路线问题(SBRP)属于复杂度极高的强NP 难(strong NP‐hard)问题，目前的VRP 算法能较好地用于单个学校的校车路线规划，但不适用于混载SBRP，而现有求解混载SBRP的算法在路线缩减上仍有较大的提升空间。文章提出一种启发式求解方法：利用有时间窗装卸问题(PDPTW)的邻域算子搜索邻域解，采用记录更新法(record‐to‐record travel)优化校车路线数目。rn 与现有算法相比，该算法扩大了邻域解的搜索空间，在全局范围内对校车路线进行优化，测试结果表明能够优化出需要更少校车数辆的路线方案。