[發明專利]一種車輛路徑規劃方法及系統

有效

• 申請號: 202010176733.6
• 申請日: 2020-03-13
• 公開（公告）號: CN111337042B
• 公開（公告）日: 2021-11-02
• 發明（設計）人: 楊超;陳炳秋;夏雨微;聞海洋;賈琳;程鎮
• 申請（專利權）人: 湖北大學
• 主分類號: G01C21/34
• 分類號: G01C21/34;G06N3/12;G06N3/00
• 代理公司: 北京金智普華知識產權代理有限公司 11401
• 代理人: 楊采良

本發明屬于車輛路徑規劃技術領域，公開了一種車輛路徑規劃方法及系統，通過初始化N個隨機路徑作為抗體放入抗體候選集，計算每條車輛路徑的距離作為每個抗體與抗原之間的親和力，初始化標記每個抗體；選擇親和力最高的前n個抗體，對每個抗體進行克隆操作，同時更新標記；對發生變異的抗體重新標記；對變異后的抗體進行重新計算親和力，選擇出與抗原之間親和力最高的N個抗體，對抗體候選集中的抗體進行更新抗體標記；當抗體滿足抗體遺忘閾值時，進行遺忘；當滿足評估函數調用次數時終止計算，得到最優的車輛路徑。本發明通過替換過程，對抗體集中的抗體進行群體標記和更新，從而達到提高算法收斂速度和收斂穩定性的效果。

技術領域

本發明屬于車輛路徑規劃技術領域，尤其涉及一種車輛路徑規劃方法及系統。

背景技術

目前，克隆選擇算法是一種受生物免疫系統克隆選擇原理啟發而設計的新型智能優化算法；Ag(antigen)抗原：本發明特指車輛路徑規劃問題需求；Ab(antibody)抗體：本發明特指各個城市路徑排序序列；遺忘機制(Forgetting mechanism)：遺忘是一種信息丟失的現象，在特定的環境下，信息的丟失是有意義的。

車輛路徑規劃問題(Vehicle Routing Problem，VRP)最早是由Dantzig和Ramser于1959年首次提出，它是指一定數量的客戶，各自有不同數量的貨物需求，配送中心向客戶提供貨物，由一個車隊負責分送貨物，組織適當的行車路線，目標是使得客戶的需求得到滿足，并能在一定的約束下，達到諸如路程最短、成本最小、耗費時間最少等目的。由于該問題的可行解是所有頂點的全排列，隨著頂點數的增加，會產生組合爆炸，它是一個NP完全問題。

由于其在交通運輸、電路板線路設計以及物流配送等領域內有著廣泛的應用，國內外學者對其進行了大量的研究。綜合過去有關車輛路線問題的求解方法，可以分為精確算法(exact algorithm)與啟發式解法(heuristics)，其中精密算法有分支界限法、分支切割法、集合涵蓋法等；啟發式解法有節約法、模擬退火法、確定性退火法、禁忌搜尋法、基因算法、神經網絡、螞蟻殖民算法等。但是，隨著問題規模的增大，精確算法將變得無能為力，因此，在后來的研究中，現有技術重點使用近似算法或啟發式算法。目前主要的車輛路徑規劃問題中求解最短路徑問題的解決方法及其缺陷如下：

1.模擬退火算法：收斂速度慢，執行時間長，參數依賴較大；

2.遺傳算法：易陷入局部早熟，收斂性能差，由連續問題歸納到組合問題求解，使得精度受到很大的影響；

3.克隆選擇算法：屬于進化算法簇，收斂速度過快，容易陷入局部最優；克隆選擇算法在求解車輛路徑規劃問題中存在兩個問題：一是存在中間抗體不能及時被淘汰影響算法效率，二是在保證抗體多樣性時新生成的抗體存在競爭力不足的問題。

4.蟻群算法：計算開銷過大，求解效率不高。

通過上述分析，現有技術存在的問題及缺陷為：

現有車輛路徑規劃方法結果不準確，精度低，效率不高且耗費時間長。如在物流車輛路徑規劃系統中使用模擬退火作為核心算法求解車輛規劃路徑時，由于該方法收斂速度慢，使用者需要等待很久才能得到解，對使用者不友好且系統效率低。再如用遺傳算法或原始克隆選擇算法作為物流車輛路徑規劃系統的核心算法時，由于這類方法易陷入局部早熟，往往得到的結果不是最優路徑，導致在實際物流配送中多耗費了人力物力，降低了物流配送效率。

解決以上問題及缺陷的難度為：在保證方法收斂速度較快的條件下，提高方法運算結果的準確性。讓使用者既不需要等待太久的時間，又可以得到較好的物流車輛路徑規劃結果。即在保證時間效率的前提下提高物流車輛路徑規劃的質量。

解決以上問題及缺陷的意義為：提高方法的收斂速度和穩定性，增強方法的求解能力。使得求解物流車輛配送路徑的系統性能得到提高，讓使用者能夠更快的得到更有效的配送路徑，在需求相同的情況下讓車輛走最少的距離，提高物流配送效率，節省人力物力。