基于改进蚁群算法的物流网络

杨平乐，崔晓燕，刘树森

(1.江苏科技大学张家港校区基础教学部，江苏张家港 215600)

(2.东南大学交通学院，江苏南京 210096)

(3.中山大学信息科学与技术学院，广东广州 510006)

基于改进蚁群算法的物流网络

杨平乐1，崔晓燕2，刘树森3

(1.江苏科技大学张家港校区基础教学部，江苏张家港 215600)

(2.东南大学交通学院，江苏南京 210096)

(3.中山大学信息科学与技术学院，广东广州 510006)

文中将受容量限制的单分配轴-辐式网络抽象为一个三次变量的混合整数线性规划模型方程;提出了一种改进的蚁群算法，将6种局域搜索算子加入算法中，因此具有较高的全局搜索能力和局部搜索能力;同时提出“解对”的概念，对问题的构成进行分解优化，转化为确定问题，切实使本问题符合蚁群算法使用的前提和优势;最后，使用澳大利亚邮政的数据进行选址仿真实验，验证此算法模型在该应用中的求解效率和计算稳定性.

轴-辐式网络;改进蚁群算法;解对;受限枢纽选址

轴-辐式网络往往来描述这样一类问题［1］:在一个包含多个点的图集中，所有的点都发送和接受货物.在这种问题的某一个子集中，所有货物的流动都必须经过其中某个特殊节点，文中称这个特殊节点为枢纽点，称该子集中的其他点为分配给该枢纽点的节点.

轴-辐式网络越来越多地应用于邮政、航空和电信等领域，是现代化物流系统的模型［2］.在设计物流系统时，物流枢纽选址需要模型化、数量化，枢纽点的合理选址能够减少货物运输费用，降低运营成本，促进生产和消费两种流量的协调配合.一个枢纽点的存在使得货物传输过程中重新查找路径选择成为可能，同样也引起了网络构建成本和运输成本的变化.轴-辐式网络在实际的物流网络设计中，其枢纽点的容量不可能无限制，因此研究容量受限的轴-辅式网络更有实际意义.文中将研究枢纽容量受限的单分配轴-辐式网络选址问题(capacitated single allocation hub location problems，CSAHLP)的解决策略.

枢纽选址问题是一个多目标、多约束的组合优化问题.国内外学者针对物流模型与算法展开了一系列的研究，建立了一系列的选址模型与算法，如重心法、数值分析法、模拟退火算法和遗传算法等［3-7］.但这些方法应用的侧重点有所不同，对于求解规模较大的实际问题存在困难.

文中研究了澳大利亚邮递系统枢纽选址问题，提出了一种改进的蚁群算法求解该问题，确定系统成本最低的枢纽点和结点的位置、规模和数量.文中将改进蚁群算法用来求解CSAHLP问题.

1 枢纽容量受限的轴-辐式网络设计模型

CSAHLP问题其实是枢纽选址问题，也可表述为物流中转站选址问题(中转站容量受限)，枢纽选址问题是轴-辐式网络设计的关键，主要包括3方面内容:确定枢纽节点的数量、枢纽节点的选址以及将非枢纽节点分配给枢纽节点.

求解整个网络运行费用成本最低是方程的目标函数，此费用包括枢纽节点固定设施费用和总的运输费用之和.

综上所述，可用三次线性方程描述CSAHLP问题的模型，如式(1).

2 蚁群算法模型

可以这么来看蚁群算法:基于解空间参数化概率分布模型的搜索算法框架［8］，在该算法中，求解空间参数化概率，信息素就是模型的参数，因而信息素模型就是这种参数化概率分布模型.基于模型的搜索算法中，通过在一个解空间参数化概率分布模型上的搜寻产生可行解，用产生的解来更新此模型的信息素，促使在新模型上的搜索能够聚集在高质量的解搜索空间内［9-12］.

具体算法步骤及参数设定如下:

1)在每个周期的循环中，蚁群中的每个蚂蚁解决问题时，他们一边移动，一边构成自己的解，直到蚂蚁构成所有的解.

