動態(tài)物流中多源多點(diǎn)最佳路徑算法研究①

畢明華,何利力

(浙江理工大學(xué) 信息學(xué)院,杭州 310018)

企業(yè)物流主要關(guān)系到配送的成本和對需求的服務(wù),目前仍處于發(fā)展階段,物流配送的能力直接影響了企業(yè)的市場競爭力,如何更快更好的把貨物送到目的地并能快速響應(yīng)市場是一個需要持續(xù)解決的問題.企業(yè)物流是一個典型的多源多點(diǎn)問題,解決這類問題的關(guān)鍵是對多目標(biāo)進(jìn)行優(yōu)化.這類問題起源于許多實(shí)際復(fù)雜系統(tǒng)的設(shè)計(jì),建模和規(guī)劃,在很多實(shí)際的領(lǐng)域中都存在多目標(biāo)優(yōu)化問題[1].與普通的單目標(biāo)相比,帶有多約束條件的多目標(biāo)路徑優(yōu)化問題更加復(fù)雜,且解往往不是唯一的.近年來,關(guān)于車輛最短路徑問題的研究層出不窮,關(guān)于這類問題的解決辦法有多種,在目標(biāo)需求點(diǎn)較多的情況下,往往會使用傳統(tǒng)的算法,但這類算法效果差強(qiáng)人意.遺傳算法是一種高效的全局尋優(yōu)算法,從串集開始的搜索最優(yōu)解,而傳統(tǒng)算法只是從單個初始值進(jìn)行迭代,這是兩者的最大區(qū)別,另外,遺傳算法搜索的覆蓋面更廣,便于全局擇優(yōu)[2].

在解決車輛配送路徑問題的研究上,目前已有了很多的研究成果,但對于多源多點(diǎn)問題并沒有得到很好地解決.文獻(xiàn)[3]提出了一種帶訂單選擇的車輛路徑問題,建立經(jīng)濟(jì)效益最大化的目標(biāo)模型;文獻(xiàn)[4]從空間角度進(jìn)行區(qū)域分割和路徑優(yōu)化,實(shí)驗(yàn)測試算法性能;文獻(xiàn)[5]提出了一種物流配送地理位置規(guī)劃的成本分析方法,建立包括所有終端成本和運(yùn)輸成本的數(shù)學(xué)模型;文獻(xiàn)[6]從按門店配送和按貨物種類2種配送方式,建立相應(yīng)模型,通過仿真實(shí)驗(yàn)比較2種成本;文獻(xiàn)[7]以提高車輛滿載率為目標(biāo)構(gòu)建優(yōu)化模型,并驗(yàn)證模型和算法的有效性;文獻(xiàn)[8] 提出了用于解決容量車輛路徑問題的遺傳算法,通過實(shí)例進(jìn)行算法測試;文獻(xiàn)[9-14]也是通過應(yīng)用遺傳算法來求解不同種類的VRP問題;文獻(xiàn)[15]將動態(tài)路徑求解問題轉(zhuǎn)換為靜態(tài)VRP序列,使用蟻群系統(tǒng)算法進(jìn)行研究DVRP問題.

以上文獻(xiàn)從不同的方面研究車輛配送路徑問題,著重于貨物種類分倉存儲的裝載配送是極少的,這與現(xiàn)實(shí)的倉儲情況存在一定的差距.實(shí)際配送當(dāng)中,往往是多種貨物的混合需求,而現(xiàn)實(shí)的企業(yè)也是通過分倉分類目進(jìn)行存儲,這就需要解決從多個倉庫取貨按各種不同貨物需求進(jìn)行分類送貨.在以往的配貨過程中,通常出現(xiàn)單輛車不能滿足需求而多輛車空載率過高的情況,因此,本文提出一種新的配送方式: 不同倉庫存儲不同種貨物,由單輛車完成配送,充分考慮需求量,配送路徑,車輛載重之間的關(guān)系,建立重量修正車輛優(yōu)化路徑模型,并通過仿真實(shí)驗(yàn)進(jìn)行可行性分析.

