论文部分内容阅读
校车路径问题(SBRP)是在满足学生交通服务各种约束条件的前提下,寻求高效的校车路径方案,将学生从乘车站点运送到学校,达到一定的服务质量目标和校车运营效率目标.现有SBRP算法主要优化校车路径长度目标,较少关注如何减少所需校车数量.鉴于减少校车数量能显著降低校车服务成本,尝试设计蚁群优化(ACO)算法求解双目标SBRP问题.在校车容量和学生最大乘车时间约束下,将减少路径数量作为第一目标,缩减路径总长度为第二目标,设计了一个ACO算法.重点讨论了校车路径构造算法、与优化目标相关的信息素更新方法、局部搜索路径改进和提升双目标的两阶段策略.采用基准案例进行测试,验证算法的有效性.与CPLEX精确算法相比,ACO算法在求解路径数量和计算效率方面具有明显的优势.
School bus route problem (SBRP) is to meet the various constraints of student transport services under the premise of seeking efficient school bus route programs, students from the bus station to school delivery, to achieve a certain quality of service objectives and school bus operating efficiency goals. SBRP algorithm mainly optimizes the target length of the school bus route and pays less attention to how to reduce the number of required school buses.Because the reduction of the number of school buses can significantly reduce the school bus service cost, try to design an ant colony optimization (ACO) algorithm to solve the bi-objective SBRP problem. Under the constraint of the maximum travel time of students, the number of paths is reduced as the first goal and the total length of paths is reduced as the second objective. An ACO algorithm is designed. The algorithm of bus route construction, the pheromone updating method related to optimization objectives, The local search path improves and enhances the bi-objective strategy of two-objective strategy, and uses the benchmark case to test the validity of the algorithm.Compared with the CPLEX algorithm, the ACO algorithm has obvious advantages in solving the path number and computational efficiency.