[發明專利]一種基于強化學習的超啟發算法的車輛路徑優化方法

有效

• 申請號: 201911116073.6
• 申請日: 2019-11-15
• 公開（公告）號: CN110956311B
• 公開（公告）日: 2023-04-07
• 發明（設計）人: 張景玲;馮勤炳;余孟凡
• 申請（專利權）人: 浙江工業大學
• 主分類號: G06Q10/047
• 分類號: G06Q10/047;G06N3/006;G06Q10/0835
• 代理公司: 杭州斯可睿專利事務所有限公司 33241
• 代理人: 王利強

一種基于強化學習的超啟發算法的車輛路徑優化方法，包括以下步驟：步驟1車輛路徑問題分析；步驟2初始化；步驟3經驗池、序列池存儲；步驟4解的接受保留；步驟5判斷經驗池容量，容量足夠則進入步驟8學習，未滿，則進入步驟6；步驟6選擇Action；步驟7保留最優解；步驟8選擇學習樣本，并初始化神經網絡；步驟9神經網絡學習更新；步驟10更新目標值網絡；步驟11判斷學習結束情況，學習未結束，則進入步驟8繼續學習更新；反之，則進入步驟6選擇Action，返回主循環；步驟12程序結束，輸出車輛路徑距離最優值及最優值路徑序列。本發明提供了一種高層選擇策略為強化學習的超啟發算法的車輛路徑優化方法。

技術領域

本發明涉及一種物流配送、電子商務、智能優化、計算機應用領域，尤其涉及的是一種車輛路徑優化方法。

背景技術

車輛路徑問題是一個NP-Hard問題，求解最優解相對困難。現有的車輛路徑優化方法，包括精確算法，傳統啟發式算法和智能算法。精確算法，例如：分支定界法，最小化K-trees，動態規劃算法等，能求得全局最優解，但是當客戶點規模擴大時，求解時間呈指數增長。傳統啟發式算法，例如節約法，兩階段法等，相較于精確算法，能夠更加有效地找尋最優解，但同樣在大規模問題上，效率不佳。智能算法，例如蟻群算法，遺傳算法，禁忌搜索算法等，因其既能得到優解，又能保證效率的優點，得到許多研究者青睞。但對傳統智能算法的設計，設計者往往需要同時具備計算機算法設計基礎以及所需解決問題領域的專業知識，缺乏通用性。近年來，超啟發算法因其高效性和通用性的特點，被提出來用于解決跨領域的組合優化問題。同時，人工智能的發展，也使強化學習算法越來越受人關注，其在多種領域的表現尤為亮眼。

發明內容

為了保證算法在求解VRP問題上具有通用性的要求，同時達到利用強化學習算法根據結果優化超啟發算法的選擇策略，提升算法性能的目的，本發明提出了一種高層策略可移植的基于強化學習的超啟發式算法的車輛路徑優化方法。

本發明解決其技術問題所采用的技術方案是：

一種基于強化學習的超啟發算法的車輛路徑優化方法，所述方法包括以下步驟：

步驟1車輛路徑問題分析，采用Augerat’s?instances數據集，車輛路徑問題的成本矩陣的元素是歐幾里得距離；

假定配送中心設為i＝0，客戶點設為L(i＝1,2,3,…,L)，最多車輛數設為K(k＝1,2,3,…K)，每輛車具有相同載重量為q，每個客戶點需求量設為d_i(i＝1,2,3,…,L)，客戶i到客戶j的距離設為c_ij，優化的目標是行駛距離最短，一個完整的解包含了全部路徑的集合；

步驟2初始化，先生成Npop組個體的種群，得到最小路徑k，利用聚類思想劃分，k塊區域，得KC塊，由KC塊隨機挑選生成可行解組P(p_i＝p₁,p₂,p₃,…,p_NP)，計算種群適應度f(f_i＝f₁,f₂,f₃,…,f_NP)；隨機挑選一組可行解p_i以及對應適應度值f_i，設P_B為最優解個體，F_B為最優適應度值，設LLH算子數量為N^A，Action取值為(1,2,3,…,N^A)整數，初始化P_B＝p_i，F_B＝f_i，State＝0，Action＝random(N^A)，隨機挑選一個范圍N^A中的數；