###
:2019,28(7):9-16
←前一篇   |   后一篇→
本文二维码信息
码上扫一扫!
基于Spark的改进蚁群算法对带时间窗车辆路径问题的求解
(1.中国科学院 计算机网络信息中心, 北京 100190;2.中国科学院大学, 北京 100049)
Solving Vehicle Routing Problem with Time Window Based on Spark's Improved Ant Colony Algorithm
(1.Computer Network Information Center, Chinese Academy of Sciences, Beijing 100190, China;2.University of Chinese Academy of Sciences, Beijing 100049, China)
摘要
图/表
参考文献
相似文献
本文已被:浏览 273次   下载 253
投稿时间:2019-01-10    修订日期:2019-02-03
中文摘要: 为应对大数据时代对带时间窗车辆路径问题(VRPTW)的实时求解要求,提出基于Spark平台的改进蚁群算法.在算法层面,利用改进的状态转移规则和轮盘赌选择机制构建初始解,结合k-opt邻域搜索进行路径构建优化,改进最大最小蚁群算法中的信息素更新策略;在实现层面,利用Spark提供的API对蚁群RDD进行操作,实现蚁群分布式并行求解.在标准算例Solomon benchmark和Gehring&Homberger benchmark的实验结果表明,该算法在大规模问题的求解精度和速度上有明显提升.
Abstract:In order to cope with the real-time solution requirements of the Vehicle Routing Problem with Time Window (VRPTW) in the era of big data, this study proposed an improved parallel ant colony algorithm based on Spark platform. At the algorithm level, the improved state transition rule and roulette selection mechanism are used to construct the initial solution, and the k-opt local search is used to optimize the path construction. In addition, the improved pheromone update strategy of max-min ant colony algorithm is applied. At the implement level, the ant colony is encapsulated into RDD, which is operated by Spark API to realize distributed construction solution. The experimental results of the Solomon benchmark and Gehring & Homberger benchmark show that the proposed algorithm can improve the accuracy and speed of large-scale problems.
文章编号:     中图分类号:    文献标志码:
基金项目:
引用文本:
李奕颖,秦刚.基于Spark的改进蚁群算法对带时间窗车辆路径问题的求解.计算机系统应用,2019,28(7):9-16
LI Yi-Ying,QIN Gang.Solving Vehicle Routing Problem with Time Window Based on Spark's Improved Ant Colony Algorithm.COMPUTER SYSTEMS APPLICATIONS,2019,28(7):9-16

用微信扫一扫

用微信扫一扫