郭 放，黃宏軍，楊 珺

考慮顧客取貨半徑的電動(dòng)汽車路徑優(yōu)化與服務(wù)策略研究

郭 放，黃宏軍，楊 珺

（華中科技大學(xué)管理學(xué)院，湖北 武漢 430074）

在環(huán)境意識(shí)增長(zhǎng)與政府政策支持的有利條件下，電動(dòng)汽車在物流行業(yè)得到良好的發(fā)展機(jī)遇。有電動(dòng)汽車參與的物流服務(wù)需要配送人員、電動(dòng)汽車和顧客在預(yù)定服務(wù)策略下共同完成。為提高物流服務(wù)的效率與質(zhì)量，物流企業(yè)采取顧客自行取貨與配送人員送貨上門相結(jié)合的服務(wù)策略，在提高物流企業(yè)配送人員與車輛服務(wù)效率的同時(shí)，實(shí)現(xiàn)部分顧客對(duì)收貨時(shí)間的個(gè)性化要求、減少不確定因素對(duì)后續(xù)配送服務(wù)造成不良影響的幾率、提高服務(wù)水平。本文提出了以電動(dòng)汽車作為物流配送車輛的考慮顧客自行取貨策略的服務(wù)站點(diǎn)選址與車輛路徑問題，并構(gòu)建了整數(shù)規(guī)劃數(shù)學(xué)模型。其次，給出了基于改進(jìn)節(jié)約算法和禁忌算法的混合啟發(fā)式算法MCWSA-TS。隨后通過多組中、小規(guī)模算例驗(yàn)證了算法的有效性。最后，采用多組算例分析了覆蓋策略與覆蓋半徑對(duì)運(yùn)營(yíng)成本的影響。實(shí)驗(yàn)結(jié)果表明，考慮顧客取貨半徑的多樣化服務(wù)策略可以減少物流企業(yè)對(duì)配送人員與物流車輛的需求，縮短配送距離，進(jìn)而降低運(yùn)營(yíng)成本。

電動(dòng)汽車；選址-路徑問題；混合啟發(fā)式算法；多樣化服務(wù)策略；半徑覆蓋問題

0 引言

