一种求解双目标校车路径问题的蚁群优化算法

摘要：

校车路径问题(SBRP)是在满足学生交通服务各种约束条件的前提下,寻求高效的校车路径方案,将学生从乘车站点运送到学校,达到一定的服务质量目标和校车运营效率目标.现有SBRP算法主要优化校车路径长度目标,较少关注如何减少所需校车数量.鉴于减少校车数量能显著降低校车服务成本,尝试设计蚁群优化(ACO)算法求解双目标SBRP问题.在校车容量和学生最大乘车时间约束下,将减少路径数量作为第一目标,缩减路径总长度为第二目标,设计了一个ACO算法.重点讨论了校车路径构造算法、与优化目标相关的信息素更新方法、局部搜索路径改进和提升双目标的两阶段策略.采用基准案例进行测试,验证算法的有效性.与CPLEX精确算法相比,ACO算法在求解路径数量和计算效率方面具有明显的优势.

关键词：校车路径问题、蚁群优化、算法设计

所属期刊栏目：46

分类号：TP3(计算技术、计算机技术)

资助基金：国家自然科学基金41401461

在线出版日期：2016-03-10（万方平台首次上网日期，不代表论文的发表时间）

页数：共9页

页码：50-58