基于人工蜂群算法的自适应物流选址规划方法

肖琴，张永韡，汪镭

基于人工蜂群算法的自适应物流选址规划方法

肖琴，张永韡，汪镭

物流选址规划是物流体系中具有重要战略意义的投资问题和决策问题。传统解决方案仅考虑最短路径规划问题，没有统一考虑运营费用因素，得到的规划方案在实际实施中往往并不理想。此外，传统线性规划方法在解决大规模规划问题时性能不佳，且易陷入局部极值。通过运营费用矩阵表达规划区域内不同位置的运营费用，结合物流路径评价，提出了物流选址的综合评价方法，并使用蜂群算法优化综合评价目标。实验证实，提出的方法具有可行性，可求解总成本最低的多个物流中心位置，并自适应的规划各物流中心负责区域。

物流选址；物流规划；蜂群算法；最优化

0　引言

在物流发展愈发迅速的当今社会，对物流中心选址方案的设计和优化这方面的探索与研究显得尤为重要。选址问题一直是备受关注的研究热点，已有众多学者对选址问题进行了研究，提出了多种方法[1-4]，如：线性规划、非线性规划、启发式算法、重心法、神经网络、层次分析法等，为物流中心选址优化奠定了基础。然而这些传统的方法[5]在解决大规模物流选址优化问题时性能不佳，难以自适应的决定最佳的物流中心数量和位置。为解决复杂的物流选址规划问题，多种智能型算法[6-7]及其改进算法被应用于其中，如遗传算法，粒子群算法，蚁群算法等。但这些算法普遍容易早熟且收敛缓慢，计算的精度也很难提高。Karaboga[8]于2005年提出了一种新型的群智能算法，即人工蜂群算法(Artificial Bees Colony,ABC)。文献[9]详细论述了蜂群算法的基本理论及其应用情况，并比较分析了遗传算法、蚁群算法、粒子群算法和蜂群算法的优缺点及其适用范围。文献[9,10]指出相比于其它智能算法，ABC算法具有原理简单、控制参数少、收敛速度快、鲁棒性强等优点，已经被应用于函数优化、路径规划、组合优化及复杂优化等问题。基于蜂群算法的上述优点，本文将蜂群算法用于实际物流中心选址优化，算法可根据实际地图的大小，配送点数量等因素自适应决定最佳的物流中心数量和位置，进一步拓展了蜂群算法的应用领域。实际选址中地租是一个不可忽视的因素，本文采用运营费用矩阵的方法，可以方便的输入初期建设成本或者场地租金等于位置相关的成本因素，弥补传统物流中心选址方法仅考虑单一最短路径问题的不足。

1　问题描述

物流选址的好坏影响配送范围内的配送模式及配送距离，进而影响物流中心的工作效率及服务质量。在影响物流选址的众多因素中，主要包括自然因素和社会因素。其中自然因素包括自然条件（山川河流），土地条件、道路分布等；社会因素包括基础设施条件、客户需求量分布、供应商状况、社会政策等。为了突出主要矛盾，简化问题模型，本文主要考虑运输成本和运营成本对选址规划方案的影响。

1.1运输成本

对于物流中心选择，首要考虑的是配送路径导致的运输成本。尽管随着交通工具的多样化和路网的发展，这一因素的影响将逐渐降低，但目前仍是需要首先考虑的问题。在实际情况下，运输成本包括多个方面，如运输距离，道路种类，运输工具类型及装卸成本等。在这里，仅考虑与选址位置密切相关的运输距离的影响。其他组分由于并不随选址位置变化而改变，故不影响最终结论。

对于多个物流中心的选址问题，若运输距离与费用呈线性关系，则运输成本可表示为公式（1）：

1.2运营成本

运营成本在不同的情况下可以有不同的组成：对于租赁现有库房的，主要考虑租金的影响，对于自主新建物流中心的，主要考虑地价及前期建造成本。如何确定不同选址位置所对应的运营成本，并不是本文讨论的范畴，因此，使用如下方式计算运营成本如公式（3）：

