含多條橫向巷道的倉庫揀選路徑優化研究

房殿軍，彭一凡

（同濟大學 中德學院，上海 201804）

含多條橫向巷道的倉庫揀選路徑優化研究

房殿軍，彭一凡

（同濟大學 中德學院，上海 201804）

以含有多條橫向巷道的倉庫為對象，以行走總距離最短為目標，對其揀選作業路徑問題進行了研究，在對該問題進行了數學描述的基礎上，通過設定揀選點在去程或回程上的分布規則以及相鄰巷道揀選點的作業順序，開發和實現了一種新的基于組合式規則的啟發式算法。同時，分析了不同的揀選巷道長度、揀選巷道數量、揀選點數及橫向巷道數量對揀選作業行走總距離的影響。實驗結果表明，橫向巷道能夠明顯優化揀選距離，但其數量不宜超過4條。

倉庫；揀選作業；路徑優化；多橫向巷道

1 引言

越來越多的企業為了削減成本和提高生產效率，將目光放到倉儲設施和配送中心上，訂單揀選作業開始受到管理人員和研究學者的重視。研究表明，揀貨作業占倉庫總作業成本的比例約為60%［1］。

訂單揀選作業是指基于顧客的訂單從特定的儲存位置獲取貨物的過程，訂單揀選作業的效率取決于儲存系統、倉庫布局、控制機制等諸多因素，可以通過降低揀選訂單所需的時間來減少揀選作業時間，從而提高揀選作業效率。總的揀選時間可粗略地分為訂單準備時間、揀貨行走時間、搜索貨物時間、揀取貨物時間等，其中，在人工揀選系統中，行走時間是總揀選時間最大的組成部分，占到50%左右［2］。

為了減少行走時間，可從從以下五個方面著手：（1）通過優化不同待揀選貨物的揀選順序，尋求更好的揀選路徑；（2）將揀選區域分成數個工作區即進行作業分區，揀選人員只完成其所委派區域內的待揀選貨物；（3）根據特定的分配策略，對貨物進行儲位分配；（4）對訂單進行分批處理，處于同一批次的訂單將在一次揀選作業中完成；（5）對倉庫的布局進行優化，通過調整和改變倉庫設備的尺寸和位置包括存儲區的設置，提高倉庫的利用率和揀選效率［3］。

本文將提出一種新的揀選路徑優化算法，通過對待揀選點的優化排序，縮短揀選路徑的距離，從而減少行走時間，提高揀選作業效率。除此之外，并將其運用到含有多個橫向巷道的倉庫中，通過實驗仿真探索橫向巷道的數量對揀選距離的影響，并對倉庫布局時橫向巷道的數目提出了建議。

2 問題描述

本文所考慮的是含多條橫向巷道的倉庫的揀選路徑問題。在倉庫中，至少含有兩條橫向巷道，即位于倉庫兩端的“前橫向巷道”和“后橫向巷道”。加入額外的橫向巷道，為揀選路徑的選擇提供更大柔性，從而可能獲得更短的行走距離。本文中，將橫向巷道編號依照距出入口的遠近依次編號，記為“橫向巷道1”、“橫向巷道2”等。橫向巷道將倉庫分為多個區，按距出入口的遠近，依次被稱為“區1”、“區2”等。倉庫布局的簡圖如圖1所示。圖1中的每個小方格都代表一個儲位，黑色填充的方格代表按訂單需要揀取的貨物所在的儲位［4］。

圖1 倉庫布局簡圖

倉庫呈矩形，豎直方向上的巷道稱為揀選巷道，水平方向上的巷道稱作橫向巷道，橫向巷道中并不包含儲位，僅被用來轉換巷道，即只有進入到揀選巷道中才能揀選貨架上的貨物。本文假設貨架的列數為偶數，每條揀選巷道左右兩側都含有一列貨架。在倉庫中，揀選人員能夠沿著巷道自由通行，并且揀選巷道足夠窄，忽略同一揀貨通道中左右兩邊揀貨時揀貨人員移動的距離。鑒于倉庫的出入口位于第一條橫向巷道的邊緣和中間，對平均揀選路徑的影響不超過1%［5］，本文中假設出入口位于倉庫的左下角，第一揀選巷道和第一條橫向巷道的交界處，同時是揀選任務起始點和終點。

通常情況下，這些橫向巷道將倉庫分為多個區塊，形成多區塊的倉庫，在揀選路徑規劃時，按照待揀選點所處分區的不同進行分類，逐個分區進行揀選［6］。在本文中，揀選員將逐條巷道依次揀選貨物，橫向巷道僅作為揀選員在揀選巷道間移動的通道，而根據橫向巷道對倉庫所進行的分區，僅作為揀選員在揀選巷道間移動時選擇經過的橫向巷道的參照。

