基于负载量均衡的AGV快递分拣系统布局优化

张得志，肖博文，徐巍

基于负载量均衡的AGV快递分拣系统布局优化

张得志，肖博文，徐巍

(中南大学 交通运输工程学院，湖南 长沙 410075)

随着我国AGV快递分拣系统中物流量不断增加，优化AGV快递分拣系统布局，成为提高其分拣系统效率的关键。首先，在分析造成基于AGV分拣系统拥堵的关键影响因素基础上，研究基于AGV快递分拣系统中取货口和投递口布局优化问题，构建相应的整数规划优化模型，该优化模型以整个分拣系统负载量均衡为优化目标。其次，针对该优化模型特征设计了相应的改进遗传算法。最后，以某快递分拣中心布局优化为例，进行相应数值仿真研究，以验证上述优化模型及其算法的有效性。研究结果表明：1) 本文提出的改进遗传算法，能有效降低系统的负载量标准差；2) 四向四站式布局策略和对角四站式布局策略优化后的负载量标准差相比双向四站式布局策略分别减少了22.89%和55.7%。

快递分拣；布局优化；负载均衡；遗传算法；案例分析

随着电子商务行业的快速发展，快递包裹量不断增加，包裹分拣量日益庞大，对作业效率、准确率和客户体验的要求也在不断提高，电商物流中心、快递分拨中心等对高效率、低成本、高柔性的分拣解决方案需求大幅上升[1]。在此背景下，兼备柔性、效率和成本优势的AGV(Automated Guided Vehicle，无人搬运车)快递分拣系统应运而生[2]。AGV快递分拣系统快递量规模日益扩大，所引发的AGV快递分拣系统拥堵问题逐渐凸显。拥堵问题将减慢拣货过程，导致更多的任务积压，降低AGV的周转率，并可能造成更多的安全问题[3]，因此拥堵对分拣效率造成的影响不容忽视。AGV在同一时间同一地点作业造成的节点负载量(即网络节点在当前路由策略下的实际吞吐量)不均衡是造成拥堵的主要原因，这在实际运用中是不可避免的[4]。当单位时间内产生的节点负载量超过某一确定值时，网络交通流将快速陷入拥堵状态[5]。拥堵状态下，某些路段的交通流量将达到饱和状态，而部分路段处于非饱和或车流稀少的状态[6]。因此避免单位节点出现过大负载量是解决拥塞的关键。负载量较高的取货站的布局以及不同投递口快递量之间的差异是造成AGV分拣系统负载量不均的原因。合理的安排系统内部各功能单位及相关辅助设施的相对位置以确保系统工作畅通，对系统工作效率有着至关重要的影响。优化取货口和投递口的相对位置布，以均衡系统整体负载量，可降低系统拥堵程度。本文引入负载量标准差刻画负载均衡程度，现有研究中，袁洋等[7]运用区域负载标准差刻画AGV运行路网的区域负载均衡水平,提出了考虑负载均衡的改进A*算法，显著提升了区域负载均匀程度。基于规划论的布局优化方法是目前主流的布局优化方法，布局优化问题可转化为整数规划问题或混合整数规划问题，通过求解对应的数学模型即可得到布局方案[8]。由于布局优化问题属于NP-hard问题, 大量启发式算法被提出以求解问题。Paes等[9]采用遗传算法求解不等面积设施布局问题。Ahonen等[10]运用禁忌搜索算法，考虑AGV尺寸并对设施布局问题进行了研究。李航等[11]将布局优化问题与AGV数量配置相结合，提出了对应的变邻域搜索算法。葛华辉等[12]以物料搬运时长最短以及AGV数量最少为目标，提出了改进的带精英策略的快速非支配排序遗传算法。但目前研究中未存在将系统负载量作为布局优化考虑因素的研究。本文以AGV快递分拣系统布局为研究对象，以负载量均衡为目标建立整数规划模型，运用A*算法[13]进行AGV快递分拣模拟实验，并设计适合本文的遗传算法进行布局优化求解，得到负载量更为均衡的布局方案。

1 问题描述与数学模型

1.1 问题描述

假设包裹数(不可分任务单元)、取货站数量、投递口数量分别为，和。任务单元随机指派，所有的快递包裹大小重量相同，投递口相互独立且无法通行，各投递口的快递量不均匀。忽略AGV故障、电量不足的情况。根据任务数，将个任务单元均匀分配到个取货站，并将AGV分指派对应取货站，一个AGV每次只能完成一个任务，AGV只能完成前后左右四向移动。