综上，物流选址总成本及表达式如公式（4）：

2　规划方案编码及评价准则

2.1规划方案编码

完整的规划方案包含3个方面：物流中心的数量，各中心的位置以及各中心所负责的配送点。其中每个中心的位置需要两个数值分别表达横纵坐标。因此确定物流中心位置的规划方案可以由长度为的数组表示。同时，为了确定每个物流中心所负责的配送点，可将配送点编号作为编码的一部分整合到规划方案编码中。令中心负责个物流点数，完整的规划方案编码结构如图1所示：

图1　.规划方案编码

每个中心负责配送点的分配方法如图2所示：

图2　配送点分配方法

由于配送点编号随机排序，上述编码方式可以表达任意的配送点分配方案。

3.2评价准则

给定配送方案，需要分别确定运输成本和运营成本。运输成本由物流中心到每个配送点的距离决定，在真实地图上，该距离随着选择路径的不同有很大差异，且涉及交通状况等众多复杂动态因素。为了简化问题，本文选择欧氏距离计算方案。使用欧氏距离含义非常直观，但由于地图上两点之间的通行距离大于等于直线距离，故计算得到的运输成本为实际运输成本的下限。采用欧氏距离的计算方法如公式（5）：

其中 为物流中心 的横坐标， 为配送点 的横坐标。根据式（5）得到物流中心与配送点之间的距离后，可以根据式（2）计算每个物流中心到每一个配送点的距离和。但在多个物流中心情况下，每个物流中心只负责部分配送点，因此可以采用下式计算运输费用如公式（6）：

为了根据给定的物流中心坐标计算其运营费用，需要首先建立运营费用的地图。考虑需要规划的区域，首先将地图网格化，然后根据调查的结果标记每个网格内的运营费用，可以得到关于运营费用的矩阵。物流中心的运营费用为相应网格内标记的费用，实际中只需根据物流中心坐标查询运营费用矩阵即可得到该中心的运营费用。

以镇江市城区地图[11]为例，经网格化后得到费用矩阵的示意如图3所示：

图3　运营费用地图及费用矩阵

如图3，将地图划分为1公里见方的网格，并按照不同区域的费用标注网格，可以得到费用矩阵。此地图中中心商业区的运营费用最高，而东南角的区域费用最低。注意到有山脉与河流，这些位置为不可行区域，为了避免将物流中心规划到这些区域，此类区域的费用权值为无穷大。此外，其他已知的不可规划区域（如住宅区，铁路沿线等）也可以设置较高的费用系数以避免规划方案将物流中心设置在该区域内。在实际中，费用矩阵的划分可以更加细致，以使网格的形态尽量贴近实际地形。

根据上述方案分别得到选址方案的运输费用和运营费用，对方案的最终评价可以是两部分简单相加，也可以是在权衡重要性之后取两部分的加权和。

3　蜂群算法及实现

3.1蜂群算法

蜂群算法模拟蜂群中的分工合作，将整个蜂群划分为工蜂(Employed Bees)，观察蜂(Onlooker Bees)以及侦查蜂(Scouts)。并且以食物源中食物的数量决定该食物源被蜂群探查的概率。基本上，蜂群算法使用工蜂针对每个食物源进行全局搜索，使用观察蜂对当前食物源按照食物数量概率的进行局部搜索，当一个食物源耗尽时，使用侦查蜂在可行空间内随机搜索新的食物源。

当食物源初始化完成后，工蜂对每一个食物源进行探查，并使用下式生成候选食物源[8]如公式（8）：

使用轮盘赌选择将要探查的食物源，并使用公式（8）搜索该食物源的邻域，同样根据贪心准则选择是否更新食物源。当所有观察蜂完成工作后，逐个检查每个食物源被探查的次数，如果次数超过了事先确定的探查次数上限，则放弃该食物源，并且由侦查蜂随机的确定新的食物源。

