[1]郭咏梅,胡大伟,陈 翔.改进蚁群算法求解带时间窗的应急物流开环车辆路径问题[J].长安大学学报(自然科学版),2017,37(06):105-112.
　GUO Yong-mei,HU Da-wei,CHEN Xiang.Solution of emergency logistics open-loop vehicle routing problem with time window based on improved ant colony algorithm[J].Journal of Chang’an University (Natural Science Edition),2017,37(06):105-112.
点击复制

改进蚁群算法求解带时间窗的应急物流开环车辆路径问题()
分享到：

长安大学学报（自然科学版）[ISSN:1006-6977/CN:61-1281/TN]

卷:
第37卷
期数:
2017年06期
页码:
105-112
栏目:
交通工程
出版日期:
2017-11-20

文章信息/Info

Title:
Solution of emergency logistics open-loop vehicle routing problem with time window based on improved ant colony algorithm
文章编号:
1671-8879(2017)06-0105-08
作者:
郭咏梅; 胡大伟; 陈 翔
长安大学 汽车学院，陕西 西安 710064
Author(s):
GUO Yong-mei;  HU Da-wei;  CHEN Xiang
School of Automobile, Chang’an University, Xi’an 710064, Shaanxi, China
关键词:
交通工程; 应急物流; 开环车辆路径问题; 可靠性; 蚁群算法; 鱼群算法
Keywords:
traffic engineering;  emergency logistics;  open-loop vehicle routing problem;  reliability;  ant colony algorithm;  fish swarm algorithm
分类号:
U491
文献标志码:
A
摘要:
为解决受灾区域的物资运输问题，研究应急物流背景下带时间窗的开环车辆路径问题。将灾后道路通行性能差异及物资运输优先级考虑入约束范围，在确保应急物资运输可靠性的基础上，提出基于物流响应能力最大化的车辆路径模型。同时，考虑到传统优化算法收敛性差、易陷入局部最优的缺点，提出一种改进的蚁群算法以突破已有的算法瓶颈。该算法混合了人工鱼群算法与蚁群算法，将拥挤度因子引入蚁群算法以指导蚁群的聚集，从而提高蚁群算法求解的质量。通过一个基础算例对所提出模型与算法进行验证，得到最优解优化曲线并求解最优解，采用1组CMT与GWKC标准算例对提出的改进蚁群算法的性能进行评估计算试验。分别采用模拟退火算法、变邻域搜索算法及邻域搜索算法对标准算例进行求解。研究结果表明：提出的改进蚁群算法在求解收敛性与精确性上有显著优势，提出的算法在迭代60次后得到最优解，收敛速度比蚁群算法提前了68个迭代循环，最优解优化接近7.8%；在相同试验环境下，实例数据的规模与算法所求得最优解的差值无关，即算例规模并不影响算法求解的精确度；提出的改进蚁群算法在可接受时间范围内，通过适当延长邻域搜索运算时间可显著提升求解精度，在各组试验结果中相比于其他算法均求得了最优的结果，在CMT2中改进蚁群算法求得的最优解比已知上界优化了超过40%。
Abstract:
In order to solve the problem of material transportation in the affected area, an emergency logistics open-loop vehicle routing problem with time window (EL-OLVRPTW) was studied. Taking into account the difference of road traffic performance and the priority of material transportation after disaster, a vehicle routing model based on the maximization of logistics response ability was proposed on the basis of ensuring the reliability of emergency material transportation. Meanwhile, an improved ant colony algorithm (IAC) was proposed to break through the bottleneck of traditional optimization algorithm. The new algorithm improved its convergence and had a great ability to keep from falling into local optimum. This algorithm combined the artificial fish swarm algorithm and the ant colony algorithm. Crowding factor was used for guiding the ant colony for its process of aggregation and finally improved the quality of its solution. The proposed model and algorithm were verified by a basic numerical case. The optimized solution curve was obtained and the optimal solution was solved. The evaluation calculation experiment was conducted on the performance of improved ant colony algorithm by adopting one CMT and GWKC standard example. Numerical calculation adopted simulated annealing algorithm, variable neighborhood search algorithm and neighborhood search algorithm on the standard examples. The results show that the IAC proposed in this paper has a significant advantage in its solving convergence and accuracy. Among these numerical results, the optimal solution solved by IAC is obtained after 60 iterations, which advances 68 iterative cycles compared with the ant colony algorithm. And optimization of the solution is close to 7.8%. Under the same experimental conditions, the scale of the instance data is independent of the difference of the optimal solution, which means the scale of the example does not affect the accuracy of the algorithms. The proposed IAC can significantly improve the accuracy of the solution by properly extending the search time for neighborhood within an acceptable time limit. Compared with other algorithms, the optimal result is obtained by the proposed IAC in each group. The optimal solution obtained by IAC is optimized more than 40% than the known upper bound in the case of CMT2.

