電動(dòng)無人駕駛配送貨運(yùn)車輛路徑優(yōu)化研究

溫欣琪，唐鑫琦

（長(zhǎng)安大學(xué) 汽車學(xué)院，陜西 西安 710064）

現(xiàn)如今，隨著我國(guó)經(jīng)濟(jì)高速穩(wěn)定發(fā)展，城市化進(jìn)程的迅速推進(jìn)，交通領(lǐng)域的不斷發(fā)展，消費(fèi)模式迎來了巨大的轉(zhuǎn)變。與此同時(shí)，傳統(tǒng)內(nèi)燃機(jī)汽車的應(yīng)用帶來了一些負(fù)面效應(yīng)，如：消耗了大量的不可再生能源、產(chǎn)生大量的噪聲污染、汽車尾氣的排放加劇溫室效應(yīng)等。隨著人們社會(huì)環(huán)境意識(shí)的不斷增長(zhǎng)，無人駕駛技術(shù)的逐漸發(fā)展和成熟，無人駕駛電動(dòng)汽車具有綠色、高能源利用率、低噪音、自動(dòng)化、無人化、信息化的優(yōu)勢(shì)被廣泛看好，智能無人物流具有成本低、效率高的優(yōu)勢(shì)逐漸成為未來發(fā)展的趨勢(shì)。然而由于電動(dòng)汽車電池和充電技術(shù)發(fā)展尚不完善，使得無人駕駛電動(dòng)物流車的標(biāo)定續(xù)駛里程普遍不高，中途充電的時(shí)間普遍偏長(zhǎng)，并且由于充電站的數(shù)量較少，且部分充電站的位置布置不適用于物流，再加上城市交通擁堵、載貨量、司機(jī)操縱特性、氣候等外界環(huán)境等因素的復(fù)雜影響，導(dǎo)致無人駕駛電動(dòng)物流車的實(shí)際續(xù)駛里程小于標(biāo)定續(xù)駛里程。這就對(duì)電動(dòng)配送貨運(yùn)車輛路徑優(yōu)化提出了更高的要求。因此，將無人駕駛技術(shù)和具有廣泛優(yōu)勢(shì)的電動(dòng)汽車結(jié)合運(yùn)用于物流配送中，并研究其路徑優(yōu)化問題是很有必要的。

SCHNEIDER[1]等在2013 年研究了帶時(shí)間窗的電動(dòng)車輛路徑優(yōu)化問題（Electric Vehicle Routing Problem with Time Windows, EVRP-TW），其中車輛必須在充電站處才能充電服務(wù)，將電池電量消耗表示成了車輛行駛距離的線性函數(shù)。YANG和SUN[2]在2015 年首次提出了純電動(dòng)物流汽車的充電站選址的車輛路徑優(yōu)化問題（Vehicle Routing Problem, VRP），充分考慮了電動(dòng)物流車的特點(diǎn)，對(duì)充電站的位置進(jìn)行了關(guān)注。DESAULNIERS[3]在2016 年研究了多次充電和單次充電的、完全充滿和部分充電的電動(dòng)車輛路徑優(yōu)化問題（Electric-Vehicle Routing Problem, EVRP）。SCHIFFER 和WALTHER[4]在2017 年提出了電動(dòng)車充電站位置選擇與路線優(yōu)化問題（Electric-Vehicle Location Routing Problem, E-LRP）。MERVE K 和BüLENT ?[5]在2018 年研究了帶時(shí)間窗的電動(dòng)汽車路徑問題，提出車站可以配備不同的電源充電器，以提供不同的功率，并討論了相應(yīng)的數(shù)學(xué)方法。RUBIANO[6]等在2019 年研究了考慮行駛距離約束和隨機(jī)行程時(shí)間下的EVRP 問題，提出了一種簡(jiǎn)單啟發(fā)式算法。目前EVRP 問題處于不斷完善的階段，關(guān)于電動(dòng)物流車路徑優(yōu)化的方法逐漸優(yōu)化。然而國(guó)外學(xué)者對(duì)于將無人駕駛技術(shù)運(yùn)用到物流配送中后產(chǎn)生的路徑優(yōu)化問題的研究并不多，對(duì)于解決其算法的設(shè)計(jì)也缺乏研究。

