蚁群聚类算法在物流网络优化中的应用

蚁群算法 网络优化

第29卷增 刊 辽宁工程技术大学学报（自然科学版） 2010年5月 Vol.29 Suppl. Journal of Liaoning Technical University（Natural Science） May 2010

文章编号：1008-0562(2010)增刊Ⅰ-0082-03

蚁群聚类算法在物流网络优化中的应用

任建华1，王 鹤2，邱云飞3

(1.辽宁工程技术大学 电子与信息工程学院，辽宁 葫芦岛 125105; 2.辽宁工程技术大学 基础教学部，辽宁 葫芦岛 125105;

3.辽宁工程技术大学 软件学院, 辽宁 葫芦岛 125105)

摘 要：为了解决物流配送中的路径优化问题,运用改进的蚁群算法来建立配送车辆路径的数学模型，通过减少蚁群的选路次数、更新信息素等策略，提高了算法的收敛速度和全局搜索能力。经过实验分析和计算，证明了应用蚁群算法可以优化物流配送线路，可以有效地解决多回路运输问题。该成果对物流企业控制成本、增强市场竞争力有一定参考价值。

关键词:物流网络；蚁群算法；聚类分析；优化调度问题 中图分类号：TP 18 文献标识码：A

Application of ant colony clustering algorithm

in logistics network optimization

REN Jianhua1，WAGH He2，QIU Yunfei3

（1.College of Electronics and Information Engineering, Liaoning Technical University, Huludao 125105, China ; 2.Department of Basic Teaching, Liaoning Technical University, Huludao 125105, China；

3.Software College, Liaoning Technical University, Huludao 125105, China;)

Abstract： To solve the vehicle routing problem, an improved ant colony algorithm is used to build a mathematical model . By reducing the number of ant colony routing and updating pheromone, the convergence speed and global search capability are improved. The experimental analysis and calculation shows that the application of ant colony algorithm can optimize the logistics and distribution lines, and effectively solve the problem of multi-loop transport. This research has reference value for controling the cost of logistics enterprises and raising the market competitiveness.

Key words：logistics network；ant colony algorithm；clustering analysis；vehicle routing problem

本文研究整车物流中具有代表性的运输车的0 引 言

配送规划问题，将选址问题和运输线路相结合物流

在经济全球化的进程中, 物流的现代化水平成配送网络优化应用于实践，对整车物流企业挖掘自为反映一个国家现代化程度和综合国力的重要标身运能、控制物流成本、提升服务质量与增强市场志，是国民经济在高起点上持续发展的基础动力，竞争力有重要意义。 是企业在激烈的市场竞争中把握竞争优势的有效方式。中国正日益重视物流科技的发展和应用，从1 物流网络优化问题 而降低物流成本，为企业和社会带来可观的经济效益。

1.1 物流网络定义 物流配送路径优化问题是典型的组合优化问

题，涉及多种学科，很多实际问题都可以归于这一从企业的微观角度出发，将物流网络定义概括类问题，应用前景广阔，所以一直成为运筹学与组为：商品从供应地向销售地移动的流通渠道。 合优化领域的研究热点问题。近年来，对车辆优化

通过对社会物流系统的抽象，形成了由物流节

调度问题的研究取得了很多有意义的成果，已经广[1]

点与运输线路连成的一个网络，如图 1 。网络中

泛用于生产、生活的各个方面，如报纸或货物投递、

的运输线路代表不同库存储存点之间货物的移动

出租车调度和包裹快递等。

路线，而物流节点就是指商品的储存点或需求点，

收稿日期：2010-03-16

基金项目：辽宁工程技术大学优秀青年基金资助项目（09260）

蚁群算法 网络优化

增 刊 任建华，等：蚁群聚类算法在物流网络优化中的应用 83 例如仓库、配送中心、物流中心、厂、供货商等。任意一对物流节点之间可能有多条运输线路相连，这些线路代表了不同的运输方式、不同的运输路线或不同的商品。物流节点也代表那些库存流动过程中的临时经停点，如物流中心。

工厂 物流中心 配送中心零售商

图1 物流网络结构 Fig.1 logistics network structure

模型，因此它在路径优化方面有着天然的优势，本文就是针对这种特点，研究一种基于蚁群算法的优化路径算法，利用蚁群算法隐含的并行性的特征引入了优化选路方法，通过减少基本蚁群算法中的选路次数，减小选路时间，提高算法的执行效率。 2.1 基本的蚁群算法

定义如下参数： 为模拟蚁群系统的寻径方法[4]，

m 蚁群中蚂蚁的数量； ηij 路径（ij）的能见度；

τij(t) t时刻在路径ij上的信息量；

k τij(t) 蚂蚁k在本次循环中留在路径ij上的

信息量；

