基于強化學習的車輛路徑規劃問題研究

劉虹慶 王世民

(北京工商大學計算機與信息工程學院 北京 100048)

0 引 言

車輛路徑規劃問題(Vehicle Routing Problem, VRP)于1959年由Dantzig等[1]提出。該問題定義在一定約束條件下(車載容量、客戶需求量、運輸過程等)尋求車輛的最優化行車路線，使得運輸成本最低或運輸距離最短。VRP問題是NP難問題[2]，也是運籌學和組合優化領域的研究熱點之一[3]。近年來，啟發式算法在求解大規模VRP問題中得到廣泛的應用和探索。在啟發式算法已得到成熟應用的背景下，本文從機器學習的全新角度出發，通過強化學習對車輛路徑規劃問題進行建模和求解值得探索。本文主要貢獻如下：

(1) 為求解小規模的車輛路徑規劃問題設計了時間差分模型。為減小狀態空間過大造成的存儲和計算消耗，采用了動態表更新的方法，設計貪婪獎懲機制以加快算法收斂速度，使用Sarsa和Q-learning兩個算法進行優化。

(2) 為求解大規模車輛路徑規劃問題設計了蒙特卡洛模型。借鑒啟發式算法的思想，設計了能夠有效模仿代理與環境交互的環境模型。使用環境模型采樣和蒙特卡洛更新優化代理策略和值函數。

(3) 在小規模算例和大規模算例上分別進行實驗，在小規模數據集上對時間差分模型的實驗結果及性能進行了分析和對比。同時在大規模數據集上將蒙特卡洛模型和傳統啟發式算法進行了實驗比較和分析。

1 相關工作

求解VRP問題的算法大致可分為精確算法和啟發式算法(包括元啟發式算法)兩類。其中精確算法能得到最優解，但計算復雜高，不適合用于求解大規模的VRP問題。啟發式算法又可分為基于鄰域的算法和種群法兩大類。基于鄰域的算法在搜索過程中維持單一解，通過在鄰域解之間按策略迭代尋求更優解。該類算法包括迭代局部搜索[4-5]、變鄰域搜索[6-8]、禁忌搜索[9-10]、大鄰域搜索[11]等。為避免陷入局部最優解，迭代局部搜索引入擾動機制通過擾動當前局部最優解產生新解。變鄰域搜索在不同鄰域之間切換并進行系統搜索，通過對局部最優解的擾動得到新的搜索起始點。禁忌搜索通過引入禁忌表和相應禁忌準則來避免迂回搜索。大鄰域搜索采用破壞與重建的思想擴大鄰域搜索空間以得到更優解。種群法則通過模仿生物的群體行為從解空間中尋求優化解，在搜索過程中能同時維持多個解。該類方法包括遺傳算法[12-13]、蟻群算法[14-15]、蜂群算法[16-17]、粒子群算法[18-19]、伊藤算法[20-22]等。遺傳算法通過模仿自然界的選擇與遺傳的機理來尋找最優解，是一種具有全局最優性的算法，但遺傳算法對初始種群的選擇有一定依賴性，且在求解大規模問題時收斂速度慢。蟻群算法、蜂群算法和粒子群算法通過模仿蟻群、蜂群和鳥類的群集智能行為來搜索最優解，有較好的并行性，收斂速度較快。但該類算法的性能依賴于參數的設定，且易陷入局部最優解。伊藤算法通過模仿粒子系統中的粒子相互碰撞與作用的動力學規律來進行算法設計與問題求解。該算法一般與蟻群算法或粒子群算法結合以解決收斂速度慢和局部最優的問題。

強化學習作為除監督學習、非監督學習之外的第三類機器學習方法，近年來受到越來越多的關注和應用。強化學習可以在沒有背景知識的情況下通過最大化長期回報來優化代理的行為策略，相比于其他機器學習方法，具有強大的自適應性。強化學習在路徑規劃任務上已經得到了廣泛的應用。文獻[23]提出一種監督式強化學習算法以解決強化學習收斂慢的問題。文獻[24]提出使用Q-learning解決無人駕駛船舶路徑規劃問題。文獻[25]提出使用勢能場知識作為啟發信息初始化Q值，以加快算法的收斂速度。文獻[26]采用RBF (Radial Basis Function) 網絡對Q學習算法的動作值函數進行逼近，并應用于智能車路徑規劃。文獻[27-29]將強化學習方法應用到機器人路徑規劃研究。

2 模型設計

VRP問題的詳細描述可參考文獻[1]。令V={v0,v1,…,vnu}表示運輸網絡節點，其中v0表示配送中心，vi(i≠0)表示第i個客戶所在位置，nu表示客戶的數量。用d(i,j)表示節點vi到vj的距離，當i=j時，d(i,j)=0。設每輛車的最大載重量為L,第i個客戶的貨物需求量為qi。強化學習維持一個Q表存儲值函數，以表示策略。每輪開始，代理通過當前策略選擇一個動作執行并得到環境的反饋，通過反饋更新Q表，如此循環往復，直至收斂。強化學習流程由圖1所示。接下來分別介紹小規模問題的時間差分模型和大規模問題的蒙特卡洛模型。

