基于GA算法的電子商務物流中心揀貨流程仿真研究

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

關鍵詞：揀貨;CA算法;揀貨路徑;物流

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

文獻標識碼：A

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

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

1 揀貨作業(yè)

1.1 問題描述

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

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

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

1.2 問題分類

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

1.3 建立模型

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

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

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

B目標模型，假設每一趟車次構成一個回路，確認每趟車次的調度和路徑安排，從而使其所有回路總的行走距離最小。

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

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

2.1 算法流程

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

2.2 編碼方案的確定

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

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

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

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

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

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

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

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

Fit（x）= r/X

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

2.4 交叉算子與選擇算子的設計

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

以下為交叉操作：

A首先隨機選取一個交配區(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)境下進行算例計算。

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

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

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

3.2 一單多車

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

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

4 結語

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

參考文獻

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

[2]徐天亮.運輸與配送[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)工程理論與實踐，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].計算機工程與應用，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)濟與管理、職業(yè)教育等。基金項目：以學生就業(yè)能力為核心的職業(yè)教育考試制度的探索與研究（SZJG-1612）