人工蜂群算法通过轮盘赌选择，使优秀的解具有更多的概率被进一步探查。同时，对于劣解也保证了在每一周期至少被工蜂探查一次，有效的平衡了算法的探索与开发；候选解生成方式类似差分算法，在搜索过程中自适应的调整搜索范围：当食物源之间彼此较远时，算法可以大范围探索可行解空间，在算法运行后期，食物源之间的距离较近时，公式（8）又保证了生成候选解的局部搜索能力。最后算法对每个食物源的搜索设置了次数上限，保证了任何一个特定的解不会长久的占据种群主体，有效改善了其他同类算法早熟收敛的缺陷，并增加种群多样性。

3.2算法流程

选址优化算法主要包括初始化，编码，解码与演化优化几个部分，下面逐一进行介绍。

3.2.1初始化与编码

3.2.2解码算法

在算法的评价阶段，需要将取值[0,1]之间的数列翻译为规划方案以评价其优劣，解码流程如下：

Step 4. 根据已有的配送点坐标和其对应的物流中心坐标计算运输距离及运营费用，并使用综合的费用函数作为该规划方案的评价。

3.2.3演化寻优

一、工蜂阶段

Step 1. ，食物源访问次数 ；

Step 3. 对候选解进行解码并计算适应度，如果适应度更大，则更新食物源，，否则；

二、观察蜂阶段

Step 1. 根据式（9）计算每个食物源被选择的概率，；

Step 2. 按照概率选择食物源，若选中第 个食物源，随机生成以及，按照工蜂阶段Step 2和Step 3使第和个食物源的第位进行交叉，得到候选解；

Step 3. 解码候选解并计算适应度，如果候选解适应度更大，则更新食物源，，否则；

三、侦查蜂阶段

4　仿真实验

以镇江市主城区为例，将主城区划分为4乘4的网格，使用图3中的运营费用矩阵，选择10个配送点，配送点覆盖了市区的主要居住区和商业区。使用蜂群算法搜索最佳规划方案，算法主要参数设置如下：蜂群规模100，其中工蜂50，观察蜂 50，侦查蜂数量不计入种群规模。设置食物源访问次数的上限为观察蜂数量与编码长度之积，目标函数计算次数上限为10万次。物流中心数量上限为5个，配送点位置分布如图4所示：

图4　配送点位置分布及运营费用

网格内右上角为该区域的运营费用。

在上述参数设置下运行算法50次，所得最佳选址方案成本的均值为11.49，最小成本为11.34，最大成本为12.63，中位数为11.35，标准差为0.33，算法运行较为稳定。其中47次运行结果给出了两个物流中心的结论。最佳方案得到的物流中心分布如图5所示：

图5　最佳方案的物流中心分布于配送点分配

其中，空心圆圈标明了物流中心选址位置，其中的数字代表物流中心标号和与之配套的配送点。其中2号物流中心负责城西的四个配送点，而1号物流中心负责剩余的6个配送点。从选址结果可以发现如下几点结果：

（1）物流中心均位于靠近运营费用变化的边界上，如1号中心位于运营成本2与3的交界部分，但巧妙的避开了成本3的区域。而2号中心同样位于成本2和3交界的区域。观察2号中的坐标可知，最终2号中心规划在成本2的区域中。

（2）物流中心位于其负责的配送区域中心位置，最大化的提高了配送效率，降低了运输成本。

（3）在高运营成本的惩罚下，选址方案自动的避开了山川河流和高密度商业区，同时物流中心总数根据运营地图参数自动适应，显示了算法良好的普适性。

5　总结

本文提出的物流中心规划算法具有较好的适应性，可根据地图大小，配送点数量等因素自适应决定最佳的物流中心数量和位置，并决定每个物流中心所负责的配送点和辖区。采用运营费用矩阵的方法，可以方便的输入初期建设成本或者场地租金等于位置相关的成本因素。通过赋予不可达区域更高的运营费用，可以使最终的规划方案成功避开该类区域。算法实施简单，适应性与普适性强，具有较高的实用价值。