圖1 強化學習流程

2.1 小規模問題的時間差分模型

在小規模VRP問題中，將原問題中多個車輛從配送中心出發獨立完成配送并回到配送中心轉化為等價的單車輛經過多次往返完成配送(即僅有一個代理)的單代理強化學習問題。代理選擇下一步動作和代理當前的位置、載重量及各客戶的分配狀態有關。此時，強化學習的環境應包含以下信息：代理的位置、代理剩余載重量、客戶的配送狀態。狀態可用序列表示，具體地，任一狀態s∈S表示為s=(sloc,sload,s1,s2,…,snu)。其中：sloc∈{0,1,…,nu}表示代理在當前s狀態下所處的位置，若sloc=i(i≠0)，則表示代理當前處在vi客戶節點，sloc=0表示代理當前處在配送中心v0;0≤sload≤L是狀態s下代理剩余的載重量;si(i=1,2,…,nu)表示第i個客戶的配送狀態，若客戶i在s狀態下未被配送，則si=qi，反之，則si=0。

令A(s)表示在狀態下代理所有可能的動作，Q(s,a)表示狀態動作值函數，作為強化學習優化的目標。代理在當前環境下以一定策略選擇一個節點前進，其中a∈{0,1,…,nu}。將貪婪策略記為D(s)1，ε-貪婪策略記為D(s)2。

代理選擇一個動作同時會改變環境的狀態，將這個過程表示為狀態轉移函數T(s,a)=s′。狀態轉移函數涉及到代理位置的變更，載重量的變化，客戶分配狀態的變化，該過程由算法1描述。

算法1T(s,a)

輸入：當前狀態s和選擇的節點a。

輸出：下一狀態s′。

1.s′=s;

3. ifa=0 then

5. else

9. end if

10. end if

11. returns′

代理每執行一個動作會通過回報函數R(s,a)得到環境的反饋，以引導代理從試錯中學習。為加快算法的收斂速度，在回報函數中引入貪婪獎懲機制，對代理在不同情形下執行的動作給予不同的獎勵或懲罰：代理原地不動，則懲罰;代理每執行一次動作給予與其移動距離相當的懲罰;當代理到達一個未配送的客戶節點時給予獎勵，反之，則懲罰;當代理回到配送中心時完成了整個任務則獎勵。回報函數為:

(1)

式中：ρ為一個特定的獎勵值，被設定為網絡中最長路徑段的相反數，即ρ=-max(d(i,j))。

時間差分模型的目標是最大化值函數QD(s,a)：

以上模型可通過Sarsa和Q-learning進行單步更新求解，兩個算法的更新流程由算法2和算法3給出。

算法2Sarsa

1. 初始化值函數Q(s,a)、episode次數M、初始狀態集Sinit?S、終止狀態集Send?S

2. fori=1 toMdo

3. 初始化狀態s∈Sinit

4. 使用ε-貪婪策略從s中選擇a:a=Dact(s)2

5. repeat

6. Take actiona

7.s′=T(s,a),r′=R(s,a);

9.Q(s,a)←Q(s,a)+β[r′+αQ(s′,a′)-Q(s,a)];

10.s=s′,a=a′;

1. untils∈Send

12. end for

算法3Q-kearning

1. 初始化值函數Q(s,a) episode次數M、初始狀態集Sinit?S、終止狀態集Send?S

2. fori=1 toMdo

3. 初始化狀態s∈Sinit

4. repeat

5. 使用ε-貪婪策略從s中選擇a:a=Dact(s)2

6. Take actiona

7.s′=T(s,a),r′=R(s,a);

9.Q(s,a)←Q(s,a)+β[r′+αQ(s′,a′)-Q(s,a)];

10.s=s′;

1. untils∈Send

12. end for

同時，考慮到只有少量的狀態對于搜索最優解是有用的，采用動態表更新方法。當且僅當代理探索到一個新的狀態時，才將該狀態加入到狀態集合，并在Q表中增加該狀態的記錄。這樣可以避免由于狀態空間過大帶來的存儲空間和計算資源的消耗。

2.2 大規模問題的蒙特卡洛模型

由于狀態空間隨客戶點數量增加呈指數級增長，時間差分模型求解大規模VRP問題變得不實際。可通過構建模型，通過采樣模擬代理和環境的交互求解大規模問題：(1) 將可行解分解為多條以配送中心為起點和終點的路徑集合，記為H；(2) 最優解必定包含在所有可能的H的集合中；(3) 通過蒙特卡洛法搜索最優解，結合啟發式算法思想加快搜索速度。將H中的路徑記為h，長度記為d(h),則問題的目標是從找到路徑長度之和最小的H，即:

強化學習求解大規模VRP問題選擇合適的環境模型值得進一步研究。本文在環境模型中使用了啟發式函數，可在算法迭代過程中優化策略的同時不斷優化環境模型。將環境模型記為E，由算法4描述。

算法4環境模型E

1. 初始化未訪客戶集U={1，2，…，nu}、解集H={}、S狀態代理剩余載重量sload=L

2. repeat

3. ifU? then

