電動無人駕駛配送貨運車輛路徑優化研究

溫欣琪，唐鑫琦

（長安大學 汽車學院，陜西 西安 710064）

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

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

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

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

1 模型構建

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

1.1 模型聲明

現實中的配送問題是十分復雜且靈活的，不利于研究，為此本文構建的模型對現實的配送問題進行了簡化，為此設立了如下的假設條件：

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

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

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

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

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

6）電動車輛從配送中心發出時的電池電量應該屬于充滿的狀態，并且在客戶點處服務時電量不消耗；

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

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

1.2 模型構建

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

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

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

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

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

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

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

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

1.3 模型驗證

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

表2 各節點的測試數據

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

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

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

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

圖1 小規模算例求解結果

2 算法設計

2.1 算法流程

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

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

圖2 算法流程圖

2.2 算法驗證

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

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

圖3 MATLAB 小規模算例求解結果

2.3 算法應用

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

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

對大規模算例進行求解，得到其求解的最優結果，最低成本是402.295 7 元/km。大規模算例的MATLAB 求解結果如圖4 所示。

圖4 MATLAB 大規模算例求解結果

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

3 結論

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

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

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