多人揀選系統(tǒng)擁堵的馬爾科夫建模與仿真研究

尚嬌，周麗，路雪鵬，李亞坤

多人揀選系統(tǒng)擁堵的馬爾科夫建模與仿真研究

尚嬌，周麗，路雪鵬，李亞坤

（北京物資學(xué)院 信息學(xué)院，北京 101149）

為了降低揀選系統(tǒng)擁堵率提高應(yīng)急物資的運輸效率，文中提出一種基于馬爾科夫的多人擁堵模型。分別構(gòu)建窄通道貨位單件揀選和貨位多件揀選情況下的馬爾科夫狀態(tài)轉(zhuǎn)移矩陣，求解平穩(wěn)分布，獲得揀選概率與擁堵率的函數(shù)關(guān)系式，并通過仿真分析不同因素變化對擁堵率的影響。研究發(fā)現(xiàn)在貨位單件揀選情況下，揀選概率取值為0.3左右時，系統(tǒng)擁堵率達到峰值，之后隨揀選概率的增大而減??；在貨位多件揀選情況下，揀選概率與系統(tǒng)擁堵率呈正相關(guān)，系統(tǒng)擁堵率隨著揀選概率的增加而增加。在實際揀選作業(yè)中，為了降低系統(tǒng)擁堵率，貨位單件揀選應(yīng)盡量避免揀選概率在0.3左右；貨位多件揀選應(yīng)盡量降低揀選概率。

應(yīng)急物流；窄通道；擁堵率；馬爾科夫

2020年全國爆發(fā)新冠肺炎疫情，醫(yī)療用品成了各地的急需物資，2021年河南發(fā)生洪澇災(zāi)害，河南人民在全國求助應(yīng)急搶險物品。如何更高效地應(yīng)對自然災(zāi)害，提高應(yīng)急物資的運輸水平成了文中研究的主要問題。Wu等[1]針對未來應(yīng)急物流保障需求，研究了系統(tǒng)工程方法和智能技術(shù)在應(yīng)急物流領(lǐng)域的演變趨勢和應(yīng)用重點，分析了各種系統(tǒng)工程方法和關(guān)鍵技術(shù)在物流建模、仿真、分析、預(yù)測、評價、決策、管理、控制和規(guī)劃設(shè)計，為實現(xiàn)應(yīng)急物流跨越式發(fā)展提供了系統(tǒng)的工程基礎(chǔ)和技術(shù)解決方案。Sun等[2]提出了一個雙目標(biāo)魯棒優(yōu)化模型，考慮了各種需求的不確定性，包括傷亡人數(shù)、救援物資數(shù)量和運輸時間等因素，以確定由傷亡群、臨時設(shè)施和綜合醫(yī)院組成的三級救援鏈中的設(shè)施位置、應(yīng)急資源配置和傷亡運輸計劃。Wang等[3]對如何確定最優(yōu)的應(yīng)急設(shè)施數(shù)量及其最佳位置的問題進行了全面的綜述，建模為一個離散的基于覆蓋范圍的應(yīng)急設(shè)施選址問題，還討論了基于覆蓋模型的常用求解方法和未來的研究方向。Liu等[4]基于已定義的PLPR的乘性一致性，開發(fā)了一種一致性改進算法，在此基礎(chǔ)上建立DEA模型，從可接受的乘性一致性PLPR中推導(dǎo)出備選方案的優(yōu)先權(quán)向量，并通過應(yīng)急物流配送選擇的算例驗證了該方法的有效性和適用性。

