需求可拆分校车路径问题的元启发式算法

• 作者: 孔云峰 郑泰皓 郑珊珊 陈小潘
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 校车路径问题 需求拆分 元启发式算法 模拟退火
• 年，卷（期）: 2016,（10）
• 所属期刊栏目: 人工智能
• 页码范围: 234-241,261
• 页数: 9页
• 分类号: TP301.6
• 字数: 9619字
• 语种: 中文
• DOI: 10.11896/j.issn.1002-137X.2016.10.045

摘要

校车路径规划中,允许站点乘车需求拆分通常能有效地降低校车服务成本.将该问题定义为需求可拆分校车路径问题(SDSBRP)进行求解.由于校车服务中要顾及学生最大乘车时间,且优化目标要兼顾所需校车数量和校车行驶距离,经典SDVRP算法难以直接应用于SDSBRP.因此分析了该问题的解特征,首次构建双目标SDSBRP数学模型,并首次设计针对该问题的元启发式求解算法.该算法首先构造初始可行解,然后在模拟退火算法框架下,引入站点需求拆分的邻域搜索算子进行迭代搜索,逐步改善解的质量.邻域搜索中,设计了多目标问题的邻域接受准则来引导邻域解的搜索方向,并引入破坏重建机制来增加解的多样性.使用已有的测试案例集和改造的测试案例进行算法测试,实验结果表明所提算法收敛性好,能够显著降低校车服务成本.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈小潘	河南大学黄河中下游数字地理技术教育部重点实验室	19	87	5.0	8.0
5	孔云峰	河南大学黄河中下游数字地理技术教育部重点实验室	82	984	17.0	28.0
6	郑珊珊	河南大学计算机与信息工程学院	9	13	2.0	3.0
7	郑泰皓	河南大学民生学院	4	13	2.0	3.0