李 眩,吴晓兵,刘 琼

(铜陵职业技术学院 经贸系，安徽 铜陵 244061)

0 引 言

物流作为一个新兴服务行业，正在全球范围内迅速发展，给生产、生活及国际贸易带来重大影响.其中，物流配送中心在物流系统中举足轻重，是物流系统的中心枢纽，连接着货物供应和配送需求2个重要的物流节点，通过大规模采购和高效配送方式能有效降低企业的运营成本，为企业带来更大的利润.物流配送中心选址问题[1]是物流系统的核心问题.物流配送中心在空间上的分布和选址必须合理和科学，需考虑多种因素对整个物流系统运行效率和效益的影响.因物流配送中心选址问题存在非线性、复杂度高、约束条件多且相互之间难以协调，传统数学模型难以求得全局最优解.由于基本蚁群算法[2]有结构简单、易实现、采用群体并行搜索方式计算求解且求解效率较高的优点，本研究应用变异和自适应的精英策略对基本蚁群算法进行改进，将其应用于带约束条件的物流配送中心选址问题中，并在MATLAB中用仿真实例验证其合理和可行性.

1 物流配送中心选址问题

物流系统中，物流配送中心的任务就是根据客户需求及时、准确和经济地配送货物，决定着物流系统的运作效率.由于物流配送中心在空间上的位置对于物流活动具有十分重要的影响，合理科学的物流配送中心选址不仅可以大幅降低建设成本，还可以有效促进物流系统的均衡良性发展，因此对物流配送中心选址问题的研究具有理论和实际意义.物流配送中心选址问题属于最小成本问题[3]，既要考虑前期建设成本，又要考虑后期配送成本及商品流通加工成本，是复杂度较高且带有多约束的非线性优化问题.对于物流配送中心选址问题的数据模型存在如下假设：1个客户仅由1个物流配送中心供应，物流配送中心的容量能满足客户的需求；根据2个点的坐标计算出的直线距离近似看成此2个点间的运输距离；在允许的配送范围内，配送车辆能在一定的时效范围内将货物配送给客户，故配送的时效性约束可以转化为最大允许配送距离来描述；配送的客户都在一定范围内，即客户的坐标有上限与下限约束.本数学模型的设计思路是，给定1个地址集合，从中选出满足要求的地址建立物流配送中心，使得选出的地址建立物流配送中心与各需求点组成的配送系统总成本最小.

在区域范围内拟为n个客户建立1个物流配送中心，客户i的坐标为(xi,yi)，需求量为ωi，最大允许配送距离为D.确定物流配送中心的坐标为(X，Y)，单位货物运输成本为p(单位：元/(t·km))，g表示商品在物流配送中心的单位流通加工费用.将配送区域划分为m个子区域，对应子区域内物流配送中心的建设成本为Cj，此时物流配送中心的寻址问题就简化为在满足最大允许配送距离的前提下使得总成本f(包括建设成本、商品在物流配送中心的流通加工总费用及后续配送成本)最小.

物流配送中心选址问题的数学模型描述如下：

目标函数：

(1)

约束条件：

(2)

Ia≤xi≤Ib,Ua≤yi≤Ub

(3)

ωi≥0,D≥0,p≥0,Cj≥0

(4)

上述式中，Ia与Ib为选址问题m个可行解坐标xi的下限与上限，即下限Ia=[min(xi)]，上限Ib=[max(xi)]；Ua与Ub为选址问题m个可行解坐标yi的下限与上限，即下限Ua=[min(yi)],上限Ub=[max(yi)].式(1)表示后期运营和前期建设总成本最低，然而实际中仅考虑最低运输周转量或后期成本最低这个条件是不够的，因为有些紧急情况下一些货物的配送有时效性要求，比如抢险救灾物资、生鲜冷链产品、紧急医护产品等货物；式(2)表示每个客户的配送距离必须在允许范围之内，通过此约束条件将时效性要求转变为配送距离要求，利于后期编程的简化；式(3)表示配送的客户点都分布在一定的地理范围内；式(4)表示各参数在实际应用中的非负要求.式(1)～式(4)共同构成满足时效性要求的物流配送中心选址问题的数学模型，表示满足时效性要求下总成本最小的选址目标.

对于物流配送中心选址这种复杂非线性问题的求解，由于传统数学算法求解效率低或很难求得最优解，启发式智能算法被应用来求解该类问题.虽然传统智能算法有早熟收敛等缺点，在求解物流配送中心选址问题时会出现求解精度不高而导致物流系统配送效率低的情况，但通过适当改进和优化，算法的效率和全局收敛能力会得到显著提高.改进后的算法完全可以求解多约束条件且复杂非线性的诸如物流配送中心选址的实际问题.