在環(huán)境意識(shí)增長(zhǎng)與政府政策支持的有利條件下，電動(dòng)汽車在物流行業(yè)得到良好的發(fā)展機(jī)遇。城市內(nèi)小件物流配送服務(wù)處于物流環(huán)節(jié)的末端，通常是由配送人員將快件從區(qū)域配送中心送達(dá)顧客處。由于顧客分散、市內(nèi)交通情況復(fù)雜以及服務(wù)過程存在的諸多不確定因素影響，服務(wù)過程產(chǎn)生的成本以及占用的服務(wù)資源占到整個(gè)物流環(huán)節(jié)的35%-60%[1]。其中，配送人員與車輛數(shù)目、服務(wù)路徑選擇、物流服務(wù)時(shí)間以及顧客簽收效率等因素都會(huì)影響企業(yè)物流成本與顧客滿意度水平。收貨地點(diǎn)周邊交通狀況與停車條件為物流服務(wù)時(shí)間增添了不確定因素，難以預(yù)測(cè)且不可控的顧客收貨效率也會(huì)阻礙配送計(jì)劃的順利執(zhí)行。除上述不確定因素以外，物流服務(wù)水平還與可使用車輛數(shù)目、服務(wù)路徑設(shè)計(jì)等相互影響?？s短車輛配送路徑，減少待服務(wù)節(jié)點(diǎn)（顧客點(diǎn)）有助于提高服務(wù)質(zhì)量，減少顧客點(diǎn)之間相互影響的機(jī)會(huì)。但是，物流車輛的車載容量沒有得到充分利用，可能導(dǎo)致車輛與人員成本的顯著提升。另一方面，物流企業(yè)希望充分利用車輛載重量，使其在一條配送路徑中服務(wù)更多顧客點(diǎn)。一旦在某一顧客點(diǎn)處產(chǎn)生延誤，路徑中后續(xù)顧客的配送時(shí)間均會(huì)受到影響，從而影響到整體服務(wù)水平。由此可見，高效的物流配送服務(wù)需要配送人員和顧客在預(yù)定服務(wù)策略下協(xié)作完成。因此，物流企業(yè)希望在提高物流企業(yè)配送人員與車輛服務(wù)效率的同時(shí)，實(shí)現(xiàn)部分顧客對(duì)收貨時(shí)間的個(gè)性化要求、減少不確定因素對(duì)后續(xù)配送服務(wù)造成不良影響的幾率、提高服務(wù)水平。為實(shí)現(xiàn)這一目的，部分物流企業(yè)采用了在顧客密集區(qū)域開設(shè)顧客自行取貨服務(wù)站點(diǎn)的服務(wù)模式。位于站點(diǎn)服務(wù)區(qū)域內(nèi)的顧客可自行前往服務(wù)站點(diǎn)取回貨物，而對(duì)于位于站點(diǎn)服務(wù)半徑之外的顧客則由物流車輛直接將其所需貨物送至顧客處。例如，阿里巴巴旗下大型物流服務(wù)平臺(tái)菜鳥驛站已經(jīng)開設(shè)了超過40000個(gè)物流服務(wù)站點(diǎn)為在淘寶和天貓（阿里巴巴旗下網(wǎng)上購(gòu)物平臺(tái)）網(wǎng)購(gòu)商品的顧客提供包裹免費(fèi)保管服務(wù)。目前，菜鳥驛站服務(wù)站點(diǎn)主要包括校園菜鳥驛站、社區(qū)便利店、物業(yè)、連鎖超市、郵局報(bào)刊亭等。此外，京東也采取了類似策略開設(shè)京東派服務(wù)點(diǎn)。目前，京東派主要集中在全國(guó)范圍內(nèi)本科院校和?？圃盒?。顧客自行取貨服務(wù)模式的整體成本不僅取決于配送成本、服務(wù)站點(diǎn)成本，還與顧客節(jié)點(diǎn)、站點(diǎn)備選位置的空間分布情況相關(guān)。尤其在本文采用電動(dòng)汽車作為物流車輛的情形下，電量不足時(shí)物流車輛需前往服務(wù)站點(diǎn)充電或更換電池，服務(wù)站點(diǎn)選址直接影響配送路徑策略。

