Flying-V型倉儲布局下的揀貨路徑優化

劉建勝，張 昆，雷兆發

（南昌大學機電工程學院，江西 南昌 330031）

1 引言

隨著經濟的全球化發展對現代物流行業的服務效率提出了更高的要求，在現代物流中的倉儲是一個重要環節，它是集中反映了物資的活動狀況，是連接生產、供應、銷售的中轉站，對提高物流效率起著關鍵性作用。而在倉庫作業中，訂單揀貨作業是被視為最耗成本和勞動力的一個環節。文獻[1]研究發現，訂單揀貨作業可占到倉庫日常作業總量的60%。因此，針對不同的倉庫布局，不同的揀貨方式中的訂單揀貨作業的路徑優化問題的研究是一項重要課題。而訂單揀貨所用時間的長短是衡量訂單揀貨作業效率的重要指，而時間與訂單揀貨路徑密切相關，因此，減少揀貨作業行駛的距離可以有效地提高倉庫作業的效率。

近年來，針對不同的倉庫布局及不同的訂單分布情況，文獻[2-6]運用遺傳算法、蟻群算法等智能算法對倉庫中揀貨作業路徑進行了研究。文獻[12]考慮了存儲分配策略和訂單優化等方面，從而提高了揀貨作業效率。文獻[7]研究了蟻群算法求解車間配送最短路徑問題，取得了良好的搜索效果，表明了改方法能有效的發現最優解。而文獻[9]研究了不同倉庫布局對揀貨路徑的影響，他們通過放寬約束，而提出了兩種新的布局：Flying-V型布局和Fishbone型布局，Flying-V型布局是對傳統布局斜切揀貨通道形成的，而Fishbone布局是對Flying-V布局中的指定揀貨通道旋轉90°形成的。他們的研究證明了在總貨位數量相等條件下，與傳統布局相比，這兩種新布局能使起始點（P&D點）和貨物之間的行走距離大約分別減少10%和20%。主要研究在Flying-V倉庫布局下的路徑優化問題。

2 問題描述

整個的倉庫布局平面圖，如圖1所示。P&D點為倉庫的出入口，為了能更好對Flying-V布局倉庫揀貨路徑優化研究，故作出如下假設：（1）揀貨員一次揀貨作業完成一個訂單，不考慮揀貨車輛限載問題；（2）忽略揀貨員在揀貨通道內進行左右兩側貨物揀選時行走的距離；（3）揀貨員允許在揀貨通道折返行走；（4）將倉庫布局分成四個揀貨區域，貨物區域編號順時針從倉庫左下角開始依次為一、二、三、四區。

圖1 Flying-V倉儲布局Fig.1 Flying-V Storage Layout

2.1 參數設計

圖1 中標明了一、二區的排和列的編號順序，三、四區的排和列的編號順序是一、二區關于中心線的鏡像。在四個揀貨區域分別建立了四個虛擬的平面坐標系，使得布局中的每個貨位都有唯一的編碼，用數組｛K，X，Y｝代表對應的貨位編號，其中K（K=1，2，3，4）表示貨區號，X（X=1，2，…，Xmax）表示貨架的列數，Y（Y=1，2，…，Ymax）表示貨架的排數。例如：｛1，5，6｝表示貨物位于一區第五列第六排。圖1中P&D點記為｛0，0，0｝。研究平面倉庫揀選路徑，不考慮貨位的高度，貨位的長和寬設為l，揀貨通道和垂直或水平主通道的寬度均為l，斜對角主通道的寬度為2l。

2.2 建立模型

這里研究揀貨路徑優化問題主要是考慮怎樣將一個訂單中所有的貨物一次性全部揀出，并使其總的揀貨路徑最優。該類問題類似于旅行商問題。因此結合TSP的數學模型設計了揀貨路徑問題的數學模型：

式中：S—揀貨員完成一次訂單揀選作業時總的行走距離；i，j∈Ω—所有待揀選貨位以及出發點；i=0—出發點；d ij—貨位i與貨位j之間的最短距離；u i—揀選點i的揀選順序（u0=1）；n—揀貨點的數量，模型的決策變量是x ij，其取值為：

目標函數式（1）是完成一次訂單所行走的最小距離；式（2）和式（3）確保每個揀選點有且只有一個前項和后項任務；式（4）確保揀選路線中不出現子回路；式（5）表示決策變量的取值域。

2.3 計算任意兩點之間的距離

因倉庫布局存在P&D點，因此計算任意兩點間的距離分兩種情況：一種是P&D點與任意貨位之間的距離，而另一種是任意兩貨位之間的距離。僅繪制通道的布局簡圖，如圖2所示。

圖2 Flying-V倉儲布局簡圖Fig.2 Sketch of Flying-V Storage Layout

（1）P&D點與任意貨位i之間的距離：

貨位點位于一四區：

貨位點位于二三區：

（2）任意兩貨位點之間的距離：

兩貨位點在同一區域：

不同通道上：

兩貨位點在不同的區域分以下幾種情況：

當兩揀貨點在一二區時：

當兩揀貨點在一三區時：

當兩揀貨點在一四區時：

當兩揀貨點在二三區時：

