考慮差異化服務(wù)時間的多車型電動汽車路徑優(yōu)化與充電策略研究

郭 放，楊 珺，楊 超

(1.鄭州大學(xué)管理工程學(xué)院，河南 鄭州 450001；2.華中科技大學(xué)管理學(xué)院，湖北 武漢 430074)

1 引言

城市內(nèi)小件貨物送貨上門服務(wù)處于物流環(huán)節(jié)的最末端。受到交通、人員以及環(huán)境的影響，市內(nèi)配送環(huán)節(jié)產(chǎn)生的服務(wù)成本占據(jù)物流環(huán)節(jié)總成本的35%-60%[1]。為提高物流配送效率搶占末端配送市場，物流企業(yè)和學(xué)者在服務(wù)模式以及服務(wù)效率等方面進行了諸多嘗試。陳義友等[2]研究了顧客差異化選擇對自提點選址的影響。符卓等[3]研究了顧客需求可依據(jù)訂單拆分情形下的物流車輛路徑問題。此外，配送車輛的多樣性、服務(wù)路徑選擇、人車匹配策略以及服務(wù)時間差異化等因素都會影響物流運營成本。因此，高效的物流配送服務(wù)需要物流專員、配送車輛和顧客三方協(xié)作完成。在熟悉顧客點周邊的環(huán)境的情況下，物流專員能夠快速準(zhǔn)確地找到配送地址與合適的停車點，甚至能夠熟悉顧客點周邊交通狀況從而避開擁堵的路段。物流專員的服務(wù)時間存在差異，由此帶來的經(jīng)濟效益也愈加受到物流企業(yè)的重視。除差異化服務(wù)時間以外，物流專員指派策略還與配送車輛載重量、行駛成本和顧客位置等多種因素相互影響。相對于大型配送車輛，小型配送車輛較低的可變成本使其在路徑選擇方面更加靈活。但是，受到載重量較小的限制，物流企業(yè)需要安排更多數(shù)目的車輛與人員才能夠滿足服務(wù)需求。另一方面，具備較大載重量的車型可以滿足更多顧客點的服務(wù)需求。車輛服務(wù)路徑的增加可能會導(dǎo)致物流配送人員對配送區(qū)域和配送顧客不熟悉，增加了整體服務(wù)時間成本。由此可見，統(tǒng)籌安排物流專員、配送車輛和顧客三者的匹配工作，有助于物流企業(yè)提高人員、物流車輛、服務(wù)時間等資源的利用效率，降低運營成本。

近幾年來，國內(nèi)外學(xué)者分別從車隊規(guī)模、車型選擇和差異化服務(wù)時間等方面拓展了對物流路徑優(yōu)化問題的研究。一部分學(xué)者探討了多車型車輛路徑問題(HVRP)，Golden等[4]研究了考慮車隊規(guī)模與車型選擇的車輛路徑問題，在其研究中多車型通過不同的載重量體現(xiàn)。Liu和Shen[5]基于不同型號車輛的行駛成本不同而載重量相同的假設(shè)，探討了時間窗約束下的HVRP問題。Taillard[6]結(jié)合了禁忌搜索和列生成算法的優(yōu)勢，采用混合算法解決了兼顧可變成本和不同載重量的多車型車輛路徑問題。Salhi等[7]在多車型車輛路徑問題的基礎(chǔ)上進一步探究了載貨返程情形下的服務(wù)策略。另一部分學(xué)者研究了考慮差異化服務(wù)成本的車輛路徑問題(VRP)。差異化服務(wù)相關(guān)研究集中于小件商品的物流配送領(lǐng)域，服務(wù)的差異性通常表現(xiàn)為服務(wù)成本不同。Zhong等[8]采用差異化服務(wù)成本體現(xiàn)物流服務(wù)專員對不同服務(wù)對象的熟悉程度，通過允許跨區(qū)域服務(wù)實現(xiàn)路徑策略的靈活性。Schneider等[9-11]在VRP問題的研究中引入了配送人員個性化服務(wù)時間的概念。服務(wù)時間的差異通過熟悉因子σis體現(xiàn)，熟悉因子表示熟悉服務(wù)對象i的物流專員s(以下簡稱為熟悉專員)相對于對服務(wù)對象完全陌生的物流專員(以下簡稱為陌生專員)可節(jié)約的服務(wù)時間百分比。例如，熟悉因子σis=0.2的時候，熟悉專員的服務(wù)時間降低為陌生專員的80%。Sungur等[12]采用補償隨機規(guī)劃和魯棒優(yōu)化分別對顧客點和服務(wù)時間的不確定性進行研究。Schneide等[13]在時間窗約束下研究服務(wù)時間差異化的車輛路徑問題。上述文獻從不同角度分別研究了考慮多車型或差異化服務(wù)時間的車輛路徑問題，鮮有文獻涉及關(guān)于協(xié)調(diào)物流專員、配送車輛和顧客三方匹配策略的研究。

