多物流配送中心选址及求解

李艳冰，徐克林，朱 伟

（同济大学 机械工程学院，上海201804）

物流系统中，配送中心是连接物流上下游的枢纽，对促进生产与消费的协调与配合、保证物流系统的平衡发展起着重要作用.在各企业努力降低成本、增加利润和增强竞争力的今天，配送中心的选址问题尤为受人关注.多配送中心选址问题（multidistribution center location problem，MDLP）的求解具有NP（非确定多项式）难的性质，近年来，各种启发式 算 法［1－3］和 智 能 算 法［4－5］的 研 究 成 为 该 领 域热点.

蚁群算法采用正反馈并行自催化机制，具有较强的顽健性及分布计算能力，容易与其他优化算法相融合，尤适于求解复杂的组合优化问题［6］，但因其不能直接求解MDLP等原因，目前蚁群算法在这方面的研究成果不多.为此，通过改变禁忌表设置方式、改进转移规则、2－opt优化及信息素更新等策略，本文提出了改进的蚁群算法求解多配送中心选址问题并通过数值实验验证了模型和算法的有效性.

1 MDLP模型

多配送中心选址问题可描述为：在给定的P个候选位置中选择k个点，以合理的规模建立配送中心，服务l个客户点的配送需求.如何选择k个位置，使得在满足客户需求及配送中心供应能力前提下，服务成本（运输成本、配送中心的可变成本和固定成本之和）最小.

假定每个客户点需求只由一个配送中心服务，记Ci（1≤i≤p）为中心i的供应能力，qj（1≤j≤l）为客户点j的需求量，duv为网络中节点u到v的距离，ruv是节点u到v的运输费率，Ni是配送中心i服务的客户点数，配送中心i服务的第j个客户记为sji，fi为中心i的固定费用，则MDLP模型如下：

其中，式（1）为目标函数，表示系统服务成本最低；式（2）表示所选配送中心总的服务能力不小于所有客户总的需求量；式（3）表示每个被选中心的服务能力不小于其服务客户的总需求量；式（4）表示客户需求由一个配送中心服务；式（5）为配送中心i服务的客户数量表达式；式（6）为配送中心的数量约束；zi，yij为决策变量.

2 MDLP与扩展K－TSP的映射

在研究MDLP时，发现它与扩展K－TSP有诸多相似点.为此，把扩展K－TSP作为MDLP的数学原型，下面考察K－TSP与MDLP的映射关系.

2.1 扩展 K－TSP问题

扩展K－TSP问题可描述为：k个人从k个城市出发分头去访问n＋1个城市，每个城市有且仅有一个人到达，最后k个人都回到原出发城市，问怎样安排使得k个人的总访问路线最短［7］？

该问题的数学语言表示为：设V＝（v1，v2，…，vn，vn＋1）为平面上n＋1个点的集合；G＝（V，E）是V上的完全图；W：E→R为权函数.称H为图G＝（V，E）的k－周游路，如果它是k条子周游路的集合H＝（H1，H2，…，Hk），这里：①Hi至少包含2条边，i＝1，2，…，k；②Hi经过顶点vi，i＝1，2，…，k；③任给存在唯一的子周游路Hj（j＝1，2，…，k）经过v.

k－周游路H的长度记为L（H），即

2.2 K－TSP与 MDLP映射过程

由对MDLP的描述可知，在 MDLP中，一组（k个）配送中心被选定，这些配送中心可以映射为KTSP中的K个出发城市，l个需求点相当于K－TSP中被访问的n＋1个城市，运输工具从选定的k个配送中心出发给l个需求点的配送过程可映射为KTSP中旅行商从给定的k个城市出发分头去访问n＋1个城市的过程，MDLP的总服务成本最小可以映射为K－TSP的总访问路线最短.二者的映射关系如图1所示.

图1 MDLP与扩展K－TSP映射过程Fig.1 Mapping between MDLP and expended K－TSP

由此可知，求解扩展K－TSP的算法可应用于MDLP.

3 求解MDLP的改进蚁群算法

3.1 蚁群算法

蚁群算法（ant colony algorithm，ACA）是受启于蚂蚁觅食行为的一种仿生算法.在蚁群算法中，为每只蚂蚁设置一个禁忌表tabu，其中存放已经访问过的节点.当一只蚂蚁在t时刻从节点i向节点j转移时，按式（10）确定的概率选择转移目标［8］.

