多人拣选系统拥堵的马尔科夫建模与仿真研究

尚娇，周丽，路雪鹏，李亚坤

多人拣选系统拥堵的马尔科夫建模与仿真研究

尚娇，周丽，路雪鹏，李亚坤

（北京物资学院 信息学院，北京 101149）

为了降低拣选系统拥堵率提高应急物资的运输效率，文中提出一种基于马尔科夫的多人拥堵模型。分别构建窄通道货位单件拣选和货位多件拣选情况下的马尔科夫状态转移矩阵，求解平稳分布，获得拣选概率与拥堵率的函数关系式，并通过仿真分析不同因素变化对拥堵率的影响。研究发现在货位单件拣选情况下，拣选概率取值为0.3左右时，系统拥堵率达到峰值，之后随拣选概率的增大而减小；在货位多件拣选情况下，拣选概率与系统拥堵率呈正相关，系统拥堵率随着拣选概率的增加而增加。在实际拣选作业中，为了降低系统拥堵率，货位单件拣选应尽量避免拣选概率在0.3左右；货位多件拣选应尽量降低拣选概率。

应急物流；窄通道；拥堵率；马尔科夫

2020年全国爆发新冠肺炎疫情，医疗用品成了各地的急需物资，2021年河南发生洪涝灾害，河南人民在全国求助应急抢险物品。如何更高效地应对自然灾害，提高应急物资的运输水平成了文中研究的主要问题。Wu等[1]针对未来应急物流保障需求，研究了系统工程方法和智能技术在应急物流领域的演变趋势和应用重点，分析了各种系统工程方法和关键技术在物流建模、仿真、分析、预测、评价、决策、管理、控制和规划设计，为实现应急物流跨越式发展提供了系统的工程基础和技术解决方案。Sun等[2]提出了一个双目标鲁棒优化模型，考虑了各种需求的不确定性，包括伤亡人数、救援物资数量和运输时间等因素，以确定由伤亡群、临时设施和综合医院组成的三级救援链中的设施位置、应急资源配置和伤亡运输计划。Wang等[3]对如何确定最优的应急设施数量及其最佳位置的问题进行了全面的综述，建模为一个离散的基于覆盖范围的应急设施选址问题，还讨论了基于覆盖模型的常用求解方法和未来的研究方向。Liu等[4]基于已定义的PLPR的乘性一致性，开发了一种一致性改进算法，在此基础上建立DEA模型，从可接受的乘性一致性PLPR中推导出备选方案的优先权向量，并通过应急物流配送选择的算例验证了该方法的有效性和适用性。

对于仓库内机器人的拥堵问题，很多学者通过路径规划来尽量避免拥堵的产生，在求解此类路径优化问题时，目前最多使用的算法为A*算法，该算法对避免拣选系统的拥堵情况有较明显的效果[5-9]。陈少华等[10]鉴于仓储拣选拥堵问题的重要性和多发性，对仓储拣选作业过程中影响拣选拥堵率的布局、拣选策略、储位指派、路径策略的国内外相关研究和解决方案进行了讨论和综述。Torsten等[11]研究了不同存储策略和拣选路径组合下的拣选机器人拥堵问题，设计了一个基于智能体的模拟模型（ABS）用于矩形仓库中的订单拣选，研究拣选机器人的行为以及他们与环境的相互作用，并对其拣选顺序选择过程的影响进行了评估，得出最优的存储策略和拣选机器人数量。Isravel等[12]提出了一种基于中心性的Q学习路由交通工程方法，用于拥堵检测和优化交通路由，并在不同的网络场景下，对不同的流量路径进行了仿真。结果表明，该方法在路径长度、时延、链路利用率、吞吐量和计算时间等方面优于现有方法。Aimtongkham等[13]提出了一种新的最小化拥堵的拣选方法，利用多级模糊逻辑来指定队列控制的最优通知级别。对拥堵发生时的提醒进行了调整，使模块更加灵活，提高了路由发现效率。