1 問題完整性描述

本文著重研究了單輛車承運(yùn)情況下基于多倉庫和多目的地的最佳路徑配送,并提出一種基于重量修正的新配送方式.從車輛貨物裝載倉庫路徑的選擇,到中間路徑的優(yōu)化,找到其費(fèi)用最低,耗時(shí)更少的一條最佳配送路徑.配送分兩種情況: 一種是車輛非滿載情況,即總需求量不大于車輛本身載重量,這種情況下不做重量修正的最短路徑配送;另外一種是車輛滿載情況,即需求量大于車輛本身載重量,就要從不同需求點(diǎn)對不同種貨物的需求量進(jìn)行分析,確定最開始配貨的倉庫,選擇優(yōu)先配送的目的地,完成車容量差值的修正后,實(shí)現(xiàn)多目的地的共同配送.如圖1所示.

圖1 配送方式圖

2 將實(shí)際問題轉(zhuǎn)化為數(shù)學(xué)模型

多倉庫,多目的地的物流配送路徑優(yōu)化問題的數(shù)學(xué)模型如下.建立成本最小目標(biāo)函數(shù):

其中,i表示需求點(diǎn),N表示需求點(diǎn)的總數(shù)量,dis(a,b)表示需求點(diǎn)a和b之 間的距離.j表示倉庫點(diǎn),J表示倉庫點(diǎn)的總數(shù)量.C與C′為互斥變量,當(dāng)需求總量大于車輛本身載重時(shí),需要計(jì)算部分需求點(diǎn)的距離,此時(shí)C為1,C′為0;否則,當(dāng)載重量滿足時(shí),只需計(jì)算兩個倉庫之間的距離,此時(shí)C為0,C′為1.K表示所有需求點(diǎn)的集合.jk,(j+1)m分別表示倉庫j與倉庫j+1之間的兩個需求點(diǎn),且假設(shè)每兩個倉庫點(diǎn)之間的k,m取值各不相同,其值根據(jù)適應(yīng)度算法動態(tài)生成.多源多點(diǎn)問題的配送路徑優(yōu)化問題有以下約束條件:

1)存在多個倉庫j1,j2,j3,···,jn,其存儲的產(chǎn)品種類分別為h1,h2,h3,···,hn.

2)各個需求點(diǎn)對不同種產(chǎn)品的需求總和不超過其存儲總量:

3)車輛的裝載重量不超過該車型的最大載重量

其中,I表示倉庫j到倉庫j+1之間的需求點(diǎn)總數(shù)量.q(i)表 示需求點(diǎn)i的需求量.當(dāng)車輛到達(dá)下一個倉庫時(shí),假設(shè)上一個倉庫與下一個倉庫之間需求點(diǎn)的貨物需求總量小于該車的最大載重量.

4)倉庫只經(jīng)過一次.

cj表示倉庫經(jīng)過的次數(shù).源于貪心策略和現(xiàn)實(shí)運(yùn)輸情況,這里規(guī)定倉庫只經(jīng)過一次,即將所有需求點(diǎn)對此倉庫存儲的貨物需求總量一次性裝車,減少其配送成本.

5)每個需求點(diǎn)經(jīng)過次數(shù)最少一次且不能超過兩次.

ci表示需求點(diǎn)經(jīng)過的次數(shù).需求點(diǎn)每多經(jīng)過一次,其成本多增加一份,因此這里規(guī)定需求點(diǎn)最少經(jīng)過一次且不能超過2次,若需求總量大于車輛本身載重且此需求點(diǎn)適應(yīng)度值較高,允許經(jīng)過一次部分卸貨以減少需求點(diǎn)的總量,之后第二次經(jīng)過時(shí)滿足剩余需求.否則,只允許經(jīng)過一次且滿足此需求點(diǎn)所有種類的貨物需求.