3 模型介紹及算法求解

揀選路徑問題主要是考慮怎樣將一次揀選任務中的貨物從儲位中依次取出，使得此次揀選任務的行走路徑最優。這類問題類似于Steiner TSP問題，與經典的TSP問題不同，其所求得的路線不需要經過所有的節點，而且在必要的情況下可以多次經過同一個節點。

3.1 模型假設

（1）各個待揀選點間相互獨立；

（2）揀選員在每個待揀選點取貨花費的時間是相同的；

（3）揀選通道和橫向通道均無行走方向限制；

（4）揀貨員執行的揀選任務在出發前既已確定，且揀選過程中不發生變動；

（5）揀選員沿揀選巷道和橫向巷道的中間行走；

（6）除最后一個分區外，其余所有分區含有相同排數的貨架，且最后一個分區所含有的貨架排數不少于其他任一分區含有的貨架排數。

3.2 數學模型

Steiner TSP問題一般可以根據0-1規劃模型進行求解：

其中：i，j∈Ω—揀選員要經過的揀選點以及Depot，其中i=0表示Depot；dij—揀選點i和j之間的行走距離；ui—揀選點i的揀選順序，其中u0=1；ω—揀選點和Depot數量總和。

決策變量xij=1表示揀選員決定在完成i點的任務后前往j點（i，j∈Ω，i≠j）。目標函數式（1）要求取得完成一個訂單的行走路線的最小值；約束（2）和（3）確保每個任務點有且只有一個前項和后項任務；約束（4）確保揀選路線中不出現子回路；約束（5）是定義決策變量的取值域。揀選路線規劃問題的研究目的就是確定揀貨點間的揀選順序，即xij的取值。

3.3 基于組合算法的路徑優化原理

本文所提出的組合算法是一種新的啟發式算法，在解決揀選路徑優化問題上，首先假設揀選員是按照待揀選點的分布狀況逐條巷道依次完成揀選任務，其次，聯系到mid-point算法和Largest Gap算法，將分布較分散的待揀選點放入回程上揀選，然后，根據揀選員所處的位置同待揀選點的相對位置關系決定待揀選點的揀選順序。新的組合算法利用了回程時的行走路徑，同時，揀選員到達下一待揀選點時總是將行走距離最短的路徑作為揀選路徑，因而，其在路徑優化中體現出更加有效的優化效果。

3.3.1 確定回程中揀選的待揀選點。在mid-point策略中，除了第一個和最后一個有揀選點的巷道要完整穿過，其他巷道根據中點分成前后兩部分，位于后半部分的揀選點放入回程中揀選，

在Largest Gap策略中，巷道被最大間隔而不是中點劃分成前后兩個部分。將以上兩種算法所考慮的巷道前后兩部分劃分依據綜合考慮，本文中假設出現以下兩種情況巷道內的待揀選點將放到回程中揀選：（1）此揀選巷道中所有的待揀選點都位于倉庫的前端，將此巷道內所有的待揀選點放入回程中揀選，如圖2a所示；（2）此揀選巷道中揀選點間的最大間隔不小于貨架總長的一半時，將此巷道內位于前端的待揀選點放入回程中揀選，如圖2b所示。

圖2 在回程時揀選的揀選點示意圖

3.3.2 揀選巷道內揀選點揀選順序。揀選員在逐條巷道依次完成揀選任務時，揀選巷道內揀選點揀選順序的確定原則是從揀選員所在的位置到達下一待揀選巷道內最后一個揀選點時所行走的距離最短。當揀選員到達某條揀選巷道中的最后一個待揀選點時，將此位置作為參照點，在示意圖中用實心圓圈表示。根據參照點和下一待揀選巷道內待揀選點的位置關系，確定下一待揀選巷道內的待揀選點的揀選順序。

記揀選員所處參照點位于分區Z0，第y0排；下一待揀選巷道內最前方的待揀選點位于分區Z1，第y1排；下一待揀選巷道內最后方的待揀選點位于分區Z2，第y2排。若下一待揀選巷道僅含一個待揀選點，則Z1=Z2且y1=y2。則：

當Z0≠Z1≠Z2，即三者不位于同一分區時：

圖3 當時，揀選順序確定示意圖

圖4 當時，揀選順序確定示意圖

當Z0=Z1=Z2，即三者位于同一分區時，

假設分區Z0由第y3排至第y4排貨架構成，則：

圖5 揀選順序確定示意圖二

鑒于回程上揀選人員在揀選巷道間移動時，對待揀選點的揀選排序規則仍與去程時相同，因而，在本文的圖例中，僅列出了去程時的情況，回程時類似，不再重復說明。