距離計算公式中參數介紹：式中：i，j—待揀選貨位；N i—貨位i，j的通道編號；K i—貨位i的貨區編號；S i—貨位i，j到揀貨通道起始端的距離；L i—貨位i，j所在的揀貨通道的長度；H—相鄰揀貨通道間的距離；L—相鄰揀貨通道截斜對角主通道的長度；S2—揀貨通道轉至垂直（水平）主通道消耗的距離；S1—揀貨通道轉至斜對角主通道消耗的距離。

由于Flying-V布局的對稱性，兩揀貨點在二四區的距離公式等同于兩揀貨點在一三區時的距離公式，而三四區的兩揀貨公式與一二區的距離公式相同。

3 算法設計

蟻群算法是采用正反饋機制，其使得搜索過程不斷收斂，最終逼近最優解。近年來，許多學者致力于蟻群算法的研究，并且成功解決了許多組合優化問題，如調度問題，指派問題，旅行商問題等，都取得了比較理想的實驗結果。

3.1 初始化參數

m為蟻群的總數量，n為節點的數量，d ij為節點i到節點j的距離，τij(t)為t時刻節點i與節點j連接路徑上的信息素濃度，α為信息素重要程度因子，β為啟發函數重要程度因子，Q為信息素釋放總量，iter_max為最大迭代數，迭代數初始值設為iter=1。

3.2 構建解空間

將螞蟻隨機地置于不同的出發點，螞蟻的移動是根據各個節點間連接路徑上的信息素濃度來決定其訪問下一個城市，P kij(t)表示t時刻螞蟻k從節點i轉移到節點j的概率，其計算公式為：

其中初始時刻，各個節點間連接路徑上的信息素濃度相同，設τij(0)=τ0，ηij(t)為啟發函數，其值為ηij(t)=1∕d ij表示螞蟻從節點i轉移到節點j的期望程度；allowk(k=1，2，…，m)為螞蟻k待訪問節點的集合。

3.3 更新信息素

在螞蟻釋放信息素的同時，各個節點間連接路徑上的信息素也在逐漸消失，以參數ρ(0<ρ<1)表示信息素揮發程度，當所有螞蟻完成一次循壞后，各個節點間連接路徑上的信息素按如下公式進行實時更新：

采用如下的Ant Cycle System模型計算螞蟻釋放的信息素濃度：

4 蟻群算法解決路徑優化問題

4.1 算法實現

在倉庫揀貨過程中，蟻群算法的實現步驟如下：

（1）參數初始化，為了能直觀地反應出優化效果，設定倉庫中的垂直主通道，水平主通道，揀貨通道，貨架的長和寬均為1，這里研究隨機選10訂單，每個訂單有30個待揀貨點，則n=30，選擇螞蟻數m=50，信息素重要程度因子α=1.5，啟發函數重要程度因子β=2，信息素總量Q=50，將m只螞蟻置于n個頂點上。

（2）更新禁忌表（tabu）和允許訪問的節點表（allowed），對每只螞蟻k（k=1，2…m），按照概率P kij從節點i轉移到節點j，將頂點j置于tabu中，而在allowed表中去掉頂點j。

（3）計算螞蟻行走的路徑長度，計算各螞蟻行走的路徑長度L k的值，并記錄其最小值。

（4）更新螞蟻軌跡強度，按更新方程修改軌跡強度。

（5）判斷迭代條件，若迭代數iter小于iter_max且無退化行為，則iter=iter+1，轉向步驟2。

（6）輸出最優解。

4.2 實驗仿真

仿真實驗的程序采用MATLAB語言設計，程序設計的終止條件即最大的迭代次數iter_max=1000，而其他參數的初始值采用上文中設定的初始值。隨機產生一個有30個貨位點的訂單樣本，貨位位置信息，如表1所示。

表1 訂單中30個貨位點及其編號Tab.1 30 Locations and Numbers in Order

圖3 蟻群算法路徑示意圖Fig.3 Path Diagram of Ant Colony Algorithm

圖4 傳統穿越策略路徑示意圖Fig.4 Path Diagram of Traditionally Traversal Strategy

圖5 S形啟發算法路徑示意圖Fig.5 Path Diagram of S-shaped Heuristic Algorithm

用傳統穿越策略，S形啟發算法和蟻群算法三種算法分別進行仿真實驗，得到的揀貨順序及路徑示意圖如下：

蟻群算法：

傳統穿越策略：

S形啟發算法：

三種算法的結果比較，如表2所示。

表2 算法計算結果表Tab.2 Calculating Results of Algorithm

從表2可以看出蟻群算法對路徑優化的效果還是比較顯著的，為了進一步更全面，準確的反映蟻群算法的優化性能，將隨機產生出10個訂單，每個訂單的貨位數為30個，用其上三種算法分別對這10個訂單進行實驗，實驗結果，如表3所示。從實驗結果來看，蟻群算法在路徑優化上要優于S形啟發算法。

表3 三種算法比較Tab.3 Comparison of Three Algorithms

5 結論

選擇合理的揀貨路徑對于降低物流配送中心運營成本，提高物流效率具有重要作用。通過對flying-V型倉儲布局特點建立了路徑優化模型，采用傳統穿越策略，S形啟發算法，以及蟻群算法三種算法進行路徑優化，并對結果作了比較，結果顯示蟻群算法能更好地解決倉庫揀貨路徑優化問題。