算例中为了展示方便，将地图划分为4乘4网格，得到运营费用矩阵较为笼统。在实际中可采用更高精度的划分方法，以提供与现实问题相匹配的运营费用矩阵。由于运营费用通过查表得到，不增加编码长度，因此不影响算法搜索性能。此外，算例中配送点不能覆盖城区所有居民区与商业区。但详尽的考虑势必增加编码长度，增加求解难度，如何在最优性与实用性之间权衡算法，是值得进一步探讨的问题；同时，探索更加简洁的选址方案编码表达，进而提高算法搜索效率，也值得更多思考。

[1] 方志贤. 物流中心选址方法综述[J]. 物流科技,2008,31(09):42-44.

[2] CarolineProdhon,ChristianPrins. A survey of recent research on location-routing problems[J]. European Journal of Operational Research,2014,238(1):1-17.

[3] 胡敏. 多址重心法在 A公司区域配送中心选址中的应用研究[D].上海交通大学,2014.

[4] 徐仕强. 基于组合赋权TOPSIS模型的物流中心选址研究[J]. 物流技术,2014,33(6):132-134.

[5] Lin Li,ShixinLiu,JiafuTang. Basic models for solving distribution center location problems: A review[C]. 2007 International Conference on Service Systems and Service Management,2007,1-5.

[6] 汪镭,张永韡,郭为安,吴启迪. 自然计算发展趋势研究[J]. 微型电脑应用,2010,26(07):1-5+10+6.

[7] 黄敏镁. 粒子群算法在物流中心选址中的应用[J]. 计算机工程与应用,2011,47(04):212-214

[8] Karaboga D.An idea based on honey bee swarm for numerical optimization[R].Technical Report-TR06,ErciyesUniversity,2005.

[9] 张超群,郑建国,王翔. 蜂群算法研究综述[J]. 计算机应用研究,2011,28(09):3201-3205+3214.

[10] 秦全德,程适,李丽,史玉回. 人工蜂群算法研究综述[J].智能系统学报,2014,9(02):127-135.

[11] ] http://map.baidu.com/,2015.10.22.

Adaptive Logistic Hubs Location Based on Artificial Bees Colony

Xiao Qin1，Zhang Yongwei2,Wang Lei3
(1. Center of Information Constructionand Management,Jiangsu Univensiey of Science and Technology,Zhenjiang 212003,China; 2. College of Electronics and Information,Jiangsu University of Science and Technology,Zhenjiang 212003,China; 3. College of Electronics and Information Engineering,Tongji University,Shanghai 201804,China)

Location of logistic hubs is an important investment and decision problem in logistic systems. Traditional solutions consider only shortest path,and the operation cost is not taken into consideration. The solutions cannot be well implemented in practice. Besides,linear programming has poor performance when solving large-scale programming problems and can be easily trapped in local optima. The operation cost of different areas is represented by operation cost matrix. Combined with path criteria,a comprehensive criterion is proposed,which is optimized by artificial bees colony algorithm. The experiment results show that the proposed method is practical,capable of locate multiple logistic hubs which have lowest total cost,and it can divide responding area of each logistic hub adaptively.

Logistic Location; Logistic Planning; Artificial Bees Colony; Optimization

TP311

A

1007-757X(2016)03-0005-04

国家自然科学基金（61075064，61034004，61005090）

肖 琴（1983-），女，江西，江苏科技大学，硕士，研究方向：数据挖掘，江苏 212003

张永韡（1983-），男，甘肃，江苏科技大学讲师，博士，研究方向：智能控制，江苏 212003

汪 镭（1970-），男，江苏，同济大学教授，博导，研究方向：群体智能，智能控制，上海 201804

（2015.10.21）