含多條橫向巷道的倉庫揀選路徑優(yōu)化研究

房殿軍，彭一凡

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

含多條橫向巷道的倉庫揀選路徑優(yōu)化研究

房殿軍，彭一凡

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

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

倉庫；揀選作業(yè)；路徑優(yōu)化；多橫向巷道

1 引言

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

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

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

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

2 問題描述

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

圖1 倉庫布局簡圖

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

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

3 模型介紹及算法求解

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

3.1 模型假設

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

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

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

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

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

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

3.2 數(shù)學模型

Steiner TSP問題一般可以根據(jù)0-1規(guī)劃模型進行求解：

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

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

3.3 基于組合算法的路徑優(yōu)化原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Step 4.2：揀選員到達過最右巷道，下一待揀選巷道為當前揀選巷道左邊的待揀選巷道，根據(jù)上文所述的動態(tài)規(guī)劃原則，確定下一待揀選巷道內(nèi)的待揀選點的揀選順序。

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

Step 6：最終，返回Depot。

4 仿真結果分析

4.1 實驗設計

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

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

表1 實驗參數(shù)表

表2 實驗參數(shù)組合示例

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

4.2 實驗結果與分析

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

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

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

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

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

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

圖7 行走距離變化趨勢圖

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

5 結束語

揀選路優(yōu)化是提揀選效率重要的手之一，受到多企業(yè)管者和學者關注和研究。本文提出了一種針對含有多條橫向巷道的倉庫布局的揀選路徑優(yōu)化算法—組合算法，仿真結果顯示，在含有多條橫向巷道的倉庫中，若將除“前橫向巷道”和“后橫向巷道”之外的橫向巷道作為連接巷道，在揀選密度較低的情況下，能夠顯著地優(yōu)化揀選路徑的距離，但是，過多的橫向巷道對揀選距離的優(yōu)化效果不明顯，甚至可能會造成揀選距離的增加，額外的橫向巷道數(shù)量不宜超過2條，即倉庫內(nèi)的橫向巷道數(shù)量不宜超過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］陳方宇.多區(qū)塊倉庫環(huán)境下訂單揀選路線規(guī)劃研究［D］.武漢:華中科技大學，2014.

［4］王宏，符卓，左武.基于遺傳算法的雙區(qū)型倉庫揀貨路徑優(yōu)化研究［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-），男，山東人，博士，教授，主要研究方向：物流系統(tǒng)規(guī)劃、供應鏈管理。