校车路径问题的改进迭代局部搜索算法

• 作者: 侯彦娥 党兰学 孔云峰 谢毅
• 来源期刊: 计算机应用研究
• 关键词: 校车路径问题 迭代局部搜索 大规模邻域搜索 自适应选择
• 年，卷（期）: 2016,（11）
• 所属期刊栏目: 算法研究探讨
• 页码范围: 3255-3260
• 页数: 6页
• 分类号: TP301.6
• 语种: 中文
• DOI: 10.3969/j.issn.1001--3695.2016.11.013

摘要

针对考虑站点服务时间、学生最大乘车时间约束的校车路径问题（SBRP），提出一种改进迭代局部搜索（ILS）算法以提升求解质量。该算法使用大规模邻域搜索（LNS）算法作为扰动算子；在解的破坏过程中，设计一组解的破坏因子并赋予一定的选择概率，每隔若干次迭代后根据解的质量自适应更改破坏因子的选择概率，进而调整解的破坏程度。为提升ILS解的多样性，算法采用了基于偏差系数的邻域解接受准则。在国际基准测试案例上进行了测试，测试结果表明在ILS算法中使用自适应调整破坏程度的LNS扰动比常规扰动和其他破坏扰动的求解质量有大幅提升；与蚁群算法的比较结果进一步验证了改进算法的有效性。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	党兰学	河南大学计算机与信息工程学院	25	168	7.0	12.0
2	孔云峰	河南大学黄河中下游数字地理技术教育部重点实验室	82	984	17.0	28.0
3	侯彦娥	河南大学黄河中下游数字地理技术教育部重点实验室	24	150	6.0	10.0
7	谢毅	河南大学黄河中下游数字地理技术教育部重点实验室	10	41	4.0	6.0