汪麗穎[7]在2016 年研究了電動(dòng)車充電站策略和VRP 問題，將自適應(yīng)變領(lǐng)域搜索和禁忌搜索混合，提出了一種新型啟發(fā)式求解算法，并得出快速充電設(shè)施和超快速充電設(shè)施的組合表現(xiàn)更有利于實(shí)現(xiàn)系統(tǒng)總成本最優(yōu)的條件。沈續(xù)昌[8]在2018年建立了考慮貨物重量的EVRP 問題的新模型，同時(shí)考慮了運(yùn)輸距離，車身自重，貨物載重量對(duì)電能的消耗，模型中還考慮了取貨送貨的實(shí)際問題。張鵬威[9]在2019 年構(gòu)建了有限充電設(shè)施下的多配送中心的EVRP 問題，設(shè)計(jì)了分散搜索算法來求解，并提出將配送中心作為充電站的方式來提高效率，緩解充電設(shè)施不足的影響。無人駕駛EVRP 問題以及無人配送路徑優(yōu)化逐漸成為配送的一個(gè)重要課題，但國(guó)內(nèi)相關(guān)的研究文獻(xiàn)目前也較少，熊會(huì)元[10]等在2019 年研究得出電動(dòng)無人集卡可以推動(dòng)智慧物流的發(fā)展。胡覺亮[11]等在2020年研究了城市物流中電動(dòng)無人車配送優(yōu)化的問題，明確使用電動(dòng)無人車進(jìn)行城市物流配送可以提高效率并降低成本。目前無人駕駛EVRP 問題面臨著核心模型構(gòu)建不夠完善和路徑規(guī)劃算法有待進(jìn)一步研究的問題。

本文在前人的研究基礎(chǔ)上，進(jìn)一步對(duì)電動(dòng)無人駕駛車輛路徑優(yōu)化問題進(jìn)行研究，提出了本文研究的無人駕駛電動(dòng)物流車路徑優(yōu)化問題的數(shù)學(xué)模型，運(yùn)用LINGO 軟件進(jìn)行小規(guī)模算例測(cè)試，以驗(yàn)證模型的合理性。并將用于求解車輛路徑優(yōu)化問題的節(jié)約里程法進(jìn)行改進(jìn)，用于解決電動(dòng)車輛路徑優(yōu)化問題。運(yùn)用MATLAB 軟件求解驗(yàn)證模型的小規(guī)模算例，來證明算法的可行性，求解一個(gè)大規(guī)模算例，證明本文算法可以求出合適的解，并發(fā)現(xiàn)設(shè)計(jì)算法的不足之處。

1 模型構(gòu)建

本文研究的是電動(dòng)無人駕駛的VRP 問題，這是在傳統(tǒng)的VRP 問題、EVRP 問題上的拓展，不僅考慮了電動(dòng)車輛路徑優(yōu)化的約束條件，還加入了無人駕駛產(chǎn)生的新的約束條件。并且由于電動(dòng)無人駕駛配送貨運(yùn)車輛相較于普通電動(dòng)物流車最大的優(yōu)勢(shì)在于降低運(yùn)營(yíng)成本、人力成本，可以實(shí)現(xiàn)全天配送，防風(fēng)雨，有效解決城鄉(xiāng)“最后一公里”配送問題，提高了運(yùn)輸配送效率，從而進(jìn)一步降低了單位配送里程的成本。

1.1 模型聲明

現(xiàn)實(shí)中的配送問題是十分復(fù)雜且靈活的，不利于研究，為此本文構(gòu)建的模型對(duì)現(xiàn)實(shí)的配送問題進(jìn)行了簡(jiǎn)化，為此設(shè)立了如下的假設(shè)條件：