本文基于站點(diǎn)的覆蓋思想與顧客自行取貨策略，研究了在顧客自行取貨與送貨上門相結(jié)合的多樣化服務(wù)策略下的電動(dòng)汽車服務(wù)設(shè)施選址與服務(wù)路徑優(yōu)化問題(Cover-EV-LRP)。Cover-EV-LRP由Dantzig等[2]提出車輛路徑問題(VRP)延伸而來，VRP問題研究?jī)?nèi)容為指派位于起點(diǎn)的車隊(duì)為所有顧客點(diǎn)提供服務(wù)，使得目標(biāo)函數(shù)(例如配送距離、配送時(shí)間或其他成本)最小。帶有容量約束的車輛路徑問題CVRP要求所有車輛從起點(diǎn)出發(fā)完成服務(wù)任務(wù)后回到出發(fā)點(diǎn)，且車輛配送貨物總量不得超過其最大載重量。 Baldacci等[3]分別在單一起點(diǎn)和多起點(diǎn)情形下采用精確算法研究了帶容量限制的多車型車輛路徑問題。Rivera J C，Afsar H M 等[4]研究了允許車輛帶有累積載重量限制的VRP問題，并針對(duì)該問題提出了基于迭代鄰域搜索的啟發(fā)式算法。Jin J，Crainic T G等[5]提出了一種改進(jìn)合作并行的啟發(fā)式算法求解帶有容量約束的VRP問題。上述研究均要求路徑網(wǎng)絡(luò)節(jié)點(diǎn)不能被同一車輛多次訪問。然而，在現(xiàn)實(shí)生活中廣泛存在如下情況：一輛配送車輛在服務(wù)若干顧客后再次前往之前去過的服務(wù)站點(diǎn)補(bǔ)充電量。允許服務(wù)站點(diǎn)為同一配送車輛提供多次充電服務(wù)有助于降低站點(diǎn)開設(shè)成本與車輛行駛成本。本文在1.3節(jié)拓展模型中考慮了同一車輛多次到訪同一站點(diǎn)的情況，并對(duì)模型進(jìn)行了相關(guān)改進(jìn)。隨著VRP 相關(guān)問題的拓展研究逐步深入，由于時(shí)間、成本或其他資源(例如車輛數(shù)量或里程等)限制，車輛無(wú)法或者沒有必要到達(dá)每個(gè)網(wǎng)絡(luò)節(jié)點(diǎn)的情形引發(fā)了部分學(xué)者的關(guān)注與探究。Current等[6]首次在旅行商問題(TSP) 中加入了“覆蓋(Cover)”這一概念，未被車輛直接訪問的顧客節(jié)點(diǎn)的需求由車輛送達(dá)覆蓋其的服務(wù)點(diǎn)，顧客需自行前往服務(wù)點(diǎn)取貨。至此，該問題由TSP拓展為CSP問題。CSP問題致力于構(gòu)建一條盡可能短的哈密頓回路為顧客提供服務(wù)，要求未在回路上的顧客與至少一個(gè)在回路上的顧客的距離小于事先給定的覆蓋半徑(顧客自行取貨半徑)。Salari，Naji-Azimi等[7]提出基于鄰域搜索的啟發(fā)式算法求解CSP問題。Hachicha等[8]將“Cover”引入VRP問題(Cover-VRP)，指派多組車輛分別構(gòu)造哈密頓回路為顧客提供服務(wù)。Ha M H，Bostel N等[9]采用一種精確算法(分支切割算法)求解Cover-VRP問題。上述文獻(xiàn)提出的模型均建立在所有顧客點(diǎn)的需求量必須為1的基礎(chǔ)上，不能體現(xiàn)出實(shí)際操作中顧客點(diǎn)的差異化需求。也沒有考慮車輛最大載重容量限制，而是退而求其次約束每條線路最大顧客數(shù)量。此外，上述文獻(xiàn)均沒有涉及到車輛在途補(bǔ)充能源等問題（加油或充換電池）。本文構(gòu)建的數(shù)學(xué)模型允許車輛在服務(wù)過程中根據(jù)電量需求前往站點(diǎn)補(bǔ)充電量。模型考慮了車輛容量約束，顧客需求量為不小于1的整數(shù)，且每條線路的顧客需求量不超過車輛最大載重量。

