改進的兩階段算法求解差別費率車輛調度問題

吳成賓,聶志萍

(1.成都大學現代教育技術中心,四川成都 610106;2.成都大學工業制造學院,四川成都 610106)

0 引 言

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

1 差別費率VRP數學模型

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

設計以配送成本最低為優化目標的最佳配送路線,其數學模型可描述如下:

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

2 兩階段求解算法

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

2.1 改進的掃描算法

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

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

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

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

2.2 改進的單親遺傳算法

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

算法具體實現過程如下:

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

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

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

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

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

(5)終止準則.達到規定代數則終止.

3 實例計算與結果分析

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

表1 需求及坐標數據表

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

表2 3種配送成本方案對比

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

圖2為人工調度傳統配送路線,其中,0～15分別代表配送中心及各客戶,實心圓點越大,表示該客戶所需貨物質量越大,實線表示負載配送線路,虛線表示空載返回.

圖2 人工調度傳統配送路線

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

圖3為經典遺傳算法配送路線.

圖3 經典遺傳算法配送路線

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

圖4為改進的兩階段算法配送路線.

圖4 改進的兩階段算法配送路線

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

4 結 語

改進的兩階段算法能快速解出差別運輸費率VRP的優化路徑,可以有效降低傳統調度方案的配送成本,此對普遍存在融資難的小、微型物流配送企業來說,這種改進在一定程度上減輕了流動資金壓力,有利于企業在競爭激烈的市場中持續發展.

[1]姜昌華.遺傳算法在物流系統優化中的應用研究[D].上海:華東師范大學,2007.

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

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

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

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

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

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