基于遺傳算法的倉內(nèi)揀貨優(yōu)先問題研究

楊海祥

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

關(guān)鍵詞：遺傳算法;排隊問題

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

1 問題分析

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

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

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

2 模型的建立與求解

現(xiàn)根據(jù)倉庫貨格的編號[abc]，首先建立距離計算模型。

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

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

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

同時將整個揀貨路徑優(yōu)化模型定義為：

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

將上述模型中的揀貨員分批后的每一批訂單所在的貨架位置信息輸入到系統(tǒng)中來，應(yīng)用matlab 來對遺傳算法進行實現(xiàn)，通過求解得出每一臺AGV揀貨員的任務(wù)分配及路徑優(yōu)化結(jié)果。對訂單按照貨架信息進行任務(wù)分配及路徑規(guī)劃。

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

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

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

3 結(jié)論

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

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

參考文獻：

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

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

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

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

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

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

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

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

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

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

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

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

[13] 薛永吉.倉儲物流系統(tǒng)仿真及應(yīng)用研究[D].東南大學，2006.

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

【通聯(lián)編輯：代影】