另一方面，零排放的特點使得電動汽車非常適合城市良性發(fā)展的需求，促使其在城市物流配送行業(yè)中得到關(guān)注與應(yīng)用[14]。國家各部門相繼出臺了一系列政策法規(guī)推進電動物流汽車產(chǎn)業(yè)和配套服務(wù)設(shè)施快速發(fā)展，為電動汽車在物流配送行業(yè)的普及提供了有力保障。電動物流車輛行駛距離受電池容量約束，電量不足時需要前往充電站點通過充電模式補充電量。如何科學(xué)地規(guī)劃電動汽車服務(wù)路徑與充電策略，優(yōu)化電動汽車物流與服務(wù)網(wǎng)絡(luò)成為了近來的研究熱點問題。Erdogan和Miller-Hooks[15]最早提出綠色車輛路徑問題(Green Vehicle Routing Problem，GVRP)，建立起以累計行駛距離最短為優(yōu)化目標(biāo)的混合整數(shù)規(guī)劃模型。Schneider等[16-17]研究了時間窗與允許在途充電的電動汽車路徑優(yōu)化問題，并在文中采用變鄰域搜索和禁忌搜索相結(jié)合的混合啟發(fā)式算法對上述問題進行求解。楊珺等[18]研究電動汽車物流配送網(wǎng)絡(luò)的設(shè)施選址和配送路徑優(yōu)化問題，提出了禁忌搜索和改進節(jié)約算法相結(jié)合的兩階段啟發(fā)式算法。Bruglieri等[19]將電動汽車在服務(wù)站點的充電量作為決策變量，研究了帶時間窗約束且允許在途充電的電動汽車路徑問題。研究結(jié)果發(fā)現(xiàn)在帶時間窗的前提下靈活可變的充電策略能夠以較低的資金投入為顧客提供更加高效率的服務(wù)。

近期，部分學(xué)者將多車型與電動物流汽車車輛路徑問題結(jié)合起來進行研究。揭婉晨等[20]和Penna等[21]研究了含時間窗的多車型電動汽車車輛路徑問題(E-HVRPTW)，其中揭婉晨等[20]運用基于列生成的分支定價算法求解該問題的最優(yōu)解，并提出了兩種加速策略優(yōu)化算法求解效率。Hiermann等[22]根據(jù)不同車型電動汽車的能源消耗和載重量等性能的差異性，將電動物流車隊的車輛數(shù)和車型選擇作為優(yōu)化對象。

本文與已有研究的主要區(qū)別在于考慮了物流專員、配送車輛和服務(wù)對象三方協(xié)調(diào)匹配策略。研究了將上述三方指派與匹配策略作為優(yōu)化對象的多車型電動汽車配送路徑問題。隨后，本文提出了基于改進節(jié)約算法、混合遺傳算法以及禁忌搜索算法的混合啟發(fā)式算法MCWGATS。采用CPLEX求解小規(guī)模算例并將其結(jié)果與MCWGATS算法的計算結(jié)果進行比較，證實了算法的有效性。最后，分析多車型與差異化服務(wù)時間對運營成本的影響。

2 問題描述及數(shù)學(xué)模型

2.1 問題描述

2.2 基礎(chǔ)模型

基于上述條件， 數(shù)學(xué)模型如下：

(1)

(2)

(3)

?h∈V{o,o′},k∈K

(4)

(5)

(6)

(7)

(8)

(9)

(10)

?k∈K,s∈S,i∈V{o′}

(11)

uhk≤ugk-qhxghk+Uk(1-xghk)