1）各個(gè)節(jié)點(diǎn)的位置是已知的，由坐標(biāo)(x,y)表示，并由此可以計(jì)算出任意倆節(jié)點(diǎn)間的距離；

2）各個(gè)客戶點(diǎn)的需求是已知的，并且是固定的，不會(huì)發(fā)生變化，且每個(gè)客戶點(diǎn)的需求量要一次配送完成，不進(jìn)行二次配送，即需求是不可拆分的；

3）參與配送的電動(dòng)無人駕駛配送車輛的車型是固定單一的，每輛車的最大載重量和電池的容量是固定的，并且假設(shè)百公里耗電量是一給定值，并且耗電量隨行駛里程的增加成正比增大；

4）車輛配送的成本總體上隨著配送距離的增加而升高，即車輛配送的成本和配送距離呈正比關(guān)系；

5）單配送中心進(jìn)行配送，即所有參與配送的車輛從一個(gè)配送中心出發(fā)進(jìn)行配送，配送完成后返回該配送中心；

6）電動(dòng)車輛從配送中心發(fā)出時(shí)的電池電量應(yīng)該屬于充滿的狀態(tài)，并且在客戶點(diǎn)處服務(wù)時(shí)電量不消耗；

7）配送服務(wù)無時(shí)間窗的要求，即在任意時(shí)刻送達(dá)即可。

為了更加清晰地描述構(gòu)建的電動(dòng)無人駕駛配送貨運(yùn)車輛路徑優(yōu)化模型，本文對(duì)模型設(shè)計(jì)到的集合、變量、參數(shù)做了如下說明，如表1 所示。

1.2 模型構(gòu)建

由于電動(dòng)無人駕駛配送貨運(yùn)車輛的最大優(yōu)勢(shì)體現(xiàn)在成本上面，因此，本文選取總成本最低作為研究的目標(biāo)函數(shù)。車輛配送的成本總體上隨著配送距離的增加而升高，可以認(rèn)為車輛配送的成本和配送距離成正比關(guān)系，將正比系數(shù)記為N，便可以得到如下的目標(biāo)函數(shù)：

電動(dòng)無人駕駛配送貨運(yùn)車輛有最大的額定載質(zhì)量，超載容易增加事故發(fā)生率，也使車輛更易受損，增加維修成本，因此，要限制車輛的裝載量小于額定載質(zhì)量。建立的約束可以用如下的數(shù)學(xué)公式表示：

配送車輛在配送中心裝載貨物后，出發(fā)完成配送任務(wù)，并且在完成配送任務(wù)后，要回到配送中心，進(jìn)行卸貨或再次裝載。同時(shí)要保證開出的車輛要全部回到配送中心。本文假設(shè)有一個(gè)配送中心，因此，建立的約束可以用如下的數(shù)學(xué)公式表示：

電動(dòng)物流車在行駛的過程中，電池的電量在不斷地消耗，已知電動(dòng)物流車的電池容量為C，每單位行駛里程電池的耗電量為h。電動(dòng)物流車在從配送中心出發(fā)的時(shí)候，電池電量應(yīng)該是充滿的。建立的約束可以用如下的數(shù)學(xué)公式表示：

電動(dòng)物流車的電池電量低于某一值時(shí)，電動(dòng)物流車容易因沒電而停駛，如若停駛時(shí)距離充電站距離過遠(yuǎn)，將影響配送效率。并且對(duì)于電動(dòng)車來說，在配送的過程中，電池的電量會(huì)有所消耗，因此，到達(dá)下一個(gè)目的地的電量應(yīng)該小于出發(fā)目的地的電池電量。因此，要對(duì)到達(dá)節(jié)點(diǎn)的電量進(jìn)行計(jì)算，計(jì)算的公式可以用如下的數(shù)學(xué)公式表示：