4. 初始化一條子路徑h=(0)

5. 從U中隨機選擇一節點a

6.sload=sload-qa;

7. 將a加至子路徑h

8. 從U中移除a

9. repeat

11. ifsload≥qathen

12.sload=sload-qa;

13. 將a加至子路徑h

14. 從U中移除a

15. else

16. break

17. end if

18. until

19. 將0添加至子路徑h

20. 將0添加至子解集H

21. end if

22. until

23. returnH

(2)

令hsa表示從s到a的直連路徑，則式(2)中(s,a)表示路徑中含有hsa的所有H的集合，QD(s,a)表示在D策略下代理從s位置移動到a位置的值函數。策略D借鑒啟發式算法的思想，將s狀態下選擇動作a的概率定義為:

(3)

式中：λ和μ是模型的參數。λ控制模型的全局性，λ越大，則代理以越大的概率選擇當前Q(s,a)最大的動作執行。μ控制了模型的局部性，μ越大，則由d(s,a)引入的局部差異越大，模型偏向于更隨機地做出決策。

蒙特卡洛法從環境模型中采樣得到一組序列，其中有個序列含路徑段hsa，記為{H1,H2,…,Hw}。將值函數中的期望用均值近似，則有：

(4)

i=1,2,…,W

在實際計算時，使用一個計數表記錄所有的在采樣中出現過的次數，將W用C(s,a)替代，并且每采樣一個序列便更新相應的值函數QW(s,a)。蒙特卡洛模型(MCRL)由算法5描述。

算法5MCRL

1. 初始化值函數Q(s,a)=Qinit(s,a)、計數表C(s,a)=0、M、每一采樣時間的序列數量W

2. fori=1 toMdo

4. forj=1 toWdo

5. 使用環境模型E采樣一個episodeH

7. end for

9. for eachhinHdo

10. for each pair (s,a) inhdo

11.C(s,a)=C(s,a)+1;

13. end for

14. end for

15. end for

16. end for

3 仿真實驗與分析

實驗環境為Windows 10 64位操作系統, Intel Core i5 處理器，8 GB RAM，實驗工具為Python 3.6。

3.1 小規模問題仿真實驗

小規模問題仿真實驗選用文獻[34-37]的仿真數據樣例，該樣例包含8個客戶，配送中心有2輛車, 每輛的最大載重量為8噸，具體信息可參考文獻[30]。該問題已知最優解的路徑長度為67.5。Sarsa和Q-learning算法的實驗結果如圖2所示。

圖2 Q-learning和Sarsa不同參數設定對比圖

Q-learning和Sarsa均未使用環境模型，在優化的前期階段解，選擇動作的隨機性較強。Q-learning隨著更新輪數的增加，解的路徑長度下降速度相對于Sarsa快，展現了時間差分法優化速度快的特點和異步策略更新的優勢。當ε較大時，Q-learning更多地選擇隨機策略以探索可能的更優解，加快了收斂速度。但當ε過大時，算法對現有的最優解利用較少，隨機性過大大，算法將難以收斂到最優解。強化學習算法在合適的ε下具有近似的全局最優性，可避免在啟發式算法中容易出現的局部最優問題。

3.2 大規模問題仿真實驗

大規模問題選用文獻[34]中標準CVRP實例庫Set A中的算例進行測試。將MCRL算法和遺傳算法(GA)、粒子群算法(PSO)及蟻群算法(ACO)在不同測試數據下的結果進行對比,其中:GA[35]、PSO[39]的結果來源于文獻[31]，ACO使用文獻[36]的LNS-ACO算法的結果。各算法得到的最優解由表1給出。

表1 大規模問題實驗對比表

可以看出，MCR算法在A-n32-k5、A-n33-k5、A-n34-k5、A-n39-k6、A-n44-k6及A-n46-k7算例上都能達到最優解。在A-n60-k9和A-n80-k10算例上，MCRL算法的最優解均超過了GA和PSO，與LNS-ACO算法的最優解相當。MCRL算法結合了強化學習交互式學習的特性和啟發式函數快速收斂的優點，既能保證強化學習在大規模VRP問題上的有效應用，又能提高模型的容錯率、可擴展性和可交互性。同時，將強化學習和啟發式函數相結合的方法可應用在更多的規劃問題和組合優化問題中，相比于單純的啟發式算法有更廣的應用范圍。

4 結 語

引入強化學習研究車輛路徑規劃問題。從不同的問題規模出發，設計了使用Sarsa和Q-learning算法求解小規模問題的方法和使用蒙特卡洛模型求解大規模問題的方法。通過實驗測試了兩類方法在求解不同規模的VRP問題下的表現，并和現有的啟發式算法進行了對比，驗證了強化學習求解VRP問題的有效性，為研究車輛路徑規劃問題及相似的組合優化問題提供了新的思路。將強化學習的方法結合啟發式算法可以有效利用強化學習交互性學習的特性和啟發式算法快速收斂的優勢。下一步工作可考慮使用函數近似的方法代替表更新的方法，例如，通過引入神經網絡近似值函數，以梯度下降的方法更新網絡參數，以應對狀態空間過大的問題。