?h∈V{o},g∈V{o′},g≠h,k∈K

(12)

uok≤Uk?k∈K

(13)

uhk≥0≤?k∈K,h∈V{o′}

(14)

?h∈V{o},g∈V{o′},g≠h,k∈K

(15)

(16)

(17)

(18)

(19)

(20)

xghk,ysk,zisk∈{0,1} ?h∈V{o},g∈V{o′},k∈K,j∈J,s∈S

(21)

3 啟發(fā)式算法MCWGATS

本節(jié)采用啟發(fā)式算法MCWGATS求解考慮物流專員個性化服務(wù)時間的多車型電動汽車路徑與充電策略問題。MCWGATS主要由改進節(jié)約算法(MCWS)、混合遺傳算法(HGA)和禁忌搜索(TS)組成。

3.1 初始選址

依次將各備選位置作為圓心，標(biāo)記其周圍Qk/2距離內(nèi)的顧客點(此處k為最大行駛距離最短的車型)。將所有備選點根據(jù)其標(biāo)記的顧客數(shù)目按照由高到低的順序排列在集合G中，隨后將集合G的前n個點添加到站點集合S0。

3.2 路徑預(yù)處理

步驟1：為每一個等待服務(wù)的顧客點i生成一條對應(yīng)的線路(o-i-o)，其中o為配送中心。

步驟2：核查路徑(o-i-o)是否滿足最大行駛里程約束。本節(jié)假設(shè)車輛離開配送中心時電池狀態(tài)為滿電量Qk，doi+dio≤Qk表示此路徑符合行駛里程約束，可移入可行路徑集合FR。反之則移入不可行路徑集合IR。

本文設(shè)定預(yù)處理階段為一位顧客提供服務(wù)的車輛最多可在往返途中各充電一次。在執(zhí)行上述步驟1-4后依舊存在不符合行駛里程約束的路徑，則視為選址方案存在不可行路線。

3.3 服務(wù)路徑優(yōu)化

首先對本節(jié)涉及的概念進行介紹：

(c)路徑節(jié)約值：找出可行線路中與o點相連的毗鄰點，計算任意連接不同路徑上兩個毗鄰點的savekk′值。假設(shè)點i和j分別是路徑r1和r2上與o點相連的毗鄰點。r1、r2和r3的路徑長度分別為s1、s2和s3。其中,r3是r1和r2連接后產(chǎn)生的新路徑，S3=S1+S2-doj-doi+dij。計算路徑r1、r2和r3的顧客需求量，滿足相應(yīng)載重需求的最小車輛行駛成本系數(shù)記為w1、w2和w3。將毗鄰點以成對的形式按照節(jié)約值savekk′降序排列放入節(jié)省對列表SPL中，save12=w1*S1+w2*S2-w3*S3。將SPL中小于0 的savekk′值和與之對應(yīng)的毗鄰點刪除。

(d)合并收益：路徑ra和rb連接成為新路徑rc的合并收益為Ararb。合并收益包括路徑熟悉度損失grarb，里程節(jié)約值saverarb和斷點懲罰值erarb。

Ararb=β1saverarb-β2tigrarb-β3erarbra,rb∈R

(22)

其中，

β1+β2+β3=1,β1,β2,β3≥0

(23)

grarb

(24)

(25)

步驟1：查找當(dāng)前所有可行線路中與配送中心o相連的點(毗鄰點)，計算不同路徑上兩個毗鄰點對應(yīng)的合并收益。將毗鄰點以成對的形式按照合并收益降序排列存入節(jié)省對列表SPL。將SPL中小于0 的合并收益和對應(yīng)的毗鄰點刪除。

步驟2：將SPL節(jié)省對按照合并收益降序順序執(zhí)行線路合并。合并方法如下：刪除毗鄰點與o點之間的連接線，隨后將兩個毗鄰點直接相連。

步驟3：檢查合并路徑是否滿足里程約束與載重量約束。如果不滿足載重量約束則放棄此次合并，繼續(xù)對SPL中下一組進行合并。如果合并后的路徑不滿足里程約束，則在兩個毗鄰點之間加入一個繞行成本最低的充電站。如果路線仍不可行則放棄此次線路合并，繼續(xù)對SPL中下一組進行合并。