3.3.3 揀選巷道間移動時所經由的橫向巷道的確定。在確定下一待揀選巷道內待揀選點的揀選順序之后，需要根據揀選員此時所處的位置和下一時刻將要到達的待揀選點的位置，來確定揀選員在揀選巷道間移動時所經由的橫向巷道。不妨假設，假設下一揀選點位于分區Z1，第y1排。

根據揀選員所處的參照點與下一揀選點間相對位置的不同，可以分為以下三種情況考慮：

（1）參照點位于下一揀選點所處分區之前的分區，即：Z0＜Z1；揀選員將經由橫向巷道Z0+1進入下一待揀選巷道，如圖6a所示；

（2）參照點位于下一揀選點所處分區之后的分區，即：Z0＞Z1，揀選員將經由橫向巷道Z0進入下一待揀選巷道，如圖6b所示；

（3）參照點同下一揀選點位于同一分區，即Z0=Z1，若y0+y1≥y3+y4，則揀選員將經由橫向巷道Z0+1進入下一待揀選巷道，如圖6c所示；若y0+y1＜y3+y4，則揀選員將經由橫向巷道Z0進入下一待揀選巷道，如圖6d所示。

圖6 揀選員進入下一待揀選巷道示意圖

組合算法的具體流程如下：

Step 1：找出所有含有待揀選點的揀選巷道，并定義揀選巷道編號最小即最靠左的揀選巷道為最左巷道，定義編號最大即最靠右的為最右巷道。

Step 2：揀選員從Depot出發，到達最左巷道，沿著揀選巷道由近及遠揀選最左揀選巷道內所有的待揀選點。

Step 3：如果當前揀選巷道是最后一條含有待揀選點的巷道，則前往Step 4；如果當前揀選巷道不是最后一條含有待揀選點的巷道，則前往Step 6。

Step 4：接下來分為兩種情況：

Step 4.1：揀選員尚未到達過最右巷道，下一待揀選巷道為當前揀選巷道右邊的待揀選巷道，根據下一條待揀選巷道內待揀選點的分布狀況，將下一待揀選巷道內的待揀選點分為去程上揀選和回程上揀選兩類，按照上文所說的動態規劃規則，確定其中的去程上揀選的待揀選點的揀選順序。

Step 4.2：揀選員到達過最右巷道，下一待揀選巷道為當前揀選巷道左邊的待揀選巷道，根據上文所述的動態規劃原則，確定下一待揀選巷道內的待揀選點的揀選順序。

Step 5：揀選員按照最短的行走路線到達下一個待揀選點，并依照揀選順序依次揀選當前揀選巷道內的揀選任務。前往Step 3。

Step 6：最終，返回Depot。

4 仿真結果分析

4.1 實驗設計

通過實驗尋找在不同的貨架規模和一次揀選作業中不同數量的待揀選點數的情況下，橫向巷道數量同揀選路徑長度間的關系，及若將橫向巷道作為揀選巷道間的連接通道時，最佳的橫向巷道數量。

實驗分為兩個步驟進行：第一步是在一個指定的布局下，逐漸增加橫向巷道的數量，以考察在揀選不同數量的揀選點情況下，揀選路徑長度的變化以及最優的橫向巷道數量；第二步是變化倉庫布局及倉庫大小，重復第一步的實驗，以觀察在不同的倉庫布局及大小的情況下，最優的橫向巷道數量。倉庫內的基礎參數如下：單個貨格長1m，單個貨格寬0.5m，揀選巷道寬1m，橫向巷道寬1m。實驗參數設計見表1，實驗參數組合示例見表2。

表1 實驗參數表

表2 實驗參數組合示例

在本文中，訂單隨機生成，訂單指定的揀貨點都服從獨立同分布，隨機地從庫區中選取，不考慮由于需求帶來的每個貨位的不同揀選頻率，這些與文獻［7］假設相同。

4.2 實驗結果與分析

隨機生成待揀選點位置，實驗程序是在VB平臺上實現，共進行了8×5×10×5=2 000組實驗，每個實驗數據組合均進行100次實驗，取得平均行走距離（單位：m），作為實驗結果。

以組合算法為基礎，通過變化揀選巷道長度L，揀選巷道數量N及待揀選點數K對行走距離s的影響，并在此基礎上，進一步分析，增加橫向巷道的數量對行走距離s的影響，最終總結出最優的橫向巷道數量。

通過對數據結果（如圖7所示）的分析可以發現，當橫向巷道數量為M=2時，行走距離s隨著L、N、K的增加而增加，但增加的幅度逐漸減少。同時，在相同的倉庫布局下，即揀選巷道長度和數量均相同，待揀選點的數量越多，行走距離越多；但當待揀選點數量增加到一定程度，即平均每條揀選巷道的待揀選點數量較多，揀選密度較高時，揀選員不得不穿越每條巷道，此時行走距離達到極限值，再增加待揀選點數量，行走距離基本不變。

