[發明專利]一種考慮實際多約束的多條等效最優路徑規劃方法

在審

• 申請號: 202210874939.5
• 申請日: 2022-07-25
• 公開（公告）號: CN115146866A
• 公開（公告）日: 2022-10-04
• 發明（設計）人: 葛洪偉;張海飛;江明;李婷
• 申請（專利權）人: 江南大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/06;G06Q10/08;G06N3/00
• 代理公司: 哈爾濱市陽光惠遠知識產權代理有限公司 23211
• 代理人: 呂永芳

本發明公開了一種考慮實際多約束的多條等效最優路徑規劃方法，屬于交通運輸科技領域。該方法基于城市物流配送中的實際情況，考慮更加符合現實生活的復雜路網約束、負載約束、時間窗約束以及需求可拆分約束，構造對應的目標函數；在求解多條等效最優路徑時，設計了一種改進差分進化算法，首先在初始化過程中利用廣義反向學習策略生成反向顧客種群，同時搜索當前空間和轉換空間的解；且采用三種概率方式在種群中選擇生成差分向量的個體，自適應平衡體的探索能力和開發能力，提高決策空間和目標空間的多樣性；而且對產生突變的個體進行合法化處理，而非直接丟棄，從而使得超出解空間范圍的個體能夠得到修正，進一步保證了可以得到多條等效最優路徑。

技術領域

本發明涉及一種考慮實際多約束的多條等效最優路徑規劃方法，屬于交通運輸科技領域。

背景技術

在過去的幾十年里，車輛路徑問題(Vehicle Routing Problem,，VRP)及其變體由于能夠模擬各種領域的實際應用而獲得了廣泛的普及。面向實際多約束的VRP(Rich VRP，RVRP)在實際應用中比VRP更具相關性。RVRP的目標是在給定的約束條件下找到合理的車輛分配和路線規劃，從而使成本最小化。在RVRP中，成本可以是車輛/路線的數量、所有車輛行駛的總距離、總行駛時間等。

RVRP是應運實際需求而產生的，作為一個NP難問題，同時又是一個多目標優化問題，其目標函數的重要性因領域而異。例如，對于食品配送和醫療行業，延遲時間至關重要；貨物運輸業可以考慮總行程作為比其他目標最小化的關鍵目標，因為燃料的消耗與行駛距離成正比，因此從經濟角度來看，重要的是將所有車輛行駛的總距離減少至最小；對于小型工業，與其他目標相比，車輛數量的最小化可能是最優先的目標。而在對車輛路徑進行規劃時，決策者希望可以同時獲得滿足目標需求的多條路徑，從而保障決策的穩定性.

VRP及其基本變體已被廣泛探討，針對實際問題的RVRP近年來成為新的研究趨勢。關于RVRP的研究雖然取得了一定的研究成果，但仍存在某些問題：(1)忽略了物流配送過程是建立在復雜城市路網基礎上的，目前關于RVRP的研究均未考慮城市復雜路網對車輛路徑的影響。(2)求解目標單一，目前對RVRP的研究主要以某一角度進行目標求解，如最小的運輸成本(minimum total cost)、最短的運輸距離(minimum travel time)、最短顧客等待時間(minimum the average waiting time of customers)、最短運輸時間(minimum traveltime)等，但在實際的物流配送過程中，需要考慮多目標的優化。(3)RVRP的大多數現有數據集要么不考慮真實世界特征，要么來自經典的單目標數據集，不存在模擬真實世界特征的問題實例。因此使得求解RVRP的相關方法也各不相同。(4)資源利用率不高，對于大多數物流企業或配送中心，每次的運輸任務可支配的車輛數量以及配送人員等資源都是有限的。因此如何降低物流運輸成本，最大化地利用有限資源，提高運輸車輛的裝載率，對路徑優化相關研究至關重要。