摘要：針對物流配送中心常見的雙區(qū)型倉庫進(jìn)貨路徑的特點(diǎn)，來建立數(shù)學(xué)模型，然后采用CA算法來求解最優(yōu)揀貨路徑，以此來降低物流成本中的揀貨作業(yè)成本這里采用遺傳算法進(jìn)行揀貨路徑的仿真試算，同時與S-shape啟發(fā)式算法，傳統(tǒng)穿越策略以及動態(tài)規(guī)劃方法進(jìn)行比較，最后的出結(jié)論證明采用遺傳算法優(yōu)化揀貨路徑問題，能夠非常有效的求解出揀貨路徑的最優(yōu)距離，這樣也就縮短揀貨作業(yè)的時間，進(jìn)而大大提高了物流中心的揀貨作業(yè)效率。

關(guān)鍵詞：揀貨;CA算法;揀貨路徑;物流

中圖分類號：F713.36;F252;TP391.9

文獻(xiàn)標(biāo)識碼：A

文章編號：1001-5922（2020）06-0171-05

物流中心進(jìn)行各項(xiàng)內(nèi)部作業(yè)時，其中一項(xiàng)最重要的工作就是揀貨作業(yè)，揀貨作業(yè)就是根據(jù)訂單進(jìn)行分揀，將客戶訂購的貨物分別從倉庫里面挑選出來然后發(fā)貨的業(yè)務(wù)。想要提高配送中心的工作效率首要就是提高揀貨作業(yè)的效率，因?yàn)閽涀鳂I(yè)工作比較繁瑣，人力資源消耗較大，耗時也比較久，作業(yè)時間是整個物流配送中心總的作業(yè)時間的30-40%，所以對揀貨流程的優(yōu)化就至關(guān)重要[8]。訂單揀貨路徑問題可以看作是以指撓沸組合優(yōu)化問題，如果能夠合理地安排訂單中貨物的揀取順序，就能夠大大減少揀貨工作人員在揀貨作業(yè)是的行走距離，從而加快了揀貨速度，客戶的等待時間也就大大縮短。優(yōu)化揀貨路徑的問題也有了一定的研究成果，當(dāng)倉庫規(guī)模比較小時，可以采用分支定界法等方法求解，但是當(dāng)規(guī)模增大時，求解就會變得非常復(fù)雜，那么傳統(tǒng)的優(yōu)化方法就無法解決這些問題了。這里主要針對不同的揀貨路徑所存在的不同特點(diǎn)，然后設(shè)計相應(yīng)的遺傳算法對其進(jìn)行仿真研究。

1 揀貨作業(yè)

1.1 問題描述

物流配送中心常見的倉庫類型就是雙區(qū)型倉庫[7]，所以我們這里研究的問題也是針對雙區(qū)型倉庫而言的。雙區(qū)型倉庫主要是由許多等長的巷道組成，然后在巷道兩旁排列一定數(shù)量的貨架，這些貨架是倉庫貨物存放的主要區(qū)域，雙區(qū)型倉庫與單區(qū)型倉庫相比較而言最大的不同就是它的橫向過道有3條，多出的中間這條過道對提高倉庫揀貨效率有非常大的幫助。常見的倉庫示意圖如圖l所示。

如圖中所示，I/O表示倉庫的出人口，其中每個貨品的儲位點(diǎn)由一個小方格代替，訂單中需要揀取的貨品的儲位點(diǎn)也已經(jīng)在圖中標(biāo)明。方塊上所標(biāo)識的數(shù)組即表示其對應(yīng)的儲位標(biāo)號，例如其中一個數(shù)組a-b-c中，a表示該儲位所在的揀貨的巷道編號，1-10為其取值范圍，6則表示該儲位位于揀貨巷道a的方向，左邊用1表示，右邊用2表示，c則代表該儲位所在的行的編號，取值范圍為1-40，例如6-1-26則表示該儲位位于倉庫的第6巷道左邊的第26行。這里我們將同一巷道中左右兩邊進(jìn)行揀貨時人員移動的距離忽略。

將訂單的揀貨時間可以分成幾個部分，即行走時間，搜索時間以及分揀時間等等。根據(jù)相關(guān)人員的研究發(fā)現(xiàn)，揀貨時間中行走時間通常要占到50%以上，由此可見為了有效的縮短揀貨時間應(yīng)該盡可能地減少行走時間，行走時間的長短又跟行走路徑的路線長短直接相關(guān)[6]，所以為了提高揀貨效率應(yīng)該將優(yōu)化揀貨路徑作為重要的研究內(nèi)容。

