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

郭 放，黃宏軍，楊 珺

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

郭 放，黃宏軍，楊 珺

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

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

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

0 引言

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

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

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

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

1.1 問題描述

1.2 基礎模型

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

S.T.

1.3 拓展模型

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

1.4 拓展模型線性化

引理 1.

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

2 算法實現(xiàn)

2.1 初始選址

步驟2.2：計算服務站點覆蓋的顧客點需求量總和并將其作為該站點的需備貨量。

步驟2.3：更新顧客點集合，包括已開設的服務站點和未被任何服務站點覆蓋的顧客點。

2.2 路徑子問題

步驟1：（路徑初始化）

2.3 優(yōu)化當前解

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

步驟2(LS)：采用點移動，點交換，點插入和局部交換策略進行局部搜索。

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

（1）點移動策略的優(yōu)化對象為任意一條服務路徑。將路徑中的每一個點從當前位置移動到同一路徑中的其他位置。

（2）點交換策略的優(yōu)化對象為任意一對服務路徑。從兩條路徑中分別選取一個點將其放入另一條配送路徑中，交換點在新路徑中的服務順序為使得行駛距離增加量最小的服務順序。

2.4 禁忌搜索

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

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

3.1 測試用例

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

3.2.1模型與算法的驗證分析

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

3.2.2 多樣化服務策略影響性分析

表2 多樣化服務策略實驗結(jié)果對比

圖1 路徑成本對比

Figure 1 Comparison of path cost

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

Figure 2 Comparison of vehicle amount required for distribution

3.2.3 服務半徑敏感性分析

表3 服務半徑敏感性實驗結(jié)果對比

表4 服務半徑敏感性實驗結(jié)果對比2

圖3 配送線路示意圖

圖4 配送線路示意圖

4 結(jié)束語

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

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

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

[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] 揭婉晨, 楊珺, 楊超. 多車型電動汽車車輛路徑問題的分支定價算法研究[J]. 系統(tǒng)工程理論與實踐, 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

國家自然科學基金重大資助項目（71320107001）；中央高校基本科研業(yè)務費專項資助（2015QN175）；武漢市黃鶴英才（現(xiàn)代服務）計劃資助項目

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

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