對于倉庫內(nèi)機器人的擁堵問題，很多學(xué)者通過路徑規(guī)劃來盡量避免擁堵的產(chǎn)生，在求解此類路徑優(yōu)化問題時，目前最多使用的算法為A*算法，該算法對避免揀選系統(tǒng)的擁堵情況有較明顯的效果[5-9]。陳少華等[10]鑒于倉儲揀選擁堵問題的重要性和多發(fā)性，對倉儲揀選作業(yè)過程中影響揀選擁堵率的布局、揀選策略、儲位指派、路徑策略的國內(nèi)外相關(guān)研究和解決方案進行了討論和綜述。Torsten等[11]研究了不同存儲策略和揀選路徑組合下的揀選機器人擁堵問題，設(shè)計了一個基于智能體的模擬模型（ABS）用于矩形倉庫中的訂單揀選，研究揀選機器人的行為以及他們與環(huán)境的相互作用，并對其揀選順序選擇過程的影響進行了評估，得出最優(yōu)的存儲策略和揀選機器人數(shù)量。Isravel等[12]提出了一種基于中心性的Q學(xué)習(xí)路由交通工程方法，用于擁堵檢測和優(yōu)化交通路由，并在不同的網(wǎng)絡(luò)場景下，對不同的流量路徑進行了仿真。結(jié)果表明，該方法在路徑長度、時延、鏈路利用率、吞吐量和計算時間等方面優(yōu)于現(xiàn)有方法。Aimtongkham等[13]提出了一種新的最小化擁堵的揀選方法，利用多級模糊邏輯來指定隊列控制的最優(yōu)通知級別。對擁堵發(fā)生時的提醒進行了調(diào)整，使模塊更加靈活，提高了路由發(fā)現(xiàn)效率。

文中運用馬爾科夫的無記憶性來計算多機器人擁堵模型，而馬爾科夫性在倉庫布局和擁堵率的計算方面也有一些研究。Nalivajevs等[14]給出了一個新的偽隨機實例生成器，它反映了倉庫訂單提取和發(fā)布新的基準(zhǔn)測試床。還使用條件馬爾科夫鏈搜索框架自動生成新的GTSP元啟發(fā)式訓(xùn)練，專門用于倉庫訂單提取。Wang等[15]使用帶TOA和卡爾曼濾波器的超寬帶開發(fā)板來計算定位結(jié)果在出現(xiàn)非視距誤差時存在局限性，提出了基于馬爾科夫鏈和手指匹配的2種方法，證明了這2種方法很好地解決了非視距誤差問題。Roy等[16]提出了一種基于嵌入式馬爾科夫鏈的分析方法，用于估計半開放排隊網(wǎng)絡(luò)中從負(fù)荷依賴站出發(fā)的間隔時間的第一和第二矩。Zhou等[17]用離散馬爾科夫方法研究了具有傳統(tǒng)布局、S型揀選路徑和分類存儲策略的窄通道雙揀選系統(tǒng)的揀選擁堵問題。研究了揀選面的揀貨數(shù)量對擁堵率的影響，對比了揀選者的行走速度與揀貨速度相同和相差較大時的擁堵率。Zhou等[18]研究了寬通道揀貨系統(tǒng)的影響因素，發(fā)現(xiàn)揀貨密度和揀貨面的個數(shù)對揀貨時間比有影響，構(gòu)造了揀選和行走速度一對一比條件下的離散馬爾科夫狀態(tài)轉(zhuǎn)移概率矩陣，分析了揀選時間比、揀選密度與揀選面的個數(shù)之間的關(guān)系。研究結(jié)果可為揀貨策略選擇提供參考，代表了隨機過程在物流作業(yè)系統(tǒng)應(yīng)用研究的理論基礎(chǔ)。

1 擁堵的產(chǎn)生

窄通道揀選系統(tǒng)具有節(jié)省倉庫面積，提高空間利用率的優(yōu)點，但是在實際揀選作業(yè)中，企業(yè)為了提高顧客的響應(yīng)速度，同一時間揀選系統(tǒng)中通常會有多個揀選者工作，因此容易發(fā)生揀選擁堵的情況。窄通道背景下的擁堵包括2種，如圖1所示，倉庫通道后方揀選者不能通過前方揀選者或與前方揀選者并行。

圖1 擁堵示意圖

擁堵現(xiàn)象會延長后方揀選者的作業(yè)時間，降低倉庫揀選效率，而揀選作業(yè)作為供應(yīng)鏈上的關(guān)鍵環(huán)節(jié)，會影響到整個供應(yīng)鏈的時效性。為了降低揀選擁堵率，提高揀選作業(yè)效率，有必要對揀選系統(tǒng)擁堵率進行建模研究。

2 模型假設(shè)、符號說明與狀態(tài)描述

2.1 模型假設(shè)

由于現(xiàn)實倉庫布局具有多樣性，為了方便理論研究，做如下假設(shè)。

1）假設(shè)每列貨架為一個揀選單元，揀選者在同一揀選單元各層進行揀貨作業(yè)的時間相同。

2）在實際揀選作業(yè)中，同一通道兩側(cè)的揀選單元揀選距離相同，故假設(shè)每個貨位包括2個分別位于通道兩側(cè)的揀選單元，倉庫所有貨架由個貨位組成。