相似文献/References:

[1]王建伟,李娉,高洁,等.中国交通运输碳减排区域划分[J].长安大学学报(自然科学版),2012,32(01):0.
[2]李曙光,周庆华.具有破坏排队的离散时间动态网络装载算法[J].长安大学学报(自然科学版),2012,32(01):0.
[3]凌海兰,郗恩崇.基于随机波动条件的公交客运量预测模型[J].长安大学学报(自然科学版),2012,32(01):0.
[4]田娥,肖庆,陆小佳,等.安全驾驶的横向安全预警报警阈值的确定[J].长安大学学报(自然科学版),2012,32(01):0.
[5]侯贻栋,赵炜华,魏 朗,等.驾驶人空间距离判识规律心理学分析[J].长安大学学报(自然科学版),2012,32(03):86.
　HOU Yi-dong,ZHAO Wei-hua,WEI Lang,et al.Analysis on psychology in cognitive distance about drivers[J].Journal of Chang’an University (Natural Science Edition),2012,32(06):86.
[6]赵跃峰,张生瑞,魏 华.隧道群路段运行速度特性分析[J].长安大学学报(自然科学版),2012,32(06):67.
　ZHAO Yue-feng,ZHANG Sheng-rui,WEI hua.Operating speed characteristics of tunnel group section[J].Journal of Chang’an University (Natural Science Edition),2012,32(06):67.
[7]林 杉,许宏科,刘占文.一种高速公路隧道交通流元胞自动机模型[J].长安大学学报(自然科学版),2012,32(06):73.
　LIN Shan,XU Hong-ke,LIU Zhan-wen.One cellular automaton traffic flow model for expressway tunnel[J].Journal of Chang’an University (Natural Science Edition),2012,32(06):73.
[8]刘俊德,徐 兵,梁永东,等.交通事故下高速公路行车安全评估[J].长安大学学报(自然科学版),2012,32(06):78.
　LIU Jun-de,XU bing,LIANG Yong-dong,et al.Traffic safety assessment of expressway in the accident[J].Journal of Chang’an University (Natural Science Edition),2012,32(06):78.
[9]芮海田,吴群琪,赵跃峰,等.公路建设对区域经济发展的影响分析——以陕西省为例[J].长安大学学报(自然科学版),2012,32(06):83.
　RUI Hai-tian,WU Qun-qi,ZHAO Yue-feng,et al.Influence of highway construction on regional economy development——taking Shaanxi as an example[J].Journal of Chang’an University (Natural Science Edition),2012,32(06):83.
[10]彭 辉,续宗芳,韩永启,等.城市群城际运输结构配置客流分担率模型[J].长安大学学报(自然科学版),2012,32(02):91.
　PENG Hui,XU Zong-fang,HAN Yong-qi,et al.Sharing ratios model of passenger flows in intercity transportation structure configuration among urban agglomeration[J].Journal of Chang’an University (Natural Science Edition),2012,32(06):91.
[11]王 茵,胡大伟,李 博.基于多供应主体的应急物资供应模型[J].长安大学学报(自然科学版),2016,36(06):98.
　WANG Yin,HU Da-wei,LI Bo.Emergency resource supplying model under multi-supply subjects[J].Journal of Chang’an University (Natural Science Edition),2016,36(06):98.

备注/Memo

备注/Memo:
收稿日期：2017-06-11 基金项目：国家自然科学基金项目（61503043）；中央高校基本科研业务费专项资金项目(310822151030)；陕西省自然科学基础研究计划项目（2015JQ6214，2015JO7272）作者简介：郭咏梅（1980-），女，辽宁东港人，讲师，工学博士研究生，E-mail: gymei@chd.edu.cn。通讯作者：胡大伟（1963-），男，北京市人，教授，博士研究生导师，E-mail: dwhu@chd.edu.cn。
更新日期/Last Update: 2017-12-18