在取货站，任务被自动识别并为AGV指派目标投递口，AGV将货物运送至指定投递口的邻接点并完成货物投递任务。任务完成后，AGV根据任务分配的规则返回分配的下一个任务的取货站执行下一次任务，直到所有任务完成。忽略包裹装载与投递过程，分拣过程连续。AGV快递分拣系统作业流程如图1所示。

图1 AGV快递分拣系统作业流程

采用栅格法建立环境地图模型。将环境地图分割成多个大小相同的栅格，每个栅格代表相应系统单位节点，通过二维网络模式存储AGV分拣系统的环境信息，网格的大小和数量取决于AGV和工作空间的大小。本文根据目前普遍采用的双向四站式布局策略分拣单元系统构建初始模型，取货站相向分布于系统边缘两侧，每侧对称分布2个取货站，共计4个取货站，16个投递口中心对称分布于系统中心，呈正方形分布，相邻投递口间隔一单位网格，如图2所示。在此类模型中，货物因目标地不同而被AGV送入不同投递口，不同目标地货量存在差异，因而投递口成为目标投递口的概率不尽相同；为忽略因取货站取货量不同对系统负载量均衡所造成的影响，假设不同取货站的出货量相同。同时，为聚焦于投递口货量差异与取货站布局对系统负载均衡程度的影响，仅对该模型进行单AGV多次模拟实验，等概率选取取货站并依据货量差异随机选取投递口作为单此任务的起始点与目标点，以忽略多AGV任务调度对负载均衡程度造成的影响。

图2 双向四站式布局策略

1.2 数学模型

基于以上描述，以负载量标准差刻画AGV快递分拣系统负载量均衡程度，并以负载量标准差最小化为目标，建立AGV快递分拣系统负载量均衡整数规划模型，基于负载量标准差优化AGV快递分拣系统取货站和投递口的相对位置布局。

目标函数：

约束条件：

N表示第行第列子区域负载量(被访问次数)，其中∈,={1,2,3,…,N}，N表示地图模型的横向节点数，∈,={1,2,3,…,N}，N表示地图模型的纵向节点数。取货站={1,2,…,s}，为取货站数量；投递口={1,2,…,d}，为投递口数量。P为取货站被选为起点或目标点的概率，P为投递口被选为任务起点或目标点的概率。目标函数(1)表示负载量标准差最小化，其中N×N表示单元系统总节点数；约束(2)～(3)限定取货站和投递口的数量，约束(4)表示所有取货站出货的概率相同，约束(5)表示负载量的非负约束与整数约束，约束(6)为概率的非负约束。

2 求解算法

由于目标布局优化问题为NP-hard问题，本文采用启发式算法对模型进行求解，采用A*算法进行模拟实验，采用遗传算法作为优化算法对不同流向快递量不均匀的投递口布局进行优化。具体步骤如下。

Step 1 初始化：设定种群规模、交叉概率、变异概率、最大迭代次数、模拟实验次数、精英数量、投递口概率。

1) 基因编码：采用符号编码法进行基因编码，染色体如图3所示。其中基因的位置依次代表不同投递口，P为对应不同流向货物的快递量占比(模拟实验中投递口被选中的概率)。

图3 染色体基因编码示例

Step 2 模拟实验：遍历当前种群中的个体，解码个体基因，构成对应地图模型进行模拟实验。

1) 解码。根据当前个体的基因序列，调整投递口被选择的概率，形成相应的地图模型。

2) 选取取货站。根据取货点个数，等概率随机选取任一取货站，并将其设置为起点。

3) 选取投递口。根据当前地图模型中各投递口快递量占比，随机选取投递口，并将其设置为终点。

4) 路径寻优。运行A*算法搜寻最优路径并记录路径。

5) 选取取货站。以当前终点为起点，等概率随机选取取货站为终点返回。

6) 路径寻优。运行A*算法搜寻最优路径并记录路径。

7) 统计负载。统计经过节点，累加计算地图各节点负载量。

8) 终止条件判断。判断是否完成次分拣任务，若完成则输出地图各节点负载量并跳出实验，否则转到2)。

Step 4 选择：采用二元锦标赛法选择染色体。

Step 5 交叉：为了保证投递口快递量占比之和始终为1，本文采用排序交叉法执行交叉操作。在这种交叉方法中，随机选中亲代1的染色体中的一个子集，添加至后代染色体中的相同位置，然后从所选子集的结束位置开始，依照亲代2的基因顺序依次插入后代染色体中还没有的基因，如图4所示。

