没有合适的资源?快使用搜索试试~ 我知道了~
论文研究-基于改进蚁群算法的车辆路径优化问题研究.pdf
需积分: 49 16 下载量 176 浏览量
2019-07-22
20:52:47
上传
评论 6
收藏 1.33MB PDF 举报
温馨提示
试读
4页
物流活动中需要找出各个配货节点之间的最短路径, 用以指导物流车辆调度, 进而节约物流成本。提出解决车辆路径优化问题的方法, 针对蚁群算法的缺点, 分别对信息素更新策略、启发因子进行改进, 并引入搜索热区机制, 有效解决了蚁群算法的缺陷。最后, 以哈尔滨市局部地图为原型, 应用MATLAB软件对改进蚁群算法求解车辆路径优化问题的性能进行仿真, 并与基本蚁群算法对比分析, 验证了改进蚁群算法的有效性和可行性。
资源推荐
资源详情
资源评论
收稿日期:20111107;修回日期:20111212 基金项目:黑龙江省哲学社会科学基金资助项目(08E004);中央高校基本业务费专项基
金资助项目(HEUCF120910)
作者简介:陈迎欣(1975),女,河北景县人,副教授,博士,主要研究方向为建模仿真、危机管理(hexieshehui2011@163.com).
基于改进蚁群算法的车辆路径优化问题研究
陈迎欣
(哈尔滨工程大学 经济管理学院,哈尔滨 150001)
摘 要:物流活动中需要找出各个配货节点之间的最短路径,用以指导物流车辆调度,进而节约物流成本。提
出解决车辆路径优化问题的方法,针对蚁群算法的缺点,分别对信息素更新策略、启发因子进行改进,并引入搜
索热区机制,有效解决了蚁群算法的缺陷。最后,以哈尔滨市局部地图为原型,应用 MATLAB软件对改进蚁群
算法求解车辆路径优化问题的性能进行仿真,并与基本蚁群算法对比分析,验证了改进蚁群算法的有效性和可
行性。
关键词:蚁群算法;车辆路径优化;信息素;物流
中图分类号:TP301 文献标志码:A 文章编号:10013695(2012)06203104
doi:10.3969/j.issn.10013695.2012.06.007
StudyonVRPbasedonimprovedantcolonyoptimization
CHENYingxin
(SchoolofEconomics&Management,HarbinEngineeringUniversity,Harbin150001,China)
Abstract:Logisticsactivitiesneedtofinddifferentdistributionnodeoftheshortestpath,toinstructthelogisticsvehicle
scheduling
,andthensavethelogisticscost.Thispaperproposedthesolutionofvehicleroutingoptimizationproblem.Inorder
toconquerthedefectsandimprovethebasicantcolonyoptimization,itimprovedpheromonesupdatingstrategy,stimulating
factorandtheintroductionofsearchhotspots,solvedthedefectsofantcolonyoptimizationeffectively.WiththehelpofHarbin
citymapastheprototypeandtheMATLABsoftware,itcarriedoutsimulationtochecktheimprovedantcolonyoptimization.
Theresultverifiesthefeasibilityandeffectivenessoftheimprovedantcolonyoptimization.
Keywords:antcolonyoptimization;vehicleroutingproblem(VRP);pheromone;logistics
!
引言
车辆路径问题(vehicleroutingproblem,VRP)是物流系统
优化环节中关键的一环。对运输车辆进行优化调度,通过选择
车辆的最佳运输路径,合理安排车辆调度顺序,可以有效减少
车辆的空驶率和行驶距离。VRP已经应用到牛奶配送、报纸
和快件投递、垃圾车的线路优化及连锁商店的送货线路优化等
众多社会领域
[1]
。
由于该问题属于求解较为困难的组合优化
NPhard问题
而且具有强有力的应用背景,长期以来吸引着大量学者对其不
断地进行研究探索,研究人员从最初的精确算法开始,逐步将
目光投向更广阔的启发式算法,如禁忌搜索算法、遗传算法、蚁
群算法等。钟石泉等人
[2]
对软、硬时间窗约束的 VRP进行了
研究,并用禁忌搜索算法分别进行求解;Chao
[3]
利用禁忌搜索
算法求解了多车型的
VRP;Chen等人
[4]
利用遗传算法来处理
钢铁领域采用半挂车运输车辆进行物流配送中的车辆时间表
制定及路径选择问题;唐炉亮等人
[5]
通过对蚁群算法的改进
解决了 GPS数据的公众出行路径优化问题。这些算法在 VRP
的求解上取得了可喜的成果,但也存在着不少问题,如禁忌搜
索算法存在对初始解有较高的依赖性的缺点;遗传算法有局部
搜索能力不强、易陷入早熟、总体上可行解的质量不是很高的
缺点。
蚁群算法自从被提出就受到了广泛的关注,该算法在解决
路径优化、任务分配等问题时表现出了良好的性能,但是蚁群
算法也存在一定的缺陷,如在解决大规模问题时,收敛速度慢、
运算时间长、容易陷入局部最优解等
[6]
。本文将基本蚁群算
法进行改进,克服了以上缺点,使算法性能更好,得到了运输效
率更高、运算结果更精确的车辆路径优化算法。
"
HB$
的数学模型
VRP的 数 学 模 型 表 述 如 下:假 设 客 户 点 共 有 k个 (1,
2,…,k),将第 i个客户点的货物需求量设为 g
i
(i=1,2,…,
k),配送中心派出车辆承担运输任务,其载重量为 q。设 g
i
<
q,求满足货运需求的最短路线。
为了方便地安排路线,可以事先估算需要使用的车辆数
目。在现实情况中,车辆数目的需求量取决于货物装车(或
卸车)的复杂程度,装卸越复杂,约束条件就越多,车辆的实
际载货量就越小。用户自主选择的车辆数目可以由下列公
式求得:
m=[
∑
g
i
/
α
q]+1 (1)
其中:m表示所需的车辆数;[]表示取整;
α
是参数,且 0<
α
<
1
。约束条件越多的情况下,货物装车、卸车越复杂,
α
值就越
小,一般取
α
=085。
用 c
ij
表示点 i到点 j的运输成本(如时间、路程、花费等),
第 29卷第 6期
2012年 6月
计 算 机 应 用 研 究
ApplicationResearchofComputers
Vol29No6
Jun2012
资源评论
weixin_39840914
- 粉丝: 435
- 资源: 1万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功