2)在每只蚂蚁完成求解时，根据解的构成进行信息素更新.蚂蚁通过信息素交换各自的解.通过信息素的更新，使得解空间趋向优化区域.下一只蚂蚁的移动方向和移动方向的概率，以及以后蚂蚁选择移动路径，由更新之后的信息素来决定.

更新所用的公式如下所示:

式中q0∈(0，1)是常数，q∈(0，1)是随机数，τgh(i，j)为解构成部分(i，j)的信息素，ηg(i，j)为解构成(i，j)启发式因子，α为蚂蚁在爬行过程中积累的信息量在蚁群搜索过程中的重要程度，β为启发式因子的相对强弱.Jgh(r)为被第g个蚁群中的第h个蚂蚁在步骤r中能加入到解构成中.在下一步之前随机产生q.如果q的值不大于常数q0，就从余下全部可行的解构成之中找出［τgh(i，j)］α·［ηg(i，j)］β最大的那个解构成，也就是接下来要被选择的解构成;如果q的值大于常数q0，则按方程(9)计算出来的概率来选择下一个解构成.

4)每一个周期循环中，找到达到最优目标函数值的蚂蚁，然后由其更新关于解构成的全局信息素，使用的公式如下:

3 用改进的蚁群算法解决CSAHLP的策略

3.1 改进蚁群算法的设计

蚁群算法固有的容易陷入局部最优的缺点在CSAHLP问题中体现得比较明显，相比于TSP问题来说，因为CSAHLP问题里蚁群选择路径的多样性导致其运算过程中容易陷入局部最优.

在用蚁群算法解决CSAHLP问题时引入了禁忌表搜索方法，该算法显著收缩每一步解空间的分布，能够加快收敛，可以在有限次循环中得到较优解.同时采用与局域搜索策略相结合的方法，以达到避免陷入局部最优，同时加快算法的收敛速度.利用多只蚂蚁以枢纽选址模型的总成本最低为依据划分枢纽点和节点，为更好地表述想要的结果，文中提出解对的概念，在CSAHLP问题中，把一个节点i和其对应的枢纽点k称为一个解对，特别的，为了下面解的有序性将枢纽点k和枢纽自身k也称为一个解对.

举例:对一般情况，解的构成假设有i，m通过k，l向j运送货物，可用图1描述.

有了解对的概念后，文中把CSAHLP问题的解分解为多个离散解对的构成.经过解对模型处理后可以得到以下数个解对(图2).不难看出，在CSAHLP问题中，有多少个城市对就有多少个解对，解分解为解对后，将此问题转变为确定问题，便于算法求解.

图1 解的描述Fig.1 Solution composition

图2 解对Fig.2 Solution pair

改进的蚁群算法处理CSAHLP步骤如下.

2)下面开始寻找解对:每只蚂蚁挑选一个随机化的城市序列，开始构造解对，从第一个城市开始构造解对，在每一个城市上kj蚂蚁都运用伪随机比例选择规则，使用式(8，9)寻找与其关系最强的城市构成ksp，文中用数组链接的方式标记为comba［kj］= kjsp，特别注意的是，标记完后需要把 ksp的 comba［kjsp］标记成comba［kjsp］=kjsp，以防止后续运算中ksp指向其他别的城市，即枢纽不再和已知以外的点构成任何解对.找到解对后，把Cap(ksp)容量减去Weight(kj)，即Cap(ksp)=Cap(ksp)-Weight(kj)，体现容量限制的约束.每只蚂蚁都根据此步骤构造自己的解.

3)计算目标函数值:每只蚂蚁爬行完途中所有点后，对解对进行整理，依据式(1)计算出目标函数值L.

4)局部信息素更新:每只蚂蚁计算完目标函数值L后，对其解对进行局部信息素更新.

5)全局信息素更新:每个周期循环中目标函数值L最小的那只蚂蚁将根据自己的解对进行全局信息素更新.

6)连续多次计算，如结果之差小于ε，则保存解，并清空禁忌搜索表，否则转向步骤2.

3.2 局域搜索策略

