改进的蚁群算法在矿山物流配送路径优化中的研究
第 28卷 第 6期
2004年 12月
中 国 钼 业
CHINA M0LYBDENUM INDUSTRY
V01．28 No．6
December 2OO4
改进 的蚁群算 法在 矿 山物流 配送路径优化 中的研 究
杨 瑞 臣 ．云 庆夏
(西安建筑科技大学 ，西安 71o055)
摘 要：物流配送路径优化问题是公认的 NP难题 ，本文运用一种新型的模 拟进化算法——蚁群算法对其进行求
解 。针对车辆路径问题及蚁群算法各 自的特点 ，本文对蚁群算法进行 多方面改进 ，以优化其搜索能力和加快收敛
速度。文中通过对实例计算求解，取得了满意的结果，从而证明了新算法的有效性。
关键词 ：蚁群算法；车辆路径问题 ；物流配送
中 图分 类号 ：TD5 文 献标 识码 ：A 文章 编 号 ：1006—2602(2004)06—0016—03
STUDY oF RoVED ANT Co LoN Y SYS’I’EM IN ’I．HE RoU’I’ING
oP，I唧 ZATIo N Fo R P=HYSICAL DIsTRⅡI唧 o N IN ～ⅡNES
YANG Rui—then，YUN Qing—xia
(Xi~Ln University of Architecture& Technology，xi，锄 710055，Shaanxi，China)
Abstract：Physical distribution routing optimizing is a famous NP —Hard problem．1’IIis paper use ant colony system
(ACS)，which is a novel simulated evolutionary algorithm，to solve the problem．According to the features of the
Vehicle Routing Problem and th e algorith m ，ACS is improved to enhan ce th e searching ability an d convergence．
Satisfied computational resul~ on given problems are reported，which shows that th e impro ved ACS is useful an d ef-
fective．
K ey words：an t colony system ；vehicle ro uting pro blem ；physical distribution
1 概 述
在露天 矿 山 中 ，运 输 费 用 通 常 占矿 石 成 本 的
60％ ～70％。因此 ，运输 路径 的 优化具 有 巨大 的经
济 意义。通常 ，矿山运输路径 的优化包 括矿石 、废 石
及材 料的运输 ，可统 称 为物 料配送 路线 的 优化 。它
是一类 NP—HARD 问题 ，精 确 的算 法 有分 枝 定 界
法 、K状树法 、Lagrang decomposition等 ，但 它们 只 能
求解相对 简单 的问题 。有些研 究者提 出过几种启 发
式算法 ，如节约法 、扫描 法等 ，这 些方 法尽 管能 够解
决此类问题，但也存在一定的缺陷 ，如节约法的组合
零乱 、边 缘 点 难 以组 合 ，扫 描 法 非 渐 进 优 化 等 ? 。
近年来遗传算 法 、禁忌搜 索算法 、模拟退火算法等都
在此 问题 上进行 了运用 ，并取得 了成功 。
本文 另辟 新径 ，将蚁群算 法应用于物 流配送路
径优化 的求解 ，并对 算法 中有 关 部分进 行 改进 以提
基金 项 目：陕西省 自然 科学基 金 资助课 题 (No．2001J06)
收 稿 日期 ．,2004—07—28
作者 筒介 ：杨瑞 臣 (1978一)，男 ，汉 族 ，西安 建 筑 科 技 大学 硕 士 研 究
生 ，研 究方 向 为计 算机 应 用。
高求解效率 。
从一般意义上讲 ，物流配送是指按顾 客的要 求 ，
用多个车辆从配送 中心对顾 客进行 配给 。各顾客点
的位置和需求量 为已知 ，各车辆 的载重量 已知 ，力求
寻找一个优 秀 的配 送方 案 ，使 得 总 代价 最 小 (所 用
车辆尽量少 ，行车总距 离尽量 短 )，同时满 足 以下 条
件及假设 ：
① 所有 的配送车辆以配送 中心为起点并最终
回到配送 中心 。
② 每条配送路径上各需求点的需求量之和不
超过车辆的载重量 。
③ 每条配送路径的长度不超过车辆一次允许
行驶 的最大距离 。
④ 每个需求点的需求 由且仅 由一辆车一次送
货满 足。
2 蚁群算 法的基本思想
蚁群算 法是 一种模拟 自然界蚂蚁觅食行 为的启
发式搜索算 法 。蚂 蚁觅食 时 ，会在 所 经过路 线 上 留
下一种称 为信息素 (pheromone)的物质 ，以此来标 识
维普资讯 http://www.cqvip.com
第 28卷 第 6期 杨瑞 臣：改进的蚁群算法在矿山物流配送路径优化中的研究 ‘ ·17·
路线 ，其它 蚂 蚁 可 以并 且 习惯 追 踪 此 信 息 素爬 行 。
在确定位置 的食物 和蚁 穴之间 ，较近的路线 ，蚂蚁重
复爬行的次数就更高些。由于每只蚂蚁每经过一次
都要释放信息 素 ，这 样重 复次 数 多 的路 线 由于其 信
息素浓度较 大就更 容 易被 其它 蚂蚁 选 中 ，这 样整 个
蚁群就 由开始 的多路线爬行逐渐集 中到最短的路线
上爬 行 ，使 路 线 得 到 优 化 选 择 。 意 大 利 学 者 M．
Dorigo模拟此过程提 出 了蚁群算法 J。以生活在 离
散时空 、具 有一定记 忆能 力 的人 工蚂蚁 替代 真实 自
然界 的蚂蚁 ，对旅行商 问题 (TSP)、任务分 配 问题 进
行启发式 的蚂 蚁搜 索 ，已取得 了很好的效果 。下 面 ，
我们用蚁群算 法来 解决物料配送路径 优化问题 。
3 配送路 径优化 问题的蚁群算法
我们用一 赋权 有 向图 G=(V，A，d)来表示 配送
路径 问题 ，其 中 V = { 。， 。， ：， }为 一系列点 的集
合 。 用来表示 配送 中心 ， (i= 1，2，?? ，n)表示
各顾 客 ，A ： {( ， )I ，vi∈V，i≠J}为一系列弧
的集合 ，d 与弧 ( ，vj)相联 系 ，表示 到 vi的距离 ，
对于顾客 给定 了需求量 q (其 中 q。=0)，在前述
第 1节 的约束 下 ，寻 找最 短 的路径 ，当然 ，使 用 车辆
也应尽可 能少 。
我们用 人工 蚂蚁替 代 车辆来 服务顾 客点 ，当下
一 个要服 务 的顾 客 点会 使 运 载 总量 超 出 汽 车载 重
量 ，或者使运距超过一次最 大行驶距离时 ，就返 回到
配送 中心 。，表示 这辆车完成此次运输 ，该辆车接着
出发服务其余 顾客 ，直 到所有 顾 客点 都得 到 了一次
服务 ，此时代表该 车的蚂 蚁完成一次巡游 。当所有蚂
蚁都巡游一 次 ，记 为一次 循环 。一次 循环后 ，根 据各
蚂蚁巡游历程 的好坏 (目标 函数 值 )，计算 信息 素增
量 ，更 新相 关路径上 的信息 素 。由于人 工蚂蚁 具有记
忆和判别 的能力 ，蚂蚁在 i顾 客 点选 择服务 的下 一
个顾客点 ．『时 ，主要考虑 两个 因素 ，一 是 i，J两顾客
点之 间的关 系的亲密程度 ，称为 可见度 ，记 为 77 ；另
外考虑 的是 由迄今完成 的循环所得路 径方案体现 出
来 的由 i到 ．『的可行 性 ，即信息 素浓 度 。易见 ，在
蚁群配送优 化迭代 中 ，关 键部分有三个 ：
① 顾客 i到顾客．『的转移概率
f ： ! ，， ，
Pif：J∑[ m] [7／ ]卢／J ∈。 。 d’(1)
allowed = I vi∈V， ∈i是此次 尚未服务到
的顾客 }
② 可见度 77 的表示
1
77 =手 (2)
③ 信息素浓度更新规则
nk
7 一ij =P· +∑△ (3)
此种蚁 群算 法可 以求解 配送路 径 问题 ，但存 在
计算量大 ，易 出现收敛过早 或停滞 等缺点 。
4 蚁群算法的改进
根据 以上的分析 ，针对 关键部分分别作改进 ，以
提高搜 索能力及效果 。本 文从下述三方面进行改进 。
(1)可见度 的改进
由于在配送 问题 中，配送 中心 是车辆 的起 始点
及终点 ，但 (2)式作 为局部启发量 ，没有考虑 到中心
点 的作用 ，使得最优解 不 易很快 被 发现 。鉴于此 ，我
们引入节 约值 SAVE，用此改造可见度 。记 SAVE =
d +d。 —d ，即由 i到 ．『所 能节约 的路径长度 。改造
后 ：
77 f： 丁
SAVEij (4)
叼 ■ 4
(2)信息浓度更新规则 的改进
为了加速收 敛 ，我们 有 限度增加 全局 最优解 的
影 响力。每次循环后 ，只对全局较优 的 k个解所 在线
路上 的信 息素浓度进行更新 。规则如下 ：
t ，
=p· +A∑ (5)
= 1
其中 ，1一P为挥发度 (即p为信 息素挥 发后所剩
的浓 度 )，k为取较优 解 的个 数 ， 为 第 最优 的 目
标值 ，A为更 新系数 ，用 以控制信息 素浓 度增加 的幅
度 。
(3)参 数的改进
为了加快 收敛速度 ，同时又兼 顾增大搜索范 围 ，
在蚁群循 环时 ，我们 在 不 同阶段 (循环 次 数 )，采 用
不 同的挥 发度 1一P及不 同的更新 系数 A。在初始时
为 了扩 大搜索范 围，我们 采用较小 的挥发度 ，较小 的
更新 系数 。在 即将结束 时 ，为 了加快 收敛 ，采用 较大
的挥 发度 ，并加大更新 系数 。
5 实例计 算
本文对文献 中的两 个 实例 分别 用 改进 的蚁
群算法在 matlab6．0环境 中进行 了计 算 比较 。
实验 1：某物流 中心有 2台配送 车辆 ，其载 重量
均为 8 t，车辆每次配送 的最 大行驶距 离为 50km，配
维普资讯 http://www.cqvip.com
· 18· 中 国 钼 业 2004年 12月
送 中心(其编号 为 0)与 8个客户之 间及 8个客户相
互之 间的距 离 dq(i,j：1，2，?? ，8)，8个客户的需
求量 (_『=1，2，?? ，8)均见表 1。要求合 理安排车
辆配送路线 ，使配送 总里程最短 。
表 1 实验 1的已知 数据
文献 [3]采用 混合 遗 传算 法 ，得 到 的平 均最 优
解 是 69．1 km。
本 文采 用蚁群算 法 ，取 蚂蚁 数 为 16，最 大循 环
次 数 NC为 10，取 =1， =2，循 环次数 NC<7时 ，
取 1一P=0．1，A =1，当 NC≥7时 ，取 1一P=0．3，
A =2。随机求解 10次 。得到结果如表 2，10次计算 ，
除一次结果 为 69外 ，其余 均得到 了最 优解 67．5，试
验结果 十分理 想。
表 2 实验 1的改进蚁群算法的计算结果
实验 2：某 物流 中心有 5台配送 车辆 ，车辆 的最
大载重量均 为 8 t，一 次配送 的最大行驶距离均 为 50
km，需要 向 20个 客 户 送 货 。物 流 中 心 的 坐 标 为
(14．5 km，13．0 km)，20个 客户 的坐标及其货 物需
求量 见表 3。
表 3 实验 2的 已知数 据
文献 采用 混合 遗传 算法 ，得 到 的平 均最优 解
是 122．0 km。
本文采用 蚁群算 法 ，取 蚂蚁 数 为 20，最 大循 环
次 数 NC为 10，取 =1， =3，循 环次数 NC<7时 ，
取 1一P=0．1，A =1，当 NC≥7时 ，取 1-p=0．3，
A =2。同样 随机求解 10次。得到结果如 表 4：
表 4 实验 2的改进蚁群算法的计算结果
比较文献 中结 果而 言 ，得 到 了比较理 想 的结
论 ，其 中两次得 出 108．6 km 的满意解 ，路径 为 0—5
— 14 —2 — 12 —9 —10 —7 — 1—0 —8 — 19 — 15 — 16 —
13—6-0—18—20—1 1—17—3—0—4—0，图形见
图 1，但 10次计 算所 用 车辆 均 为 4辆 ，没有 得 出使
用 3辆 车完成配送任务 的结论 。
6 结 束语
蚁群算 法是一种新型 的模拟进化算 法 。本文用
蚁群算法完成 了物流 配送 车辆 路径 问题 的求 解 J。
根据物流配送 的特殊性 ，对蚁群算 法进 行 了改进 ，并
取得 了比较理 想的效 果 。对蚁群算法及 车辆路 径问
题 的研究有一定 的参 考价值 。 图1 配送路径图
(下转第 28页)
维普资讯 http://www.cqvip.com
· 28· 中 国 钼 业 2004年 12月
机过滤 。洗涤 滤饼 的水 ，返 回配酸 器 。
杂工序处理 。
3．3 除杂工序
滤 液送 至 除 经仔细洗涤后 ，离心甩 干 ，送至后处 理工序 。
3．5 后 处 理 工 序
上述滤液 先加 人适量草 酸钠 溶液 除去 Ca¨ ，再
用浓度 30％ 的液 碱 处 理 至 pH12，使 Mg 生成 Mg
(OH) ，过 滤 。滤 液 中含 有 Fe 和 Al¨ ，因此 在
在送人浓缩器 中加热 时 ，同时加 人少 量硫 酸 中和 至
pH6．7～7．0，并加人 少量双氧水使 Fe 完全 氧化 成
Fe¨
，
这样就可使 上述杂质离 子生成氢氧化 物沉淀 。
为使料 液 脱 色 ，还 应 往 溶 液 中加 入 少 量 粉 状 活 性
炭 [2]。浓缩操作 的终 点 为溶 液 中含 Li：SO 200 g／L
时 为止 。料 液经板框 过 滤机 过滤后 ，澄 清 的滤液送
至沉淀工序 待用 。
3．4 沉 淀 工 序
先将 纯碱配制成准饱 和溶液 (15℃时 ，约为 20。
Be )，经澄清后 ，将 上层清液精 细过滤 。过滤好 的碱
液送人反应 罐 中，加热 至 90℃。在充 分搅 拌 下 ，以
细流状慢慢 地加人净化 合格 的 Li：SO 溶 液 ，立 即生
成 白色 的 Li CO ：
Li2SO4+Na2HCO3 Li2CO3 +Na2SO4
在此操 作 过 程 中 ，应 随 时 检查 罐 内料 液 的 pH
值 (用广泛 pH试 纸测 定 )，发现其 pH值 由 12开 始
下 降 ，就应减慢 加 入 Li：SO 溶 液 的速 度 ，以免 锂 盐
过量 ，造成碳酸锂沉淀吸附、包裹 SO 。沉淀作用
的终点是 pH9．0～10．0。当沉 淀终点 pH<9．0时 ，
成 品 SO 一指标有 上 升趋 势 ；当其 pH>10．0时 ，纯
碱耗用量增 大 ，影 响生产成本 。因此 ，上述沉淀作 用
终点 的 pH值必 须要求操作人员 加 以精细控制 。
沉淀作 用达到终点后 ，继续保 温搅拌 一段时 间。
复查其 pH值无变 化后 ，则 可将罐 内料浆送 人 WH一
800型过 滤式离 心 机 内，分 离母 液后 进 行洗 涤 。母
液补加少量 硫 酸调 整 pH值 为 中性 后 ，用于 回收硫
酸钠 。洗涤 回水返至浸取工 序稀 释浓硫酸用 。沉 淀
(上接 第 18页)
参 考文 献
[1] 郎茂祥．基于遗传算法的物流配送路径优化 问题研究
[J]．中国公路学报 ，2002，15(7)．
[2] Dorigo M，Gambardella L M．Ant Colony System：A Coop-
erative Learning Approach tO the Traveling Salesman
Problem[J]。IEEE Transactions on Evolutionary Coputa．
上述处 理好 的 Li：CO，沉淀 ，含 水量 为 3％ ～5％
左右 ，将 其送到用蒸 汽 间接加 热 的转筒 干燥 器 内进
行干燥 ，干燥 终点 为 含水 量 0．1％ 以内。经 干燥 合
格的碳酸锂再经 粉碎 、筛 析 、取样 化 验 、分装 即为成
品。
4 产 品质 量和 经 济效 益
按本文所介 绍的生产工艺所生产 制得 的碳酸锂
的质量指标 如下 ：
含量 (Li2CO3)，％ >98．0 氯化 物 (C1)，％ <
0．05
硫 酸盐 (SO )，％ <0．10
<0．12
氧化钙 (CaO)，％ <0．12
<0．0l
氧化 钠 (Na：O)，％
氧化 铁 (Fe：O)，％
重金属 (Pb)，％ <0．00 1 水 分 ，％ <0．10
由上述数 据清 晰地表 明 ，采用经 改进后 的新 工
艺所生产 出的碳 酸锂 的质 量是令 人 满意 的 ，而且 产
品尤其 以硫 酸盐 、重金属 等杂 质指 标 的低微 程度 而
获得 了用户 的青 睐。
经对新 法生产碳酸锂 的工业化 生产 实践 的经济
核算 ，新工 艺 的工 厂成本 仅 为 12 000 fr_／t左右 ，目
前市场上碳酸锂 的销 售价格为 29 6OO元 (今后仍 有
上升 的势头 )，其利润率 可达 60％ 以上 ，从而具有 十
分显著 的技术 经济效 益和社会效益 。
鸣谢 ：本工 艺及其 改进在 ．Y-~4t5大生产过程 中，
专家组l侯瑞星l高工做了大量的努力和工作，谨表诚
挚的怀念之 情 !
参考 文献
[1] 秦玉楠．精细化工 中活性炭的使用技术和经验[J]．中
国钼 ，2004，28(5)．
tion，1997，1(1)．
[3] 郎茂祥 ，胡思继．用混合遗传算法求解物流配送路径
优化 问题 的研究 [J]．中国管理科学 ，2002，10(10)．
[4] Bemd Bullnheimer，Richard F Hard，Christine Strauss．
An improved An t System algorithm for the Vehicle Rou．
ting Problem[J]．Annals of Operations Research，89
(1999)319—328。
维普资讯 http://www.cqvip.com
改进的蚁群算法在矿山物流配送路径优化中的研究.pdf
