溫欣琪，唐鑫琦

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

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

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

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

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

1 模型構(gòu)建

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

1.1 模型聲明

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

1）各個節(jié)點的位置是已知的，由坐標(x,y)表示，并由此可以計算出任意倆節(jié)點間的距離；

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

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

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

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

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

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

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

1.2 模型構(gòu)建

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

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

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

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

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

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

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

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

1.3 模型驗證

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

表2 各節(jié)點的測試數(shù)據(jù)

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

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

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

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

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

2 算法設(shè)計

2.1 算法流程

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

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

圖2 算法流程圖

2.2 算法驗證

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

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

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

2.3 算法應(yīng)用

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

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

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

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

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

3 結(jié)論

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

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

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