與此同時(shí)，電動(dòng)汽車具有的清潔環(huán)保等特點(diǎn)促使其在城市物流配送領(lǐng)域日益受到重視，并得到越來越多的推廣與應(yīng)用[9]。各級(jí)政府部門相繼出臺(tái)多項(xiàng)促進(jìn)電動(dòng)物流汽車及其相關(guān)產(chǎn)業(yè)快速發(fā)展的政策與建議，為電動(dòng)物流汽車市場(chǎng)的拓展與相關(guān)服務(wù)設(shè)施網(wǎng)絡(luò)的完善提供保障。與傳統(tǒng)燃油汽車不同，電動(dòng)物流汽車依靠車載電池為其提供動(dòng)力，車輛需在電量耗盡之前前往電動(dòng)汽車服務(wù)設(shè)施為電池充電或者更換電池。兼顧電動(dòng)物流車輛的充、換電需求與顧客的配送需求，統(tǒng)籌規(guī)劃服務(wù)設(shè)施選址與配送路徑策略有助于提高物流服務(wù)效率降低成本，該問題也成為了近年來業(yè)界與學(xué)術(shù)界的研究熱點(diǎn)。Erdogan 等[11]首先提出綠色VRP的概念(Green Vehicle Routing Problem，GVRP)，建立起以車輛行駛距離成本最小為目標(biāo)函數(shù)的數(shù)學(xué)模型，隨后提出一種改進(jìn)C-W節(jié)約算法探索此問題的滿意解。Schneider等[12][13]在其研究中對(duì)電動(dòng)汽車中途停站充電問題的模型及其求解方法進(jìn)行了探討，并基于禁忌搜索與變鄰域搜索提出了一種求解此類問題的高效率混合啟發(fā)式算法。Yang Jun 和 Sun Hao[14]研究了在采用更換電池模式的情形下電動(dòng)物流汽車服務(wù)設(shè)施網(wǎng)絡(luò)和車輛路徑優(yōu)化策略，隨后，采用基于禁忌搜索和大鄰域搜索的多階段混合啟發(fā)式算法對(duì)問題進(jìn)行了求解。Keskin M 和 Catay B[15]研究了允許部分充電的電動(dòng)汽車服務(wù)策略，車輛接受充電服務(wù)的時(shí)候可以根據(jù)實(shí)際需求來決定充電量與充電時(shí)間。Koc C等[16]將使用車輛數(shù)目作為優(yōu)化對(duì)象之一。在車輛不受最大行駛里程約束的假設(shè)條件下，通過優(yōu)化倉(cāng)庫(kù)選址和車輛路徑策略降低企業(yè)資金投入。揭婉晨等[17]研究了多車型電動(dòng)汽車車輛路徑問題，并利用精確算法（分支定價(jià)算法）尋求問題最優(yōu)解。以上文獻(xiàn)可以看出，目前關(guān)于電動(dòng)汽車車輛路徑與設(shè)施選址問題的研究中尚未考慮覆蓋策略，服務(wù)形式均為單一的送貨上門。因此，本文將站點(diǎn)的覆蓋思想應(yīng)用于電動(dòng)物流車輛選址與路徑問題。研究了顧客自行取貨與送貨上門相結(jié)合的多樣化服務(wù)策略下，將服務(wù)站點(diǎn)選址、配送路徑設(shè)計(jì)與顧客服務(wù)策略選擇作為優(yōu)化對(duì)象的電動(dòng)汽車配送路徑問題。同一車輛在配送途中允許多次前往同一站點(diǎn)接受充電服務(wù)。開設(shè)的服務(wù)站點(diǎn)同時(shí)具備為車輛充電和暫存貨物供顧客自行取貨的功能，其覆蓋范圍內(nèi)的顧客需求均通過車輛送達(dá)此處由顧客自行取貨。未處于任何站點(diǎn)服務(wù)范圍內(nèi)的顧客由車輛送貨上門。本文首先提出了Cover-EV-LRP模型，其由CVRP拓展而來，屬于NP-hard問題。其次，基于改進(jìn)節(jié)約算法以及禁忌搜索算法提出了一種名為MCWSA-TS的混合啟發(fā)式算法用于模型求解。隨后，將MCWSA-TS與CPLEX的計(jì)算結(jié)果進(jìn)行對(duì)比，證實(shí)模型的準(zhǔn)確性與算法的有效性。最后，對(duì)覆蓋策略與相關(guān)參數(shù)對(duì)運(yùn)營(yíng)成本的影響進(jìn)行了探討。

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

1.1 問題描述

1.2 基礎(chǔ)模型

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

S.T.

1.3 拓展模型

s.t.：(2)-(7)，(11)-(25)

1.4 拓展模型線性化

引理 1.

s.t.：(2)-(7),(11)-(25),(27)

2 算法實(shí)現(xiàn)

2.1 初始選址

步驟2.2：計(jì)算服務(wù)站點(diǎn)覆蓋的顧客點(diǎn)需求量總和并將其作為該站點(diǎn)的需備貨量。

步驟2.3：更新顧客點(diǎn)集合，包括已開設(shè)的服務(wù)站點(diǎn)和未被任何服務(wù)站點(diǎn)覆蓋的顧客點(diǎn)。

2.2 路徑子問題

步驟1：（路徑初始化）

2.3 優(yōu)化當(dāng)前解

步驟1(GA)：對(duì)于配送途中物流車輛前往充電站點(diǎn)次數(shù)不少于兩次的服務(wù)線路，采用貪婪策略將其中一個(gè)站點(diǎn)移除，若在當(dāng)前路徑上行駛的物流車輛滿足最大里程限制則更新當(dāng)前路徑。否則，保持原路徑策略。

步驟2(LS)：采用點(diǎn)移動(dòng)，點(diǎn)交換，點(diǎn)插入和局部交換策略進(jìn)行局部搜索。