1.2 問題分類

根據(jù)揀貨工作人員所用推車的容量將訂單的揀貨方式分為一單多車和一單一車兩種類型。其中，一單多車是指將一個訂單中所需要的全部物品通過一輛推車來回多次從倉庫中取回，這也表示這個訂單上的貨物的總量超過了一輛推車的最大容量;一單一車是指一個揀貨訂單中所需要的所有貨品由一輛推車來回一次從倉庫中取回，即該訂單的貨品總量不超過推車的最大容量[2]。

1.3 建立模型

在研究一單多車揀貨路徑問題時，我們最需要考慮的就是如何將所需要的的貨品合理地分配到每個車次中揀取，以確保其揀貨路徑最優(yōu)，該問題問題與運(yùn)籌學(xué)中的涉及的車輛路徑問題（VRP）相似[1]，VRP描述的問題主要是當(dāng)提供一系列的客戶點(diǎn)，需要確定合理地行車路線，然后再從車場發(fā)車，有秩序的為這些客戶服務(wù)，這里通常會設(shè)定一些約束條件，諸如客戶需求量或者車輛最大載重以及時間限制等等，使得總的運(yùn)輸成本控制到最小。

一單多車的揀貨路徑問題就可以根據(jù)這類車輛路徑問題（VRP）的數(shù)學(xué)模型來設(shè)計一個合理的數(shù)學(xué)模型。

A條件假設(shè)，我們假設(shè)有n次車倉庫的出人口出發(fā)，到倉庫的許多不同的儲位去取貨品，并假設(shè)儲位分別為v1，v2：…vn。同時假設(shè)源點(diǎn)以及多個儲位的位置是已知的。

B目標(biāo)模型，假設(shè)每一趟車次構(gòu)成一個回路，確認(rèn)每趟車次的調(diào)度和路徑安排，從而使其所有回路總的行走距離最小。

C各個變量的表示，第i次車與其對應(yīng)的回路上的第i個儲位點(diǎn)的取貨量用O表示，第i條回路上的儲位數(shù)用Z，表示，第i次車對應(yīng)的路徑用ci表示，第i次車對應(yīng)的回路上第J儲位點(diǎn)用G ij表示，每次車對應(yīng)的編號用i表示，推車的最大載重量用W表示，某訂單上需要揀取貨品的總量用V表示，某訂單中貨品在倉庫中的儲位數(shù)用m表示，源點(diǎn)用v0表示，需要的車次數(shù)用n表示，總的行走距離用S表示，第i次車對應(yīng)的回路中排列第j-1個儲位點(diǎn)和第i個儲位點(diǎn)之間的最短距離用di（j - 1）j表示，最后第i次車對應(yīng)回路中的第Z。個儲位點(diǎn)和源點(diǎn)v0。間的最短距離用di（li）（0）表示。

2 GA算法求解揀貨路徑問題

2.1 算法流程

GA算法，即遺傳算法，是一種應(yīng)用非常廣泛的計算模型，其主要模擬的是遺傳學(xué)機(jī)理的生物進(jìn)化過程，以及達(dá)爾文生物進(jìn)化論的自然選擇[3]。這里我們建立模型，然后運(yùn)用遺傳算法求解揀貨路徑問題首次就要確定一個優(yōu)化的算法流程，如圖2所示。

2.2 編碼方案的確定

當(dāng)揀貨類型為一單一車時，可以運(yùn)用自然數(shù)編碼的方法，將需要揀貨訂單是上的貨品對應(yīng)其在倉庫中的儲存位置依次用自然數(shù)編號，然后就可以用這些自然數(shù)的序列表示揀貨的路徑。