3 對模型求解

3.1 編碼方式

遺傳算法的進(jìn)化過程是建立在染色體編碼結(jié)構(gòu)基礎(chǔ)上的,編碼的好壞對算法的性能有很大的影響,相比二進(jìn)制0-1的編碼方式,自然數(shù)編碼更加直觀,簡潔,尤其在多源點(diǎn),多目的地的求解問題中更具優(yōu)勢.因此,本文采用自然數(shù)編碼.其編碼方式如下: 每個需求點(diǎn)編碼都大于0,其編號分別為 1,2,···,n;表示形式為r1,r2,···,rn;每個倉庫的編碼都不大于0,其編號分別為0,-1,-2,···,m,表示形式為s0,s1,s2,···,sm.

通過預(yù)定義數(shù)組的方式定義倉庫所在城市,當(dāng)檢測為倉庫時(shí),將編號值取反作為數(shù)組下標(biāo)來獲取相應(yīng)的倉庫城市.具體的染色體編碼表示如圖2所示,其中t,k,p表示待定需求點(diǎn),由具體的函數(shù)動態(tài)計(jì)算確定.

圖2 染色體編碼

3.2 初始種群的產(chǎn)生

遺傳算法的初始種群對最終解的優(yōu)劣有很大的影響,選擇合適的初始種群并確定合理的規(guī)模大小是很必要的,因此,本文采用了如下方法來產(chǎn)生初始種群并繪制了產(chǎn)生初始種群的流程圖如圖3所示.

1)首先,計(jì)算出所有目的地的需求總量與汽車載重量之間的差值C.

2)將染色體編碼表示為數(shù)組chromosome,chromosome中的下標(biāo)為0的位置為0,表示從某一倉庫出發(fā).

3)使用Random函數(shù)生成隨機(jī)數(shù),用來檢測下一個到達(dá)的點(diǎn)是否為倉庫點(diǎn).其概率為: 倉庫點(diǎn)數(shù)/(需求點(diǎn)數(shù)+倉庫點(diǎn)數(shù)),當(dāng)小于此值時(shí),即為倉庫點(diǎn).

4)當(dāng)判定為倉庫點(diǎn)時(shí),若為最后一個倉庫點(diǎn)且差值C大于0,轉(zhuǎn)步驟3)若為最后一個倉庫點(diǎn)且差值C不大于0,則說明汽車載重量已經(jīng)滿足,執(zhí)行步驟5);若非最后一個倉庫點(diǎn)且差值C不大于 0,則將剩余倉庫點(diǎn)依次加入數(shù)組chromosome并執(zhí)行步驟5);若非最后一個倉庫點(diǎn)且差值C大于0,判定此隨機(jī)數(shù)是否已經(jīng)加入過數(shù)組chromosome,即: 是否此需求點(diǎn)已經(jīng)經(jīng)過一次,若此隨機(jī)數(shù)未加入過數(shù)組chromosome,則取反加入并計(jì)算每個需求點(diǎn)對此倉庫貨物的需求量的和將其加入差值C.若已加入,則判斷相鄰數(shù)是否加入,直到找到未加入的倉庫點(diǎn),并取反加入數(shù)組chromosome.當(dāng)判定不為倉庫時(shí),則重新生成隨機(jī)數(shù)為下一次到達(dá)的需求點(diǎn).若此需求點(diǎn)已經(jīng)加入數(shù)組chromosome,處理方式與倉庫相同,并將差值C的值減去此需求點(diǎn)需求的值.完成后執(zhí)行步驟3)繼續(xù)查找下一次需要經(jīng)過的倉庫點(diǎn)或需求點(diǎn).

5)到此階段說明當(dāng)前的差值C已經(jīng)不大于0,后續(xù)只需要在各個需求點(diǎn)之間尋找一條最優(yōu)路徑即可.

圖3 產(chǎn)生初始種群的流程圖

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

