考慮貨物類別的電動汽車路徑優(yōu)化問題研究

張艷偉，黃志紅

(武漢理工大學 物流工程學院，湖北 武漢 430063)

電動汽車依靠車載電池提供動力，能夠有效減少尾氣污染,節(jié)約環(huán)境治理成本，這一特點促使其在物流配送行業(yè)中得到廣泛的關(guān)注與應(yīng)用[1]。電動汽車產(chǎn)業(yè)和配套服務(wù)設(shè)施的快速發(fā)展為電動汽車在物流配送行業(yè)的普及提供了有力保障。然而，電動汽車最大行駛距離受到電池容量的限制。此外，由于貨物性質(zhì)和配送條件的差異，現(xiàn)實中普遍存在著部分類別的貨物不能與指定類別貨物在同一車廂中混合運輸?shù)那闆r，而這些貨物本身可以和除開指定類別以外的大多數(shù)種類的貨物一起配送。主要原因有：①配送條件不同。如土豆和紅薯在運輸過程中適宜的溫度不同，紅薯喜溫，溫度適合在15 ℃以上，否則就會僵心；土豆喜涼，溫度適合在2～4 ℃，否則就會發(fā)芽。②貨物性質(zhì)不同。如茶葉不能與糖一同配送，這兩類物品放在一起會導致茶葉吸收潮濕而發(fā)霉。此外茶葉等具有吸附性的貨物不能和樟腦丸、香皂、香水、香煙等具有異味的貨物裝在同一車廂內(nèi)。③其他原因。如未出欄的育肥豬不宜和用于產(chǎn)崽的母豬共同運輸，運輸會使豬產(chǎn)生應(yīng)激反應(yīng)。體重差異過大可能導致小豬被大豬壓死或踩傷。這就產(chǎn)生了帶有貨物類別約束的車輛路徑問題(vehicle routing problem，VRP)。貨物類別和運輸路徑是相互制約的，忽略貨物類別的差異性可能增加貨物在運輸途中的損失，降低對顧客的服務(wù)水平。忽略運輸路徑的優(yōu)化，更多的配送車輛和更長的配送距離又將產(chǎn)生高昂的運輸成本。只有兼顧兩方面的約束，才可能實現(xiàn)問題的全局優(yōu)化。這也對車輛路徑問題提出了更高要求。因此，科學地規(guī)劃電動汽車配送路徑，優(yōu)化電動汽車物流網(wǎng)絡(luò)成為近期的研究熱點問題。

近年來，國內(nèi)外學者從多方面對電動汽車路徑優(yōu)化問題進行了研究，取得了豐富的成果。王征等[2]建立起帶二維裝箱約束的物流配送車輛路徑模型，提出了解決該問題的啟發(fā)式算法Memetic。王長瓊等[3]研究了三維裝載約束下的汽車零部件循環(huán)取貨路徑優(yōu)化問題，在循環(huán)取貨過程中考慮實際車輛路徑約束和三維裝載約束條件，構(gòu)建了三維裝載約束下零部件循環(huán)取貨路徑優(yōu)化模型，提出了一種混合禁忌算法求解該問題。YANG等[4]研究了電動汽車物流配送系統(tǒng)配送路徑優(yōu)化問題，考慮了配送車輛的最大載重量及電動汽車每次充滿電的最大行駛里程。揭婉晨等[5]研究了含時間窗的多車型電動汽車車輛路徑問題，考慮配送車輛不同的載重量和最大行駛里程。王勝等[6-7]采用改進混合啟發(fā)式算法對車輛路徑問題進行了研究。BORTFELDT等[8]將車輛路徑問題與車輛裝載問題進行整合優(yōu)化，并在路徑優(yōu)化中考慮車輛裝載體積和質(zhì)量約束．

