| 需求可拆分校车路径问题的元启发式算法 |
| |
| 引用本文： | 陈小潘,孔云峰,郑泰皓,郑珊珊.需求可拆分校车路径问题的元启发式算法[J].计算机科学,2016,43(10):234-241, 261. |
| |
| 作者姓名： | 陈小潘 孔云峰 郑泰皓 郑珊珊 |
| |
| 作者单位： | 河南大学黄河中下游数字地理技术教育部重点实验室 开封475004;河南大学计算机与信息工程学院 开封475004,河南大学黄河中下游数字地理技术教育部重点实验室 开封475004,河南大学民生学院 开封475004,河南大学计算机与信息工程学院 开封475004 |
| |
| 基金项目： | 本文受国家自然科学基金青年科学基金项目(41401461,7)资助 |
| |
| 摘 要： | 校车路径规划中,允许站点乘车需求拆分通常能有效地降低校车服务成本。将该问题定义为需求可拆分校车路径问题(SDSBRP)进行求解。由于校车服务中要顾及学生最大乘车时间,且优化目标要兼顾所需校车数量和校车行驶距离,经典SDVRP算法难以直接应用于SDSBRP。因此分析了该问题的解特征,首次构建双目标SDSBRP数学模型,并首次设计针对该问题的元启发式求解算法。该算法首先构造初始可行解,然后在模拟退火算法框架下,引入站点需求拆分的邻域搜索算子进行迭代搜索,逐步改善解的质量。邻域搜索中,设计了多目标问题的邻域接受准则来引导邻域解的搜索方向,并引入破坏重建机制来增加解的多样性。使用已有的测试案例集和改造的测试案例进行算法测试,实验结果表明所提算法收敛性好,能够显著降低校车服务成本。
|
| 关 键 词： | 校车路径问题 需求拆分 元启发式算法 模拟退火 |
| 收稿时间： | 2015/8/19 0:00:00 |
| 修稿时间： | 2015/11/23 0:00:00 |
Metaheuristic Algorithm for Split Demand School Bus Routing Problem |
| |
| CHEN Xiao-pan,KONG Yun-feng,ZHENG Tai-hao and ZHENG Shan-shan.Metaheuristic Algorithm for Split Demand School Bus Routing Problem[J].Computer Science,2016,43(10):234-241, 261. |
| |
| Authors: | CHEN Xiao-pan KONG Yun-feng ZHENG Tai-hao and ZHENG Shan-shan |
| |
| Affiliation: | Key Laboratory of Geospatial Technology for Middle and Lower Yellow River Regions of Ministry of Education, Henan University,Kaifeng 475004,China;College of Computer and Information Engineering,Henan University,Kaifeng 475004,China,Key Laboratory of Geospatial Technology for Middle and Lower Yellow River Regions of Ministry of Education, Henan University,Kaifeng 475004,China,Minsheng College,Henan University,Kaifeng 475004,China and College of Computer and Information Engineering,Henan University,Kaifeng 475004,China |
| |
| Abstract: | |
| |
| Keywords: | School bus routing problem Split deliveries Metaheuristic algorithm Simulated annealing |
|
| 点击此处可从《计算机科学》浏览原始摘要信息 |
|
点击此处可从《计算机科学》下载全文 |
|
