蚁群算法在物流路径优化中的应用及仿真

31 1 蚁群算法的不足 虽然蚁群算法能够缩小问题求解搜索范围 ,
降低问题复杂度 ,获得较优物流路径 ,但是与其他 算法相比较 ,该算法一般需要较长的搜索时间 ,每 只蚂蚁构造的回路只是可行解的组成部分 ,各蚂 蚁构造的回路可能组成可行解 ,但是也可能找不 到可行解 ,从而出现停滞现象 ( stagnatio n behav2 ior) ,即搜索进行到一定程度后 ,所有个体所发现 的解完全一致 ,不能对解空间进一步搜索 ,不利于 发现更优解 。
-
ρ理解为轨迹的挥发度城市时的可行顶点集 ;Δτikj 表示第 k 只
蚂蚁在本次循环中在边弧 ( i , j) 上留下的信息量 ;
Δτij 表示 蚂 蚁 在 边 弧 ( i , j ) 上 留 下 的 信 息 素 的
数量 。
蚁群算法相关规则 :
(1) 路径转移规则 。初始时 , 每只蚂蚁被随
第 32 卷 第 2 期 2009 年 2 月
合肥工业大学学报 ( 自然科学版)
J OU RNAL O F H EFEI UN IV ERSIT Y O F TEC HNOLO GY
Vol. 32 No . 2 Feb. 2009
蚁群算法在物流路径优化中的应用及仿真
吴云志 , 乐 毅 , 王 超 , 张友华
( School of Information and Computer Science , Anhui Agricult ural Univer sit y , Hefei 230036 , China)
Abstract : The ant colo ny op timizatio n ( ACO) algorit hm is a novel simulated evolutio nary algorit hm which is suitable for solving co mplicated co mbinatio n p ro blems. The current ACO co nverges slowly , and result s in stagnatio n behavior so metimes. In t his paper ,by taking t he ACO algorit hm as t he core , t he optimal logistics pat h is o btained based o n t he shortest pat h met hod and t he assigned co st . The op timum parameter is selected to imp rove t he ACO algorit hm and avoid t he appearance of local solu2 tio n. The experimental result s show t hat t he efficiency of t he imp roved algorit hm is enhanced ,and t he algorit hm is co nvergent in t he experimental enviro nment . Key words :ant colo ny ptimizatio n (ACO) algorit hm ; pat h selectio n ; optimal pat h ; simulatio n
212
合肥工业大学学报 (自然科学版)
第 32 卷
用的算法有模拟退火算法 、GA 算法等 。启发式 方法能较好地求解描述比较具体的问题 ,较精确 优化方法简单实用 ,缺点是难以知道什么时候最 优启发式解已经被求得 。目前物流系统中的最优 路径问题 ,要充分考虑多项因素 ,如距离 、代价及 时间等 ,但启发式方法往往只能用于解决有限规 模的问题 ,不适用于现实中的大规模运输问题 ,有 关研究结果也证明了这一点 。而蚁群算法作为一 个群体启发式算法 ,由于其自身所具备的特点和 良好的性能被应用到物流优化路径选择 ,可以用 来求解大规模物流路径[3 ] 。
本文求解物流配送优化问题的基本思想 ,是 在求 解 旅 行 售 货 员 问 题 ( Traveling Salesman Pro blem ,简称 TSP) 的蚁群算法基础之上 ,根据 车辆路径优化问题的具体情况 ,使用蚁群算法作 为物流路径选取的核心算法 ,其中与蚁群算法结 合的启发式算法实现采用最短路径法和自定义代 价 2 种方法相结合 ,使用 Matlab 的算法库实现蚁 群算法 ,并选择不同城市数进行了测试 。
Appl ication and simulation of the ant colony optimization algorithm in logistics path optimization
WU Yun2zhi , YU E Yi , WAN G Chao , ZHAN G Yo u2hua
第 2 期
吴云志 ,等 :蚁群算法在物流路径优化中的应用及仿真
213
全局更新规则为 τij ( t + n) = ρ3τij ( t) +τij ( t , t + n) (4)
其中
m
∑ Δτij ( t , t + n) = Δτikj ( t , t + n)
(5)
k =1
3 物流路径优化问题的蚁群算法实现
0 引 言
1 算法选择
随着国民经济的快速增长和社会需求的增加 ,
车辆路径问题是在 20 世纪 50 年代由 Dantz2
原来从事大量储存 、运输的物流管理活动在产品多 ig 和 Ramser 提出的[1 ,2] 。当时的车辆路径问题
样化及小批量化的情况下变得空前复杂起来 。物 主要是静态的车辆路径问题 ,描述的是一个运筹
有大量蚂蚁做出的蚁群集体行为表现出了信息的
正反馈现象 :某路径上走过的蚂蚁越多 ,则后来者 选择该路径的概率也越大 。蚁群算法可以解释为
是一种特殊的强化学习算法 ,它在一定程度上可 以加快进化过程 ,而且本质上是一种并行算法 ,不 同个体 (agent) 之间不断进行信息交流和传递 ,从 而相互协作 。有利于发现较优解 ,从而获得较优 物流路径[4 - 6 ] 。
流系统是一个网络系统 ,是一个由物流路线与物流 学中的优化问题 ,有一个配送中心 (或调度中心) ,
节点组成的实体网络 ,其中物流线路承担着商品运 在车辆的数目确定 、服务对象数目一定 、对服务时
输的重要作用 。在物流配送路径的优化选择中 ,使 间没有要求的情形下 ,总目标是用最少的车辆 ,使
用合适的方法 ,采用合适的技术 ,制订合理的配送 总的行程最短 。
(安徽农业大学 信息与计算机学院 ,安徽 合肥 230036)
摘 要 :蚁群算法是一种模拟进化算法 ,适合于求解复杂的组合优化问题 ,传统蚁群算法收敛速度慢 ,有时可 能出现停滞现象 。该文以蚁群算法为核心 ,采用最短路径法和自定义代价获取最优物流路径 ,通过优选参数 改进蚁群算法 ,从而有效避免局部解的出现 。实验结果表明 ,改进后的算法效率具有较大改进 ,算法在实验环 境下收敛性较好 。 关键词 :蚁群算法 ; 路径选择 ; 最优路径 ; 仿真 中图分类号 : TP18 文献标识码 :A 文章编号 :100325060 (2009) 0220211204
蚁群进化算法是是一种处理复杂优化问题的 算法 ,它是一种群体仿生的智能优化算法 ,通过模 拟蚂蚁搜索食物行为来产生最优解[4 - 6 ] 。蚂蚁群 找到食物时 ,它们总能找到一条从食物到巢穴之 间的最优路径 。蚁群算法主要特点是 :正反馈 、分 布式计算 、能够较好地与其他启发式算法相融合 。 正反馈过程使得该方法能很快发现较好解 ;分布 式计算使得该方法易于并行实现 ;与其他启发式 算法相结合 , 使得该方法易于发现较好解 。
值为 0 ; Pikj 为蚂蚁 k 由位置 i 到 j 的概率 ; Cij 为城 市 i 和城市 j 之间的代价 ;ηij 为边弧 ( i , j) 上的能
见度 ,ηij = 1/ Cij ;α为轨迹的相对重要性 (α≥0) ;β
为能见度的相对重要性 (β≥0) ;ρ为轨迹的持久
性 (0
≤ρ≤1)
,1
省高等学校省级自然科学研究重点资助项目 ( KJ 2008A056) 和安徽农业大学校长青年基金资助项目 (2006) 作者简介 :吴云志 (1974 - ) ,女 ,安徽滁州人 ,安徽农业大学讲师.
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved.
利用蚁群算法模拟蚂蚁搜索食物的过程 ,可 实现货物配送最优路径获取问题 。蚂蚁之间通过 一种称为外激素 (p hero mo ne) 的物质进行信息传 递 ,从而互相协作 ,完成负责的任务 。在运动中 , 蚂蚁能够在所经过的路径上留下外激素 ,且在运 动过程中蚂蚁能够感知这种物质的存在及强度 ,
并倾向于朝着该物质强度高的方向移动 。因此 ,
τij ( t + 1) = ρ3τi j ( t) +Δτij ( t , t + 1) (2) 其中
m
∑ Δτij ( t , t + 1) = Δτikj ( t , t + 1)
(3)
k =1
© 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved.
TSP 可用图 G = ( N , A) 表示 ,其中 N 为要访
问的城市集合 , A = { ( i , j) | i , j ∈N , 且 i ≠j} 是
连接其中任意 2 个城市的弧的集合[3 ,7 ] 。
蚁群算法相关变量如下 : m 为蚂蚁个数;