文中运用马尔科夫的无记忆性来计算多机器人拥堵模型，而马尔科夫性在仓库布局和拥堵率的计算方面也有一些研究。Nalivajevs等[14]给出了一个新的伪随机实例生成器，它反映了仓库订单提取和发布新的基准测试床。还使用条件马尔科夫链搜索框架自动生成新的GTSP元启发式训练，专门用于仓库订单提取。Wang等[15]使用带TOA和卡尔曼滤波器的超宽带开发板来计算定位结果在出现非视距误差时存在局限性，提出了基于马尔科夫链和手指匹配的2种方法，证明了这2种方法很好地解决了非视距误差问题。Roy等[16]提出了一种基于嵌入式马尔科夫链的分析方法，用于估计半开放排队网络中从负荷依赖站出发的间隔时间的第一和第二矩。Zhou等[17]用离散马尔科夫方法研究了具有传统布局、S型拣选路径和分类存储策略的窄通道双拣选系统的拣选拥堵问题。研究了拣选面的拣货数量对拥堵率的影响，对比了拣选者的行走速度与拣货速度相同和相差较大时的拥堵率。Zhou等[18]研究了宽通道拣货系统的影响因素，发现拣货密度和拣货面的个数对拣货时间比有影响，构造了拣选和行走速度一对一比条件下的离散马尔科夫状态转移概率矩阵，分析了拣选时间比、拣选密度与拣选面的个数之间的关系。研究结果可为拣货策略选择提供参考，代表了随机过程在物流作业系统应用研究的理论基础。

1 拥堵的产生

窄通道拣选系统具有节省仓库面积，提高空间利用率的优点，但是在实际拣选作业中，企业为了提高顾客的响应速度，同一时间拣选系统中通常会有多个拣选者工作，因此容易发生拣选拥堵的情况。窄通道背景下的拥堵包括2种，如图1所示，仓库通道后方拣选者不能通过前方拣选者或与前方拣选者并行。

图1 拥堵示意图

拥堵现象会延长后方拣选者的作业时间，降低仓库拣选效率，而拣选作业作为供应链上的关键环节，会影响到整个供应链的时效性。为了降低拣选拥堵率，提高拣选作业效率，有必要对拣选系统拥堵率进行建模研究。

2 模型假设、符号说明与状态描述

2.1 模型假设

由于现实仓库布局具有多样性，为了方便理论研究，做如下假设。

1）假设每列货架为一个拣选单元，拣选者在同一拣选单元各层进行拣货作业的时间相同。

2）在实际拣选作业中，同一通道两侧的拣选单元拣选距离相同，故假设每个货位包括2个分别位于通道两侧的拣选单元，仓库所有货架由个货位组成。

3）假设所有货物按照随机存储的原则存储，每个货位的拣选概率相同。

4）假设仓库中同时存在多个拣选者，所有拣选者的拣选时间相同，行走时间相同，并且拣选时间与行走时间的比例为1∶1。拣选时间指拣选者拣选一件货物所需的时间，行走时间指拣选者通过一个货位所需的时间。

图2 传统布局下S型拣选路径示意图

6）将仓库布局按照拣选方向抽象为环形拣选系统，该环形拣选系统按照顺时针顺序进行拣选，表示该拣选者处于拣选状态，表示该拣选者处于行走状态。当其中2位拣选者位于相邻的货位，并且位于拣选方向前方的拣选者处于拣选状态，位于拣选方向后方的拣选者处于行走状态时，仓库发生拥堵。

2.2 符号说明

为了方便构建多人拣选系统拥堵模型，做出以下符号说明：为货位总数量；为拣选者数量；1为第1位拣选者与第2位拣选者之间的相对距离；2为第2位拣选者与第3位拣选者之间的相对距离；3为第3位拣选者与第1位拣选者之间的相对距离；i为第位拣选者所处的状态；i为第位拣选者所处的位置；为拣选者处于拣选状态；为拣选者处于行走状态；为货位被拣选的概率；为货位不被拣选的概率。

上述符号有以下约束条件：

2.3 状态描述

图3 拣选者分布

