房殿軍，彭一凡

（同濟(jì)大學(xué) 中德學(xué)院，上海 201804）

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

房殿軍，彭一凡

（同濟(jì)大學(xué) 中德學(xué)院，上海 201804）

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

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

1 引言

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

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

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

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

2 問題描述

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

圖1 倉庫布局簡圖

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

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

3 模型介紹及算法求解

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

3.1 模型假設(shè)

（1）各個(gè)待揀選點(diǎn)間相互獨(dú)立；

（2）揀選員在每個(gè)待揀選點(diǎn)取貨花費(fèi)的時(shí)間是相同的；

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

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

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

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

3.2 數(shù)學(xué)模型

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

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

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

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

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

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

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

圖2 在回程時(shí)揀選的揀選點(diǎn)示意圖

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

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

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

圖3 當(dāng)時(shí)，揀選順序確定示意圖

圖4 當(dāng)時(shí)，揀選順序確定示意圖

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

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

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

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

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

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

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

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

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

圖6 揀選員進(jìn)入下一待揀選巷道示意圖

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

Step 1：找出所有含有待揀選點(diǎn)的揀選巷道，并定義揀選巷道編號(hào)最小即最靠左的揀選巷道為最左巷道，定義編號(hào)最大即最靠右的為最右巷道。

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

Step 3：如果當(dāng)前揀選巷道是最后一條含有待揀選點(diǎn)的巷道，則前往Step 4；如果當(dāng)前揀選巷道不是最后一條含有待揀選點(diǎn)的巷道，則前往Step 6。

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

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

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

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

Step 6：最終，返回Depot。

4 仿真結(jié)果分析

4.1 實(shí)驗(yàn)設(shè)計(jì)

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

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

表1 實(shí)驗(yàn)參數(shù)表

表2 實(shí)驗(yàn)參數(shù)組合示例

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

4.2 實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

圖7 行走距離變化趨勢(shì)圖

圖8 橫向巷道對(duì)行走距離影響

5 結(jié)束語

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

［1］吳政潔.物流中心即時(shí)批次訂單的揀貨研究［D］.臺(tái)灣:國立中央大學(xué)，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］.武漢:華中科技大學(xué)，2014.

［4］王宏，符卓，左武.基于遺傳算法的雙區(qū)型倉庫揀貨路徑優(yōu)化研究［J］.計(jì)算機(jī)工程與應(yīng)用，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ī)劃、供應(yīng)鏈管理。