步驟4：將SPL中所有毗鄰點對合并之后，識別合并后的線路中多余的充電站點并刪除。

步驟5：返回本環(huán)節(jié)步驟1進入新一輪線路合并，直到任意兩條可行線路都不能進一步合并。

3.4 物流專員指派子問題

求得服務(wù)路徑策略后調(diào)用改進混合遺傳算法為其指派物流專員使服務(wù)時間成本最低。本節(jié)使用物流專員自身排列的編碼方法來確定配送路徑策略。直接生成N個1～N間不重復(fù)的整數(shù)的排列，每個自然數(shù)表示一個物流專員個體。根據(jù)排列中數(shù)字的順序，依次指派給配送路徑集合中的路徑。當(dāng)路徑集合中的配送路徑數(shù)多于可使用的物流專員數(shù)目的時候，認(rèn)定該個體對應(yīng)解為不可行解。在群體初始化過程中，采用隨機生成的方式產(chǎn)生M個不同個體，每個個體包含N個1～N間不重復(fù)的整數(shù)的排列。適應(yīng)度公式F=1/(Z+MP)，Z為目標(biāo)函數(shù)值，M表示該配送方案中缺少物流專員的數(shù)目，P表示對缺少物流專員的懲罰權(quán)重。為了控制算法的收斂速率確保其不過早陷入局部最優(yōu)解，本節(jié)將每代群體中適應(yīng)度最高的個體復(fù)制后存入下一子代第一行，其余個體根據(jù)適應(yīng)度大小在輪盤賭機制下以一定概率進入下一代。進化代數(shù)達(dá)到指定值則終止。

3.5 局部搜索

本節(jié)采用局部搜索中的點移動、點交換以及點插入策略進一步優(yōu)化當(dāng)前解。

(1)點移動：將點i從當(dāng)前位置移動到同路徑的其他位置。

(2)點交換：從兩條路徑分別選取一個點加入到對方路徑，交換點在新路徑中的位置為該點插入后距離增量最小處。

(3)點插入：以路徑1中的顧客點i為例，在路徑2中找出距離i點最近的兩個點a和b。將i點移動到路徑2中a點和b點之間的位置，并將原路徑2中a、b兩點間各點依次移動到b點之后。

3.6 禁忌搜索

步驟1：初始化站點集合，計算目標(biāo)函數(shù)值并賦給當(dāng)前解和滿意解，置空禁忌表。

步驟2：在已建成的充電站點集合中隨機選擇一個點并刪除此處的充電站點。隨后，在沒有建站的備選點中隨機開設(shè)一個充電站點。在新的鄰域生成后再次求解，將產(chǎn)生的新解存入候選解集中。

步驟3：如果當(dāng)前解的最小值優(yōu)于滿意解，則認(rèn)為此候選解滿足特赦準(zhǔn)則，更新滿意解與其目標(biāo)函數(shù)值。否則，在未被禁忌的候選解中選擇成本最小的解作為當(dāng)前解。同時用與它對應(yīng)的禁忌對象替代最早進入禁忌列表的禁忌對象。

重復(fù)執(zhí)行步驟2-3直到迭代次數(shù)達(dá)到預(yù)定最大次數(shù)，執(zhí)行步驟4。

步驟4：如果站點數(shù)達(dá)到最大值或者增加ψ次后滿意解仍沒有改進則停止。否則，充電站點數(shù)目加1，返回步驟1開始下一輪搜索。

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

本節(jié)通過多組算例驗證MCWGATS的尋優(yōu)能力并分析車型和服務(wù)時間等參數(shù)對運營策略的影響。實驗的計算機參數(shù)配置為Intel(R) I5-4460，3.20GHz，8GB RAM。算法在JAVA 中實現(xiàn)為單線程代碼。

4.1 測試用例