3）假設(shè)所有貨物按照隨機存儲的原則存儲，每個貨位的揀選概率相同。

4）假設(shè)倉庫中同時存在多個揀選者，所有揀選者的揀選時間相同，行走時間相同，并且揀選時間與行走時間的比例為1∶1。揀選時間指揀選者揀選一件貨物所需的時間，行走時間指揀選者通過一個貨位所需的時間。

圖2 傳統(tǒng)布局下S型揀選路徑示意圖

6）將倉庫布局按照揀選方向抽象為環(huán)形揀選系統(tǒng)，該環(huán)形揀選系統(tǒng)按照順時針順序進行揀選，表示該揀選者處于揀選狀態(tài)，表示該揀選者處于行走狀態(tài)。當(dāng)其中2位揀選者位于相鄰的貨位，并且位于揀選方向前方的揀選者處于揀選狀態(tài)，位于揀選方向后方的揀選者處于行走狀態(tài)時，倉庫發(fā)生擁堵。

2.2 符號說明

為了方便構(gòu)建多人揀選系統(tǒng)擁堵模型，做出以下符號說明：為貨位總數(shù)量；為揀選者數(shù)量；1為第1位揀選者與第2位揀選者之間的相對距離；2為第2位揀選者與第3位揀選者之間的相對距離；3為第3位揀選者與第1位揀選者之間的相對距離；i為第位揀選者所處的狀態(tài)；i為第位揀選者所處的位置；為揀選者處于揀選狀態(tài)；為揀選者處于行走狀態(tài)；為貨位被揀選的概率；為貨位不被揀選的概率。

上述符號有以下約束條件：

2.3 狀態(tài)描述

圖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 構(gòu)建擁堵率模型

倉庫在時刻的狀態(tài)僅與時刻?1的狀態(tài)有關(guān)，不受其他歷史狀態(tài)的影響，并且只影響時刻+1的倉庫狀態(tài)。正因為這種“無記憶”性，文中考慮建立離散時間馬爾科夫模型來分析狀態(tài)的轉(zhuǎn)移概率矩陣。

[(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)不堵]

記為倉庫狀態(tài)的Markov轉(zhuǎn)移概率矩陣，簡稱為轉(zhuǎn)移矩陣，有：

則位揀選者在倉庫中進行揀選作業(yè)的平均擁堵率為：

3.1 貨位單件揀選

3.1.1 狀態(tài)轉(zhuǎn)移矩陣

其他轉(zhuǎn)態(tài)轉(zhuǎn)移情況依次類推，繪制部分馬爾科夫鏈狀態(tài)轉(zhuǎn)移圖見圖5。

圖4 貨位單件揀選下（1,2,7）堵的狀態(tài)轉(zhuǎn)移情況

圖5 貨位單件揀選下狀態(tài)轉(zhuǎn)移圖

下面根據(jù)馬爾科夫模型的構(gòu)建原理建立狀態(tài)轉(zhuǎn)移矩陣1，由于狀態(tài)轉(zhuǎn)移矩陣1階數(shù)過高，因此將矩陣1進行分級描述。

2）第2次分級。以二級矩陣1為例，闡述二級矩陣的推導(dǎo)過程。各個二級矩陣為某一類狀態(tài)到另一類狀態(tài)的概率轉(zhuǎn)移矩陣，因此構(gòu)成二級矩陣的元素為具體狀態(tài)之間的轉(zhuǎn)移概率。

綜上所述，118堵到217不堵的轉(zhuǎn)移概率為：

其他轉(zhuǎn)移概率求解過程同上，求得1中各元素取值見表1。同理可求其他二級轉(zhuǎn)移矩陣。

表1 H1中各元素取值

3.1.2 平穩(wěn)分布與擁堵率

圖6 貨位單件揀選情況下p與的關(guān)系

3.2 貨位多件揀選

3.2.1 狀態(tài)轉(zhuǎn)移矩陣

依次類推，繪制部分馬爾科夫鏈狀態(tài)轉(zhuǎn)移見圖8。

對貨位多件揀選的狀態(tài)轉(zhuǎn)移矩陣2進行分級描述，具體操作步驟如下。

圖7 貨位多件揀選下的狀態(tài)轉(zhuǎn)移情況

