[發明專利]一種基于深度強化學習的動態路徑優化問題求解方法

有效

• 申請號: 202010855264.0
• 申請日: 2020-08-24
• 公開（公告）號: CN112116129B
• 公開（公告）日: 2022-11-01
• 發明（設計）人: 劉弘;張子臻
• 申請（專利權）人: 中山大學
• 主分類號: G06Q10/04
• 分類號: G06Q10/04;G06N20/00;G06Q10/08
• 代理公司: 廣州粵高專利商標代理有限公司 44102
• 代理人: 張金福

本發明公開了一種基于深度強化學習的動態路徑優化問題求解方法，包括以下步驟：S1：動態路徑優化問題定義；S2：構建深度強化學習框架，所述深度強化學習框架包括四個組成部分，分別為狀態、智能體、動作和獎勵，所述狀態包括所有顧客及所有點對之間預計所需要的通行時間，所述智能體在不同狀態下進行決策，得到對應的動作，所述動作為下一位訪問的顧客，所述獎勵為從倉庫點出發，訪問所有顧客后回到倉庫點所需要的時間；S3：利用深度強化學習框架得出優化后的路徑。本發明利用了深度強化學習算法，將動態路徑優化問題的動態環境嵌入到模型中，使得模型能感知到環境的動態變化，從而使其在極短時間內得到一個較優的解。

技術領域

本發明涉及運籌學領域中的車輛調度領域，更具體地，涉及一種基于深度強化學習的動態路徑優化問題求解方法。

背景技術

路徑優化問題是傳統的NP-complete組合優化問題，在物流調度行業中有著廣泛的應用。根據現實生活中實際約束的不同，又有多種不同的變種，如車輛路徑問題，提貨送貨問題等等。路徑優化問題的一個經典變種：動態路徑優化問題。

動態路徑優化問題定義在有向完全圖G＝(V，E)上，其中V代表點集，包含了1個倉庫點(0號點)、c位需要服務的顧客(用集合C表示)和n-c-1個可能需要服務的顧客的地點；E代表邊集。動態路徑優化問題是一個非對稱性問題，即問題不保證邊集E中方向相反的邊(i，j)與(j，i)長度相等。銷售員需要在一天的開始(t＝0)從倉庫點出發，然后訪問集合C中所有的顧客恰好一次(銷售員在訪問顧客后需立即出發前往下一個目的地)，最后回到倉庫點。任意兩點i，j之間所需要的通行時間，和當前時間t相關。即銷售員若在t＝t₀時刻從點i出發，目的地是點j，那么所需要的通行時間是g_ij(t₀)。其形式化定義如下：問題的目標為最小化旅行總時間，即min∑_i∈{0}∪c∑_j∈{0}∪cg_ij(s_i)x_ij，其中x_ij∈{0，1}。滿足每位顧客恰好被訪問一次(入度出度都為1)，即銷售員必須在t＝0時刻從倉庫點出發，即s₀＝0。銷售員必須在訪問完點i時，必須立刻出發去訪問下一個點j，且通行時間為g_ij(s_i)，即g_ij(s_i)x_ij＝(s_j-s_i)x_ij。

公開日為2018年05月18日，中國專利CN108053059A公開了一種運用基于重用策略的智能群體算法優化動態路徑優化問題的方法。傳統的路徑優化問題需要在一個靜態的搜索空間中找到一條代價最小的哈密頓回路。但實際上，現實世界中一些可以以路徑優化問題為模型的應用并不都是靜態的。它們的問題模型中的城市集合和權重矩陣是動態變化的。在動態環境中，上一次環境中搜索結果可以被新環境下的群體重用并得以學習。目前解決動態路徑優化問題的主要解法以啟發式算法為主，如遺傳算法、蟻群算法等。啟發式算法的優點在于能得到較優的解，而缺點在于所需運行時間過長。不適合用于求解動態路徑優化問題這類在線問題。

用于求解路徑優化問題的主要算法可以分為三類。第一類是精確算法，精確算法如分支定界法，分支切割法，列生成法等。這類算法的思路是遍歷所有解空間，并將不可能是最優解的空間舍棄。精確算法能找到問題的最優解，卻需要耗費極大量的搜索時間。第二類是啟發式算法，如鄰域搜索法、模擬退火、遺傳算法等等。啟發式算法。啟發式算法一般首先需要一個或一組最優解，之后迭代對這些解進行優化。第三類是構造算法如最近鄰法，最近插入法，最遠插入法等。構造算法根據問題特點，直接得到一個解，不需要對解進行優化。構造算法的運行速度快，而一般來說解的質量較低。

發明內容

本發明提供一種基于深度強化學習的動態路徑優化問題求解方法，快速高質量的獲得問題的最優解。

為解決上述技術問題，本發明的技術方案如下：