[發明專利]應用于求解電動貨車集散貨路徑規劃的方法及裝置

在審

• 申請號: 202210546556.5
• 申請日: 2022-05-19
• 公開（公告）號: CN114897249A
• 公開（公告）日: 2022-08-12
• 發明（設計）人: 成明;張成浩;謝剛;黎怡彤;王馨恬;王靜妍;鄭鍇
• 申請（專利權）人: 蘇州大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06F30/20;G06F111/06;G06F111/08
• 代理公司: 蘇州市中南偉業知識產權代理事務所(普通合伙) 32257
• 代理人: 李柏柏

本發明涉及一種應用于求解電動貨車集散貨路徑規劃的方法，該方法包括輸入車場數據、需求節點數據、充電站節點數據以及電動貨車數據；以最小化總時間為目標，將所有的需求節點插入進車場到車場的路徑中，生成包含有若干條路徑的初始解，設置最大迭代次數，令當前解x_c為初始解，對當前解x_c進行迭代；在迭代過程中采用各種插入和移除算子，在每次的迭代中更新算子選擇概率，并針對同時集散貨機制和多次插入充電站機制設計了相應的求解算子和流程，以達到提升求解質量的目標，并且在求解時充分考慮等待時間，顯著提高了求解精度。

技術領域

本發明涉及電動貨車路徑規劃技術領域，尤其是指一種應用于求解電動貨車集散貨路徑規劃的方法及裝置。

背景技術

傳統的化石能源車輛越來越受到限制，越來越多的城市物流選擇電動貨車作為運輸工具。但是電動貨車有限的電池容量和有限的續航導致其在路徑規劃時不能像傳統貨車那樣靈活訪問各個取送貨點。因此如何解決電動貨車的路徑規劃問題成為運輸行業研究的重點。

目前已經有很多方法可以用來解決車輛路徑規劃問題，比如鄰域搜索、禁忌搜索、遺傳算法以及蟻群算法等等。這些方法雖然可以解決傳統車輛路徑規劃問題，但是它們并不能解決電動貨車路徑規劃問題。因為在電動貨車路徑規劃中，當主體對象切換為電動貨車時，電動車存在電量有限需要訪問充電站的情況，其訪問充電站需要花費一定的時間進行充電，不能夠像傳統車輛訪問加油站加油的時間可以幾乎不計，并且充電站的出現使得車輛的訪問目的地可能在顧客點和充電站之間切換，并且充電站的訪問次數不像顧客點那樣確定，同時擁有取貨和送貨需求的顧客點最多被訪問兩次，而充電站理論上可以訪問無限次，因此現有技術中解決傳統貨車路徑規劃問題的方法不能應用于電動貨車領域。

Ropke和Pisinger[1]于2006年提出自適應大鄰域搜索算法應用于求解一般車輛的集散貨路徑規劃問題；Keskin和[2]于2016年改進自適應大鄰域搜索算法，應用于求解帶時間窗的電動車路徑規劃問題；Kancharla和Ramadurai[3]于2020年進一步改進自適應大鄰域搜索算法，應用于求解考慮非線性充電和載貨量耗電的電動車路徑規劃問題。上述方案[2]和方案[3]中雖然對象為電動貨車，但是每條路徑中的充電站插入數量有限，且方案沒有考慮到同時集散貨的情況，某些算子不能適應同時取貨和送貨的機制，以及多次插入充電站的機制，而且方案在求解時沒有考慮等待時間，導致其求解精度較低。因此，迫切需要提供一種應用于求解電動貨車集散貨路徑規劃的方法來克服現有技術存在的缺陷。

[1]Stefan Ropke and David Pisinger.(2006).An Adaptive LargeNeighborhood Search Heuristic for the Pickup and Delivery Problem with TimeWindows.Transportation Science,vol.40,no.4,455-472.

[2]Merve Keskin and Bülent(2016).Partial recharge strategiesfor the electric vehicle routing problem with time windows.TransportationResearch Part C:Emerging Technologies,vol.65,111-127.

[3]Surendra Reddy Kancharla and Gitakrishnan Ramadurai.(2020).Electric vehicle routing problem with non-linear charging and load-dependentdischarging.Expert Systems with Applications,vol.160,113714.

發明內容