綜合來看，多數(shù)研究車輛路徑問題的文獻大多關(guān)注于路徑長度的最小化，僅將貨物重量納入考慮范圍?？紤]了貨物屬性的文獻也僅僅關(guān)注于貨物形狀，沒有根據(jù)貨物配送要求與條件將貨物分類配送。鑒于此，筆者建立基于電動汽車運營成本最小化的考慮貨物分類配送的電動汽車車輛路徑?jīng)Q策模型， 與已有研究的主要區(qū)別為：①除了重量外，賦予貨物配送屬性參數(shù)。貨物僅能和與其屬性相同或相近的貨物共同配送;②提出了MCWS和MHGA兩種啟發(fā)式算法來解決該問題，并對兩種算法的求解性能進行比較。

1　問題描述及數(shù)學模型

1.1　問題描述

物流配送網(wǎng)絡(luò)G=(V,E)，其中V={v1,v2,…,vn}表示頂點集合，由顧客集合I、配送中心o和虛擬配送中心o′ 共同組成，即V=I∪{o}∪{o′}。E={(vi,vj):vi,vj∈V,vi≠vj}表示弧的集合。集合I中每個節(jié)點i都具有需求量參數(shù)qi和分類參數(shù)ci。將貨物分為A，B，C 類，對應(yīng)的分類參數(shù)分別為-1，0，1，其中A類貨物可以和B類貨物共同配送，B類和C類也可以共同配送，但是A類貨物和C類貨物不可以共同配送。集合E中每條弧都包含非負權(quán)值屬性dij，dij表示節(jié)點i和j之間的距離。K={k}表示配送車輛集合。集合K中每一輛車k都包含兩個非負權(quán)值屬性，即車輛k的最大載重Uk和滿電量狀態(tài)下最長行駛里程Q。集合R={r1,r2,…,rz}是配送路徑的集合，每條路徑由一輛車負責配送。pik為車輛k到達節(jié)點i的電量還能行駛的距離；uik為車輛k離開節(jié)點i時的剩余載重量；qi為節(jié)點i處顧客的需求量；γ為車輛行駛單位距離的單位成本；xijk為0-1變量，當車輛k經(jīng)過弧(i，j) 時，xijk=1，否則為0。

1.2　數(shù)學模型

基于上述條件，構(gòu)建如下數(shù)學模型:

(1)

s．t．

?j∈I

(2)

(3)

?i∈V

(4)

(5)

(6)

ujk≤uik-qjxijk+Uk(1-xijk)

(7)

?j∈V

uok≤Uk?k∈K

(8)

ujk≥0?k∈K,j∈V

(9)

(10)

?j∈V

pjk≤pik-dijxijk+Q(1-xijk)

(11)

?i∈V

pok=Q?k∈K

(12)

pjk≥0?j∈V

(13)

xijk∈{0,1}?i∈V

(14)

上述模型中，式(1)表示最小化運營成本；式(2)表示每個顧客點只被服務(wù)一次；式(3)表示各點車流量平衡；式(4)表示配送車輛從倉庫出發(fā)，服務(wù)若干顧客點后最終回到原來的出發(fā)點；式(5)表示每輛車最多服務(wù)一條路徑；式(6)表示參與配送任務(wù)的車輛數(shù)目不能超過擁有的車輛總數(shù)；式(7)表示配送車輛按照路徑途經(jīng)各點的剩余貨物量。如果車輛k在經(jīng)過顧客點i后直接到達顧客點j(即xijk=1)，則車輛離開j點時剩余貨物量等于離開i點時的剩余貨物量減去j點的需求量，否則，式(7)被松弛；式(8)確保任何一條路徑中的顧客總需求量不能超過提供服務(wù)的車輛的最大載重量；式(9)表示剩余貨物量為非負；式(10)表示只有屬性相同或相近的貨物才能由一輛車配送；式(11)表示配送車輛按照路徑途經(jīng)各點的剩余電量，邏輯關(guān)系類似于式(7)；式(12)表示車輛離開起點時的電量；式(13)表示充電量為非負數(shù)；式(14) 表示變量屬性。

