改進(jìn)的兩階段算法求解差別費(fèi)率車輛調(diào)度問題

吳成賓,聶志萍

(1.成都大學(xué)現(xiàn)代教育技術(shù)中心,四川成都 610106;2.成都大學(xué)工業(yè)制造學(xué)院,四川成都 610106)

0 引 言

經(jīng)濟(jì)的持續(xù)平穩(wěn)發(fā)展離不開物流配送業(yè)的支撐.據(jù)有關(guān)資料顯示,在物流成本中,配送環(huán)節(jié)是成本消耗較大的環(huán)節(jié),它約占物流總成本的1/3～2/3左右[1].目前,不少中小物流企業(yè)仍然依靠人工手段來編制配送方案,配送效率偏低,配送線路也不盡合理,整個(gè)配送方案有較大的優(yōu)化余地及成本下降空間.因此,研究物流配送車輛調(diào)度問題(Vehicle Routing Problem,VRP)具有重要的理論和現(xiàn)實(shí)意義,對(duì)該問題研究得相對(duì)較多的是尋求最短路徑VRP[2-3],但車輛行駛距離計(jì)算并不總能精確地刻畫運(yùn)輸成本.實(shí)際上,物流配送行業(yè)通常根據(jù)車輛在負(fù)載和空載情況下分別核算運(yùn)輸成本:當(dāng)負(fù)載時(shí),成本與行駛距離及負(fù)載重量正相關(guān);而當(dāng)空載時(shí),成本只與行駛距離呈簡單的線性正相關(guān)關(guān)系.基于此,本研究通過建立不同的成本核算模型,并將改進(jìn)的掃描算法和單親遺傳算法結(jié)合起來,通過探尋較為優(yōu)化的配送線路,以期獲得滿意的最小配送成本方案.

1 差別費(fèi)率VRP數(shù)學(xué)模型

設(shè)有1個(gè)配送中心(編號(hào)為0)為N個(gè)客戶(1,2,…,N)配送物資,每個(gè)客戶的貨物需求量為wi(i= 1,2,…,N);配送中心有若干臺(tái)準(zhǔn)載質(zhì)量為 E0的車輛,滿足任意wi≤E0;每臺(tái)車輛出發(fā)時(shí)只裝載本次出行所必須的貨物量,要求每個(gè)客戶只能由一輛車配送一次且僅一次;客戶 i到客戶j的距離為dij,配送中心到客戶的距離為 d0j(i,j=1,2,3,…,N),車輛每抵達(dá)一個(gè)客戶即卸下所需貨物,在最后一個(gè)客戶處卸完貨后,空車返回.根據(jù)物流配送行業(yè)的精確成本核算方法,當(dāng)車輛負(fù)載時(shí),每噸每公里運(yùn)費(fèi)成本為α元;當(dāng)空載返回配送中心時(shí),成本為每公里β元,設(shè) cij表示從點(diǎn)i到j(luò)的配送成本,m為配送用到的車輛數(shù)(子路徑數(shù)),并定義以下變量:

設(shè)計(jì)以配送成本最低為優(yōu)化目標(biāo)的最佳配送路線,其數(shù)學(xué)模型可描述如下:

式中,式(1)為配送總成本目標(biāo)函數(shù);式(2)為滿足不準(zhǔn)超載的約束;式(3)為確保任意一個(gè)客戶的配送任務(wù)僅由1臺(tái)車輛來完成,所有配送任務(wù)則由 m臺(tái)車完成;式(4)及式(5)限定到達(dá)和離開任一客戶的車輛有且僅有1臺(tái);式(6)保證任一臺(tái)車最多只能同時(shí)為一個(gè)客戶服務(wù);式(7)為車輛從配送中心出發(fā)時(shí)所載貨物的質(zhì)量,以及每到達(dá)一個(gè)客戶處卸貨后,車上貨物的剩余質(zhì)量;式(8)為成本計(jì)算非連續(xù)函數(shù);式(9)給出了車輛負(fù)載時(shí)任意2個(gè)節(jié)點(diǎn)之間的配送成本,它是節(jié)點(diǎn)間距離以及車輛所載貨物質(zhì)量的函數(shù);式(10)表示車輛空載時(shí),配送成本只與距離有關(guān).

2 兩階段求解算法

本研究提出的兩階段求解算法的具體思路為:第一階段采用改進(jìn)的掃描算法[4]以獲得滿足所有約束條件的一組初始解;第二階段,采用這組初始解作為初始種群,并用改進(jìn)的單親遺傳算法[5-7]進(jìn)行大范圍搜索和優(yōu)化,以獲得較滿意的解.

2.1 改進(jìn)的掃描算法