假設(shè)訂單中需要揀取的貨品有4種，并且他們分別分布在倉庫中的4個不同儲位上，那么就可以將倉庫的出入點(diǎn)用0表示，然后給4個貨品依次編號卜4，則可以假設(shè)訂單的揀貨路徑為：①出入口一②儲位點(diǎn)1→③儲位點(diǎn)2→④儲位點(diǎn)3→⑤儲位點(diǎn)4→⑥出人口，該路徑用CA算法可以表示為自然數(shù)列{0 12 3 4 0）。

當(dāng)揀貨類型為一單多車時，則訂單的揀貨任務(wù)就需要多次車才能完成，這里我們可以在對應(yīng)的自然數(shù)列中插入0用來顯示多車次的特點(diǎn)。

假設(shè)訂單上需要從倉庫揀取的貨品有7種，并且這7種貨品分別分布在倉庫的7個不同儲位上，0用來表示倉庫的出人口，7個不同的儲位點(diǎn)分別用1-7的自然數(shù)表示，則這個訂單的揀貨路徑可以表示為：路徑1：①出入口→②儲位點(diǎn)1→③儲位點(diǎn)2→_④儲位點(diǎn)3→⑤儲位點(diǎn)4→⑥出人口，路徑2：①出人口→②儲位點(diǎn)5→③儲位點(diǎn)6→④儲位點(diǎn)7→⑤出人口。該路徑用GA算法可以用自然數(shù)列表示為：{0 1 2 3 4 0 5 6 7 0）。

這里的0有兩層含義，其一是代表揀貨路徑的起始點(diǎn)，其二則是用來對GA編碼進(jìn)行分隔的，從上面的編碼表達(dá)中可以看出，我們首先得到的是一個自然數(shù)列{12 3 4 5 6 7），然后再從左開始加入一點(diǎn)，當(dāng)加入到超出推車的最大載重量時，按照加入點(diǎn)的依次進(jìn)行排列，我們可以得到一條子路徑，這也就是揀貨作業(yè)時的第一次車的揀貨路徑，可以用數(shù)列表示為{1 2 3 4），然后從沒有加入點(diǎn)的地方繼續(xù)依次加入，我們會重新獲得一條新的子路徑，如此重復(fù)這個過程，直到所有的點(diǎn)都被加人為止，最后在所選的可行數(shù)列中加入0用來將這些子路徑分隔開來，就可以得到最后的總路徑，用染色體編碼表示為{012 3 4 0 5 6 7 0）。在對染色體編碼進(jìn)行交叉等相關(guān)的操作時，可以將編碼中表示多車的0從染色體編碼中去除，完成算法操作后再根據(jù)上面的編碼方式插入0，最后得到相應(yīng)的染色體編碼。

2.3 確定適應(yīng)度函數(shù)

這里取哈密爾頓圈長度的倒數(shù)為問題的適應(yīng)度函數(shù)[4]，本文中我們將這個函數(shù)乘以一個系數(shù)用以調(diào)節(jié)避免其適應(yīng)度過小的問題，該系數(shù)值為：r= 76.2. max dd.Z ch rom 0.5

則該問題的適應(yīng)度函數(shù)為：

Fit（x）= r/X

系數(shù)r中的max dd表示揀貨任務(wù)訂單中需要揀取貨品所在儲位點(diǎn)之間的最長距離，而lchrom則表示的是編碼后的染色體長度，也就是揀貨路徑中所經(jīng)過的儲位點(diǎn)數(shù)，X則表示其對應(yīng)的可行解的揀貨路徑的長度。

2.4 交叉算子與選擇算子的設(shè)計

這里的初始解群是通過隨機(jī)生成的方式產(chǎn)生的，再根據(jù)適應(yīng)度比例從父代中每次選取2個個體，最后根據(jù)相應(yīng)的概率進(jìn)行交叉變異操作。

以下為交叉操作：

A首先隨機(jī)選取一個交配區(qū)域，如

A=1 2|3 4 5 6|7 8 9

B=9 8|7 6 5 4|3 21

B然后在A的前面或者后面加上B的交配區(qū)域，在B的前面或者后面加上且的交配區(qū)域，就可以的到

A'=7 6 5 4|12 3 4 5 6 7 8 9

B'=3 4 5 6|9 8 7 6 5 4 3 21

C依次刪除A中經(jīng)過交配區(qū)域后與其交配區(qū)相同的儲位號碼，就可以得到最終的子串

A'=765412389

B'=345698721

該方法與其他方法相比較來看，其主要優(yōu)勢在于它可以在即使兩個父串一樣的情況下，也能夠在一定程度上產(chǎn)生變異效果，這也很好的保持了群體的多樣化特征。

3 算例測試

3.1 一單一車

這里我們采用C語言在Visual C++6.0環(huán)境下進(jìn)行算例計算。

生成隨機(jī)的11組儲位序號，這11組儲位序號也就表示11份訂單的揀貨任務(wù)，然后我們用幾種算法對揀貨路徑進(jìn)行優(yōu)化運(yùn)算，這里我們比較了動態(tài)規(guī)劃，遺傳算法和S-shape啟發(fā)算法的優(yōu)化運(yùn)算結(jié)果，這里得到的運(yùn)算結(jié)果如表1所示。

根據(jù)表中的運(yùn)算結(jié)果可以看出，相比較傳統(tǒng)穿越策略揀貨，采用S-shape啟發(fā)算法優(yōu)化問題后其揀貨距離大多能夠減少10%_30%，采用動態(tài)規(guī)劃優(yōu)化問題后的揀貨距離大多能夠減少20%-40%，采用遺傳算法優(yōu)化問題后其揀貨距離能夠減少30%-50%，由此可見采用遺傳算法求解最佳的揀貨路徑更加有效，同時其求解時間也在可以接受的范圍內(nèi)，具有可行性。

我們選取表中的第1個訂單，然后分別采用4種求解方法得到線對應(yīng)的揀貨路徑，如圖3～圖6所示。

3.2 一單多車

訂單上的需要揀取的貨品的儲位我們可以隨機(jī)生成100個，這里需要考慮到倉庫推車的載重能力，可以在儲位表示的基礎(chǔ)上再講=加上一個數(shù)字，其表示為這個儲位上所揀取的貨品的質(zhì)量，例如{6 -l - 26 - 2.8}，它表示為這個儲位在倉庫的6號巷道的左邊的第2行，同時這個儲位上所需要揀取的貨品的質(zhì)量為2.8kg，這里假設(shè)推車的最大載重量為30kg。

因?yàn)閯討B(tài)規(guī)劃方法與S-shape啟發(fā)式算法不能對不同車次之間的揀貨任務(wù)進(jìn)行優(yōu)化分組運(yùn)算[5]，也就是無法處理一單多車的問題，所以我們只能采用遺傳算法對其進(jìn)行優(yōu)化求解，我們這里同樣使用C語言程序在Visual C++6.0環(huán)境下進(jìn)行運(yùn)算求解，得到的結(jié)果是總的揀貨行走距離為960m，一共需要9車次完成訂單的揀取任務(wù)。

4 結(jié)語

為了降低物流配送中心的揀貨成本，提高物流配送效率，減少客戶等待時間，提升客戶購物體驗(yàn)，就需要合理地安排揀貨路徑，對應(yīng)訂單的揀取類型，對其建立揀貨路徑的數(shù)學(xué)模型，并應(yīng)用GA算法對其進(jìn)行優(yōu)化求解，同時將其優(yōu)化結(jié)果同動態(tài)規(guī)劃方法和S形啟發(fā)式算法的優(yōu)化結(jié)果進(jìn)行比較，結(jié)果表明優(yōu)化揀貨路徑最好的求解方法就是遺傳算法，揀貨路徑的優(yōu)化能夠縮短物流中心的揀貨時間，從而提高其工作效率。

參考文獻(xiàn)

[1]陳伊菲，劉軍，倉庫揀貨作業(yè)路徑VRP模型設(shè)計與應(yīng)用[J].計算機(jī)工程與應(yīng)用，2006，42（6）：208-212.

[2]徐天亮.運(yùn)輸與配送[M].北京：中國物資出版社，2002.

[3] Hwang H，Back W，Lee M K.Clustering algorithms fororder packing in an automated storage and retrieval sys-tems[J].lnternational Journal of Production Research.1988.26（2）：189-201.

[4] Goetschalckx M.Ratliff H D.Order picking in an aisle[J].IIE Transactions 1988.20（1）：52-62.

[5]符卓.帶裝載能力約束的開放式車輛路徑問題及其禁忌搜索算法研究[J].系統(tǒng)工程理論與實(shí)踐，2004（3）：123-126.

[6] Tho L D，Rene M B M.de Koster R.Travel time esti-mation and order batching in a 2-block warehouse[J].Eu-ropean Journal of Operational Research.2007.176 （1）：375-388。

[7]鐘石泉，杜剛，賀國光.有時間窗的開放式車輛路徑問題及其遺傳算法[J].計算機(jī)工程與應(yīng)用，2006，42（34）：200-205.

[8] Roodbergen K J，de Koster R.Routing order pickersin a warehouse with a middle aisle[J].European Joumalof Operation Research，2001.133（1）：31-45.

作者簡介：王云波（1978-），男，陜西寶雞人，碩士研究生，副教授，主要研究方向：企業(yè)經(jīng)濟(jì)與管理、職業(yè)教育等?；痦?xiàng)目：以學(xué)生就業(yè)能力為核心的職業(yè)教育考試制度的探索與研究（SZJG-1612）