[發明專利]應用交叉引力搜索的車輛路徑規劃方法

有效

• 申請號: 201710644216.5
• 申請日: 2017-08-01
• 公開（公告）號: CN107462255B
• 公開（公告）日: 2021-02-23
• 發明（設計）人: 郭肇祿;王洋;劉小生;劉趙陽;尹寶勇;李大海;余法紅
• 申請（專利權）人: 江西理工大學
• 主分類號: G01C21/34
• 分類號: G01C21/34
• 代理公司: 贛州凌云專利事務所 36116
• 代理人: 曾上

本發明公開了一種應用交叉引力搜索的車輛路徑規劃方法。本發明采用交叉引力搜索算法來實現車輛運輸路徑的規劃。在交叉引力搜索算法中，以一定的概率執行基本引力搜索算法的位置更新操作算子，同時以一定的概率執行基于當前最優個體的高斯采樣操作算子，以此加快算法的收斂速度，提高車輛路徑規劃的效率。本發明能夠在很大程度上加快傳統引力搜索算法的收斂速度，提高車輛路徑規劃的效率。

技術領域

本發明涉及車輛路徑規劃領域，尤其是涉及一種應用交叉引力搜索的車輛路徑規劃方法。

背景技術

當前，互聯網技術正在高速發展，它已經滲透到了人類生活中的每一個部分，并在很大程度上改變了人類的生活方式。由于互聯網的高速發展，人們網購的流行程度越來越高，如網上買衣服，網上訂外賣等互聯網業務已經深入人心。與此同時，網上購物的盛行對現代物流系統提出了更高的要求。在互聯網的物流系統中，人們常常會遇到如下車輛路徑規劃問題：給定了若干個運輸點的坐標，需要為一輛運輸車規劃出一條運輸路徑，使得運輸車從源運輸點出發經過每個運輸點一次且僅一次后再回到源運輸點。這個車輛路徑規劃問題廣泛存在于互聯網的物流系統中，它是一個NP完全性問題，當問題的規模比較大時，傳統的精確算法難以在短時間內規劃出有效的路徑。鑒于這種現狀，人們往往利用模擬自然進化規律的演化算法來解決這個車輛路徑規劃問題。

引力搜索算法是一種較新的演化算法，它在求解許多工程優化問題中表現出非常有潛力的性能。為此，引力搜索已經廣泛應用于來解決各種工程優化問題。例如，李沛和段海濱利用改進萬有引力搜索算法的來規劃無人機的航路，實驗結果表明該方法能夠在復雜環境下規劃出無人機的最優航路(李沛,段海濱.基于改進萬有引力搜索算法的無人機航路規劃[J].中國科學:技術科學,2012,42(10):1130-1136.)；王宇等利用引力搜索算法來設計船舶艙室，實驗結果表明該方法能夠求解出較滿意的設計方案。(王宇,黃勝,廖全蜜,楊放青.基于引力搜索算法的船舶艙室布置方法[J].上海交通大學學報,2016,50(01):131-139.)；李海濤等利用量子引力搜索來優化支持向量機(SVM)的訓練參數，并利用訓練好的SVM來實現自動駕駛儀的故障診斷，實驗結果表明該方法能夠比遺傳算法和基本引力搜索算法獲得更高的分類準確率。(李海濤,何玉珠,宋平.基于量子萬有引力搜索的SVM自駕故障診斷[J].北京航空航天大學學報,2016,06:1093-1098.)。

雖然引力搜索已經廣泛而深入地應用到了各種工程問題，并在解決許多工程優化問題中獲得了較滿意的結果，但傳統引力搜索在解決車輛路徑規劃問題時往往存在著收斂速度慢，規劃效率不高的缺點。

發明內容

本發明的目的是提供一種應用交叉引力搜索的車輛路徑規劃方法。它在很大程度上克服了傳統引力搜索在解決車輛路徑規劃問題時收斂速度慢，規劃效率不高的缺點，本發明能夠加快傳統引力搜索的收斂速度，提高車輛路徑規劃的效率。

本發明的技術方案：一種應用交叉引力搜索的車輛路徑規劃方法，包括以下步驟：

步驟1，輸入車輛所需經過各運輸點的坐標，并確定運輸點的數量D；

步驟2，用戶初始化參數，設置種群大小Popsize，最大評價次數MAX_FEs；

步驟3，令當前演化代數t＝0，當前評價次數FEs＝0；

步驟4，隨機產生初始種群其中個體下標i＝1,2,...,Popsize；并且為種群P_t中的第i個個體，其中個體按公式(1)進行初始化：

其中維度下標j＝1,2,...,D；并且為個體的當前位置，表示D個運輸點的順序權值；為個體中第j個運輸點的順序權值；為個體在每一維度的當前速度，其中為個體在第j維度的當前速度；rand為服從均勻分布的隨機實數產生函數；