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

有效

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

1.一種基于深度強化學習的動態路徑優化問題求解方法，其特征在于，包括以下步驟：

S1：動態路徑優化問題定義：在有向完全圖G＝(V,E)上，其中V代表點集，包含了1個倉庫點、c位需要服務的顧客，用集合C表示，和n-c-1個可能需要服務的顧客的地點；E代表邊集，由于動態路徑優化問題是一個非對稱性問題，即不保證邊集E中方向相反的邊長度相等，求從倉庫點出發，然后訪問集合C中所有的顧客恰好一次，最后回到倉庫點的最小時間；

S2：構建深度強化學習框架，所述深度強化學習框架包括四個組成部分，分別為狀態、智能體、動作和獎勵，所述狀態包括所有顧客及所有點對之間預計所需要的通行時間，所述智能體在不同狀態下進行決策，得到對應的動作，所述動作為下一位訪問的顧客，所述獎勵為從倉庫點出發，訪問所有顧客后回到倉庫點所需要的時間；

S3：利用深度強化學習框架得出優化后的路徑；

步驟S2中所述狀態包括靜態部分和動態部分，其中，靜態部分包括每一位顧客的編號及在各時間片上每兩個點之間預計所需的通行時間，顧客的編號為每個顧客在數據集中出現次序，動態部分包括在某一特定時刻，每兩個點之間預計所需通行時間，以及每個點是否被訪問；

在各時間片上每兩個點之間預計所需的通行時間y_i通過地圖API查詢得到，在t時刻，每兩個點之間預計所需通行時間g_ij(t)通過對y_i進行三次樣條擬合得到；

每個點的訪問情況v_i(t)初始為1，若某位顧客在t時刻被訪問，則對于所有 t′＞t，都有v_i(t′)＝0；

所述智能體采用一個編碼解碼結構的注意力模型，由編碼器和解碼器組成，所述編碼器將所述狀態的靜態部分編碼至每個顧客的特征向量上，解碼器將所述狀態的動態部分編碼至中間向量，再將每位顧客的特征向量及中間向量解碼到每位顧客被選為下一位訪問顧客的概率p_i，之后，解碼器根據每位顧客的訪問狀況v_i(t)和概率p_i選擇下一位訪問的顧客j。

2.根據權利要求1所述的基于深度強化學習的動態路徑優化問題求解方法，其特征在于，所述編碼器由多個全連接神經網絡和一個多層自注意力網絡組成，所述解碼器由多個全連接神經網絡和一個單層自注意力網絡組成。

3.根據權利要求2所述的基于深度強化學習的動態路徑優化問題求解方法，其特征在于，所述智能體選擇完下一位訪問的顧客j后，當前時刻t需要加上當前路徑實際花費的通行時間f_lj(t)，其中l為上一位訪問的顧客，f_lj(t)＝g_lj(t)+Φ，式中，g_lj(t)為在t時刻，顧客l和顧客j之間預計所需的通行時間，Φ為一個服從正態分布的隨機變量。

4.根據權利要求3所述的基于深度強化學習的動態路徑優化問題求解方法，其特征在于，更新當前時刻的同時，狀態的動態部分也隨之被改變：重新獲得當前時刻的預計通行時間，并將訪問狀況中已經服務顧客對應的訪問情況設置為0，此時，解碼器將根據新的狀態進行下一輪的解碼。