每次操作均要求滿足車輛載重量和行駛里程約束。比較優(yōu)化前后的目標(biāo)函數(shù)解，并在滿足條件時(shí)更新滿意解與相應(yīng)的目標(biāo)函數(shù)值。4種搜索策略如下文所述。

（1）點(diǎn)移動(dòng)策略的優(yōu)化對(duì)象為任意一條服務(wù)路徑。將路徑中的每一個(gè)點(diǎn)從當(dāng)前位置移動(dòng)到同一路徑中的其他位置。

（2）點(diǎn)交換策略的優(yōu)化對(duì)象為任意一對(duì)服務(wù)路徑。從兩條路徑中分別選取一個(gè)點(diǎn)將其放入另一條配送路徑中，交換點(diǎn)在新路徑中的服務(wù)順序?yàn)槭沟眯旭偩嚯x增加量最小的服務(wù)順序。

2.4 禁忌搜索

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

3 實(shí)驗(yàn)結(jié)果及分析

3.1 測(cè)試用例

3.2 實(shí)驗(yàn)結(jié)果與分析

3.2.1模型與算法的驗(yàn)證分析

表1 CPLEX與MCWSA-TS結(jié)果對(duì)比

3.2.2 多樣化服務(wù)策略影響性分析

表2 多樣化服務(wù)策略實(shí)驗(yàn)結(jié)果對(duì)比

圖1 路徑成本對(duì)比

Figure 1 Comparison of path cost

圖2 配送所需車輛數(shù)對(duì)比

Figure 2 Comparison of vehicle amount required for distribution

3.2.3 服務(wù)半徑敏感性分析

表3 服務(wù)半徑敏感性實(shí)驗(yàn)結(jié)果對(duì)比

表4 服務(wù)半徑敏感性實(shí)驗(yàn)結(jié)果對(duì)比2

圖3 配送線路示意圖

圖4 配送線路示意圖

4 結(jié)束語(yǔ)

近年來，電動(dòng)汽車在物流行業(yè)得到良好的發(fā)展機(jī)遇。以電動(dòng)汽車作為物流配送車輛的考慮顧客自行取貨服務(wù)模式的站點(diǎn)選址與車輛路徑問題是一個(gè)應(yīng)用前景廣泛的現(xiàn)實(shí)問題。電動(dòng)汽車參與的物流配送服務(wù)需要配送人員、配送車輛和顧客在預(yù)定服務(wù)策略下共同完成。尤其在本文采用電動(dòng)汽車作為物流車輛的情形下，電量不足時(shí)物流車輛需前往服務(wù)站點(diǎn)充電或更換電池，服務(wù)站點(diǎn)選址直接影響配送路徑策略，這也進(jìn)一步增加了問題的復(fù)雜性。物流企業(yè)出于提高配送人員與服務(wù)時(shí)間等資源的利用率、降低運(yùn)營(yíng)成本提高顧客滿意度水平的目的，采用了在顧客密集區(qū)域開設(shè)顧客自行取貨服務(wù)站點(diǎn)的服務(wù)模式，服務(wù)站點(diǎn)可為顧客提供包裹代收及暫存服務(wù)。服務(wù)站點(diǎn)有相應(yīng)的服務(wù)范圍，位于站點(diǎn)服務(wù)區(qū)域內(nèi)的顧客可自行前往服務(wù)站點(diǎn)取回貨物，而對(duì)于位于站點(diǎn)服務(wù)半徑之外的顧客則由物流車輛直接將其所需貨物送至顧客處。開設(shè)站點(diǎn)提供顧客自行取貨服務(wù)既有助于物流企業(yè)降低運(yùn)營(yíng)成本，又能滿足部分顧客對(duì)收貨時(shí)間的個(gè)性化要求、減少不確定因素對(duì)后續(xù)配送服務(wù)造成不良影響的幾率。基于顧客自行取貨與配送人員送貨上門的多樣化服務(wù)策略，本文提出了考慮站點(diǎn)覆蓋的電動(dòng)汽車路徑優(yōu)化與換電策略問題，建立了該問題的整數(shù)規(guī)劃數(shù)學(xué)模型并且給出了基于改進(jìn)節(jié)約算法與禁忌算法結(jié)合的混合啟發(fā)式算法MCWSA-TS。