無人駕駛的電動(dòng)物流車還有一個(gè)特點(diǎn)，有人駕駛時(shí)，駕駛?cè)藛T可以自行觀察電池電量，選擇合理的方式，合理的時(shí)間前往充電，而無人駕駛的電動(dòng)物流車就需要程序來判斷充電的時(shí)間，為此需建立一個(gè)約束。查閱特斯拉電池系統(tǒng)的電池曲線的測(cè)試實(shí)驗(yàn)結(jié)果的相關(guān)資料可知，25%～75%的充放，是比較合理的，對(duì)電池使用壽命的影響較小。本文選取30%，即電池電量低于0.3C就應(yīng)該返回配送中心進(jìn)行充電。建立的約束可以用如下的數(shù)學(xué)公式表示：

根據(jù)確定的假設(shè)和定義的參數(shù)，參考上文的目標(biāo)函數(shù)以及約束條件，建立的電動(dòng)無人駕駛配送貨運(yùn)車輛路徑優(yōu)化的數(shù)學(xué)模型如下：

式（7）為目標(biāo)函數(shù)，表示總成本最低。式（8）為每個(gè)顧客點(diǎn)都需要被服務(wù)，且只能被服務(wù)一次；式（9）為流量平衡；式（10）為每次配送都以配送中心為起點(diǎn)，以配送中心為終點(diǎn)，并且出入庫車輛的數(shù)目一定；式（11）為若車輛k服務(wù)節(jié)點(diǎn)i，則讓其對(duì)應(yīng)的r為1；式（12）為載貨量約束。式（13）為從配送中心和充電站離開的時(shí)候滿電量；式（14）為在客戶點(diǎn)處不消耗電量；式（15）為電動(dòng)車輛的電量不能低于0.3C，不能大于C；式（16）用來計(jì)算車輛到達(dá)任意節(jié)點(diǎn)的電量；式（18）定義了一個(gè)輔助變量z，并要求它非負(fù)；式（17）和式（18）限制線路中產(chǎn)生子回路；式（19）定義了一個(gè)0,1 決策變量x；式（20）定義了一個(gè)0,1非決策變量r；式（21）定義了一個(gè)連續(xù)變量y，并對(duì)它的取值范圍進(jìn)行了約束。

1.3 模型驗(yàn)證

本文選取一小規(guī)模算例，用LINGO 軟件對(duì)算例進(jìn)行計(jì)算，來驗(yàn)證模型的合理性。本文考慮隨機(jī)生成客戶點(diǎn)，同時(shí)對(duì)時(shí)間窗不進(jìn)行限制要求，因此，將Solomon 算例中的R 系列的R107 作為小規(guī)模算例，選取R107 中的7 個(gè)點(diǎn)，選取6 個(gè)分散的點(diǎn)作為客戶點(diǎn)。其中0 點(diǎn)為配送中心，1—6點(diǎn)為配送客戶點(diǎn)，這樣就形成了配送中心位于客戶點(diǎn)中心，各個(gè)客戶點(diǎn)分散分布，各個(gè)方位都距離配送中心合理的小規(guī)模算例，具體參數(shù)信息如表2 所示。

表2 各節(jié)點(diǎn)的測(cè)試數(shù)據(jù)

考慮實(shí)際情況以及模型驗(yàn)證和簡(jiǎn)潔合理性，對(duì)模型中涉及的數(shù)學(xué)參數(shù)進(jìn)行了賦值，以用于模型求解，主要的數(shù)學(xué)參數(shù)有最大載重量，電動(dòng)物流車的電池容量，車輛運(yùn)輸成本和車輛行駛距離的正比系數(shù)，每單位行駛里程的耗電量，參與配送的無人駕駛電動(dòng)物流車的車輛數(shù)目，具體的參數(shù)取值如表3 所示。

表3 無人駕駛電動(dòng)物流車的參數(shù)信息