2　啟發(fā)式算法MCWS

Clarke-Wright節(jié)約算法是一種求解車輛路徑問題的經(jīng)典啟發(fā)式算法，ERDOAN等[9]對算法進行改進以解決電動汽車車輛路徑問題(GVRP)。筆者采用啟發(fā)式算法MCWS(modified Clarke-Wright savings heuristic)求解區(qū)分貨物類別的電動汽車配送路徑問題，具體步驟為：①為每個需要服務(wù)的顧客點i生成一條對應(yīng)的路徑(o-i-o)，其中點o為配送中心。②查找出可行路徑中與點o相連的毗鄰點，計算任意連接不同路徑上兩個毗鄰點的saving值，將毗鄰點以成對的形式按照saving值降序排列放入節(jié)省對列表SPL中，saving=doj+doi-dij。③將SPL節(jié)省對按照saving值降序順序執(zhí)行路徑合并。如果兩個毗鄰點不屬于同一條路徑，兩條對應(yīng)路徑的需求點之和小于車輛的載重限制，且貨物類別可以同時配送，則將兩個點所在的路徑合并。合并方法如下: 刪除毗鄰點與點o之間的連接線，隨后將兩個毗鄰點直接相連。合并后檢查新路徑是否滿足電動汽車行駛路徑的電量約束。如果不滿足，則放棄此次路徑合并。兩路徑合并流程如圖1所示。④將SPL中所有毗鄰點對合并之后，返回步驟①進入新一輪路徑合并，直到任意兩條可行路徑都不能進一步合并為止。⑤為了提高解的質(zhì)量，筆者采用移動和交換兩種形式進一步優(yōu)化當前解。移動是指移動路徑中某一顧客點的位置，將其與同路徑中其余所有顧客點依次互換位置。交換是指交換不同路徑中兩個顧客點的位置。以上兩種策略均采用窮舉法實現(xiàn)，優(yōu)化過程需滿足車輛行駛里程和載重量約束。路徑優(yōu)化流程如圖2所示。

圖1　兩路徑合并流程

圖2　路徑優(yōu)化流程

3　啟發(fā)式算法MHGA

遺傳算法是一種借鑒自然選擇和自然遺傳機制的隨機化搜索方法，其全局搜索能力較強而局部搜索能力不足。爬山算法是一種基于鄰域搜索技術(shù)的，沿著有可能改進解的質(zhì)量的方向進行單方向搜索(爬山)的方法，其具有較強的局部搜索能力。筆者將遺傳算法與爬山算法相結(jié)合，為彌補遺傳算法局部搜索能力的缺陷，采用改進混合遺傳算法MHGA(modified hybrid genetic algorithm)求解區(qū)分貨物類別的電動汽車配送路徑問題。重點需要考慮以下幾個問題：

(1)編碼方案。筆者使用顧客自身排列的編碼方法來確定配送路徑策略。該方法直接生成N個1～N間不重復的整數(shù)的排列，每個自然數(shù)表示一個顧客個體。例如一條染色體為(7,4,1,3,6,5,2)，則表示等待服務(wù)的顧客點順序為(N7,N4,N1,N3,N6,N5,N2)。根據(jù)排列中數(shù)字的順序，依次指派給配送車輛，滿足以下3個條件之一,則由對應(yīng)顧客點開始將其指派給下一輛配送車輛:①配送路徑長度超過車輛一次配送的最大行駛距離;②當前貨物類別不能與之前已指派給該車輛的配送貨物類別一起配送;③顧客的需求量之和超過車輛最大載重量。如果顧客需求的配送路徑數(shù)多于可使用的配送車輛數(shù)目，則該個體對應(yīng)一個不可行解。

(2)群體初始化。假設(shè)群體規(guī)模為M，則采用隨機生成的方式得到M個不同個體，每個個體包含N個1～N間不重復的整數(shù)的排列。