考虑到基本蚁群算法具有调整参数少、原理较简单且易实现的优点，本研究尝试应用基本蚁群算法来求解物流配送中心选址问题，但发现基本蚁群算法和其他智能算法一样易早熟收敛且求解精度不高.为此，本研究引入变异和自适应调整机制的精英策略对基本蚁群算法进行改进，并用于物流配送中心选址问题以提高问题的求解精度.

2 带变异的自适应精英改进蚁群算法

2.1 基本蚁群算法

基本蚁群算法是受自然界蚁群集体觅食行为的启发而诞生的仿生智能算法.蚂蚁个体行为很简单，但由个体组成的蚁群却能完成远超个体能力的复杂任务，个体之间通过信息素来进行信息的传递，共同协作完成复杂任务.蚁群有能力在没有任何先行提示情况下找到从巢穴到食物的最短路径，并能跟随环境变化搜索新的路径，此处体现了一种信息的正反馈现象[4]，即，某路径上走过的蚂蚁越多，此路径上蚂蚁留下的信息素就多，对后面蚂蚁的吸引力就越大，就越使其向信息素强度高的方向移动，从而通过此种信息交流达到搜索食物的目的.蚂蚁具有的智能行为得益于蚂蚁的简单行为规则，该规则让蚂蚁具有多样性和正反馈能力.在蚂蚁觅食时，多样性使蚂蚁不会走进死胡同导致无限循环，是蚂蚁的一种创新能力；正反馈使优良信息保存下来，是蚂蚁的一种学习强化能力.多样性与正反馈的巧妙结合使蚂蚁具有智能行为.如果多样性过剩，蚂蚁过于活跃，则蚁群会有过多的随机运动而陷入混沌状态；如果多样性不够，正反馈过强，将导致蚁群僵化，当环境发生变化时蚁群不能做相应调整[5].受蚁群觅食寻找最短路径行为的启发，模仿蚁群觅食行为的基本蚁群算法被提出来，其应用从最初的旅行商问题扩展到了网络路由、车辆调度、路线航迹规划及集成电路布线设计等领域.基本蚁群算法的出现为解决复杂困难的系统优化问题提供了新的求解思路.

基本蚁群算法的蚂蚁个体被表征为优化问题的一个潜在可行解，在众多潜在可行解构成的解空间中根据适应度不断进化迭代，直至算法收敛得到最终的全局最优解.基本蚁群算法体现了蚂蚁觅食行为中的自催化机制:当一个问题的较优解附近聚集的蚂蚁较多，其留下的信息素也增多，则蚂蚁移向该区域的概率就越大，反过来也增强了该区域的信息素强度.这种自催化机制利用信息作为反馈，通过对较优解或较优方案的自增强，使得问题的解向着全局最优的方向不断进化[6].基本蚁群算法中信息素和真实蚁群一样存在着挥发，使得蚂蚁逐渐淡忘过去而不受历史经验的过分约束，同时基于概率的前进决策策略使蚂蚁向较优区域移动，从而逐步找到问题的最优解或最优方案[7].

将基本蚁群算法应用于优化问题的基本思路如下：蚂蚁个体表示待优化问题的潜在可行解，整个蚂蚁群体构成待优化问题的解空间.在较优解上，蚂蚁释放的信息素量较多.随着时间的推进，较优解上累积的信息素浓度逐渐增高，较优解位置聚集的蚂蚁数量也愈来愈多.较差解上遗留的信息素浓度会逐渐减少，直至最后被遗忘.信息素的挥发机制使得蚂蚁个体在移动时不会过多局限于以往蚂蚁留下的历史经验，最终，整个蚁群中的蚂蚁个体会在正反馈的作用下集中到最优解[8]上.

基本蚁群算法求解优化问题的实现过程如下：设置蚁群蚂蚁数Ant、迭代次数G、信息素挥发参数Rho、转移概率阈值Po及算法的搜索范围.搜索范围根据具体问题设定.蚂蚁数Ant必须根据问题规模来设置，若过小则不能保证群体的多样性，以致算法性能很差;若过大，尽管可以增加寻优的效率、阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长.基本蚁群算法对每只蚂蚁位置进行随机初始化，并依据问题定义的适应度函数计算每只蚂蚁对应的适应度值Tau(i)，进而求出蚁群当前最佳适应度值Tau(BestIndex).基本蚁群算法采用以概率为基础的状态转移策略，而蚂蚁个体依照以适应度值计算得来的状态转移概率选择前进的方向.

每只蚂蚁的转移概率如式(5)所示：

P(NC,i)=(Tau(BestIndex)-Tau(i))/

Tau(BestIndex)

(5)