運(yùn)用LINGO 軟件對(duì)選取的小規(guī)模算例進(jìn)行求解分析，將本文建立的電動(dòng)無人駕駛配送貨運(yùn)車輛路徑優(yōu)化模型轉(zhuǎn)化為L(zhǎng)INGO 語言，對(duì)1 個(gè)配送中心，6 個(gè)客戶點(diǎn)，3 輛配送車輛構(gòu)成的小規(guī)模算例進(jìn)行求解，在迭代2 434 次后，求得一個(gè)可行解78.586，即表示最短配送里程為157 km，最低成本是78.6 元/km。

求得的配送結(jié)果是配送車輛1 從配送中心發(fā)出，按順序到客戶點(diǎn)3、1 進(jìn)行配送，最后回到配送中心，即0→3→1→0；配送車輛2 從配送中心發(fā)出，按順序前往客戶點(diǎn)6、5 進(jìn)行配送，最后返回配送中心，即0→6→5→0；配送車輛3 從配送中心出發(fā)，按順序前往客戶點(diǎn)4、2 進(jìn)行配送，最后返回配送中心，即0→4→2→0。運(yùn)用AutoCAD繪圖軟件繪制的配送路線以及各個(gè)節(jié)點(diǎn)的到達(dá)順序的示意圖如圖1 所示。

圖1 小規(guī)模算例求解結(jié)果

2 算法設(shè)計(jì)

2.1 算法流程

本文研究電動(dòng)無人駕駛配送貨運(yùn)車輛路徑優(yōu)化問題采取傳統(tǒng)啟發(fā)式算法中的節(jié)約法。對(duì)比傳統(tǒng)的VRP 問題，多出了電量的約束，因此，要對(duì)傳統(tǒng)的節(jié)約里程法進(jìn)行優(yōu)化，本文使用的改進(jìn)的節(jié)約法，在計(jì)算出節(jié)約里程數(shù)并且排序后，考察載貨量約束和電量約束進(jìn)行路徑劃分。具體的考察方式是在判斷是否載重量約束的時(shí)候，同時(shí)判斷是否滿足電量約束，如果兩個(gè)條件都滿足，則選擇該點(diǎn)，輸出優(yōu)化的路徑，如果不滿足其中任意一項(xiàng)要求，則需要舍棄該點(diǎn)。

本文所研究的帶電量約束的電動(dòng)無人駕駛配送車輛路徑優(yōu)化模型的節(jié)約里程法的流程如圖2所示。

圖2 算法流程圖

2.2 算法驗(yàn)證

該小規(guī)模算例與上一章節(jié)的小規(guī)模算例為同一個(gè)算例，運(yùn)用設(shè)計(jì)的改進(jìn)的節(jié)約里程法，運(yùn)用MATLAB 軟件，編程實(shí)現(xiàn)對(duì)該小規(guī)模算例的求解。將運(yùn)用算法求解出來的結(jié)果，與LINGO 軟件的求解結(jié)果進(jìn)行比較，可以判斷設(shè)計(jì)的算法的合理性。如果二者相差的結(jié)果不大，并且運(yùn)用算法求解出來的結(jié)果更優(yōu)，則說明設(shè)計(jì)的算法是合理的，可以求解出帶電量約束和載重量約束的EVRP 問題，如果結(jié)果相差很大，說明算法還需要改進(jìn)。

如圖3 所示，由運(yùn)行結(jié)果可知運(yùn)行線路為車輛1 的路線為0→2→1→3→4→6→0，車輛2 的路線為0→5→0。最低成本為79.076 元/km。對(duì)比LINGO 軟件的求解結(jié)果可知，配送線路發(fā)生了變化，分析其原因?yàn)長(zhǎng)INGO 求解時(shí)使用了提供的所有車輛，而使用的算法設(shè)計(jì)時(shí)，在滿足電量要求的情況下，只要一條路線上的配送總量沒有超出車輛的載重量，就會(huì)一直進(jìn)行配送服務(wù)，直至到達(dá)車輛的載重量。LINGO 軟件求解的最優(yōu)解為78.586，對(duì)比算法求解的最優(yōu)解79.076 發(fā)現(xiàn)結(jié)果相近，表明算法是可行的。