kpij 蚂蚁k 在t时刻由位置i转移到位置j的概率； α 轨迹的相对重要性（α≥ 0 ）； β 能见度的相对重要性(β≥ 0 ）； ρ 信息素的持久性（0 ≤ρ＜ 1 ）； 1 –ρ 信息素的衰减度。

1.2 物流配送数学模型

一般配送车辆路径问题可描述如下： 线性规划能较好的求解平衡运输问题，因为可以将它归纳成如下线性规划模型[2]。 假设产地 i 运往销地 j 的单位运价为cij，i＝1,2,…,ｍ；j＝1,2,…,ｎ，x 为产地i至销地j的最佳运货量，z为最佳的总运费，则数学模型为

初始时刻，设所有路径上的信息素都相等,

蚂蚁k （k=1,2, ,m ）τij(0) = C ( C 是一个常数) 。

在运动过程中，根据各条路径上的信息素的大小以一定的概率pij(t)决定转移方向, pij(t)表示为

k

k

αββ

τij(t),s∈allower,j∈allowedk（2） kτis ηij(t)/∑sp(t)= 0

k

ij

minz=∑∑cijxij （1）

i=1j=1

mm

约束条件：

∑x

i=1

m

τij(t+n)=(1 ρ) τij(t)+ τij(t)

Q/Lk,若第k只蚂蚁在本次循环中经过（i，j）k τij= 0

ij

=bj,j=1,...,n

∑x

i=1

n

ij

=aj,i=1,...,n xij≥0

2.2 改进的蚁群算法

选路的次数和运算量决定基本蚁群算法的开销，如何减少蚂蚁搜索时间，提高算法执行效率，本文采用下面两种策略对蚁群算法进行优化[5]：

（1）减少选路计算量

在蚂蚁进行选路操作时，只计算距离当前客户点最近的前c个且该轮循环尚未完成配送任务的客户的选择概率。这借鉴了RBF 神经网络(Radial Basis Function Networks)的k-均值聚类算法,这可以减少选路计算量，加快算法搜索效率。 （2）信息素更新方法

因此，式（1）及其约束条件刚好构成了线性规划问题的数学模型，用线性规划方法求解，会得最优解，即满足产地可能供给量和销地需求量前提下，使总运费最小。

2 蚁群算法

蚁群算法是通过模拟自然界中蚂蚁集体寻径的行为而提出的一种基于种群(population based) 的启发式仿生进化算法. 蚁群算法最早成功地应用于解决著名的旅行商问题( TSP) . 它采用分布式并行计算机制,具有较强的鲁棒性。

蚁群算法原型本身就是一个寻找最短路径的

[3]

τij=(1 ρ)τij+ρ τij,ρ∈(0,1)

τij=Q/Lgb

（3）

式中，Lgb是当前全局最优解的路线长度；Q是常量；

蚁群算法 网络优化

84 辽宁工程技术大学学报（自然科学版） 第29卷

ρ是信息素的挥发系数

3 实验与计算

例 配送中心用2辆汽车对6个客户配送货物。设汽车的载量为6 000 kg，每次配送的最大行驶距离为40 km。配送中心与客户、客户与客户之间的距离见表1（0表示物流中心，1~6表示6个客户点ID）：

表1 配送中心、客户之间距离（单位：km） Tab.1 distance between distribution center and customer

（Units：km）

0 1 2 3 4 5 6

仅有一次找到最优解65.5 km。

然后再用改进后的蚁群算法，参数如下：蚁群共20只蚂蚁，迭代次数50次，取α=0.1，β=2，ρ=0.3，10次计算均找到最优解65.5 km。

4 结 论

本文运用改进的蚁群算法通过对物流网络配送车辆调度问题进行优化，可以看出，蚁群算法是成功的，在物流配送车辆路径问题上的应用是可行的，并取得了比较理想的效果。改进后的蚁群算法可以快速有效地求得优化物流配送路径的最优解或近似最优解。本文的研究工作，对蚁群算法及物流配送路径优化问题的研究有一定的参考价值，对整车物流企业挖掘自身运能、控制物流成本、提升服务质量与增强市场竞争力有重要意义。 参考文献：

[1] 张亚峰. 商品车物流配送网络优化研究[D]. 长春: 吉林大学，2009. [2]Ahmad Alshamranl,Kamlesh Mathur Ronald H.Ballou. Reverse

logisties:simultaneous design of delivery routes and returns strategies[J]. ComPuters&Operations Research,2007,34(2):595-619.

[3] 唐连生,程文明,张则强,钟 斌. 基于改进蚁群算法的车辆路径仿真

研究[J]. 计算机仿真, 2007(4):262-264.

[4] 刘志勋,申金升,柴跃廷. 基于自适应蚁群算法的车辆路径问题研究

[J]. 控制与决策, 2005, 20 (5) : 562 - 566.

[5] 柳 林，朱建荣. 基于遗传算法的物流配送路径优化问题的研究[J].

计算机工程与应用,2005,41(27):227-229.

0 0 3 5.5 7.5 9 20 10

1 4 0 6. 4 10 5 7.5

2 6 6.5 0 7.5 10 10 7.5

3 7.5 4 7.3 0 9 5 9

4 9 10 10 10 0 10 7.5

5 20 5 10 5 10 0 7

6 10 7.5 7.5 9 7.5 7 0

客户的需求见表2：

表2 客户货物需求量（单位：t）

Tab.2 customer demand for goods （Units：t）

客户ID 1 2 3 4 5 6

需求量 1 2 1 2 1 4

首先利用基本蚁群算法计算，设蚁群大小为20，迭代次数50次。10次计算的平均结果为70.6 m，

本文来源：https://www.bwwdw.com/article/j0i4.html