蚁群算法需与局域搜索策略相结合才能更好发挥作用.文中引入局域搜索算法以避免陷入局部最优，并加快收敛速度.文中参照文献［13］提出的6种局域搜索算子进行运算.在介绍这6种局域搜索算子前要定义组团，组团是指划分节点群，群内含有1个枢纽节点和被分配给该枢纽的非枢纽节点，其中枢纽节点被分配给其自身.以下是6种局域搜索算子:

1)重置枢纽.将任一组团内另一随机选取的节点置为新枢纽节点，该转换应用于那些至少包含 1个非枢纽节点的组团.

2)重置节点.将任一组团的1个非枢纽节点分配给另一随机选取的组团.尤其是当某个组团内只包含1个节点时，那么将该节点分配给其他组团，就减少了组团的数量.

3)设置新枢纽.将任一随机的节点设为枢纽节点，生成只有1个节点的新组团.

4)合并组团.将某个组团内的所有节点分配给另外1个随机选取的组团内的枢纽节点，实现了这2个随机选取的组团合并为1个组团.

5)分裂组团.将1个组团内的部分节点分配给另一随机的非枢纽节点，分裂为2个组团.

6)交换节点.将2个组团内的非枢纽节点对换分配给对方组团的枢纽节点.

所有这些局域搜索算子在运算过程中都受容量约束限制，且对于每个蚁群，应在局域搜索完成后进行本身蚁群算法的全局更新.如上局域搜索算子的运算遵循最先允许准则［14］，某个局域搜索算子带来更合理的目标函数值，那么就将解更新.

4 仿真实验与结果分析

文中使用澳大利亚邮政数据对此方法进行了验证.这是目前应用于CSAHLP问题的基准数据库，含澳200个邮政中心的坐标、包裹数量、运输费用、固定设施费用以及节点容量约束，设定折扣系数χ为3，α为0.75，δ为2.固定设施费用的类型被分为紧型(T型)和松型(L型)，在固定设施费用为T型的问题中，流量较大的节点其固定建设费用也较高，使得这些节点难以被设定为枢纽，因此这类问题难于求解.对于L型的问题则不会如此.同时，容量约束也被分为紧型(T型)和松型(L型)，用来表示容量约束的强弱程度.所以，相同规模的问题可被分为4种类型:LL，LT，TL和TT型.文中分别针对节点数为10，20和25的情况进行仿真试验.

表1 计算结果Table 1 Calculation results

表2 计算结果对比Table 2 Comparisons of results

从实验结果可以清晰看到枢纽点确定情况和节点分配情况，计算结果表明:对于较难求解的25个节点的双紧约束问题，算法运算时间为1.01s，运算偏差不大于0.12%，远低于已有的其他算法，具有更优的求解效果，很好地证明了这种解决方案的可行性和可靠性.25TT以下的数据各次结果都是经过数次运行得到的最优解，且与已被证明的最优解相同.此算法在设计过程中加入了一些合并组团的方法，随机合并一些枢纽点，减少了解的个数.

5 结论

文中利用蚁群算法在求解组合优化问题上的优势，最终的解以解对的形式构造，将6种局部搜索算法嵌入各并行计算的蚁群群组内，以增强蚁群算法对最优解的搜索能力，并结合AP数据库进行了算例仿真试验.实验结果表明:改进的蚁群算法的确可以较好用于CSAHLP问题中，这样解决了很多复杂的难以计算的选址问题.其本身是概率选择算法，具有其他的固定算法所不能比拟的速度和便捷的优势.结合其他的一些成熟算法，应用前景将极为广泛，能够适应物流配送的多样化发展.

References)

［1］ Randall M.Solution approaches for the capacitated single a location hub location problem using ant colony optimization［J］.Computational Optimization Applications，2008，39:239-261.

［2］ 乔彦平，张骏.基于一种改进遗传模拟退火算法的TSP求解［J］.计算机仿真，2009，26(5):205-208.

Qiao Yanping，Zhang Jun.Traveling salesman problem solving based on an improved genetic simulated annealing algorithm［J］.Computer Simulation，2009，26(5): 205-208.(in Chinese)

［3］ 李阳.轴辐式网络理论及应用研究［D］.上海:复旦大学，2006.