Step 6 变异：为保证投递口快递量占比之和始终为1，本文采取交换变异法执行变异操作，简单地交换2个位置的遗传信息。通过循环遍历该个体染色体的每个基因，根据变异率决定是否变异。如果选中基因进行变异，就在染色体中随机选择另一个基因交换它们的位置，如图5所示。

Step 7检查是否满足终止条件：如果迭代次数达到最大迭代次数就停止整个计算，否则转到Step 2。

Step 8输出最终优化解。

整个算法的流程图如图6所示。

图4 排序交叉示例

图5 交换变异示例

图6　改进遗传算法流程图

3 算例分析

根据某快递分拣中心2019年12月份某天的快递业务量，有差别的选取16个地区，并按照各地区快递量占比分为3类，占比高于10%为DⅠ类，占比低于10%高于4%为DⅡ类，占比低于4%为DⅢ类，如表1所示。

表1　算例数据

以目前应用最为广泛的AGV快递分拣单元布局构建初始地图模型，共设置4个取货站，16个投递口。运用JAVA语言根据本文提出的改进遗传算法进行编程，设定改进遗传算法种群数大小为70，最大迭代次数为500，变异概率为0.05，交叉概率为0.9，精英数量为5，仿真实验任务量为50 000。

使用本文提出的改进遗传算法对实例进行仿真优化，得到最优小负载量标准差为702.521 5，进化过程如图7所示。双向四站式布局优化前负载量结果如图8(a)所示，优化后负载量情况如图8(b)所示。

图7 改进遗传算法流程图

(a) 双向四站式布局策略优化前负载量；(b) 双向四站式布局策略优化后负载量；(c) 四向四站式布局策略优化后负载量；(d) 对角四站式布局策略优化后负载量

调整取货站位置，提出四站式布局策略与对角四站式布局策略，并应用本文提出的改进遗传算法对实例进行仿真优化，四向四站式布局策略负载量情况如图8(c)所示，对角四站式布局负载量情况如图8(d)所示。

分析图8可发现，负载量标准差低的系统布局负载量均匀度有明显改善。在AGV快递分拣系统中，取货站与投递口的相对位置对系统负载量均衡的影响较为明显。从取货站布局的角度分析，取货站口的负载量往往较高，增大相邻取货口之间的平均距离能有效降低地图负载量标准差。从投递口的角度分析，DⅠ等级的投递口对负载量标准差的影响最为明显，DⅡ等级投递口次之，DⅢ投递口对负载量标准差的影响较小。加大DⅠ等级的投递口与取货站之间的平均距离能有效降低负载量标准差，提升系统负载量均衡水平。

表2　改进遗传算法优化结果

3种布局负载量标准差优化前后情况如2表所示。分析表2数据可知，本文提出的改进遗传算法，通过优化不同快递量投递口的位置布局，能有效降低系统的负载量标准差。对比目前广泛应用的双向四站式布局策略，四向四站式布局优化后的负载量标准差减少了22.89%，对角四站式布局优化后的负载量标准差减少了55.7%，优化效果明显。

4 结论

1) 以AGV快递分拣系统为研究对象，以负载量均衡为优化目标，考虑了取货站与投递口布局对分拣系统整体负载量的影响，运用A*算法进行模拟实验，并提出适用于此模型的基因编码与交叉变异策略，形成改进遗传算法对模型进行优化。根据实际算例进行验证，证明模型和算法对于AGV快递分拣系统布局问题具有良好的优化效果，能够帮助快递分拣中心寻找布局优化方案。

2) 提出四向四站式布局策略和对角四站式布局策略，优化后的负载量标准差相比当前广泛使用的双向四站式布局策略分别减少了22.89%和 55.7%。增大相邻取货口之间的平均距离与DⅠ等级的投递口之间的平均距离能有效降低地图负载量标准差，提升系统负载量均衡水平。

[1] Ruiping Y. The research on the application of AGV system in logistics sorting operation[J]. Automation, Control and Intelligent Systems, 2016, 4(5): 80−83.

[2] Havenga J H. Logistics and the future: The rise of macrologistics[J]. Journal of Transport and Supply Chain Management, 2018, 12(3): e1−e12.

[3] 赵雨亭. 面向多AGV系统的路径规划及监控技术研究[D]. 广州: 华南理工大学, 2018. ZHAO Yuting. Research on path planning and monitoring technology for multi-AGV system[D]. Guangzhou: South China University of Technology, 2018.