若考慮橫向巷道對行走距離的影響問題，如圖8所示，發現當揀選密度較大時，增加橫向巷道，反而會增加行走距離；當揀選密度較小時，隨著橫向巷道數量的增加，行走距離先逐漸減少到最小值，再由最小值慢慢增加；在最小值附近，減少或增加橫向巷道的數量，對行走距離的影響不大；在橫向巷道數量為最優值之前，每減少一條橫向巷道數量，行走距離增大地越來越劇烈。

當將橫向巷道作為揀選員在揀選巷道間移動時的連接通道時，一條額外的橫向巷道，也就是第三條橫向巷道，為揀選員的行動提供了一種額外的可能性，即從倉庫的1/2處由揀選員現在所處的揀選巷道轉入下一條待揀選巷道；兩條額外的橫向巷道，也就是第三和第四條橫向巷道，為揀選員的行動提供了兩種額外的可能性，即從倉庫的1/3和2/3處由揀選員現在所處的揀選巷道轉入下一條待揀選巷道；更多的額外的橫向巷道為揀選員的行動提供更多的可能性，但每一次增加橫向巷道都在原有的橫向巷道提供的優化的基礎上，對揀選路徑進行優化，并且，每一次增加橫向巷道都會引起額外的揀選路徑的增加。所以，每增加一條橫向巷道，其對揀選路徑的優化距離在快速降低，并且當橫向巷道的數量增加到一定程度時，它反而會造成揀選路徑的增加。

雖然最佳的額外橫向巷道的數量受到揀選點數量、揀選巷道長度以及揀選巷道數量的影響，但是，若將額外的橫向巷道僅作為連接通道使用時，第三條額的橫向巷道對揀選路徑的優化不超過原始路徑的5%。

圖7 行走距離變化趨勢圖

圖8 橫向巷道對行走距離影響

5 結束語

揀選路優化是提揀選效率重要的手之一，受到多企業管者和學者關注和研究。本文提出了一種針對含有多條橫向巷道的倉庫布局的揀選路徑優化算法—組合算法，仿真結果顯示，在含有多條橫向巷道的倉庫中，若將除“前橫向巷道”和“后橫向巷道”之外的橫向巷道作為連接巷道，在揀選密度較低的情況下，能夠顯著地優化揀選路徑的距離，但是，過多的橫向巷道對揀選距離的優化效果不明顯，甚至可能會造成揀選距離的增加，額外的橫向巷道數量不宜超過2條，即倉庫內的橫向巷道數量不宜超過4條。

［1］吳政潔.物流中心即時批次訂單的揀貨研究［D］.臺灣:國立中央大學，2007.

［2］Tompkins J A，White J A，Bozer Y A，et al.Facilities Planning［M］. NJ:John Wiley&Sons，2003.

［3］陳方宇.多區塊倉庫環境下訂單揀選路線規劃研究［D］.武漢:華中科技大學，2014.

［4］王宏，符卓，左武.基于遺傳算法的雙區型倉庫揀貨路徑優化研究［J］.計算機工程與應用，2009，45（6）:224-228.

［5］Petersen C G.An evaluation of order picking routeing policies［J］. International Journal of Operations and Production Management，1997，17（11）:1 098-1 111.

［6］Roodbergen K J，Koster R.Routing methods for warehouses with multiple cross aisles［J］.International Journal of Production Research，2001，39（9）:1 865-1 883.

［7］Caron F，Marchet G，Perego A.Routing policies and COI-based storage policies in picker-to-part systems［J］.International Journal of Production Research，1998，36（3）:713-732.

Study on Picking Path Optimization in Warehouse with Multiple Transverse Alleys

FangDianjun，PengYifan
（Chinesisch-DeutschesHochschulkolleg，TongjiUniversity，Shanghai 201804，China）

In this paper，with a warehouse with multiple transverse alleys as the object and with the shortest total travelling distance as the objective，we studied the picking path optimization of the warehouse，and then on the basis of a mathematical description of the problem，developed and realized a heuristic algorithm based on combination rules.Meanwhile，we analyzed the influence of different length and quantity of the picking alleys，the number of picking stations and the quantity of transverse alleys on the total travelling distance，through which we found that through the transverse alleys we can remarkably optimize the picking distance，but there should not be more than 4 of theminawarehouse.

warehouse；pickingactivity；pathoptimization；multipletransversealley

TP273

A

1005-152X（2016）05-0130-06

10.3969/j.issn.1005-152X.2016.05.029

2016-04-03

房殿軍（1961-），男，山東人，博士，教授，主要研究方向：物流系統規劃、供應鏈管理。