式中，NC表示当前的迭代循环次数;i表示蚁群中第i只蚂蚁个体;P(NC,i)表示第NC次循环中第i只蚂蚁的转移概率.当蚂蚁相对蚁群当前最佳位置较远时，P(NC,i)值将大于转移概率阈值Po，则蚂蚁应该离开当前位置区域去展开全局探索以避免陷入局部最优；当蚂蚁相对蚁群当前最佳位置较近时，P(NC,i)将小于转移概率阈值Po，则蚂蚁在当前位置邻域展开局部搜索.每只蚂蚁限定在解空间范围内移动，如果超过边界条件，则为了防止蚂蚁逃出解空间，按如下方法处理：X(i,j)>Xjmax时，X(i,j)=Xjmax；X(i,j)

根据P(NC,i)更新蚂蚁个体的位置、适应度值及蚁群最优的适应度值，随着时间的推移，如果蚁群找到当前较优解，则用当前较优解替换以前的解，这样以前的解将被遗忘.如果当前解较差，则以前的解被保留，解的信息量会因蚂蚁留下的信息素得到加强，且可行较优解的信息素含量按式(6)调整：

Tau(i)=(1-Rho)*Tau(i)+Macro(i)

(6)

式中，Tau(i)表示蚁群第i只蚂蚁找到的解的原有信息素含量;Rho表示信息素的挥发度；Macro(i)为当前循环中第i只蚂蚁找到解对应的适应度值，如此不断进化迭代直至找到问题的最优解.信息素的应用使得基本蚁群算法具有较强的自我学习能力，可根据环境信息素浓度的变化和过去的行为结果对环境进行调整，从而实现算法求解能力的再进化.

2.2 带变异的自适应精英改进蚁群算法

基本蚁群算法与其他智能算法一样，解决多维复杂优化问题时易陷入局部最优.应用自适应策略改进基本蚁群算法是重要的思路之一.通过自适应策略改变算法信息素挥发度参数，可以在保证收敛速度的同时提高全局收敛的能力.当问题规模比较大时，由于信息素挥发参数的存在，那些从未被搜索到的候选解信息量会减少至接近于0，算法的全局搜索能力降低.另外，当信息素挥发度参数较小，较优解留存的信息量比较大，以前搜索过的解被重新选择的可能性过大，则算法的全局搜索能力也会被影响.若通过增大信息量挥发参数与减少信息量的留存来提高算法的全局搜索能力，则算法的收敛速度将降低[9].因此，算法在陷入局部极值而停滞时，可以自适应增大信息素挥发参数，降低当前局部最优解的信息素浓度，极大降低当前局部最优解被重新搜索到的可能性，使得算法能重新自动搜索其他候选可行解区域，算法的全局收敛能力得到提高.

信息素挥发参数的自适应调整如式(7)所示:

(7)

式中，Rho(t)表示第t代信息素的挥发参数；a为自适应调整系数.当a取值在1.2至2之间，算法效率[10]较好.在a取值为1.5时，每次循环后信息素调整规则式(6)可改为式(8)：

Tau(i)=(1-Rho(t))*Tau(i)+Macro(i)

(8)

带精英策略的改进蚁群算法使用了遗传算法中的精英策略.遗传算法中，将当前代中最适应个体的基因进行突变和重组产生下代的个体，以此将当前最优个体的优良基因最大限度遗传到下代[11].类似地，改进蚁群算法为了使目前所找到的最优解在下代循环中对蚂蚁个体更具有吸引力，在每次循环后给予最优解以额外的信息素增量，从而突出该解的优良性.精英策略将蚂蚁的搜索行为集中到最优解附近，提高了解的质量和收敛速度，从而改进了算法的性能.按照此策略找到优质解的蚂蚁称为精英蚂蚁.

改进蚁群算法中信息素的更新规则如式(9)所示：

Tau(i)=(1-Rho(t))*Tau(i)+Macro(i)+Macro(i)/sum

(9)

式中，sum为蚁群所有蚂蚁找到的解的适应度值之和；Macro(i)/sum为给予优质解额外的信息素增量.如果第i只蚂蚁为非精英蚂蚁，找到的解不是蚁群当前最优解，其信息素仍按式(8)更新.如果第i只蚂蚁为精英蚂蚁，找到的解为蚁群当前最优解，解的信息素按式(9)更新.

从上述信息素更新的2种情况来看，精英蚂蚁找到的解的信息素含量除按正常方式更新外，另外还按照解的质量额外给信息素含量1个增量，提高了该解对蚂蚁个体的吸引力.这样，使得最优解和普通解的信息素含量差异进一步增大，将引导蚂蚁的搜索行动向最优解的领域靠近，增强了对蚁群搜索行为的指导性.