[(1,1,‒2)堵, (1,1,‒2)不堵, (1,2,‒3)堵, (1,2,‒3)不堵],…, (1,‒2,1)堵, (1,‒2,1)不堵, (2,1,‒3)堵, (2,1,‒3)不堵, (2,2,‒4),…, (2,‒4,2), (2,‒3,1)堵, (2,‒3,1)不堵,…, (‒4,1,3)堵, (‒4,1,3)不堵, (‒4,2,2), (‒4,3,1)堵,(‒4,3,1)不堵, (‒3,1,2)堵, (‒3,1,2)不堵, (‒3,2,1)堵, (‒3,2,1)不堵, (‒2,1,1)堵, (‒2,1,1)不堵]

3 构建拥堵率模型

仓库在时刻的状态仅与时刻−1的状态有关，不受其他历史状态的影响，并且只影响时刻+1的仓库状态。正因为这种“无记忆”性，文中考虑建立离散时间马尔科夫模型来分析状态的转移概率矩阵。

[(1,1,…,‒+1)堵, (1,1,…,‒+1)不堵, …,(1,‒+1,…,1)堵, (1,‒+1, …,1)不堵,…,(2,1,‒)堵, (2,1, …,‒)不堵, (2,2, …,‒‒1), …, (2,‒, …,1)堵, (2,‒, …,1)不堵, …, (‒,1,…,2)堵, (‒,1,…,2)不堵, …, (‒,2, …,1)堵, (‒,2, …,1)不堵, (‒+1,1, …,1)堵, (‒+1,1, …,1)不堵]

记为仓库状态的Markov转移概率矩阵，简称为转移矩阵，有：

则位拣选者在仓库中进行拣选作业的平均拥堵率为：

3.1 货位单件拣选

3.1.1 状态转移矩阵

其他转态转移情况依次类推，绘制部分马尔科夫链状态转移图见图5。

图4 货位单件拣选下（1,2,7）堵的状态转移情况

图5 货位单件拣选下状态转移图

下面根据马尔科夫模型的构建原理建立状态转移矩阵1，由于状态转移矩阵1阶数过高，因此将矩阵1进行分级描述。

2）第2次分级。以二级矩阵1为例，阐述二级矩阵的推导过程。各个二级矩阵为某一类状态到另一类状态的概率转移矩阵，因此构成二级矩阵的元素为具体状态之间的转移概率。

综上所述，118堵到217不堵的转移概率为：

其他转移概率求解过程同上，求得1中各元素取值见表1。同理可求其他二级转移矩阵。

表1 H1中各元素取值

3.1.2 平稳分布与拥堵率

图6 货位单件拣选情况下p与的关系

3.2 货位多件拣选

3.2.1 状态转移矩阵

依次类推，绘制部分马尔科夫链状态转移见图8。

对货位多件拣选的状态转移矩阵2进行分级描述，具体操作步骤如下。

图7 货位多件拣选下的状态转移情况

图8 货位多件拣选下状态转移图

1）第1次分级。定义状态转移矩阵2为一级矩阵，由各二级矩阵组成。例如，2为从状态1到状态1的概率转移矩阵，2为从状态2到状态1的概率转移矩阵，2为从状态1到状态2的概率转移矩阵。

2）第2次分级。将状态1中各具体状态作为横向标签，状态2中各具体状态作为纵向标签，两两组合计算转移概率，得到二级矩阵2：

综上所述，118堵到217堵的转移概率为：

其他转移概率求解过程同上，可求出2中各元素取值，见表2。同理可求其他二级转移矩阵。

3.2.2 平稳分布与拥堵率

表2 H2中各元素取值

4 拥堵率模型仿真分析

4.1 不同货位的仿真模拟

图9 货位多件拣选情况下p与的关系

图10 货位单件拣选情况下货位变化对拥堵率的影响

图11 货位多件拣选情况下货位变化对拥堵率的影响

由图11可知，在货位多件拣选的情况下，当拣选概率固定时，随着货位总量的增加拥堵率不断减小，显然货位总量的增加减小了拣选人员相遇的概率；当货位总数量固定时，拥堵率随着拣选概率的增大而增大，因为单个货位被重复拣选的次数越多，越容易阻塞后方的拣选者。

