包裹智能分拣系统提效降损交通管控方法

李 珲，肖海宁,王雨轩,顾海航,陆俊曦

(盐城工学院机械工程学院，江苏 盐城 224051)

近年来，随着我国电子商务的发展进入井喷时期，快递包裹量逐年上升，使得快递分拣及配送压力日益增大，多数快递公司在“双十一”“双十二”期间会出现配送延误甚至包裹丢失现象[1]。造成这一现象的根源在于国内快递包裹分拣工作依然依赖于人工，不仅分拣准确性及效率低，且易造成包裹的损坏。为了提升快递包裹分拣的自动化程度和效率，国内外在新型分拣系统开发、分拣作业流程及方法优化等方面开展了一系列的探索工作。如：李明等[1]针对货物品相分配优化问题，研究了设备通道配比优化数学模型和启发式求解算法；许丹[2]根据A公司分拨中心布局和采用的分拣技术，探索了一种多路并行分拣模式；杨敏[3]设计了一种垂直输送分拣设备，并从增强平稳性、提高效率、降低成本的角度对其结构进行了优化；韩兴[4]开发了一种应用于交叉带分拣机入口的自动化分拣系统，并研究了快递分拣算法；李昭等[5]设计了一种包括分拣执行机构和承接轨道的分拣装置，并对关键结构的设计方法进行了研究；黄梦涛等[6]为了提高快递分拣系统的效率和自动化程度，研究了用于快递分拣的二维码定位与校正方法；王立平[7]为了提升分拣系统的柔性及可扩展性，对某基于柔性分拣单元的高效智能分拣系统中的分拣信息识别技术、分拣优化策略等进行了研究；德国不莱梅大学生产与物流研究所开发了一款模块化的智能物流系统 Celluveyor，在一些工业场合的应用已证明其具有灵活性好、鲁棒性强、扩容方便等优势，具备广阔的应用前景[8]。然而，目前国内分拣系统依然基于滚筒、皮带等较为落后的输送技术，在分拣效率及灵活性上难以取得重大突破，此外，国内外针对如何降低包裹分拣破损率的研究较少，导致包裹在分拣过程中易发生相互碰撞而损坏，不利于易破损包裹的分拣。为了提高包裹分拣的灵活性与系统鲁棒性，本文设计了一款基于全方位轮的新型模块化包裹智能分拣系统。

1 包裹智能分拣系统简介

图1为本文设计的包裹智能分拣系统示意图，中间为分拣区域，四周分布有入口传送带与出口传送带，各出口传送带用于输出各自指定地区的包裹。待分拣包裹自入口传送带依次进入分拣区域。整个分拣区域由分拣模块整齐填充。各分拣模块安装有可识别包裹信息的数据采集装置，可根据各包裹信息确定其输送方向。通过多个相邻分拣模块的接力输送可将包裹输送至对应地区的出口传送带。

1—快递包裹；2—入口传送带；3—分拣区域；4—分拣区域出口传送带；5—分拣模块

分拣区域分拣作业整体调控流程如图2所示,由路径规划与交通管控两大功能模块组成，当新包裹进入分拣区域时，路径规划功能模块根据包裹所处的入口传送带和所需送达的地区，为其规划一条分拣路径——完成分拣所需途径的分拣模块序列。路径规划算法可采用Dijkstra算法[9]，本文不作讨论。然而，由于包裹间的分拣路径重叠在所难免，交通管控功能模块必须协调各包裹按照各自分拣路径依次进入各分拣模块，以避免包裹间发生碰撞及环形死锁。有必要针对分拣系统中可能出现的路径冲突及环形死锁，设计对应的提效降损交通管控方法。

图2 分拣作业整体流程

2 路径冲突及对应的避碰策略

2.1 主要符号简介

首先定义本文中使用的主要符号：

ΩM={Mi|1≤i≤NM}，为分拣区域分拣模块集合，其中Mi为第i个分拣模块，NM为分拣模块数。

G(Mi)为当前正占用Mi的包裹。

2.2 冲突及对应的避碰策略

图3 包裹路径冲突示例

为了避免包裹间发生碰撞，设计了基于互斥型信号量的避碰策略，通过信号量的“申请—阻塞—授权—占用—释放”机制避免系统中的各包裹发生碰撞，具体步骤如下：

其中，I(Mi) 定义为：

(1)

(2)

(3)

①循环初始化，设置m=1，进入②。

步骤3，所有包裹均已完成分拣，结束。

通过上述流程可保证任一分拣模块在任意时刻至多仅会授权给一个包裹，从而避免包裹间发生碰撞。

3 环形死锁检测与避免算法

3.1 环形死锁及其检测方法

图4 环形死锁现象示意图

首先，基于有向图理论建立包裹阻塞图模型。

定义1：包裹阻塞图ΛQ(VQ，EQ)。该图为有向图，其中顶点集VQ定义为：

VQ={Mi|Mi∈ΩM且I(Mi)=1}

(4)

边集EQ定义为：

(5)

式中：Mi为边ei,j的起点；Mj为边ei,j的终点，Mj也称为Mi的前向相邻节点，记Adj(Mi)=Mj。

定理1：在阻塞图中的一个有向环路即为环形死锁。该环形死锁可采用阻塞图中的有向节点序列表示，即环形死锁LP={Mi,…,Mj,…,Mn}。

证明：根据阻塞图的定义，LP中的任一分拣模块Mi均已被包裹占用，则环路中的所有包裹均无法移动，因此LP是环形死锁。

步骤2,检测MC是否存在前向相邻节点Adj(MC)，若Adj(MC)=Ø，则不会引发环形死锁，转步骤4；否则，转步骤3。

步骤4,输出检测结果，结束。

3.2 环形死锁临界状态及对应的死锁避免算法

若检测到环形死锁，则说明分拣系统此时处于环形死锁临界状态。下面根据环形死锁临界状态的类型，设计对应的死锁避免算法。

图5 单环形死锁临界状态示例

4 方法验证

4.1 包裹智能分拣系统仿真平台的开发

图6 多环形死锁临界状态示例

图7 包裹智能分拣系统仿真平台

4.2 实验及分析

利用该仿真模型比较3种交通管控方法。

方法1(Method 1，M1)：本文所设计的提效降损交通管控方法。

方法2(Method 2，M2)：仅采用本文所设计的避碰策略，不采用环形死锁检测与避免算法。

方法3(Method 3，M3)：全程独占法，即包裹只有在一次性获得路径全程所有分拣模块的使用权后才进入分拣区域。

图8 系统单位小时平均分拣包裹数

图9 所有包裹平均分拣耗时

图10 环形死锁临界状态出现次数

5 结束语

本文针对新型包裹智能分拣系统设计的提效降损交通管控方法，能够避免包裹间发生碰撞及环形死锁现象，有利于易破损包裹的分拣。但受试验条件限制，本文所设计的提效降损交通管控方法仅通过仿真进行了分析，没有经过实际工程试验验证，有一定的局限性，后续将尽可能和相关企业联合进行试验验证，以进一步完善所设计的提效降损交通管控方法。