[4] Gu J, Goetschalckx M, Mcginnis L F. Research on warehouse operation: A comprehensive review[J]. European Journal of Operational Research, 2007, 177(1): 1−21.

[5] 宋海权. 基于复杂网络理论的网络交通拥堵问题研究[D]. 成都: 西南交通大学, 2016. SONG Haiquan. Research of network traffic congestion based on complex networks theory[D]. Chengdu: Southwest Jiaotong University, 2016.

[6] 项俊平. 城市道路交通信号区域均衡控制方法及应用研究[D]. 合肥: 中国科学技术大学, 2018. XIANG Junping. Study on the method and application for urban road traffic signal regional eauilibrium control[D]. Hefei: University of Science and Technology of China, 2018.

[7] 袁洋, 叶峰, 赖乙宗, 等. 结合负载均衡与A*算法的多AGV路径规划[J]. 计算机工程与应用, 2020, 56(5): 251−256. YUAN Yang, YE Feng, LAI Yizong, et al. Multi-AGV path planning combined with load balancing and A* algorithm[J]. Computer Engineering and Applications, 2020, 56(5): 251−256.

[8] Tompkins J A, White J A, Bozer Y A, et al. Facilities planning[M]. 4th ed. Wiley, 2010.

[9] Paes F G, Pessoa A A, Vidal T. A hybrid genetic algorithm with decomposition phases for the unequal area facility layout problem[J]. European Journal of Operational Research, 2017, 256(3): 742−756.

[10] Ahonen H, de Alvarenga A G, Amaral A R S. Simulated annealing and tabu search approaches for the corridor allocation problem[J]. European Journal of Operational Research, 2014, 232(1): 221−233.

[11] 李航, 刘冉, 曲子灵. 采用AGV物料搬运系统的复杂生产线布局优化模型与算法[J].工业工程与管理, 2020, 25(5): 103−112. LI Hang, LIU Ran, QU Ziling. Mathematical models and algorithms for facility layout optimization of production line using AGV material handling system[J]. Industrial Engineering and Management, 2020, 25(5): 103−112.

[12] 葛华辉, 冯毅雄, 密尚华, 等. 集成自动导引车路径规划的智能制造数字化车间设备布局优化方法[J]. 计算机集成制造系统, 2019, 25(7): 1655−1664. GE Huahui, FENG Yixiong, MI Shanghua, et al. Intelligent manufacturing digital workshop layout optimization with automated guided vehicle consideration [J]. Computer Integrated Manufacturing Systems, 2019, 25(7): 1655−1664.

[13] 张少鹏, 王现康, 段坚. A~*算法在移动机器人路径规划中的应用[J]. 机械工程与自动化, 2012(6): 147−148. ZHANG Shaopeng, WANG Xiankang, DUAN Jian. Application of A-star algorithm in mobile robot path planning[J]. Mechanical Engineering & Automation, 2012(6): 147−148.

Layout optimization of AGV express parcels sorting system based on load balancing

ZHANG Dezhi, XIAO Bowen, XU Wei

(School of Traffic & Transportation Engineering, Central South University, Changsha 410075, China)

With the increase of logistics demand in the AGV express parcel sorting system, layout optimization of the AGV express sorting system has become a key to improving logistics efficiency. First, based on the analysis of the main reasons that lead to congestion in the AGV express parcel sorting system, this paper investigated the layout optimization of the pick-up and delivery ports of the AGV express parcel sorting system. An integer programming optimization model is proposed, which aims to improve the balance of the load of sort system. Moreover, we address the corresponding improved genetic algorithm to solve the above optimization model. Finally, a case study of express sorting center is given to justify the validity of the optimization model and its corresponding algorithm. The findings show that: (1) The improved genetic algorithm can effectively reduce the loads standard deviations of the system. (2) Compared with the bidirectional four-station layout strategy, the loads standard deviations of the proposed four-direction four-station layout strategy and the diagonal four-station layout strategy are reduced by 22.89% and 55.7% respectively.

express parcels sorting; layout optimization; load balancing; genetic algorithm; case study

TP249

A

1672 − 7029(2021)02 − 0509 − 07

10.19713/j.cnki.43−1423/u.T20200392

2020−05−11

国家自然科学基金面上资助项目(71672193)；国家重点研发计划资助项目(2017YFB1201304)

张得志(1976−)，男，湖南祁东人，教授，博士，从事物流系统优化研究；E−mail：dzzhang@csu.edu.cn

(编辑 阳丽霞)