图11与图10的区别在于单个货位的拣选次数，当单个货位拣选次数大于1，拣选次数的增加会导致拣选概率与平均拥堵率呈现正比例关系，并在拣选概率为1时取峰值。

4.2 不同拣选者的仿真模拟

图12 货位单件拣选下拣选者人数变化对拥堵率的影响

图13 货位多件拣选下拣选者人数变化对拥堵率的影响

5 结语

文中设计了一种基于马尔科夫的多人拣选拥堵模型，在传统仓库窄通道拣选的背景下，将仓库布局抽象成环形拣选系统，对货位单件拣选和货位多件拣选这2种拣选方式分别建立马尔科夫状态转移矩阵，通过求解平稳分布，获得拥堵率表达式，并分析拣选概率与拥堵率函数关系图。

在后续工作中，将进一步研究拣选时间与行走时间不同比值下的拥堵率。在理论方面，文章丰富了随机过程理论在仓储拣选方面的相关理论和研究内容，为研究仓库拥堵率提供了新的思路。在实践方面，文中提出的拥堵模型有望进一步降低仓库订单拣选的拥堵率，提高拣选速度，增强社会应对公共突发事件的应急能力。

[1] WU Liang, XU Dong. Research on Method and Technology of Emergency Logistics Intelligent System Engineering[M]. Singapore: Springer, 2021: 159-167.

[2] SUN Hua-li, WANG Yang, XUE Yao-feng. A Bi-Objective Robust Optimization Model for Disaster Response Planning under Uncertainties[J]. Computers & Industrial Engineering, 2021, 155(3): 107-213.

[3] WANG Wei, WU Shi-ning, WANG Shuai-an, et al. Emergency Facility Location Problems in Logistics: Status and Perspectives[J]. Transportation Research Part E Logistics and Transportation Review, 2021, 154(4): 102465.

[4] LIU Jin-pei, Zheng Y, ZHOU L, et al. A Novel Probabilistic Linguistic Decision-making Method with Consistency Improvement Algorithm and DEA Cross- Efficiency[J]. Engineering Applications of Artificial Intelligence, 2021, 99(2): 104-108.

[5] 董朝瑞, 郭欣, 李宁, 等. 基于改进A～*算法的多机器人动态路径规划[J]. 高技术通讯, 2020, 30(1): 71-81.

DONG Zhao-rui, GUO Xin, LI Ning, et al. Multi-Robot Dynamic Path Planning Based on Improved A～* Algorithms[J]. Chinese High Technology Letters, 2020, 30(1): 71-81.

[6] 刘盼盼, 杨三慧. 多移动机器人路径规划方法研究[J]. 福建质量管理, 2020, 11(1): 262-263.

LIU Pan-pan, YANG San-hui. Research on Path Planning Method of Multi-mobile Robot[J]. Fujian Quality Management, 2020, 11(1): 262-263.

[7] 张志文, 张鹏, 毛虎平, 等. 改进A^(*)算法的机器人路径规划研究[J]. 电光与控制, 2021, 28(4): 21-25.

ZHANG Zhi-wen, ZHANG Peng, MAO Hu-ping, et al. Path Planning of Mobile Robot Based on Improved A^(*)Algorithm[J]. Electronics Optics & Control, 2021, 28(4): 21-25.

[8] 王秀红, 刘雪豪, 王永成. 基于改进A～*算法的仓储物流移动机器人任务调度和路径优化研究[J]. 工业工程, 2019, 22(6): 34-39.

WANG Xiu-hong, LIU Xue-hao, WANG Yong-cheng. A Research on Task Scheduling and Path Planning of Mobile Robot in Warehouse Logistics Based on Improved A～* Algorithm[J]. Industrial Engineering Journal, 2019, 22(6): 34-39.

[9] 刘建娟, 薛礼啟, 张会娟, 等. 融合改进A^(*)与DWA算法的机器人动态路径规划[J]. 计算机工程与应用, 2021, 57(15): 73-81.

LIU Jian-juan, XUE Li-qi, ZHANG Hui-juan, et al. Robot Dynamic Path Planning Based on Improved A^(*) and DWAAlgorithm[J]. Computer Engineering and Applications, 2021, 57(15): 73-81.