式中：τij（t）为t时刻节点i，j间路径上的信息素量；ηij（t）＝1／dij为启发函数；α为信息素启发因子；β为期望函数启发因子.

为避免信息素积累淹没启发信息，当蚁群完成一次遍历后，按式（11）更新信息素.

式中：ρ（0＜ρ＜1）为信息素挥发因子；Δτij（t）为t时刻蚂蚁遍历节点i，j间路径时留下的信息素量，Δτij（t）的初始化为零.

蚁群算法（ACA）能有效求解旅行商问题（travelling salesman problem，TSP），但它不能直接求解 K－TSP，因而更不能直接求解扩展 K－TSP.ACA求解TSP问题时，每条蚁路都是一个完全路径，都是一个可行解；在求解K－TSP问题时，每只蚂蚁只形成子路径，因而存在选择子路径构造可行解的问题.蚂蚁的子路径存在下述几种情况：（1）蚂蚁的所有子路径恰好构成一个哈密尔顿通路，只是这种概率比较小；（2）蚂蚁的子路径没有覆盖所有节点，则子路径不能构造可行解；（3）子路径覆盖的节点有重复，则子路径也不能构造可行解；而在求解扩展K－TSP问题时，除以上原因外，还有蚂蚁从不同的城市出发，最后回到原出发点的问题，不像求解TSP问题那样，所有蚂蚁有相同的出发点.

ACA不能直接求解扩展K－TSP，因而也不能直接求解MDLP.为此，本文设计了改进的蚁群算法，该算法不仅可以直接求解MDLP问题，而且具有较好的求解性能及收敛速度.具体措施为：（1）改进了禁忌表的设置方式，所有蚂蚁共享一个禁忌表，而不是给每只蚂蚁单独设立禁忌表，确保蚂蚁的子路径合成一个哈密尔顿通路，从而形成问题的可行解；（2）修改了概率选择规则，在概率选择规则中加入代价引导函数.

为提高求解性能，算法使用2－opt策略优化蚂蚁子路径并设计了信息素更新规则.

3.2 改进蚁群算法（IACA）

3.2.1 蚁群共享禁忌表

蚂蚁从拟选的k个配送中心出发，为所有蚂蚁建立一个空白共享禁忌表并在其中放入k个配送中心.发生转移时，每只蚂蚁依据转移策略选择共享禁忌表里未曾记录的配送点后，随之将该配送点放入禁忌表，其他蚂蚁就不能再选择该配送点.在满足服务能力约束的情况下，蚂蚁继续选择下一个配送点，否则返回其出发的配送中心.当所有蚂蚁都返回各自的出发点后，配送结束，使用2－opt优化配送顺序并更新信息素，计算解的目标值.多次运行算法，直到目标值趋于稳定，对一个选择方案的评估结束.比较多个选择方案的目标值，目标值小者即为MDLP的解.

3.2.2 蚂蚁选择策略

为提高算法的求解性能，在蚂蚁的选择策略中加入了代价引导函数，修改后的概率选择规则如下：

式中：τij（t）为t时刻节点i，j间路径上的信息素量；ηij（t）＝1／cij为启发函数，cij为从节点i到节点j的配送代价；ζij（t）＝1／cj为代价引导函数，cj为贪婪算法得出的从各配送中心到节点j的配送成本的平均值；α为信息素启发因子；β为期望启发因子.

3.2.3 信息素更新规则

因为各子路径均可构造可行解，故对2－opt优化后的子路径的每条边均增加信息素量

式中：cm（m＝1，2，…，k）为各条子路径的配送代价.

比较各可行解的目标函数值F，设当前最好解的目标值为Fb，如果（F－Fb）／Fb＜ε成立（ε是一个较小的正常量），则给最好解的各边增加信息素量

同时，按式（11）更新信息素.为防止信息素过分悬殊导致算法陷入局部最优，依照最大最小蚂蚁策略修改各边的信息素［9］，即令τmin≤τij（t）≤τmax，若τij（t）＜τmin，则τij（t）＝τmin；若τij（t）＞τmax，则τij（t）＝τmax.

3.2.4 MDLP－IACA执行过程

（1）初始化各关键参数；

（2）清空蚂蚁的共享禁忌表tabu；

（3）将蚂蚁置于拟选各配送中心位置上，并将这些配送中心加入共享禁忌表；

（4）按式（12）执行蚂蚁转移策略，直到全部蚂蚁形成自己的子路径；

（5）对各子路径使用2－opt反复优化，并按式（13）更新可行解各边的信息素；

（6）按式（14）更新当前最好解的信息素；