圖8 貨位多件揀選下狀態(tài)轉(zhuǎn)移圖

1）第1次分級。定義狀態(tài)轉(zhuǎn)移矩陣2為一級矩陣，由各二級矩陣組成。例如，2為從狀態(tài)1到狀態(tài)1的概率轉(zhuǎn)移矩陣，2為從狀態(tài)2到狀態(tài)1的概率轉(zhuǎn)移矩陣，2為從狀態(tài)1到狀態(tài)2的概率轉(zhuǎn)移矩陣。

2）第2次分級。將狀態(tài)1中各具體狀態(tài)作為橫向標(biāo)簽，狀態(tài)2中各具體狀態(tài)作為縱向標(biāo)簽，兩兩組合計算轉(zhuǎn)移概率，得到二級矩陣2：

綜上所述，118堵到217堵的轉(zhuǎn)移概率為：

其他轉(zhuǎn)移概率求解過程同上，可求出2中各元素取值，見表2。同理可求其他二級轉(zhuǎn)移矩陣。

3.2.2 平穩(wěn)分布與擁堵率

表2 H2中各元素取值

4 擁堵率模型仿真分析

4.1 不同貨位的仿真模擬

圖9 貨位多件揀選情況下p與的關(guān)系

圖10 貨位單件揀選情況下貨位變化對擁堵率的影響

圖11 貨位多件揀選情況下貨位變化對擁堵率的影響

由圖11可知，在貨位多件揀選的情況下，當(dāng)揀選概率固定時，隨著貨位總量的增加擁堵率不斷減小，顯然貨位總量的增加減小了揀選人員相遇的概率；當(dāng)貨位總數(shù)量固定時，擁堵率隨著揀選概率的增大而增大，因為單個貨位被重復(fù)揀選的次數(shù)越多，越容易阻塞后方的揀選者。

圖11與圖10的區(qū)別在于單個貨位的揀選次數(shù)，當(dāng)單個貨位揀選次數(shù)大于1，揀選次數(shù)的增加會導(dǎo)致揀選概率與平均擁堵率呈現(xiàn)正比例關(guān)系，并在揀選概率為1時取峰值。

4.2 不同揀選者的仿真模擬

圖12 貨位單件揀選下揀選者人數(shù)變化對擁堵率的影響

圖13 貨位多件揀選下揀選者人數(shù)變化對擁堵率的影響

5 結(jié)語

文中設(shè)計了一種基于馬爾科夫的多人揀選擁堵模型，在傳統(tǒng)倉庫窄通道揀選的背景下，將倉庫布局抽象成環(huán)形揀選系統(tǒng)，對貨位單件揀選和貨位多件揀選這2種揀選方式分別建立馬爾科夫狀態(tài)轉(zhuǎn)移矩陣，通過求解平穩(wěn)分布，獲得擁堵率表達式，并分析揀選概率與擁堵率函數(shù)關(guān)系圖。

在后續(xù)工作中，將進一步研究揀選時間與行走時間不同比值下的擁堵率。在理論方面，文章豐富了隨機過程理論在倉儲揀選方面的相關(guān)理論和研究內(nèi)容，為研究倉庫擁堵率提供了新的思路。在實踐方面，文中提出的擁堵模型有望進一步降低倉庫訂單揀選的擁堵率，提高揀選速度，增強社會應(yīng)對公共突發(fā)事件的應(yīng)急能力。

[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～*算法的多機器人動態(tài)路徑規(guī)劃[J]. 高技術(shù)通訊, 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] 劉盼盼, 楊三慧. 多移動機器人路徑規(guī)劃方法研究[J]. 福建質(zhì)量管理, 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^(*)算法的機器人路徑規(guī)劃研究[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～*算法的倉儲物流移動機器人任務(wù)調(diào)度和路徑優(yōu)化研究[J]. 工業(yè)工程, 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算法的機器人動態(tài)路徑規(guī)劃[J]. 計算機工程與應(yīng)用, 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] 陳少華, 周麗, 程曉. 揀選作業(yè)擁堵率影響因素研究綜述[J]. 物流技術(shù), 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

北京社會科學(xué)基金重點項目（18GLA009）

尚嬌（1997—），女，碩士生，主攻智能物流系統(tǒng)。

周麗（1978—），女，博士，教授，主要研究方向為智能物流系統(tǒng)。

責(zé)任編輯：曾鈺嬋