在遺傳算法中,適應(yīng)度函數(shù)是遺傳操作的重要衡量指標(biāo),依賴適應(yīng)度函數(shù)值進(jìn)行區(qū)別種群個體的優(yōu)劣,適應(yīng)值越大說明染色體性能就越好,反之越差.因此,適應(yīng)值越高被選擇進(jìn)入下一代的機(jī)會越大,本文適應(yīng)度函數(shù)的模型建立分為以下兩種情況:

1)當(dāng)車輛由倉庫到達(dá)第一個需求點(diǎn)時(shí)的適應(yīng)度函數(shù)如下:

式中,N(sj,hj)表示適應(yīng)度值,M表示需求量的闕值,K表示距離的闕值,Pn(hj)表示需求點(diǎn)n對 貨物hj的需求量,dis(sj,pn)表示倉庫sj到需求點(diǎn)pn的距離.

2)當(dāng)車輛離開第一個需求點(diǎn)轉(zhuǎn)至下一個需求點(diǎn)(或倉庫)時(shí)適應(yīng)度函數(shù)如下:

其中,C表示其需求總量與車輛載重之間的差值,T為常數(shù),其值大于1,目的是用于提高適應(yīng)度.

3.4 選擇算子

根據(jù)上面確定的適應(yīng)度函數(shù)求出種群中個體的適應(yīng)值,然后對個體的適應(yīng)度進(jìn)行排序,選擇前50%的較優(yōu)個體進(jìn)行下一步.采取精英保留策略,把群體在進(jìn)化過程中迄今出現(xiàn)的最好個體直接進(jìn)入到下一代中,并將最小適應(yīng)度的個體淘汰.

3.5 模擬細(xì)胞分裂

對于求解本文最佳路徑問題,因每個個體是由多需求點(diǎn)與多倉庫點(diǎn)構(gòu)成,若使用交叉方式,當(dāng)交叉兩個個體的需求點(diǎn)或倉庫點(diǎn)時(shí),極易破壞個體的最佳基因片段,因此本文提出了一種模擬細(xì)胞分裂的方法產(chǎn)生下一代.細(xì)胞分裂是指活細(xì)胞增殖由一個細(xì)胞分裂為兩個細(xì)胞的過程,而在分裂過程中會發(fā)生基因重組.因此,本文采用這一方式,將父代個體的全部信息復(fù)制到子代個體之中,并在生成子代個體時(shí)重組基因序列.其重組規(guī)則如下:

1)若只有兩個倉庫點(diǎn),則隨機(jī)選擇兩個倉庫點(diǎn)之間的任意一個需求點(diǎn),判定其到其他需求點(diǎn)的適應(yīng)度值,找到適應(yīng)值最大的需求點(diǎn),將其與該需求點(diǎn)之后的第一個需求點(diǎn)交換.判定交換后的總適應(yīng)度值與交換之前的總適應(yīng)度值大小,若小于交換之前的總適應(yīng)度值,則舍棄此次基因重組.否則,則標(biāo)記該需求點(diǎn),下次重組時(shí)若隨機(jī)到該需求點(diǎn),則計(jì)算之后的需求點(diǎn).

2)若倉庫點(diǎn)數(shù)大于2,則每個倉庫點(diǎn)之間重復(fù)步驟1).

3)對于最后一個倉庫點(diǎn)之后的所有需求點(diǎn),采用步驟1)的方式判定其重組后的位置.

3.6 選擇變異方式

變異算子的基本內(nèi)容是通過改變?nèi)后w中個體染色體的某些基因值,來加快最優(yōu)解的收斂速度并提高種群多樣性.本文使用交換需求點(diǎn)的方式來進(jìn)行變異操作,首先生成此個體的變異概率P(n)m,將此概率與設(shè)定的總變異概率Pm進(jìn) 行比較,若P(n)m＜Pm,則生成兩個隨機(jī)數(shù)用來標(biāo)識兩個需求點(diǎn)并進(jìn)行交換;否則,進(jìn)行下一個個體的判定.對于總變異概率,使用階段性的值,即隨世代數(shù)越來越大,其總變異概率越來越小,這樣可以確保在種群的最后的階段不會破壞其中的優(yōu)秀個體.