到目前為止，已發(fā)表文獻中沒有專門用于分析物流專員差異性服務(wù)時間的實驗算例。本文采用Augerat等[23]、Rinaldi和Yarrow[24]及Taillard[25]使用的三種被廣泛應(yīng)用于VRP研究的算例作為實驗數(shù)據(jù)，相關(guān)數(shù)據(jù)可以從網(wǎng)站http://neo.lcc.uma.es/vrp/vrp-instances/獲取。熟悉因子是求解DSTHEVRP問題的重要參數(shù)，其最大值介于0.4到0.5之間[9]。本文算例中熟悉因子最大值取0.4，物流專員s為顧客點i服務(wù)所需時間tis=(1-σis)qiti。根據(jù)物流專員對于其服務(wù)對象的熟悉程度，熟悉因子σis在[0,0.4]范圍內(nèi)取值。在物流專員對服務(wù)對象完全不熟悉的情況下σis=0。通過實地調(diào)研與數(shù)據(jù)采集可知物流專員每天工作時間約10小時，人均派件100-150件，單件配送收益0.6到3元不等。由此估算出派送一件貨物平均需要4-6分鐘，本節(jié)折中選擇ti=5，η=0.5。算例中使用A、B、C 三種車型，B車型滿電量狀態(tài)下最大行駛距離為當(dāng)前網(wǎng)絡(luò)中兩點間歐幾里得距離最大值的ω倍(|I|≤20時，ω=1.2。否則ω=1.3)，B車型其余參數(shù)取值與上述網(wǎng)站對應(yīng)算例相同。A、C車型的載重與可變成本分別B車型的0.9和1.1倍，A、C車型的滿電量最大行駛距離分別B車型的0.8和1.2倍。Sce.1-3分別使用A、B和C車型。算法參數(shù)設(shè)置如表1所示。

表1 MCWGATS參數(shù)設(shè)置

4.2 算例分析

4.2.1 算法驗證

本節(jié)使用IBM CPLEX求解小規(guī)模算例并將其結(jié)果與MCWGATS算法的計算結(jié)果進行比較。為了保證實驗的一般性，實驗數(shù)據(jù)來源于Augerat[23]及Rinaldi和Yarrow[24]提出的算例，且只選用原文算例的最后n個顧客點?？紤]到實際使用效果，設(shè)定CPLEX的運行時間上限為3小時(10800s)。“*”為CPLEX運行3小時得到的滿意解，“#”表示CPLEX沒有找到可行解。實驗結(jié)果如表2所示，第11列是算法滿意解與CPLEX最優(yōu)解的相對差值(Gap)：(算法滿意解-CPLEX最優(yōu)解)/CPLEX最優(yōu)解。通過表2可以看出在CPLEX能夠在限定時間內(nèi)找到最優(yōu)解的情況下(P-n6，P-n7，P-n8)，MCWGATS算法與CPLEX計算結(jié)果非常接近并且啟發(fā)式算法的求解效率較更高。隨著算例規(guī)模增大，MCWGATS尋優(yōu)能力與計算效率的優(yōu)勢更加明顯。當(dāng)顧客數(shù)達(dá)到15時(RY-n15)，CPLEX在3小時內(nèi)不能找到可行解，而算法在5秒內(nèi)得到滿意解。實驗結(jié)果表明MCWGATS求解此問題的效果好于CPLEX，驗證了本文提出的算法的有效性。

表2 CPLEX與MCWGATS實驗結(jié)果對比

4.2.2 差異化服務(wù)時間對運營成本的影響性分析

