基于蜂群算法的物流配送规划研究*

邓向林，唐飞岳

(湖南交通职业技术学院，湖南 长沙410132)

基于蜂群算法的物流配送规划研究*

邓向林，唐飞岳

(湖南交通职业技术学院，湖南 长沙410132)

电子商务的兴起促进了现代物流业的发展，但物流公司在货物送达末梢客户的“最后一公里”路径规划上，多取决于具体配送人员的工作经验，整体效率偏低。为提高配送效率，对车辆路径问题(Vehicle Routing Problem, VRP)，以及由此延伸出的有载重限制的车辆路径问题(VRP with Capacitated, CVRP)的研究因而产生。为提升现有的蜂群算法在CVRP问题的求解效能，文章对蜂群算法进行了改进，在CVRP问题中加入分群机制来限缩蜂群探索区域，并搭配使用限制次数以增强对局部区域搜寻能力。模拟结果显示，在复杂度高的问题求解上，所提出的加强型蜂群算法比典型的蜂群算法能更有效地找到近似最佳解。

车辆路径问题；蜂群算法

0 引言

随着现代物流行业的高速发展，其已成为支持城市经济的重要动力与基础，但物流行业的运输行为也对城市带来了交通拥塞、环境污染等负面影响，因此物流行业的运营能力水平高低成为评估城市区域竞争力的关键因素之一。 车辆路径问题是对物流配送行为的一种运筹与模拟，目前绝大部分的车辆路径问题都是NP难题，为有效解决此类问题，相应的新兴算法由此产生，蜂群算法以其较强的全局寻优能力以及较快的收敛速度得到了广泛的应用。

1 研究背景

社会的进步与现代科技的发展带来了以网络购物为典型应用的电子商务活动的骤增，这也推动了物流行业的变革。按传统B2B的物流配送方式，货物需经厂商、中间商、分销商、零售商才能送达消费者手中，这已经无法满足在线购物的需求。直接送货上门的C2C模式成为更受欢迎的新方式。目前物流公司多在收送货物后，才让该区域配送人员考虑路线问题，但这往往取决于配送人员本身的经验，因行驶距离、配送时间的不确定性使得配送成本难以控制。

最早的车辆路程问题(Vehicle Routing Problem, VRP)由DANTZIG G B和RAMSER J H在1959 年首次提出[1]，迄今为止仍然是国内外研究的难点问题，由于VRP问题是属于NP-complete 问题，因此在传统的VRP问题上只能找到近似最佳解。随着VRP复杂度的提高与问题模式的改良，其困难度也呈指数型成长[2]。传统蚁群算法求解小型VRP问题相当便捷，该算法主要是建构一条路径再藉由费洛蒙的挥发程度去更改路径，每条路径上都必须计算移转率并判别行驶该路线的可能性，且几乎都为单点的路径改善，并无蜂群算法多样化的邻近搜寻方式，因此当数据结构增大，蚁群算法在效率及准确性上就会相对降低。随着C2C模式物流配送需求度的不断增长，为了提高货物送达客户的效率，对于货物配送路线的优化成为需要研究的决策支持问题。

2 CVRP问题描述

本文对车辆载重限制的CVRP(VRP with Capacitated, CVRP)问题，即从起始点(仓库)配货至各个客户的最优路线问题进行探讨。对本文所研究CVRP问题条件设置为：

(1)仓库：只有一个配送货物的定点仓库，且只考虑单纯配送情形；

(2)车辆：每辆货车只有单位100 的货物装载量，并且只考虑单一车种问题，货车均由仓库出发，行驶过每个指派的需求点，且车辆没有油耗、维修等问题；

(3)客户点与客户需求：每位客户的地点与需求都为已知；

(4)行驶路线：每辆货车都必须到达指派地点；

(5)求解目标为：对一系列需要到访的载货点与卸货点，组成合理的最短路程，使货车按照规定的行车路线去行驶，在满足货车容量限制条件的同时，使路程最短、整体使用车辆最少。

对本文研究的CVRP问题数学模型描述如下：首先必须对n个客户送货，第i个客户的需求量为di(i=1,2,3…,n)，由仓库派出m辆车来载运，第t辆车容量为ct(t=1,2,3…,m)，将货物送往各个客户，最后再回到仓库。限制条件为：

(1)每辆货车的载货量不得超过该辆货车的最大载货量；

(2)每个客户最多只能由一辆货车拜访；

(3)每一条配送路线的长度不得超过货车的最大行驶距离；

(4)客户的配送顺序不变，例如必须在拜访a点之前先到b点。

最终目标为运输总成本最小(车辆最少、路径最短)，如式(1)所示：

(1)

其中，Cij表示从客户i到客户j的运输成本，Xijt表示车辆t是否由i到j。Xijt是决策变量，1表示是，0表示否。

若配送到ij点必须由t车辆单独完成，分别记为yit、yjt，如式(2)所示：

(2)

限制每辆车的载货量不得超过该辆车的最大载货量qt，如式(3)所示：

(3)

每个客户只能由一辆车完成,而整个VRP 任务则由m辆车共同完成。分别如式(4)、(5)所示：

(4)

(5)

3 蜂群算法改善设计

蜂群算法是2005年由KARABOGA D提出的一种启发式算法[3]，分别由工蜂、观察蜂、探索蜂来执行趋近局部优化解，再效仿蜜蜂群集智慧将最佳解突显出来，在效率上比起以往的算法都有显着的提升，较适用于解决多目标的函数问题。在一般仿生式算法中，初始解几乎都为随机式，在数据较小时虽能求出近似最佳解，但随着数据变大，复杂度也成指数型增长，而在使用邻近求解的过程中，效率因而降低[4-6]。本文基于蜂群算法进行改善，结合扫描法使得整体的搜索空间缩小，对初始解的产生方法予以改变。

