求解多车型校车路径问题的混合集合划分的GRASP算法

• 作者: 侯彦娥 党兰学 孔云峰
• 来源期刊: 计算机科学
• 学科: 工学
• 关键词: 多车型校车路径问题 集合划分 贪婪随机自适应 混合元启发
• 年，卷（期）: 2018,（4）
• 所属期刊栏目: 人工智能
• 页码范围: 240-246
• 页数: 7页
• 分类号: TP301.6
• 字数: 8743字
• 语种: 中文
• DOI: 10.11896/j.issn.1002-137X.2018.04.040

摘要

针对不同规划场景下具有不同优化目标的多车型校车路径问题(HSBRP),提出一种混合集合划分(SP)的贪婪随机自适应(Greedy Randomized Adaptive Search Procedure,GRASP)算法.根据GRASP算法寻优过程中产生的路径信息构建SP模型,然后使用CPLEX精确优化器对SP模型进行求解.为了适应不同类型的HSBRP问题,改进GRASP的初始解构造函数得到一个可行解,并将其对应的路径放入路径池;在局部搜索过程中应用多种邻域结构和可变邻域下降(VND)来提升解的质量,同时在路径池中记录在搜索过程中得到提升的路径和在每次迭代中得到局部最好解的路径信息.使用基准测试案例进行测试,实验结果表明在GRASP算法中,混合SP能够有效地提高算法的求解性能和稳定性,并且该算法能适应不同优化目标下车型混合和车辆数限制两类HSBRP的求解;与现有算法的比较结果再次验证了所提算法的有效性.

作者信息

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