不同于傳統(tǒng)車輛路徑問題，本文考慮了物流專員、配送車輛和服務(wù)對象三方協(xié)調(diào)匹配策略，幫助物流企業(yè)提高人員、物流車輛、服務(wù)時間等資源的利用效率，降低運營成本。本節(jié)通過設(shè)置對照實驗組，在輸入?yún)?shù)完全一致的情況下，將對照組實驗結(jié)果與本文所述協(xié)調(diào)匹配策略進行對比分析。本文從Taillard[25]算例中選取6組實例，各組實例包含的顧客點由75到150不等。對照組采用分階段優(yōu)化策略，第一階段在不考慮時間成本的前提下采用改進節(jié)約算法與禁忌搜索完成站點選址與車輛服務(wù)路徑策略。第二階段將上一階段的最優(yōu)解作為輸入?yún)?shù)，采用混合遺傳算法完成物流專員指派策略。分階段優(yōu)化策略與MCWGATS的主要區(qū)別在于前者僅能在路徑成本最低的策略下進行物流專員指派優(yōu)化，無法統(tǒng)籌兼顧三方協(xié)調(diào)匹配策略。表3-5分別展示了Sce1-3情形下MCWGATS和分階段優(yōu)化策略的滿意解、距離成本、時間成本、建站數(shù)、求解時間以及時間成本相對差值Gap，其中GapX=(時間成本X-時間成本)/時間成本。以表3為例，受益于MCWGATS提供的協(xié)調(diào)匹配策略Sce.1的時間成本相對較低，Gap 1的平均值達(dá)到-3.49%。雖然Sce.1對照組的距離成本略低于Sce.1，Sce.1的總運營成本(滿意解)在6組實例中均比對照組更低，表4-5情況與表3類似。此外，服務(wù)策略會因目標(biāo)權(quán)重的調(diào)整產(chǎn)生相應(yīng)變化。本節(jié)以時間成本為例，分析其權(quán)重變化對于路徑選擇策略的影響。實驗結(jié)果如圖1所示，其中Tw=0.5與Tw=1.0分別表示時間成本權(quán)重為0.5和1.0情形下的距離成本與時間成本權(quán)重為0情形下距離成本的相對差值Gap。由圖1可知，所有算例的距離成本Gap均為正數(shù)且Tw=1.0對應(yīng)結(jié)果高于Tw=0.5。實驗結(jié)果可由如下現(xiàn)象解釋：在制定路徑策略時，為達(dá)到總成本最低的目的，時常需要選擇非最短的路徑來謀求更低的時間成本。因此圖1實驗結(jié)果均為正數(shù)。此外，時間成本權(quán)重越高，可接受的繞行距離越長，圖1中表現(xiàn)為Tw=1.0折線在Tw=0.5折線之上。

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

表4 Sce2實驗結(jié)果對比

表5 Sce3實驗結(jié)果對比

圖1 時間成本權(quán)重對比

4.2.3 物流專員的選擇對時間成本的影響性分析

本節(jié)從兩個方面分析了物流專員自身特性對時間成本的影響。Sce1-3情形下物流專員對顧客的熟悉因子為[0，0.4]范圍內(nèi)事先生成的隨機數(shù)。Sce1-3對照組中物流專員對顧客的熟悉因子為在集合{0，0.4}內(nèi)事先隨機選擇的數(shù)值，對照組中物流專員對顧客的熟悉程度只有兩種情況(非常熟悉和完全不熟悉)。實驗結(jié)果如表6所示，其中GapX=(SceX對照組-SceX)/SceX。Gap值為負(fù)數(shù)表示對照組的時間成本更低，其中3組出現(xiàn)在Sce1，1組出現(xiàn)在Sce2。上述現(xiàn)象的原因在于Sce.1采用的車型載重量較小且物流專員平均服務(wù)的顧客數(shù)最少，而同一路徑中服務(wù)顧客越多服務(wù)時間與效率越難以得到保障。整體來看，即便是平均服務(wù)顧客數(shù)最少的Sce.1，對照組的服務(wù)時間成本也處于不利位置。為兼顧服務(wù)質(zhì)量與運營成本，只有在安排較小車型為少數(shù)顧客提供服務(wù)時，使用對照組類型的物流專員更加有利。一般情形下，對不同區(qū)域熟悉程度相差較小的物流專員較為適合服務(wù)區(qū)域廣、顧客數(shù)量多的配送任務(wù)。圖2-3展示了Sce.1和Sce.3情形下熟悉因子取值范圍對時間成本的影響。對于不同車型，提升物流專員的熟悉因子上限均有助于降低時間成本。值得注意的是Sce.1在不同熟悉因子上限條件下時間成本差異大于Sce.3，在平均服務(wù)顧客數(shù)較少的情形下時間成本對熟悉因子上限的變化更加敏感。物流企業(yè)為少數(shù)顧客提供服務(wù)計劃的時候，安排熟悉度上限較高的物流專員能節(jié)約更多的時間成本。而在服務(wù)顧客數(shù)量較多的情形下，熟悉度上限較高的物流專員相對于熟悉度上限較低者的時間成本優(yōu)勢會在一定程度上被拉近。

表6 時間成本實驗結(jié)果對比

圖2 Sce.1時間成本對比

圖3 Sce.3時間成本對比

4.2.4 多車型的影響性分析