首先工蜂负责的工作内容为产生初始解,每只工蜂代表一个解(工蜂数量以FS表示)。接着计算该初始解是否超过本货车的负载量(如超过则再加一台货车)，然后按式(6)从所有的初始解中计算适应值并产生可能的候选解。

(6)

工蜂产生初始解前，将先对原本无规律的节点进行有顺序性的分群，再将节点依序划分为4个群，使工蜂的搜寻面积由整个搜寻区块缩小成4个等份。降低单个工蜂的搜寻面积再进一步将所求得的解交至观察蜂收敛。

观察蜂主要是从工蜂所产生的候选解中每个逐步地邻近搜寻，对初始解进行邻近搜寻(采用随机置换解、随机插入解、随机反转解、随机反转与插入解的组合策略)，计算该邻近解的适应值并让观察蜂判断此邻近解是否小于原初始解，是则进入探索蜂阶段，否则重复临近搜索。观察蜂数量以OB表示。

探索蜂的工作内容为判断观察蜂的搜寻状况，找出个解的最大限制次数，判断其是否大于探索蜂的限制次数(max_limit)，若是则由探索蜂随机找出一解，否则告知观察蜂继续对该食物源进行搜寻。

4 实验模拟与结果分析

本研究以MATLAB 7.10.0(R2010a)编写程序，执行代码的服务器主要配置为Intel(R)2.53 GHz 处理器/内存4 GB。实验样本是CVRP 标准数据集来作为测试样本，每组数据皆进行20次统计测试。将工蜂数、迭代数逐步增大，对比典型蜂群算法与本文改进的蜂群算法所求得的平均路径成本，其结果如表1所示。

表1 不同参数下典型蜂群算法与改进蜂群算法的路径成本对比表

取其中最低路径成本的参数值,即FS=100、Iterations=1 000，再分别代入不同的探索蜂的限制次数参数(max_limit)进行两种算法的效能对比，如表2所示。

表2 不同限制次数下典型蜂群算法与改进蜂群算法的路径成本对比表

由于分群法其主要目的就是规律性地限缩其探索范围，至此将所求得的优化参数(即FS=100、Iterations=1 000、max_limit=100)代入不同客户数量数据集中，两种算法的效能对比结果见表3。

从实验数据可以看出，在客户节点数小于60时，以典型蜂群算法的成本较佳，但在客户节点数超过60后，本文所提出的蜂群算法较佳。若客户节点数持续增长，由于本文所用的改进蜂群算法在初始解产生方式上明显优于典型蜂群算法，其成本优势将更为明显。

5 结论

本文主要是对典型蜂群算法进行改善，用于针对CVRP问题求解。有别于以往的仿生式算法，研究中使用分群式产生规律性的初始解，并使用单点置换法作为邻近搜索主要求解法，然后以满足搜索限制条件为约束，使用单一置换、反转法、插入法的组合搜寻策略，实验数据证实了本文所提出的加强型蜂群算法可减少算法的计算开销。

[1] DANTZIG G B， RAMSER J H.The truck dispatching problem[J]. Management Science, 1959(6):80-91.

[2] CHRISTOFIDES N, MINGOZI A, TOTH P. The vehicle routing problem[M]. New York: John Wiley & Sons,1978:318-338.

[3] KARABOGA D. An idea based on honey bee swarm for numerical optimization[R]. Technical Report-TR06, Erciyes University,2005

[4] KARABOGA D, BASTURK B. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm[J]. Journal of Global Optimization,2007,39(3):459-471.

[5] KARABOGA D, BASTURK B. On the performance of artificial bee colony (ABC) algorithm[J]. Soft Computing,2008,8(1): 687-697.

[6] KARABOGA N. A new design method based on artificial bee colony algorithm for digital IIR filters[J]. Journal of the Franklin Institute,2009,346(4):328-348.

Research for logistics distribution planning based on bee colony algorithm

Deng Xianglin, Tang Feiyue

(Hunan Communication Polytechnic, Changsha 410132, China)

The rise of electronic commerce brings the development of modern logistics industry. But the logistics company in "last mile" path planning always depends on worker who execute it, the efficiency is low. In order to improve the efficiency of distribution, the Vehicle Routing Problem(VRP) and the VRP with Capacitated(CVRP) is studied. For increasing the efficiency of the existing bee colony algorithm in CVRP problem, this paper presents an improved bee colony algorithm, adding the clustering mechanism in CVRP to narrow the colony exploration region ,and limiting times of use in the local area searching to enhance it. The simulation results show that, in the problem of high complexity, the proposed algorithm is more efficient than the typical algorithm to find the approximate optimal solution.

vehicle routing problem；bee colony algorithm

湖南省交通运输厅科技进步与创新计划项目(201138)；全国交通运输职业教育科研项目(2013B41)

TP29;F253.9

A

10.19358/j.issn.1674- 7720.2017.01.017

邓向林，唐飞岳. 基于蜂群算法的物流配送规划研究[J].微型机与应用，2017,36(1)：56-58.

2016-09-30)

邓向林(1979-)，女，本科，助理研究员，实验师，主要研究方向：计算机教育、智慧交通。

唐飞岳(1973-)，男，本科，主要研究方向：计算机网络、智慧交通。