為了提高資源利用率與服務(wù)效率，物流運(yùn)營(yíng)方需要統(tǒng)籌兼顧，通過科學(xué)的方式權(quán)衡多樣化服務(wù)策略涉及到的多方面成本。實(shí)驗(yàn)結(jié)果表明：（1）在顧客自行取貨與送貨上門服務(wù)策略下，在顧客集中的區(qū)域設(shè)立服務(wù)站點(diǎn)有助于物流企業(yè)獲得較好的成本效益；（2）受益于服務(wù)策略的多樣化，需送貨上門的顧客數(shù)量減少有助于降低配送所需車輛數(shù)目(配送人員數(shù)目)，進(jìn)一步降低企業(yè)運(yùn)營(yíng)成本；（3）在服務(wù)站點(diǎn)覆蓋半徑較大的情況下，自行取貨的顧客點(diǎn)數(shù)目較多有助于降低整體運(yùn)營(yíng)成本。但是在現(xiàn)實(shí)生活中，需要進(jìn)一步考慮自行取貨距離過長(zhǎng)可能會(huì)導(dǎo)致的顧客流失問題；（4）受到顧客點(diǎn)空間分布差異的影響，擁有相同顧客節(jié)點(diǎn)數(shù)量的不同算例在相同服務(wù)半徑下的服務(wù)策略與運(yùn)營(yíng)成本存在差異；（5）在顧客點(diǎn)與充/換電站點(diǎn)數(shù)量相對(duì)較少的情況下，為了供顧客自行取貨而專門開設(shè)服務(wù)點(diǎn)產(chǎn)生的成本抵消了自行取貨策略節(jié)省的部分配送成本，建站數(shù)量增加直接導(dǎo)致成本降低幅度減少。隨著服務(wù)網(wǎng)絡(luò)規(guī)模擴(kuò)大，服務(wù)站點(diǎn)的選擇需要協(xié)調(diào)物流車輛充/換電需求與顧客自行取貨節(jié)省的配送成本。逐漸增多的站點(diǎn)數(shù)量也為兩者的統(tǒng)籌選址提供了更多的選擇，減少為顧客自行取貨而專門開設(shè)服務(wù)站點(diǎn)的幾率。通過協(xié)調(diào)站點(diǎn)的位置同時(shí)滿足車輛充/換電需求與顧客取貨需求，實(shí)現(xiàn)Cover-LRP效益的最大化。

以下方面還有待進(jìn)一步研究，本文所考慮的配送車輛為單一車型，在未來的研究中可以進(jìn)一步分析多車型情況下的路徑與服務(wù)策略；其次，設(shè)計(jì)更加高效的算法策略將是未來工作的一個(gè)重點(diǎn)。

[1] Wasner M, Zapfel G. An integrated multi-depot hub-location vehicle routing model for network planning of parcel service[J]. International Journal of Production Economics, 2004, 90(3): 403-419.

[2] Dantzig G B, Ramser J H. The truck dispatching problem[J]. Management science, 1959, 6(1): 80-91.

[3] Baldacci R, Mingozzi A. A unified exact method for solving different classes of vehicle routing problems[J]. Mathematical Programming, 2009, 120(2): 347-380.

[4] Rivera J C, Afsar H M, Prins C. A multistart iterated local search for the multitrip cumulative capacitated vehicle routing problem[J]. Computational Optimization and Applications, 2015, 61(1): 159-187.

[5] Jin J, Crainic T G, Lokketangen A. A cooperative parallel metaheuristic for the capacitated vehicle routing problem[J]. Computers & Operations Research, 2014, 44: 33-41.

[6] Current J R, Schilling D A. The covering salesman problem[J]. Transportation science, 1989, 23(3): 208-213.

[7] Salari M, Naji-Azimi Z. An integer programming-based local search for the covering salesman problem[J]. Computers & Operations Research, 2012, 39(11): 2594-2602.

