基于負載量均衡的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

(編輯 陽麗霞)