3.7 結(jié)束標(biāo)識

若種群達(dá)到規(guī)定的遺傳代數(shù),則結(jié)束迭代,否則從選擇算子開始下一輪循環(huán).

4 實(shí)驗(yàn)分析

假設(shè)各個倉庫存放的貨物為表1,各個需求點(diǎn)對每種貨物的需求量為表2,各倉庫與各需求點(diǎn)之間的距離為表3,各個倉庫點(diǎn)之間的距離為表4,汽車載重量為3000 kg.

表1 各倉庫存放的貨物類型

表2 各需求點(diǎn)對每種貨物的需求量(kg)

表3 各倉庫與各需求點(diǎn)之間的距離(km)

表4 各需求點(diǎn)之間的距離(km)

表中倉庫編號s0,s1,s2分別對應(yīng)城市杭州,南京,合肥.表中需求點(diǎn)編號R1,R2,R3,R4,R5,R6,R7分別對應(yīng)城市寧波,上海,上饒,南昌,石家莊,濟(jì)南,北京.

本文設(shè)置初始種群數(shù)量為1000,世代數(shù)為200,初始變異概率為0.1,通過執(zhí)行100次仿真運(yùn)算,從結(jié)果中隨機(jī)取10次,如表5所示.

表5 10次測試生成的最短路程(km)

從表5中可以看出在初始種群中使用的隨機(jī)數(shù)對結(jié)果并無較大影響.在第3,5,6,9,10次測試中,其標(biāo)準(zhǔn)遺傳里程為0 KM,原因是標(biāo)準(zhǔn)遺傳算法未考慮重量修正的情況,在最終結(jié)果中因不能完成客戶點(diǎn)的需求,導(dǎo)致發(fā)生異常退出程序.對應(yīng)狀態(tài)如圖4所示,由圖4得出,改進(jìn)的遺傳算法比標(biāo)準(zhǔn)的遺傳算法路程減少約一半且10次測試結(jié)果變化幅度較平穩(wěn),其最短路程為4555.231 KM,生成的路徑如下:s0,s1,R2,R1,R3,s2,R4,R3,R1,R2,R6,R5,R7.對應(yīng)的城市為: 杭州,南京,上海,寧波,上饒,合肥,南昌,上饒,寧波,上海,濟(jì)南,石家莊,北京.

圖4 10次測試生成的最短路程(單位: KM)

圖5為需求總量與汽車載重的差值隨經(jīng)過城市數(shù)的變化圖.由圖5可以分析得出,當(dāng)汽車經(jīng)過第4個城市后,其汽車載重量已經(jīng)滿足需求總量的條件.此時(shí),汽車將前往其他倉庫點(diǎn)裝載貨物,之后按照最佳路徑完成每個需求點(diǎn)的配送.

圖5 需求總量與汽車載重的差值隨經(jīng)過城市數(shù)的變化圖

5 結(jié)論

在大規(guī)模多源多點(diǎn)倉儲物流的配送問題中,因其存在多約束條件和多優(yōu)化目標(biāo),使得優(yōu)化問題相當(dāng)困難.本文提出的基于重量修正的物流配送新方式,優(yōu)化了初始種群的產(chǎn)生,且提出了模擬細(xì)胞分裂的方式來產(chǎn)生下一代,有效地避免了傳統(tǒng)遺傳算法中“早熟收斂”等問題,經(jīng)實(shí)驗(yàn)驗(yàn)證增強(qiáng)了遺傳算法的收斂速度,在有限的計(jì)算能力下,縮短了尋優(yōu)時(shí)間.該算法對于實(shí)際運(yùn)輸中一輛車負(fù)載過重多輛車空載率較高問題是一種較好的解決方案.