(4)選擇操作。將每代群體中適應(yīng)度最高的個體復制后放入下一代第1列，其余個體根據(jù)適應(yīng)度大小，在輪盤賭機制下以一定概率進入下一代。

(5)交叉操作。由于筆者采用了序號編碼方式，不能像非序號編碼的染色體一樣任意進行交叉。采用PMX類型交叉算法，交換個體交叉點之間的片段。如果新生成的基因序號沒有出現(xiàn)沖突則保留此個體，否則通過部分映射確定新個體。PMX交叉的過程如圖3所示。

圖3　PMX交叉的過程

(6)變異操作。序號編碼下基因突變的常見方式有兩種:①互聯(lián)變異，即在變異的個體中隨機選擇兩個基因并交換其位置，從而形成一個新的子代個體；②逆轉(zhuǎn)變異，即在變異的子個體中隨機選擇兩點，將兩點之間的基因進行逆轉(zhuǎn)。筆者交替使用兩種變異技術(shù)保持群體內(nèi)個體的多樣性。

(7)爬山操作。針對遺傳產(chǎn)生的每一代中的最優(yōu)個體，隨機交換其中兩個基因的位置。如果交換基因位置后個體的適應(yīng)度增加，則保留新個體放棄原個體。否則繼續(xù)交換到指定次數(shù)為止。

(8)終止準則。筆者采用進化指定代數(shù)的終止準則。

4　實驗結(jié)果及分析

實驗的計算機參數(shù)配置為Intel(R) I5-4460，3.20GHz，8GB RAM。算法在JAVA中實現(xiàn)為單線程代碼。

4.1　測試用例

數(shù)據(jù)來源主要包括兩部分：benchmark 采用AUGERAT等[10]提出的算例，可以從網(wǎng)站http://neo.lcc.uma.es/vrp/vrp-instances/上獲取。算法使用參數(shù)來源于文獻[4]和文獻[11]。

4.2　實驗結(jié)果與分析

4.2.1模型與算法的驗證分析

為了評估模型的準確性及算法的尋優(yōu)能力，筆者使用能被IBM ILOG CPLEX12.6求解的小規(guī)模算例進行計算。隨后與混合遺傳算法和改進節(jié)約算法的計算結(jié)果進行比較。為了保證實驗的一般性，在文獻[8]提出的算例P-n16-k8中選擇6組小實例數(shù)據(jù)，小實例數(shù)據(jù)只選用了初始算例的最后n個顧客點。每組實例包含的顧客數(shù)與可用車輛數(shù)目不同。設(shè)定CPLEX運行時間的上限為3 600 s。*表示此解是CPLEX運行3 600 s得到的可行解。#表示CPLEX未能在規(guī)定時間內(nèi)找到可行解。考慮到算法中包含隨機參數(shù)，針對每一個算例都將算法運行10次，實驗結(jié)果對比如表1所示。其中N和K分別為算例包含的顧客點數(shù)目和可調(diào)配的車輛數(shù)。S表示配送路徑數(shù)目；Time表示求解時間；Gap表示算法最優(yōu)解與CPLEX結(jié)果的相對差值,Gap=(算法的最優(yōu)解-CPLEX求出的最優(yōu)解)/CPLEX求出的最優(yōu)解。通過表1可以看出啟發(fā)式算法的結(jié)果與CPLEX非常接近，并且算法求解效率較高，驗證了模型和算法的正確性。

4.2.2模型對運營成本的影響性分析

筆者將所提出的考慮貨物分類的VRP模與傳統(tǒng)VRP模型進行對比研究,從文獻[8]的數(shù)據(jù)集中選取4組實例，比較算例在兩種數(shù)學模型下的最優(yōu)運營成本。

表1　實驗結(jié)果對比

圖4　配送距離對比

圖5　混運路徑數(shù)量對比