改進(jìn)的掃描算法是一種啟發(fā)式算法,其求解過程分成以下4步:①以起始點(diǎn)(本文為配送中心)為原點(diǎn)建立極坐標(biāo)系;②根據(jù)每個(gè)客戶點(diǎn)的平面直角坐標(biāo),計(jì)算對(duì)應(yīng)的極角;③從最小的極角開始,按規(guī)定的方向(如逆時(shí)針)將該極角對(duì)應(yīng)的客戶逐個(gè)加入到當(dāng)前配送子路徑中,直到不滿足約束條件時(shí),重新建立一個(gè)新的子路徑;④重復(fù)步驟 ③,直到將全部客戶掃描完畢.

實(shí)際處理時(shí),通過反三角函數(shù)求得客戶坐標(biāo)極角.當(dāng) Y軸坐標(biāo)小于0時(shí),極角是負(fù)數(shù),并確保所有極角位于[0,2π]區(qū)間之內(nèi),再將它們按從小到大的順序生成一個(gè)雙向鏈表(見圖1),按逆時(shí)針和順時(shí)針掃描總共得到的配送路線為2N條.

圖1 極角雙向物理掃描示意圖

根據(jù)坐標(biāo)系原理,極角和平面直角坐標(biāo)反映了客戶所處的物理位置,所以極角掃描可以看成是物理掃描.另外,仿照掃描法原理,根據(jù)客戶的邏輯編號(hào)來掃描,稱之為邏輯掃描,可以得到另外2N條配送線路.

2.2 改進(jìn)的單親遺傳算法

對(duì)有N個(gè)客戶節(jié)點(diǎn)的VRP,改進(jìn)的掃描算法會(huì)生成4N條完全不同但符合約束條件的配送路徑.對(duì)此,可將每條配送路徑看成一條染色體,則4N條配送路徑就構(gòu)成了初始種群.考慮到染色體的長度可能并非一樣長,且傳統(tǒng)的遺傳算法中基于雙親的交叉算子不太適用.因此本研究采用單親遺傳算法,其最大的特點(diǎn)在于對(duì)任意個(gè)體的遺傳操作只在該條染色體上進(jìn)行,即只通過單親繁殖后代.單親遺傳算法求解過程分成以下6步:①編碼;②計(jì)算個(gè)體的適應(yīng)度函數(shù);③產(chǎn)生初始群體;④評(píng)價(jià)群體中的各個(gè)個(gè)體;⑤選擇下一代群體,若滿足停止條件,則輸出結(jié)果,否則轉(zhuǎn)下一步;⑥在每條染色體上進(jìn)行基因重組操作,產(chǎn)生新個(gè)體,轉(zhuǎn)步驟 ④.

算法具體實(shí)現(xiàn)過程如下:

(1)編碼方法.采用自然數(shù)編碼,例如有5個(gè)客戶,其編號(hào)分別為1,2,3,4,5,貨物需求量分別為3, 4,2,5,1噸.當(dāng)車輛準(zhǔn)載8 T時(shí),則可能的配送路線(染色體)表示為:0-3-4-5-0-1-2-0,即有2條子路徑,第1條從配送中心出發(fā),經(jīng)由3,4,5號(hào)客戶后返回配送中心,第2條從配送中心出發(fā),經(jīng)由1,2號(hào)客戶后返回配送中心.

(2)適應(yīng)度評(píng)估.對(duì)于每條配送路徑,在計(jì)算適應(yīng)度前,首先要判斷是否滿足所有的約束條件,若不滿足,直接令其適應(yīng)度為 -1;否則,根據(jù)式(10)計(jì)算配送成本 ci.找出成本最大值 cmax,并對(duì)每條配送路徑按以下公式計(jì)算其相對(duì)成本,

其中,ζ是一個(gè)很小的正數(shù)(算法中缺省為0.01),顯然,所有染色體的相對(duì)成本都是一個(gè)正數(shù),且落在區(qū)間[ζ,cmax+ζ)之內(nèi),cri值越大,配送成本越低,適應(yīng)度越高.

(3)選擇操作.采用精英保留和輪盤賭策略,即每代群體中的所有染色體按適應(yīng)度從大到小排列,精英個(gè)體排在最前面,直接進(jìn)入下一代,其余個(gè)體按照輪盤賭的原則確定去留.

(4)染色體重組.重組只針對(duì)非精英個(gè)體進(jìn)行.算法綜合采用基因換位、移位、倒位、突變等算子[7].

(5)終止準(zhǔn)則.達(dá)到規(guī)定代數(shù)則終止.

3 實(shí)例計(jì)算與結(jié)果分析

