校车路径问题的约束检测算法

• 来源期刊: 计算机应用研究
• 关键词: 校车路径问题 时间窗 容量 约束检测 分段检测
• 年，卷（期）: 2014,（5）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 1396-1398,1402
• 页数: 4页
• 分类号: TP18
• 语种: 中文
• DOI: 10.3969/j.issn.1001-3695.2014.05.026

摘要

依据校车服务学校的数量和顺序可将校车路径问题（SBRP）分为单校、多校不混载和多校混载三类。现有算法对不同类型的SBRP进行容量、时间窗等约束检测时采用不同的方法，对待复杂应用需要通过遍历进行检测。为此设计一种适用于不同类型SBRP的分段检测算法，将路径上的学校站点视为检测点，按检测点对路径分段，基于各个检测路段上的剩余容量和剩余时间检测整条路径是否违反约束。最后在大规模混载校车路径问题上的实验表明分段检测算法是有效的。