兩種模型在不同案例中配送距離對比情況如圖4所示。其中，模型一表示已區(qū)分貨物類別，模型二表示未區(qū)分貨物類別。由圖4可知，兩種模型在不同算例中的行駛距離非常接近，模型二的距離略短于模型一。兩種模型在不同案例中將不適宜共同配送的貨物指派給同一輛車的混運配送路徑數(shù)量如圖5所示。其中，模型一在建模之時區(qū)分了貨物類別，避免了以上情況的發(fā)生，所以在4組算例中的結(jié)果均為0。模型一可以在總路徑略微增加的情況下，通過改變路徑策略來減少混合配送的路徑，以降低貨物在配送過程中的損失，提高顧客滿意度。

筆者以算例p-n16-k6為例，展示兩種模型求解出的最優(yōu)路徑策略。算例p-n16-k6包括16個顧客點，最大可使用車輛數(shù)為6輛。圖6和圖7分別展示了模型一和模型二的路徑策略，圖中黑、白、灰3色圓圈表示顧客需求貨物類型分別為A、B、C，其中A、C兩類貨物不適宜由同一輛車混裝配送。路徑策略如表2所示。由表2可知，兩種模型在該算例中都只使用了5輛配送車輛。*表示此路徑中A、C兩類貨物由一輛車配送。其中，模型一的路徑總長度為800.48 km。模型二的路徑總長度為783.93 km。

圖6　模型一配送路徑圖

圖7　模型二配送路徑圖

序號模型一配送路徑模型二配送路徑1倉庫→8→13→7→倉庫倉庫→2→7→倉庫2倉庫→0→15→12→3→9→倉庫倉庫→6→1→0→倉庫3倉庫→11→4→10→1→倉庫倉庫→10→3→8→13→倉庫*4倉庫→14→5→2→倉庫倉庫→11→12→15→4→倉庫*5倉庫→6→倉庫倉庫→5→9→14→倉庫*路徑總長/km800.48783.93

4.2.3算法尋優(yōu)能力的對比分析

筆者采用9組不同規(guī)模算例驗證兩種算法的路徑優(yōu)化能力。算法運行10次并將最優(yōu)解記錄下來，實驗結(jié)果對比如表3所示。其中,J表示算法最優(yōu)解使用車輛數(shù)目。由表3可知，兩種算法最優(yōu)解的相對差距最大達到了11.842%。通過比較可以看出，MCWS 的解整體優(yōu)于MHGA，MHGA只在算例p-n55-k20中得到了最優(yōu)值。此外，實驗結(jié)果顯示對不同的算例，算法的求解時間大相徑庭，同類型實例的求解時間隨著模型規(guī)模的增加呈現(xiàn)出上升趨勢。規(guī)模相近的不同類型實例的求解時間也有較大差異。這表明算法的性能同時受到問題規(guī)模和數(shù)據(jù)自身特性的影響?？傮w來說，計算時間在企業(yè)可接受的時間范圍內(nèi)，不影響算法的一般實用性。

表3　實驗結(jié)果對比

5　結(jié)論

筆者在電動汽車配送車輛路徑問題的基礎(chǔ)上引入了一個重要概念，即配送貨物的混裝類別。將貨物的組合特性納入考慮范圍并建立了線性規(guī)劃數(shù)學模型，統(tǒng)籌安排車輛的行駛路徑使得物流企業(yè)在運營成本沒有明顯增加的前提下可以降低貨物運輸損失，提高服務(wù)質(zhì)量。此外，還設(shè)計了兩種求解該問題的改進型算法MCWS和MHGA，將算法在文獻[8]的小規(guī)模算例上跟CPLEX 進行比較，取得了較好的結(jié)果。隨后采用多組算例比較兩種模型下的運營成本。實驗結(jié)果表明，考慮混裝貨物類別的模型可以在略微增加配送距離的情況下，避免將不適宜混裝在一個車廂內(nèi)的貨物指派給同一車輛配送，達到降低貨物運輸損失，提高顧客滿意度的目的。最后，將兩種算法在較大規(guī)模算例上進行實驗對比。實驗結(jié)果表明，MCWS 算法對于GVRP問題有著較好的尋優(yōu)能力，而且具有較強的穩(wěn)定性，提升了該問題理論成果的實用性。