改进蚁群算法的当前最优解因为所含的信息素在当前最高，对蚂蚁个体的移动行为有很大的影响，所以当算法陷入局部最优时，蚁群当前最优适应度值(最优函数值)不再发生变化.本研究对蚁群当前最优适应度值(问题的当前最优解)给予了随机扰动使其产生突变，从而改变蚁群中蚂蚁的移动行为，增强了算法全局寻优能力，也避免了算法过早收敛.

改进蚁群算法实现变异操作的描述如下：

Tau_Best(NC)=Tau_Best(NC)+(rand(1)+100)

(10)

式中，Tau_Best(NC)为第NC代蚁群找到的当前最优解(即蚁群当前最优适应度值)；rand(1)为0到1的随机数.

只有算法陷入局部最优停顿时，蚁群当前最优适应度值才发生变异，因此如何判断算法陷入局部最优显得尤为重要.算法停顿时，表现为蚁群当前最佳适应度值与前几次最佳适应度值相等，以此来构造判断条件，如式(11)所示：

NC>n&&NC<300&&Tau_Best(NC)==

Tau_Best(NC-n)

(11)

式中，NC表示当前迭代次数;n表示参照当前的循环迭代次数.本研究中n取值为5，即发生5次循环迭代，此时算法求得的蚁群当前最优适应度值没有明显改进，即认定算法处于停顿.

3 物流配送中心选址问题求解

为了验证带变异的自适应精英改进蚁群算法应用于求解实际中比较复杂且多约束问题的有效性，本研究以物流配送中心选址问题为例，采集8位客户的位置坐标.各客户位置坐标及其后续物资需求量如表1所示.

表1 客户位置坐标与物资需求量

若在位置坐标(x,y)满足x[0,800]且y[0,800]的范围内建设物流配送中心，则前期建设成本、商品流通加工成本及后期配送总成本将最小.为了满足物流配送的时效性要求，约定配送中心到客户间的配送距离不得大于500 km，配送价格设定为10元/(t·km).商品在配送中心的单位流通加工成本为150元/t.在不同的子区域内，建设成本会不一样.若位置坐标(x,y)在x[20,400]且y[20,400]范围内，建设成本为500万元；若位置坐标(x,y)在x(400,800]且y(400,800]范围内，建设成本为650万元；若位置坐标(x,y)在x[20,400]且y(400,800]范围内，建设成本为480万元；位置坐标(x,y)在x(400,800]且y(20,400]范围内，建设成本为370万元.本研究根据给定的约束条件应用提出的改进蚁群算法优化模型确定物流配送中心的最优位置坐标，使其总运作成本最少.

本研究提出的改进蚁群算法与基本粒子群算法(惯性权重与加速因子均为常数)、基本蚁群算法(挥发参数为常数、无变异且信息素按正常无差异更新)的求解结果进行比较，得出适应度函数值变化和物流配送中心最优选址结果如图1～图4所示.

图1 基本粒子群算法适应度函数值变化曲线图

图2 基本蚁群算法适应度函数值变化曲线图

图3 改进蚁群算法适应度函数值变化曲线图

图4 物流配送中心最优选址结果

基本粒子群算法求解的最佳坐标为(283.715 1,599.999 9),运行时间为0.843 s.基本蚁群算法求解的最佳坐标为(523.477 8,577.896 6),运行时间为1.733 s.本研究提出的改进蚁群算法(即带变异的自适应精英改进蚁群算法)用于求解物流配送中心选址问题时收敛较快，求得最优解的运行时间为1.344 s，最佳坐标为(541.693 6，598.218 2)，建设成本、后期配送成本及流通成本等最少总成本为415 298万元.基本粒子群算法收敛速度虽然很快,但不能收敛于全局最优解.从适应度函数值变化看，基本蚁群算法收敛速度极慢，收敛时间也最长，而且不能收敛于全局最优解.综上所述，用带变异的自适应精英策略改进蚁群算法非常成功地求解了物流配送中心选址问题.本研究通过此改进蚁群算法求解的最优物流配送中心选址方案能满足每位客户的时效性和配送容量要求，而且显著地将总成本降低到最少.由此可知，采用带变异的自适应精英策略改进蚁群算法解决物流配送中心选址问题取得了较好的结果，在实际中具有十分积极的意义.

4 结 语

本研究通过物流配送中心选址问题数学模型的应用，验证了选址数学模型的正确性和带变异的自适应精英改进蚁群算法的合理性.改进蚁群算法解决了复杂优化问题的有效性，改善了基本蚁群算法易陷入局部最优且鲁棒性差的缺点，在物流配送中心选址问题的求解中体现了较好的动态观测性和收敛性，是一种解决优化问题及进行优化决策的好算法，具有较好的应用前景.