[8] Hachicha M, Hodgson M J, Laporte G, et al. Heuristics for the multi-vehicle covering tour problem[J]. Computers & Operations Research, 2000, 27(1): 29-42.

[9] Ha M H, Bostel N, Langevin A, et al. An exact algorithm and a metaheuristic for the multi-vehicle covering tour problem with a constraint on the number of vertices[J]. European Journal of Operational Research, 2013, 226(2): 211-220.

[10] 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-06-15,S.l.:s.n.,2012: 387-393.

[11] Erdoan S, Miller-Hooks E. A green vehicle routing problem[J]. Transportation Research Part E: Logistics and Transportation Review, 2012, 48(1): 100-114.

[12] Schneider M, Stenger A, Goeke D. The electric vehicle-routing problem with time windows and recharging stations[J]. Transportation Science, 2014, 48(4): 500-520.

[13] Schneider M, Stenger A, Hof J. An adaptive VNS algorithm for vehicle routing problems with intermediate stops[J]. OR Spectrum, 2015, 37(2): 353-387.

[14] Yang J, Sun H. Battery swap station location-routing problem with capacitated electric vehicles[J]. Computers and Operations Research, 2015, 55: 217-232.

[15] Keskin M. Partial recharge strategies for the electric vehicle routing problem with time windows[J]. Transportation Research Part C: Emerging Technologies, 2016, 65: 111-127.

[16] Koc C, Bektas T, Jabali O, et al. The fleet size and mix location-routing problem with time windows: Formulations and a heuristic algorithm[J]. European Journal of Operational Research, 2016, 248(1): 33-51.

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

Jie W C, Yang J, Yang C. Branch-and-price algorithm for heterogeneous electric vehicle routing problem [J]. Systems Engineering —Theory & Practice, 2016, 36(7): 1795-1805.

[18] Jie W C, Yang J, Yang C. Branch-and-price algorithm for heterogeneous electric vehicle routing problem[J]. Systems Engineering- Theory & Practice, 2016, 36(7): 1795-1805.

[19] Clarke G, Wright J W. Scheduling of Vehicles from a Central Depot to a Number of Delivery Points[J]. Operations Research, 1964, 12(4):568-581.

[20] Fan L, Qin Q. The Optimization Model and Empirical Analysis for Vehicle Routing Problems with Time Windows Based on C-W Algorithm[M]. LISS 2012. Springer Berlin Heidelberg, 2013:253-258.

[21] Wang Z, Li Y, Hu X. A heuristic approach and a tabu search for the heterogeneous multi-type fleet vehicle routing problem with time windows and an incompatible loading constraint[J]. Computers & Industrial Engineering, 2015, 89(C):162-176.

[22] Lai D S W, Demirag O C, Leung J M Y. A tabu search heuristic for the heterogeneous vehicle routing problem on a multigraph[J]. Transportation Research Part E Logistics & Transportation Review, 2016, 86:32-52.

[23] Silvestrin P V, Ritt M. An iterated tabu search for the multi- compartment vehicle routing problem[J]. Computers & Operations Research, 2017, 81:192-202.

[24] Soto M, Sevaux M, Rossi A, et al. Multiple neighborhood search, tabu search and ejection chains for the multi-depot open vehicle routing problem[J]. Computers & Industrial Engineering, 2017, 107: 211-222.

[25] Woensel T V. Vehicle Routing Problem with Stochastic Travel Times: Balancing Service and Transportation Costs[J]. Computers & Operations Research, 2017, 40(1):214-224.

[26] 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.

[27] Rinaldi G,Yarrow L A. Optimizing a 48-city traveling salesman problem: A case study in combinatorial problem solving[M]. New York University, Graduate School of Business Administration,1985.

[28] Taillard E. Benchmarks for basic scheduling problems[J]. European journal of operational research, 1993, 64(2): 278-285.

Study on the electric vehicle routing optimization and service strategy with the consideration of customer self-pickup radius

GUO Fang, HUANG Hongjun, YANG Jun

( School of Management, Huazhong University of Science and Technology, Wuhan 430074, China)

