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

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

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

中圖分類號(hào)：F713.36;F252;TP391.9

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

文章編號(hào)：1001-5922（2020）06-0171-05

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

1 揀貨作業(yè)

1.1 問(wèn)題描述

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

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

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

1.2 問(wèn)題分類

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

1.3 建立模型

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

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

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

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

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

2 GA算法求解揀貨路徑問(wèn)題

2.1 算法流程

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

2.2 編碼方案的確定

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

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

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

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

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

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

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

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

Fit（x）= r/X

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

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

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

以下為交叉操作：

A首先隨機(jī)選取一個(gè)交配區(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)過(guò)交配區(qū)域后與其交配區(qū)相同的儲(chǔ)位號(hào)碼，就可以得到最終的子串

A'=765412389

B'=345698721

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

3 算例測(cè)試

3.1 一單一車

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

生成隨機(jī)的11組儲(chǔ)位序號(hào)，這11組儲(chǔ)位序號(hào)也就表示11份訂單的揀貨任務(wù)，然后我們用幾種算法對(duì)揀貨路徑進(jìn)行優(yōu)化運(yùn)算，這里我們比較了動(dòng)態(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)化問(wèn)題后其揀貨距離大多能夠減少10%_30%，采用動(dòng)態(tài)規(guī)劃優(yōu)化問(wèn)題后的揀貨距離大多能夠減少20%-40%，采用遺傳算法優(yōu)化問(wèn)題后其揀貨距離能夠減少30%-50%，由此可見(jiàn)采用遺傳算法求解最佳的揀貨路徑更加有效，同時(shí)其求解時(shí)間也在可以接受的范圍內(nèi)，具有可行性。

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

3.2 一單多車

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

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

4 結(jié)語(yǔ)

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

參考文獻(xiàn)

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

[2]徐天亮.運(yùn)輸與配送[M].北京：中國(guó)物資出版社，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]符卓.帶裝載能力約束的開(kāi)放式車輛路徑問(wèn)題及其禁忌搜索算法研究[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]鐘石泉，杜剛，賀國(guó)光.有時(shí)間窗的開(kāi)放式車輛路徑問(wèn)題及其遺傳算法[J].計(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.

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