基于变异和动态自适应 的物流配送中心选址模型

李 眩，吴晓兵，刘 琼

（铜陵职业技术学院经贸系，安徽铜陵 244061）

随着世界经济的快速发展及现代科学技术的进步，物流作为国民经济的一个新兴服务行业形态，正在全球范围内迅速发展，给生产、生活及其国际贸易带来重大影响。配送中心是物流系统的中心枢纽，在很大程度上决定着物流网络结构，连接着货物供应和配送需求两个重要的物流节点，在物流系统中起着承上启下的重要作用〔1〕。物流配送中心在空间上的分布和选址必须合理和科学，其选址优化问题一直是多数企业的重要战略规划问题，也是学者们关心和关注的问题，因其存在非线性、复杂度高、约束条件多且相互之间难以协调，传统数学模型难以求得全局最优解〔2〕。粒子群算法（particle swarm optimization，PSO）具有较强的全局寻优能力，采用群体并行搜索方式计算求解，求解效率较高，收敛速度快。本文运用带变异和动态自适应双重机制对PSO算法进行改进，将其应用于带约束条件的物流配送中心的选址问题，取得了较好的结果。

1 物流配送中心选址问题

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

在区域范围内拟为n个客户建立一个物流配送中心，客户i的坐标为（xi，yi），需求量为ωi，最大允许配送距离为D。确定物流配送中心的坐标为（X，Y），单位货物每千米运输成本为p（单位：元/（吨·km）），将配送区域划分为m个子区域，对应子区域内配送中心的建设成本为Cj，物流配送中心的选址问题就简化为在满足最大允许配送距离的前提下，使得总成本f（包括建设成本和后续的配送成本）最小。

物流中心选址数学模型可以描述如下：

目标函数：

约束条件：

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

2 带变异和动态自适应双重优化的PSO算法

2.1 PSO算法简介PSO起源于对鸟群觅食行为的研究，由于鸟群觅食和优化问题求解在一些方面具有相似性，于是人们模拟鸟群觅食的生物原理去作优化决策和寻找问题最优解〔4〕。

标准PSO算法实现过程如下：假设在M维（即有M个函数自变量）搜索域中有n个粒子组成一个群体，n代表种群规模，种群太小则不能保证粒子群体的多样性，以致算法性能很差，种群太大尽管可以增加寻优的效率，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢〔5〕。Xi=（xi1，xi2，…，xiM），i=1，2，…，n为粒子i的位置向量，粒子维数取决于待优化函数的变量数，其中xik代表粒子在第k个自变量上的取值，xik∊［L，U］，在实际应用中，X每一维保证在一定的范围内，这在函数优化问题中相当于是自变量的定义域，L表示第k个自变量的取值下限，U表示第k个自变量的取值上限。Vi=（vi1，vi2，…，viM）为粒子i的速度向量，它们都是M维的，vik∊［vmin，vmax］，vmin表示粒子在第k维方向上的最小速度，vmax表示粒子在第k维方向上的最大速度，在每一代寻优中，粒子将根据粒子自身找到的历史最优位置和群体找到的历史最优位置来调整自己的飞行方向和方位〔6〕。记Pi=（pi1，pi2，…，piM）是粒子i自身找到的具有最佳适应值的位置；记Pg=（pg1，pg2，…，pgM）是整个粒子群搜索到的最优位置。

设f（x）为适应度函数，粒子i的个体最佳位置为：

群体所有粒子找到的全局最佳位置为：

第t代的第i个粒子进化到第t+1代时，第j维的速度和位置用如下的进化方程计算：

每一维粒子速度和位置都会被约束在一个范围内，如果超过边界条件，按如下方法处理，这样防止了粒子逃遁出解空间的可能性。

vij>vmax，xij＜xmax时，vij=vmax，xij=xmax或vij＜vmax，xij＜xmax时，vij=-vmax，xij=-xmax。

算法搜索性能对参数有较高的依赖性，算法涉及3个参数：惯性权重w、加速因子c1，c2。3个参数设置为定值或者线性变化会对算法寻优及效率带来不利影响〔7〕。另外，在优化前期，为了粒子具有较大速度可以提高搜索全局最优解的能力，而在后期接近最优解时，为了不使粒子速度过大偏离最优位置区域错失全局最优解陷入局部最优，因此在后期接近全局最优区域时，位置更新幅度不宜过大，应该对粒子速度进行有效掌控和约束，不能忽视后期粒子可能因速度过大俯冲脱离全局最优区域的情况出现，从而造成算法不成熟收敛〔8〕。鉴于上述原因，在PSO算法中引入非线性变化的收缩因子ρ（t），与惯性权重相比，其更能有效管束粒子的飞行速度，改善算法的收敛能力。

2.2 带变异和动态自适应双重机制的PSO算法设计随着PSO算法研究的不断深入，人们开始运用自适应变化的参数提升PSO算法性能。已有学者从惯性权重的动态调整入手来优化PSO算法，但仅靠动态调整单一参数提升算法的性能相对有限〔9〕。为此本文不仅对惯性权重和加速因子进行动态时变调整，同时引入动态时变的控制因子来约束粒子的位置更新幅度，因为参数的非线性时变调整能比线性调整获得更佳的算法性能，这几项参数的调整皆采取非线性的动态自适应时变调整策略。惯性权重的动态非线性指数递减的调整公式如下所示：

