[發明專利]一種基于強化學習的車輛路徑規劃方法

在審

• 申請號: 202010280643.1
• 申請日: 2020-04-10
• 公開（公告）號: CN111415048A
• 公開（公告）日: 2020-07-14
• 發明（設計）人: 高健;蔣佳浩
• 申請（專利權）人: 大連海事大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06Q10/08;G06Q50/26;G06N3/04;G06N3/08;G06N20/00
• 代理公司: 大連東方專利代理有限責任公司 21212
• 代理人: 李馨

本發明提供一種基于強化學習的車輛路徑規劃方法，將客戶節點的狀態序列作為輸入信息，將輸入信息送往決策網絡，決策網絡依據動作值函數選擇動作并計算規劃車輛行進路線。本發明基于歷史配送數據以強化學習算法來訓練模型，從而達到在道路交通狀況和配送目標節點數變化的情況下動態規劃行車路徑的目的。本方法考慮現實生活中復雜多變的道路交通情況和配送目標數不定的配送任務，動態調整行車路線，從而提高運輸效率并降低成本。

技術領域

本發明涉及智能交通領域，具體而言，尤其涉及一種基于強化學習的車輛路徑規劃方法。

背景技術

車輛路徑有效規劃是物流管理、公交與出租客運、以及從事相關領域運營等服務的重要環節，有助于提高運輸效率并降低成本。

Oriol Vinyals等(Vinyals O,Fortunato M,Jaitly N.Pointer networks[C]Advances in Neural Information Processing Systems.2015:2692-2700.)提出了一種簡單而有效的架構稱為Pointer Net來學習組合優化問題，該模型首次采用機器學習的方法來求組合優化問題，在sequence-to-sequence和Neural Turing Machines的基礎上使用神經注意機制解決了可變大小輸出字典的問題，并采用監督學習的方式來訓練模型，以純粹的數據驅動方法來學習計算難以處理的問題的近似解。

Irwan Bello等(Bello I,Pham H,Le Q V,et al.Neural combinatorialoptimization with reinforcement learning[J].arXiv preprint arXiv:1611.09940,2016.)改進了Vinyals等^[1]提出的指針網絡，提出了一種利用強化學習和神經網絡來解決組合優化問題的框架-神經組合優化，其中決策指針網絡由兩個長短期記憶網絡(LSTM)構成，采用Policy-gradient算法優化決策網絡。為將神經網絡作為解決組合優化問題的通用工具提供了一條有趣的研究途徑。

Khalil E等(Khalil E,Dai H,Zhang Y,et al.Learning combinatorialoptimization algorithms over graphs[C]Advances in Neural InformationProcessing Systems.2017:6348-6358.)提出了一個端到端的機器學習框架，稱為S2V-DQN，用于為圖上的NP-hard組合優化問題自動設計貪心啟發式算法，方法的核心是深度圖嵌入與強化學習的結合。框架主要由兩部分組成，首先采用Structure2Vec圖形嵌入網絡形嵌入網絡對當前的圖對當前的圖形結構進行編碼，采用采用強化學習中的Deep QLearning DQN算法進行訓練，優化決策網絡。學習策略的行為類似于逐步構建解決方案的元算法，其動作由圖形嵌入網絡在解決方案的當前狀態上確定。該框架的主要優點是充分利用了圖的結構來學習啟發式算法，學習得到的啟發式算法在相似的圖結構中可以通用。

上述提到的方法都是在已知模型的情況下進行求解的，即已知各個節點之間的二維歐幾里德距離。然而在現實配送中通常存在配送時間最短，或在規定時間內完成配送的目標。配送時間通常受到城市交通狀況的影響，而交通情況在每個時間段通常是變化的，即在每個時間段兩個節點之間的權重(時間)不是固定不變的，而且每天配送任務的目標節點數也是在某個范圍內動態變化的。現實中通常我們可以得到的是某個區域內配送過程中記錄的歷史數據，即從某個節點到某個節點在某個時間段花費了多長的時間，基于歷史配送數據采用機器學習的方法基于不同節點數來規劃配送路線，達到最小化配送時間的目標，上述方法不適用于此類問題的求解。

發明內容