With the favorable conditions of increasing environmental awareness and government support, there are good opportunities for electric vehicles to be employed in the development of the logistics industry. The logistics service of small packages in cities takes place at the end of the logistics chain, and these are usually delivered to customers by couriers from regional distribution centers. Owing to the scattered locations of customers, complex traffic situations, and uncertainties in the service process, the costs of the last mile delivery tour and its occupied service resources account for 35% -60% of the entire logistics link costs. Therefore, enterprises are eager to seek more favorable service strategies, and hope that this can help logistics enterprises to improve service times and the utilization rates of resources for couriers and reduce operating costs, as well as satisfying the personalized requirements of customers regarding delivery times, and reducing the adverse impacts of uncertain factors on follow-up delivery services to improve customer satisfaction levels.

In this paper, the site coverage concept and customer self-pickup strategy are applied to the facility location and electric vehicle routing problems. This paper studies the optimization of electric vehicle facility location and service strategies under a diversified service strategy combining customer service (within a service radius) and home delivery service (outside the service radius), and establishes a mathematical model of integer programming. The main differences between this research and existing research are: (1) The distribution service line is no longer limited to the Hamilton circuit, and this allows vehicles to accept charging/swapping services a number of times at the same service station. (2) Customers can access goods in a variety of ways, and they are no longer limited to courier delivery in a door-to-door service. (3) The service station can provide a battery charging/swapping service to electric vehicles. Customers who are in the service range of the station can pick up goods by themselves from there, while customers who are not in any service range can enjoy a home delivery service performed by the vehicles.

In the first part, the paper introduces the basics of electric vehicle routing optimization and service strategies, considering the manner of customer self-pickups, puts forward a reasonable restriction condition and hypothesis, defines the relevant parameters and decision variables, and establishes the corresponding integer programming model. This problem constitutes an expansion of the CVRP problem, and the high complexity makes it difficult to obtain a satisfactory solution in polynomial time. Therefore, in the second part this paper proposes a hybrid heuristic algorithm MCWSA-TS, based on a modified Clarke-Wright saving algorithm and the tabu search algorithm. MCWSA-TS is composed of four parts: the radius cover algorithm (RCA), modified Clarke-Wright saving algorithm (MCWSA), local search (LS), and tabu search (TS). The RCA is proposed to obtain an initial location solution and assignment strategy. Then, this paper adopts the modified savings mechanism to optimize the service line in the path subproblem. Finally, the current strategy is optimized by LS and TS. The third part presents the numerical experiments, and first introduces the set and value rules of the various parameters. In order to verify the accuracy of the model and the effectiveness of the heuristics algorithm, this paper uses IBM CPLEX12.6 to solve a series of small-scale examples, and compares the results with those of the hybrid heuristic algorithm MCWSA-TS. The experimental results show that MCWSA-TS can find satisfactory solutions of the problem in short times, and these solution are superior to those of CPLEX. Then, 21 groups of examples are selected for a comparative analysis, highlighting the impact of diversified services on the business strategy, service path cost, and the required number of vehicles (the number of couriers), in order to demonstrate its superiority. Finally, a sensitivity analysis on the service radius of the covering-LRP problem is conducted.

Electric vehicles; Location-routing problem; Hybrid heuristic algorithm; Diversified service strategy;Radius cover concept

2017-04-19

2017-10-30

Supported by the National Natural Science Foundation of China (71320107001), the Fundamental Research Funds for the Central Universities (2015QN175) and the Wuhan Modern Service Plan

U116.2；O221

A

1004-6062(2020)01-0154-010

10.13587/j.cnki.jieem.2020.01.017

2017-04-19

2017-10-30

國(guó)家自然科學(xué)基金重大資助項(xiàng)目（71320107001）；中央高?；究蒲袠I(yè)務(wù)費(fèi)專項(xiàng)資助（2015QN175）；武漢市黃鶴英才（現(xiàn)代服務(wù)）計(jì)劃資助項(xiàng)目

郭放（1990—），男，四川江油人；華中科技大學(xué)管理學(xué)院，博士研究生；研究方向：網(wǎng)絡(luò)優(yōu)化。

中文編輯：杜 健；英文編輯：Charlie C. Chen