但是，筆者研究中沒有考慮電動汽車在途充電問題，且算法效率還有提升空間，如何設(shè)計更加高效的算子將是未來工作的一個重點。

參考文獻：

[1]CHELLASWAMY C，RAMESH R，RAU C V. A supervisory control of a fuel free electric vehicle for green environment[C]∥Emerging Trends in Electrical Engineering and Energy Management(ICETEEEM).Chennai: IEEE，2012:387-393.

哺乳期仔豬出現(xiàn)嘔吐、腹瀉癥狀，隨后排出黃白色粥樣稀便，臥地不起，強迫仔豬站立，仔豬行走時左右搖擺，行走不穩(wěn)，不能正常吃乳，仔細觀察發(fā)病豬四肢內(nèi)側(cè)存在紫色點狀出血，發(fā)病豬腹瀉物中夾雜不完全的白色凝乳塊。隨著病情進一步發(fā)展，腹瀉癥狀嚴重，患病豬身體逐漸消瘦，不能正常行走，行走時左右搖晃，共濟失調(diào)，四肢叉開，口吐白沫，叫聲嘶啞，耳部和腹部皮膚表面發(fā)紅，并出現(xiàn)綠豆大小的藍紫色出血點。多數(shù)患病豬在發(fā)病中后期，排出黃色或黃褐色粥樣稀便，病豬在臨死前表現(xiàn)角弓反張，全身肌肉震顫，出現(xiàn)間歇性痙攣，后期肢體麻痹，呈現(xiàn)犬坐姿勢，有時在圈舍中轉(zhuǎn)圈或者側(cè)臥時四肢劃動呈游泳狀，最后因機體衰竭而死。

[2]王征，胡祥培，王旭坪.帶二維裝箱約束的物流配送車輛路徑問題[J].系統(tǒng)工程理論與實踐，2011，31(12):2328-2341.

[3]王長瓊，戚小振.三維裝載約束下的汽車零部件循環(huán)取貨路徑優(yōu)化研究[J].武漢理工大學學報(交通科學與工程版)，2015，39(6):1161-1165.

[4]YANG J，SUN H. Battery swap station location-routing problem with capacitated electric vehicles[J]. Computers & Operations Research，2015(55):217-232.

[5]揭婉晨，楊珺，楊超.多車型電動汽車車輛路徑問題的分支定價算法研究[J].系統(tǒng)工程理論與實踐，2016，36(7):1795-1805.

[6]王勝,譚家政,劉勇,等.求解TSP問題的改進蟻群算法[J].武漢理工大學學報(信息與管理工程版),2013,35(3):340-344.

[7]張艷偉,周萬,向家偉.基于運輸網(wǎng)絡(luò)的配送路線優(yōu)化模型[J].武漢理工大學學報(信息與管理工程版),2014,36(4):447-451.

[8]BORTFELDT A，HOMBERGER J R. Packing first，routing second：a heuristic for the vehicle routing and loading problem[J]. Computers & Operations Research，2013，40(3):873-885.

[9]ERDOAN S，MILLER H E. A green vehicle routing problem[J]. Transportation Research Part E: Logistics and Transportation Review，2012，48(1):100-114.

[10]AUGERAT P，BELENGUER J M，BENAVENT E，et al. Computational results with a branch and cut code for the capacitated vehicle routing problem[J]. Rapport De Recherche- IMAG，1995(12)：495.

[11]張瑞鋒,汪同三.新型遺傳算法求解車輛路徑問題研究[J].湖北大學學報(自然科學版),2013，42(2):120-123.