圖3 MATLAB 小規(guī)模算例求解結(jié)果

2.3 算法應(yīng)用

本文選取一大規(guī)模算例，用MATLAB 軟件對(duì)大規(guī)模算例進(jìn)行分析計(jì)算，并對(duì)計(jì)算的結(jié)果進(jìn)行分析討論。本文選取與R107 相近的R109 作為大規(guī)模算例的數(shù)據(jù)。R109 數(shù)據(jù)中包含101 個(gè)節(jié)點(diǎn)，只取用橫坐標(biāo)、縱坐標(biāo)、貨物需求量。選取R109中的50 個(gè)點(diǎn)，其中1 點(diǎn)為配送中心，2—50 點(diǎn)為配送客戶點(diǎn)，這樣就形成了配送中心位于客戶點(diǎn)中心，各個(gè)方位客戶點(diǎn)距離配送中心位置合理的大規(guī)模算例，具體參數(shù)信息如表4 所示。

表4 無人駕駛電動(dòng)物流車的參數(shù)信息

對(duì)大規(guī)模算例進(jìn)行求解，得到其求解的最優(yōu)結(jié)果，最低成本是402.295 7 元/km。大規(guī)模算例的MATLAB 求解結(jié)果如圖4 所示。

圖4 MATLAB 大規(guī)模算例求解結(jié)果

大規(guī)模算例的運(yùn)行結(jié)果如圖4 所示，完成配送任務(wù)需要5 輛車，配送的最短路程數(shù)為804.6 km，配送的最低成本為402.3 元/km。根據(jù)求得的結(jié)果發(fā)現(xiàn)算法可以求出合理的解，然而在配送的過程中由于算法本身計(jì)算過程所限，將無法合理地利用每一輛車，使每一輛車的配送任務(wù)基本相同，不至于使某些車輛的任務(wù)繁重，某些車輛的配送任務(wù)太少，而浪費(fèi)某些車輛的利用空間，增加時(shí)間成本。

3 結(jié)論

本文考察了電動(dòng)物流車及無人駕駛技術(shù)的應(yīng)用，發(fā)現(xiàn)無人駕駛配送貨運(yùn)電動(dòng)車輛應(yīng)用于配送過程中有成本低、效率高、信息化、現(xiàn)代化等顯著的優(yōu)勢(shì)。本文研究的是有電量約束的單一車型的，無時(shí)間窗約束的EVRP 問題。

在學(xué)習(xí)借鑒前人的研究?jī)?nèi)容的基礎(chǔ)上，本文提出了自己的帶有載重量約束，電量約束的車輛路徑優(yōu)化問題的數(shù)學(xué)模型，運(yùn)用LINGO 軟件對(duì)一個(gè)小規(guī)模的算例進(jìn)行求解，驗(yàn)證了建立的數(shù)學(xué)模型是可行的。提出了具有電量約束的改進(jìn)的節(jié)約里程法，并用MATLAB 軟件對(duì)算法進(jìn)行編程。在算法設(shè)計(jì)完成后，對(duì)上一章求解過的小規(guī)模算例進(jìn)行再次求解，對(duì)比求解結(jié)果，確認(rèn)了算法的可行性、合理性。并運(yùn)用設(shè)計(jì)好的算法對(duì)一個(gè)大規(guī)模算例進(jìn)行求解，分析其結(jié)果。

研究的局限性在于，在數(shù)學(xué)模型構(gòu)建中只考慮了電量約束，載重量約束和一些基礎(chǔ)的約束，未涉及充電站，時(shí)間窗限制，與現(xiàn)實(shí)生活中的實(shí)際配送情況不夠貼合。并且在設(shè)計(jì)算法進(jìn)行求解時(shí)，選擇入門的節(jié)約里程法。在未來可以進(jìn)一步豐富模型，選擇遺傳算法，蟻群算法等一些可以解決更復(fù)雜問題的復(fù)雜算法。