（7）按式（11）更新信息素，并置所有边上的信息素增量为零；

（8）若不满足结束条件，转入（2），否则，结束.

改进蚁群算法中，参数α，β，ρ对算法的求解性能及收敛情况有很大的影响.其中，α值的大小反映了配送点到配送中心的信息量受重视的程度，可理解为信息量的指数加权.α＝0，算法性能接近于贪婪算法，α值越大，蚂蚁选择以前经过的路线的可能性越大，但过大会使算法陷于局部最小解；β的大小表明启发式信息受重视的程度，β值越大，蚂蚁选择离它近的城市的可能性也越大，但过大也会使算法陷入局部最小解；ρ反映信息素的挥发程度，ρ过小会使算法过早收敛（信息素积累快），过大则导致前面蚂蚁好的搜索结果不能被后来蚂蚁充分利用.本文通过大量的仿真实验，得出α，β，ρ对算法结果的影响曲线，分别如图2～图4所示.从曲线图看出α＝1.1，β＝0.9，ρ＝0.15是较好的配置组合.

4 算例与分析

一物流配送矩形区域，范围为（0，0）到（100，1 00），其中散布着27个配送点，各配送点的坐标和需求量见表1；有9个候选配送中心，各中心的坐标、固定费用见表2；设配送中心到各配送点的运费率均为1，选取5个配送中心，使得各中心的配送总成本及固定费用成本之和最小.

表1 配送点基本数据Tab.1 Basic data for distribution points

表2 配送中心基本数据Tab.2 Basic data for distribution centers

利用Visual C＋＋6.0编程.参数设置为α＝1.1，β＝0.9，ρ＝0.15，ε＝0.05，最大迭代次数Nc，max＝1000，τmin为0.1，τmax＝10，蚂蚁数＝50，算法执行50次，算法所得解的情况见表3.

表3中GA算法（遗传算法）得到的数据是用不同初始值计算50次得到的最优结果.从表3看出，两种算法得出的配送服务点和配送规模一致，但选择的配送中心及配送中心服务总成本不一样，改进蚁群算法得到的解值明显优于遗传算法.证明改进蚁群算法在求解多配送中心选址问题是可行的.

5 结论

本文将多物流配送中心选址问题映射成扩展K－TSP过程，通过设置共享禁忌表、改进转移规则、2－opt优化及信息素更新等策略，实现了蚁群算法对多物流中心选址问题的直接求解.仿真算例及算法比对表明，本算法是求解多配送中心选址问题的较好选择.

表3 IACA算法和GA算法计算结果比较Tab.3 Results comparison between IACA and GA

［1］Da Gama F S，Captivo M E.A heuristic approach for the discrete dynamic location problem［J］.Location Science，1998（6）：211.

［2］Konstantinos G Z，Konstantinos N A.A heuristic algorithm for solving hazardous materials distribution problems［J］.European Journal of Operational Research，2004，152：507.

［3］张潜，高立群，刘雪梅，等.定位-运输路线安排问题的两阶段启发式算法［J］控制与决策，2004，19（7）：773.ZHANG Qian，GAO Liqun，LI Xuemei，et al.A two－phase heuristic approach to the location routing problem［J］.Control and Decision，2004，19（7）：773.

［4］Dorigo M，Gambardela L M.The ant system：optimization by a colony of cooperating agents［J］.IEEE Trans on System，Man and Cybernetics，1996，26（1）：29.

［5］闻育，吴铁军.基于蚁群算法的城域交通控制实时滚动优化［J］，控制与决策，2004，19（9）：1057.WEN Yu，WU Tiejun.Real－time rolling horizon optimization of urban traffic con troll based on ant algorithm［J］.Control and Decision，2004，19（9）：1057.

［6］Dorigo M，Gambardella L M.Ant colony system：a cooperative learning approach to the traveling salesman problem［J］.IEEE Trans on Evolutionary Computation，1997，1（1）：53.

［7］周爱莲.企业物流系统网络节点选址方法及应用研究［D］.南京：东南大学交通学院，2007.ZHOU Ailian.Research on the method and application of nodes location of enterprises logistics network ［D］.Nanjing：Southeast University.College of Transportation，2007.

［8］Frieze A M.An extension of Christofides heuristics to thekperson traveling salesman problem ［J］.Discrete Applied Mathematics，1983（1）：79.

［9］Thomas S，Holger H H.MAX－MIN ant system［J］.Future Generation Computer System，2000，16（8）：889.