式中k为控制因子，控制w关于t函数曲线的平滑度。随着自变量的增加，函数值递减的速度逐渐下降，指数函数改进的非线性递减的惯性权重复合PSO算法的要求。在迭代次数过程中，惯性权重值的变化应该满足如下要求：前期减少的速度比较慢，惯性权重值较大且减少幅度较小利于全局探索；后期较小且减少的速度较快，利于粒子展开精细的局部搜索，这样在保证收敛速度的同时又平衡了全局和局部搜索能力，有效避免陷入局部最优〔10〕。wstart=0.9，wend=0.4。当t=0时，w（t）=wstart=0.9，当达到最大迭代次数tmax时，w（t）=wend=0.4。k取5，后期变化步长较小有较好表现，算法能取得较好的稳定性。

为了防止粒子速度过快俯冲脱离最优解，对粒子位置更新幅度进行控制，对位置更新公式（6）引入动态自适应时变的控制因子ρ（t），对算法后期粒子位置更新幅度进行约束。其变化规律按照如下函数进行调整：

其中，ρmax设为1.8，ρmin设为0.4，α为常数，设为0.009。如此，粒子位置更新公式调整如下：

仅仅减小w会使得算法一旦陷入局部陷阱内就很难跳出，极易收敛到局部极值点，加速因子c1（t），c2（t）对算法全局和局部寻优能力亦有重要影响，所以同时对两个加速因子进行非线性的时变动态调整。也采用动态自适应时变调整策略，按照算法对加速因子的变化要求，c1先大后小，c2先小后大，以指数函数为基础构造变化关系式，使其分别呈现递减和递增变化，能让算法获得较好的全局寻优性能。其调整函数如下：

其中，c2max设为2.0，c2min设为0.6，α为常数，设为0.009。各参数变化曲线见图1。

图1 各参数变化曲线

为了增强PSO算法的全局寻优能力，陷入局部最优时能尽快跳出局部最优的约束，在上述改进的基础上受到生物在免疫遗传进化过程中变异机制的启发，对动态自适应PSO算法增加变异操作。由PSO算法的速度和位置的更新公式可知：群体最优位置和最优适应度值影响着粒子的移动，所以针对群体当前最优位置（问题的当前最优解）以一定概率进行随机变异操作，对其值进行随机扰动，尤其当陷入局部最优算法停顿时，通过引入变异算子使粒子发生跳跃，迅速逃脱局部极值的束缚，从而增强算法全局寻优能力，防止算法过早收敛。变异操作如下：g'=g+rand×d，其中g为当前群体最优适应度值所对应的最优位置，rand为在［0，1］之间均匀分布的随机数，d为变异步长（例如d=（Xmax-Xmin）/100，变异步长为搜索区间长度的百分之一）。在本文中变异概率取0.3。

3 改进的PSO算法在物流配送中心选址问题仿真求解

为了证明算法应用于求解现实中比较复杂、多约束的问题的有效性，在此将其应用于求解物流配送中心的选址，采集了8个客户的位置坐标，各客户坐标及其后续物资需求总量见表1。

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

拟在位置坐标落在20≤x，y≤800的范围内建设物流配送中心，使得前期建设成本和后期配送总成本最小。为了满足物流配送的时效性要求，约定配送中心到客户间的配送距离不得大于600 km，配送价格设定为10元/（吨·km），并在不同的子区域内建设成本不一样：在20≤x，y≤400坐标范围内，建设成本为500万元；在400＜x，y≤800坐标范围内，建设成本为650万元；在20≤x≤400，400＜y≤800坐标范围内，建设成本为480万元；在400＜x≤800，20≤y≤400坐标范围内，建设成本为370万元。根据给定的约束条件运用提出的改进PSO优化模型确定物流配送中心的最优位置坐标，使其运作总成本最小。

为了与标准PSO算法（c1，c2为常数，惯性权重线性递减）及其动态自适应PSO算法求解结果进行对比，运行对应程序，适应度函数值变化见图2，物流配送中心选址结果见图3。

图2 适应度函数值变化

图3 物流配送中心选址结果

采用本文提出的基于双重机制改进的PSO算法求解物流配送中心选址问题，具有较好的收敛性，求得最优解的迭代次数约为40次左右，最佳配送中心坐标为（513.77，599.99），建设成本和后期配送总成本最小为122 800万元。而标准PSO算法和动态自适应PSO算法在求解该问题时，虽然求解结果都接近前者的求解结果，但都没能收敛到全局最优。物流配送中心作为现代物流系统的核心和关键，其选址和布局是一个复杂的系统工程。本文构建了物流配送中心选址的数学模型，并通过改进的PSO算法求解最优物流配送中心选址方案。求得的方案满足每个客户的时效性和配送容量要求，而且能显著地将总成本降低到最少，由此可见，采用基于双重机制的PSO算法解决物流配送中心选址问题取得了较好的结果，在现实中具有十分积极的意义。

4 结束语

通过物流配送中心选址模型的应用，证明了选址模型的正确性和基于变异和动态自适应双重机制的PSO算法解决复杂优化问题的有效性，基于双重机制的PSO算法改善了易陷入局部最优、鲁棒性差的缺点，该模型应用于物流配送中心选址问题的求解，具有较好的动态观测性和收敛性。改进的PSO算法是一种解决优化问题进行优化决策的好方法，具有较好的应用前景。