［4］ 刘洪，葛少云，李慧.基于硬约束调节的改进粒子群无功优化［J］.天津大学学报，2009，42(9):796-801.

Liu Hong，Ge Shaoyun，Li Hui.Reactive power optimization based on improved particle swarm optimization algorithm with hard restriction regulation［J］.Journal of Tianjin University，2009，42(9):796-801.(in Chinese)

［5］ Alumur S，Kara B Y.Network hub location problem: the state of the art［J］.European Journal of Operational Research，2008，190(1):1-21.

［6］ Lee Der-Horng，Dong Meng.A heuristic approach to logistics network design for end-of-lease computer products recovery［J］.Transportation Research Part E，2008，44(3):455-474.

［7］ Galski R L.Application of a GEO+SA hybrid optimization algorithm to the solution of an inverse radiative transfer problem［J］.Inverse Problems in Science＆Engineering，2009，17(3):321-334.

［8］ 张亚明，史浩山，刘燕，等.WSNs中基于蚁群模拟退火算法的移动Agent访问路径规划［J］.西北工业大学学报，2012，30(5):629-635.

Zhang Yaming，Shi Haoshan，Liu Yan，et al.A better itinerary analysis for mobile agent(MA)through using ACA-SAA algorithm in wireless sensor networks［J］.Journal of Northwestern Polytechnical University，2012，30(5):629-635.

［9］ Srivastava S K.Network design for reverse logistics［J］.The International Journal of Management Science，2008，36(4):535-548.

［10］ 王保华，何世伟.不确定环境下物流中心选址鲁棒优化模型及其算法［J］.交通运输系统工程与信息，2009，9(2):69-74.

Wang Baohua，He Shiwei.Robust optimization model and algorithm for logistics center location and allocation under uncertain environment［J］.Journal of Transportation Systems Engineering and Information Technology，2009，9(2):69-74.(in Chinese)

［11］ Yu Hongtao，Xue Jingling，Wei Huo，et al.Level by level:making flow-and context-sensitive pointer analysis scalable for millions of lines of code［C］∥Proc of the 8th Annual IEEE/ACM International Symposium on Code Generation and Optimization.New York:ACM Press，2010:218-229.

［12］ Pearce J，Kelly P J，Hankin C.Efficient field-sensitive pointer analysis for C［J］.ACM Trans on Programming Languages and Systems，2007，30(1):37-42.

［13］ 秦进，史峰.物流设施选址问题的双层模拟退火算法［J］.系统工程，2007.25(2):36-40.

Qin Jin，Shi Feng.Bi-level simulated annealing algorithm for facility location［J］.Systems Engineering，2007，25(2):36-40.(in Chinese)

［14］ Costa M D G，Captivo M E，Climaco J.Capacitated single allocation hub location problem-A bi-criteria approach［J］.Computers and Operations Research，2008，35(11):3671-3695.

(责任编辑:童天添)

Logistics network based on improved ant colony algorithm

Yang Pingle1，Cui Xiaoyan2，Liu Shusen3
(1.Department of Basic Courses，Zhangjiagang Campus，Jiangsu University of Science and Technology，Zhangjiagang Jiangsu 215600，China)
(2.School of Transportation，Southeast University，Nanjing Jiangsu 210096，China)
(3.School of Information Science and Technology，Sun Yat-sen University，Guangzhou Guangdong 510006，China)

Capacitated single allocation hub-and-spoke networks can be abstracted as a mixed integer linear programming model equation with three variables.By introducing an improved ant colony algorithm which has six local search operators and the"Solution Pair"concept to decompose and optimize the composition of the problem，it can become specific and more effective to meet the premise and advantages of using ant colony algorithm.Finally，location simulation experiment is made with Australia Post data to demonstrate that this algorithm has high efficiency and stability for solving this problem.

hub-and-spoke network;improved ant colony algorithm;solution pair;capacitated hub location

TP15

A

1673-4807(2014)01-0166-05

10.3969/j.issn.1673-4807.2014.02.013

2013-09-03

国家自然科学基金资助项目(50575043，60573006)

杨平乐(1983—)，男，讲师，研究方向为人工智能、量子密码.E-mail:plyoung@126.com