本節(jié)從Augerat[23]和Taillard[25]采用的算例中共選取11組實例(顧客點數(shù)目為20-150)，通過改變可用車輛的限制型號研究車型選擇對運營成本的影響。Sce.0情形下可用車型包含A、B、C三種，而Sce.1-3只能分別使用A、B和C車型。表7的第2列表示實例包含的顧客數(shù)，第3-4列為Sce.0情形下MCWGATS求得的滿意解和求解時間。第5-10列展示Sce.X情形下MCWGATS的滿意解X以及Gap X，其中GapX=(滿意解X-滿意解0)/滿意解0。實驗結(jié)果顯示有三種車型可供使用的情形下運營總成本低于其余只能選用單一車型的情形，Sce.0以更加低廉的總運營成本完成配送任務(wù)，體現(xiàn)出多車型策略下的成本優(yōu)勢。在使用單一車型的情況下Sce.1的平均Gap最低，分別為1.23%和1.04%。受到載重量較小的約束Sce.1情形下各車輛(或物流專員)平均服務(wù)顧客數(shù)最少，物流專員可以專注服務(wù)熟悉度更高的顧客而降低因地點相鄰等原因“順路”服務(wù)熟悉度不高顧客的概率。另一方面，具備最大載重量的C車型受到時間成本和可變成本的影響，Sce.3的平均Gap最高，分別為2.80%和3.40%。

4.2.5 差異化服務(wù)時間與車型策略對時間成本的影響

本節(jié)在考慮差異化服務(wù)時間的情形下，采取隨機指派策略、分階段優(yōu)化策略與本文提出的MCWGATS算法策略的時間成本進行比較，隨后分析多車型策略在差異化服務(wù)時間下對時間成本的影響。從Taillard[25]采用的算例中選取8組對其服務(wù)時間成本進行分析。圖4隨機組表示隨機指派物流專員情形下的時間成本，對照組表示分階段優(yōu)化策略對應(yīng)的時間成本。隨機指派策略產(chǎn)生的服務(wù)時間成本在8個算例中均高于其余兩種策略。Sce.0與Sce.0隨機組的時間成本平均差異接近30%，最高達(dá)到38.2%(tai100c)。Sce.0與Sce.0對照組的時間成本平均差異為6.1%。實驗結(jié)果表明相對于僅考慮多車型的服務(wù)路徑問題(隨機組)和分階段優(yōu)化策略(對照組)，協(xié)調(diào)與兼顧服務(wù)員人、服務(wù)車型和服務(wù)對象三者匹配的HVRP問題更有利于降低成本提高企業(yè)利潤。

表7 車型實驗結(jié)果對比

圖4 多車型時間成本對比

5 結(jié)語

順應(yīng)電動汽車在物流配送行業(yè)發(fā)展趨勢，考慮差異化服務(wù)時間的多車型電動物流車輛路徑問題是一個應(yīng)用前景廣泛的現(xiàn)實問題。電動汽車參與的物流配送服務(wù)需要物流專員、電動汽車和顧客三方協(xié)作的完成。兼顧服務(wù)人員指派、車型選擇和服務(wù)對象選擇三者的匹配問題有助于提升資源利用率提高企業(yè)收益。本文提出了考慮差異化服務(wù)成本的多車型電動汽車路徑優(yōu)化與充電策略問題，并建立了該問題的整數(shù)規(guī)劃數(shù)學(xué)模型。為求得模型的滿意解，本文采用了基于改進節(jié)約算法、遺傳算法與禁忌算法結(jié)合的混合啟發(fā)式算法MCWGATS，通過多組中小規(guī)模算例驗證了算法的有效性。最后，分析了多車型類型和差異化服務(wù)時間對運營成本的影響。實驗結(jié)果表明，該模型可以幫助物流企業(yè)高效率地降低行駛成本節(jié)約服務(wù)時間進而到達(dá)降低運營成本的目的，為物流企業(yè)提供良好借鑒與幫助。以下方面還有待進一步研究，在未來的研究中可以進一步分析不同車型電池充電率，電池單位消耗率與固定成本在內(nèi)的更多因素；其次，為保障物流服務(wù)的時效性，硬時間窗因素將作為重要參數(shù)納入后續(xù)研究中；最后，設(shè)計更加高效的算法策略將是未來工作的一個重點。