某物流配送中心位于某市東部,它有15個(gè)大客戶,中心每天為這些客戶配送物料,有準(zhǔn)載質(zhì)量50 T車輛若干臺(tái),車輛每噸每公里配送成本0.35元,空車返回時(shí),每km成本0.98元.表1給出了客戶相對(duì)于中心的平面 X,Y坐標(biāo),以及各客戶的物資需求量.各客戶間實(shí)際距離從數(shù)據(jù)文件(e-vrp.dat)中獲取.

表1 需求及坐標(biāo)數(shù)據(jù)表

本研究用Visual C++2010開發(fā)了配送調(diào)度軟件,對(duì)采用人工調(diào)度、經(jīng)典遺傳算法、改進(jìn)的兩階段算法3種配送成本方案分別進(jìn)行了計(jì)算,其中,經(jīng)典遺傳算法初始種群隨機(jī)生成;改進(jìn)的兩階段算法精英個(gè)體保留比例為10%,基因換位、移位、倒位、變異率分別為0.75、0.5、0.3、0.01,最大進(jìn)化代數(shù)為5 000.3種算法分別運(yùn)行3次,結(jié)果如表2所示.

表2 3種配送成本方案對(duì)比

從表2可以看出,傳統(tǒng)調(diào)度方案平均成本為1 693.66元,經(jīng)典遺傳算法平均成本1 559.33元,兩階段算法平均成本為1 415.37元,成本降幅分別為7.9%和16.4%.

圖2為人工調(diào)度傳統(tǒng)配送路線,其中,0～15分別代表配送中心及各客戶,實(shí)心圓點(diǎn)越大,表示該客戶所需貨物質(zhì)量越大,實(shí)線表示負(fù)載配送線路,虛線表示空載返回.

圖2 人工調(diào)度傳統(tǒng)配送路線

從圖2中可見,有6條配送子路徑,各子路徑滿載率分別為96%,84%,72%,70%,94%,26%,平均滿載率約為74%.

圖3為經(jīng)典遺傳算法配送路線.

圖3 經(jīng)典遺傳算法配送路線

從圖3可見,配送總里程與人工調(diào)度相比有一定的下降,各子路徑滿載率分別為68%,94%,72%, 90%,100%,18%,平均滿載率約74%.

圖4為改進(jìn)的兩階段算法配送路線.

圖4 改進(jìn)的兩階段算法配送路線

比較圖2和圖4可見,圖2中各子路徑間存在明顯的交叉,意味著配送車輛繞了彎路,導(dǎo)致成本上升.圖3和圖4清楚地顯示了優(yōu)化后的線路,基本消除了重合的部分,理應(yīng)帶來成本的下降.而圖4配送子路徑數(shù)比圖2或3均少了一條,配送總里程也最低,僅有207公里,成本最低,各子路徑滿載率分別為 86%,94%,80%,82%,100%,平均滿載率約89%.本算法方案在該物流配送中心經(jīng)過數(shù)月的運(yùn)行,經(jīng)過實(shí)際測算,配送成本同比下降了16.1%,環(huán)比下降了14.4%,基本與理論分析結(jié)果一致.

4 結(jié) 語

改進(jìn)的兩階段算法能快速解出差別運(yùn)輸費(fèi)率VRP的優(yōu)化路徑,可以有效降低傳統(tǒng)調(diào)度方案的配送成本,此對(duì)普遍存在融資難的小、微型物流配送企業(yè)來說,這種改進(jìn)在一定程度上減輕了流動(dòng)資金壓力,有利于企業(yè)在競爭激烈的市場中持續(xù)發(fā)展.

[1]姜昌華.遺傳算法在物流系統(tǒng)優(yōu)化中的應(yīng)用研究[D].上海:華東師范大學(xué),2007.

[2]劉曉羽中,戴敏,鄭剛,等.運(yùn)鈔車車輛路徑規(guī)劃策略[J].計(jì)算機(jī)應(yīng)用,2011,31(4):1121-1124.

[3]陳森,李孟軍,李本先,等.變路網(wǎng)情況下車輛路徑問題建模及應(yīng)用[J].計(jì)算機(jī)科學(xué),2012,39(2):14-17.

[4]朱明華,范秀敏,劉炳凱,等.上海浦東新區(qū)城市生活垃圾收運(yùn)路線優(yōu)化研究[J].資源科學(xué),2009,31(9):1612-1618.

[5]郭海湘,楊娟,馬爭艷,等.煤礦物資多車型配送的改進(jìn)遺傳算法求解[J].運(yùn)籌與管理,2011,20(2):193-199.

[6]鄒書蓉,黃曉濱,張洪偉.有容量約束車輛路徑問題的多目標(biāo)遺傳算法[J].西南交通大學(xué)學(xué)報(bào),2009,44(5):782-786.

[7]李倩,文貴華,丁月華.一種改進(jìn)的求解旅行商問題的單親遺傳算法[J].計(jì)算機(jī)工程與科學(xué),2007,29(2):89-92.