基于遺傳算法的倉內揀貨優先問題研究

楊海祥

摘要：網購、快遞已經成為這個時代的專有名詞。但是在每個快遞公司的倉庫當中每時每刻都在進行著一場戰爭——以最快的速度將所有的貨物送到買家的手里。該文著重解決遺傳算法等思想，給每個揀貨員分配任務單、起始揀貨復核臺，并分別規劃理想的揀貨路線，使得 49 個任務單盡快完成出庫，并計算完成出庫需要花費的時間和每個復核臺利用率。根據揀貨員倉庫作業的特點，對目標求解模型進行約束及優化，最后遺傳算法為每個工人分配訂單后確認其順序，確定最優的訂單分配方案，之后通過排隊優化算法解決排隊問題。

關鍵詞：遺傳算法;排隊問題

快遞公司的倉庫當中每時每刻都在進行著一場戰爭——以最快的速度將所有的貨物送到買家的手里。但是很多的因素會對揀貨員的揀貨速度造成影響。本文想對當下中國的揀貨機制進行一定的改善，其中包括揀貨員的路徑，揀貨員拿貨單的順序，排隊最優等部分，將在下面展開討論。

1 問題分析

首先需要制定距離的計算公式，在行走速度相同的情況下，距離越短，時間越短。貨格與貨格、貨格與復核臺、復核臺與復核臺之間均分別存在著特殊的位置關系，觀察分析后，為方便對模型進行描述和求解，我們根據倉庫示意圖對倉庫內的元素用三維數組進行編號，將3013個元素分為貨格與貨格、貨格與復核臺、復核臺與復核臺三種情況分別進行計算，再分別建立模型并求解結果。

然后將問題簡化為起點固定、有13個終點可以選擇的路徑優化問題，運用啟發式算法、遺傳算法等思想，最短距離求解模型建立一個有起點、有終點、有活動的最短路徑目標求解模型，根據揀貨員倉庫作業的特點，對目標求解模型進行約束及優化，再對模型進行編程求解。

利用上面的模型將每個任務單完成需要的時間確定出來，之后通過時間升序排序，可以極大節約訂單等待時間。49個任務單從開始的那一刻將有9個任務單同時分配給9個揀貨員，之后9個揀貨員完成所規定的任務單時間能夠確定，但是由于復核時間為30秒，復刻臺只有4個，肯定存在等待時間，所以可以等待問題簡化為經典的排隊問題，每當一個任務單復核完成我們將給他在此復核臺直接分配下一個任務單，直至所有任務單完成。即為揀貨員的最佳完成時間。

2 模型的建立與求解

現根據倉庫貨格的編號[abc]，首先建立距離計算模型。

假設任意兩個貨格的編號為[aibici]，[ajbjcj]。當兩個貨格在同排同一巷道內且同一側時，這兩個貨格之間的距離即為縱向距離加一個巷道的寬度1500毫米，則距離[dij]為：

當兩個貨格在不同的巷道內，無論在同一側還是不同側時，都需要首先判斷揀貨員從巷道和通道交叉的哪個方向出來，因此，需要先進行最小路徑的優先選擇。按從下至上的順序第一排內兩貨格的距離計算[dij]為：

綜上，將任意兩貨格之間距離的計算分為四種情況，對于貨格不同的位置情況，對應不同的公式，利用上述模型求出距離后，結合每個貨格的長和寬，即可求出任意兩貨格之間的距離。貨格與復刻臺以及復刻臺與復刻臺之間的計算在此省略。

同時將整個揀貨路徑優化模型定義為：

綜上，將任務單[T0001]內的每個貨格以及起點復核臺[FH10]、[13]個可以作為終點的復核臺代入，求解得最優路徑。

將上述模型中的揀貨員分批后的每一批訂單所在的貨架位置信息輸入到系統中來，應用matlab 來對遺傳算法進行實現，通過求解得出每一臺AGV揀貨員的任務分配及路徑優化結果。對訂單按照貨架信息進行任務分配及路徑規劃。

批訂單中包含49個訂單，其共分布在不同的貨架上，各個貨架的貨格坐標由第一問的模型已知其三維坐標位置。

此處的坐標如（5，1，6） 代表貨架所在的位置信息為所有貨架的第一巷道右側第六個貨格。將以上的貨架貨格位置信息導入到算法中。

由運行結果可知，當算法迭代到48465次的時候得到最優解，此時最短路徑為367.5，并且可通過運行得出下表每個AGV揀貨員搬運的距離。

3 結論

在倉庫貨格與貨格之間、貨格與復核臺之間以及復核臺與復核臺之間計算距離的數學模型，是將問題簡化后所建立的，可描述性強。對于完成任務單最短路徑計算的模型，運用了最短路徑的求解思想，使得模型轉化為原點、活動以及終點之間的最短距離求解問題，降低問題復雜性，使得數學模型更易懂。

在揀貨最優的遺傳算法中，可以不受函數約束條件的限制，直接通過設定初始的值，滿足不同的需求，得出不同的最優解。具有全局搜索性，遺傳算法的搜索過程是從全局開始，在此過程中全局最優解可得，而不會落入局部最優的循環不能得到結果。綜上所述遺傳算法非常適合解決揀貨最優的問題。

參考文獻：

[1] 陳文.倉儲物流機器人批量揀選路徑規劃仿真[J].安陽師范學院學報，2019（5）：35-39.

[2] 張新艷，周雨晴.基于魚骨型倉庫的揀選路徑問題優化[J].同濟大學學報（自然科學版），2019，47（11）：1683-1690.

[3] 馮愛蘭，張小青，孔繼利.基于聚類和動態規劃的組合路徑策略[J].運籌與管理，2019，28（8）：86-92.

[4] 劉建勝，雷兆發，聶偉豪，等.一種fishbone倉儲布局下的揀選路徑優化方法研究[J/OL].中國機械工程：1-8[2020-05-24].http：//kns.cnki.net/kcms/detail/42.1294.TH.20190717.1543.002.html.

[5] 羅志文.基于改進魚骨型倉儲布局多人協同揀貨路徑優化方法研究[D].南昌大學，2019.

[6] 盛虎宜，劉長石，魯若愚.基于共同配送策略的農村電商集送貨一體化車輛路徑問題[J].系統工程，2019，37（3）：98-104.

[7] 于浩洋.基于遺傳算法的揀貨路徑優化方法[J].中國科技信息，2019（8）：91-94.

[8] 王晟旭，皇甫遙遙.基于貓群算法的人工揀選作業路徑優化研究[J].中國儲運，2020（3）：116-119.

[9] 邵劉霞，張瑞.配送中心揀選作業理論研究[J].中國市場，2012（28）：11-12，16.

[10] 李詩珍.配送中心揀貨作業優化設計與控制研究[D].西南交通大學，2008.

[11] 白寅.基于偏離度的倉庫揀貨路徑優化方法及應用[D].華中科技大學，2012.

[12] 劉思佳.A公司倉儲中心出庫作業優化研究[D].吉林大學，2014.

[13] 薛永吉.倉儲物流系統仿真及應用研究[D].東南大學，2006.

[14] 張彩霞.基于“貨到人”模式的電商訂單揀選優化研究[D].浙江理工大學，2016.

【通聯編輯：代影】