摘要
校车服务有单校、多校不混载和多校混载等多种运营模式,规划路径时考虑的约束条件和目标不同衍生出多种校车路径问题(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.
出处
《小型微型计算机系统》
CSCD
北大核心
2014年第7期1625-1630,共6页
Journal of Chinese Computer Systems
基金
国家自然科学基金项目(41201402)资助
河南省教育厅重点项目(13A520050)资助
关键词
校车路径问题
元启发算法
框架
混载
school bus routing problem
metaheuristic algorithm
framework
mixed load