[10] 陈少华, 周丽, 程晓. 拣选作业拥堵率影响因素研究综述[J]. 物流技术, 2015, 34(17): 22-25.

CHEN Shao-hua, ZHOU Li, CHENG Xiao. Summary of Researches on Influence Factors of Sorting Activity Congestion Rate[J]. Logistics Technology, 2015, 34(17): 22-25.

[11] FRANZKE T, GROSSE E H, GLOCK C H, et al. An Investigation of the Effects of Storage Assignment and Picker Routing on the Occurrence of Picker Blocking in Manual Picker-to-Parts Warehouses[J]. The International Journal of Logistics Management, 2017, 28(3): 841-863.

[12] PRIYA I D, SALAJA S, BLESSING R E. Centrality Based Congestion Detection Using Reinforcement Learning Approach for Traffic Engineering in Hybrid SDN[J]. Journal of Network and Systems Management, 2021, 30(1): 1-22.

[13] AIMTONGKHAM P, HORKAEW P, SO-IN C. Multistage Fuzzy Logic Congestion-Aware Routing Using Dual-stage Notification and the Relative Barring Distance in Wireless Sensor Networks[J]. Wireless Networks, 2021, 27(2): 1287-1308.

[14] NALIVAJEVS O, KARAPETYAN D. Conditional Markov Chain Search for the Generalised Travelling Salesman Problem for Warehouse Order Picking[C]// 2019 11th Computer Science and Electronic Engineering (CEEC), IEEE, 2019: 75-78.

[15] WANG Zi-rui, LI Shao-xian, ZHANG Zheng-yuan, et al. Research on UWB Positioning Accuracy in Warehouse Environment[J]. Procedia Computer Science, 2018, 131: 946-951.

[16] ROY D, KRISHNAMURTHY A, HERAGU S S, et al. A Multi-Tier Linking Approach to Analyze Performance of Vehicle-Based Warehouse Systems[J]. SSRN Electronic Journal, 2016, 83: 173-188.

[17] ZHOU Li, NIU Xia-xia, ZHAO Sheng-li, et al. Research on Congestion Rate of Classified Storage Narrow Channel Picking System for IoT Security[J]. Wireless Networks, 2020, 26(8): 1-17.

[18] ZHOU Li, LIU Hong-jian, ZHAO Xiao-qing, et al. Study on the Estimation of Blocking Rate in Wide-Aisle Picking System[J]. Soft Computing, 2019, 23(13): 4891-4902.

Markov Modeling and Simulation of Congestion in Multi-person Picking System

SHANG Jiao, ZHOU Li, LU Xue-peng, LI Ya-kun

(School of Information, Beijing Wuzi University, Beijing 101149, China)

The work aims to propose a multi-person congestion model based on Markov, in order to reduce the congestion rate of the picking system and improve the transportation efficiency of emergency materials. The Markov state transition matrices of single picking in cargo slot and multiple picking in cargo slot in narrow channel were constructed to solve the stationary distribution, and obtain the functional relationship between the picking probability and the congestion rate. The effect of different factors on the congestion rate was analyzed by simulation. Under single picking in cargo slot, the system congestion rate reached its peak at the picking probability of about 0.3, and then decreased with the increase of the picking probability. Under multiple picking in cargo slot, the picking probability was positively correlated with the system congestion rate, and the system congestion rate increased with the increasing picking probability. Therefore, in the actual picking operation, in order to reduce the system congestion rate, the picking probability of about 0.3 should be avoided under single picking in cargo slot and under multiple picking, the picking probability should be reduced as much as possible.

emergency logistics; narrow channel; congestion rate; Markov

O29

A

1001-3563(2023)01-0111-12

10.19554/j.cnki.1001-3563.2023.01.013

2022–03–07

北京社会科学基金重点项目（18GLA009）

尚娇（1997—），女，硕士生，主攻智能物流系统。

周丽（1978—），女，博士，教授，主要研究方向为智能物流系统。

责任编辑：曾钰婵