校车路径问题元启发算法框架设计及应用  

Design and Application of Metaheuristic Framework for School Bus Routing Problem

作　　者：侯彦娥[1,2] 党兰学[1] 孔云峰[1] 陈小潘[1,2] 陈奕名[3] 

机构地区：[1]河南大学黄河中下游数字地理技术教育部重点实验室,河南开封475004 [2]河南大学计算机与信息工程学院,河南开封475004 [3]哈尔滨工程大学,哈尔滨150001

出　　处：《小型微型计算机系统》2014年第7期1625-1630,共6页Journal of Chinese Computer Systems

基　　金：国家自然科学基金项目(41201402)资助;河南省教育厅重点项目(13A520050)资助

摘　　要：校车服务有单校、多校不混载和多校混载等多种运营模式,规划路径时考虑的约束条件和目标不同衍生出多种校车路径问题(SBRP)的应用场景.SBRP属于NP问题,中大规模的应用基本都是采用启发式算法求解.在分析SBRP问题模型的基础上,总结元启发算法的特征,设计一个针对SBRP的元启发算法框架.该框架能够支持三种运营模式、不同的约束条件、单目标或多目标问题求解.最后利用框架直接构建具体应用的元启发求解算法,采用国际标准案例库对算法进行验证.结果表明基于框架可以快速地实现不同应用场景下SBRP的元启发算法.School bus service is divided into many kinds of operation modes,such as single school,single load multiple schools and mixed load multiple school and so on. When it comes to plan route satisfying various constraints and different objectives,there are many applications for school bus routing problem（ SBRP）. SBRP is a NP-hard problem,and it is generally recognized that middle and large size SBRP applications are resolved by heuristic algorithms. This paper proposes a metahenuristic algorithm framework for SBRP,based on the analysis of SBRP problem model and summarizing the features of metaheuristic algorithms. The framework can solve three operation modes,different constraints,and single objective or multi-objective problems. And then,metaheuristic algorithms combining with certain SBRP application is built and tested on the benchmark problem instances. The test results proved that metaheuristic algorithm,built based on the proposed framework,can be quickly realized and applied to different SBRP applications.

关 键 词：校车路径问题 元启发算法 框架 混载 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]