劉虹慶 王世民

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

0 引 言

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

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

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

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

1 相關(guān)工作

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

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

2 模型設(shè)計

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

圖1 強化學習流程

2.1 小規(guī)模問題的時間差分模型

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

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

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

算法1T(s,a)

輸入：當前狀態(tài)s和選擇的節(jié)點a。

輸出：下一狀態(tài)s′。

1.s′=s;

3. ifa=0 then

5. else

9. end if

10. end if

11. returns′

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

(1)

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

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

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

算法2Sarsa

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

2. fori=1 toMdo

3. 初始化狀態(tài)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. 初始化值函數(shù)Q(s,a) episode次數(shù)M、初始狀態(tài)集Sinit?S、終止狀態(tài)集Send?S

2. fori=1 toMdo

3. 初始化狀態(tài)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

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

2.2 大規(guī)模問題的蒙特卡洛模型

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

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

算法4環(huán)境模型E

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

2. repeat

3. ifU? then

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

5. 從U中隨機選擇一節(jié)點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位置的值函數(shù)。策略D借鑒啟發(fā)式算法的思想，將s狀態(tài)下選擇動作a的概率定義為:

(3)

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

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

(4)

i=1,2,…,W

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

算法5MCRL

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

2. fori=1 toMdo

4. forj=1 toWdo

5. 使用環(huán)境模型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 仿真實驗與分析

實驗環(huán)境為Windows 10 64位操作系統(tǒng), Intel Core i5 處理器，8 GB RAM，實驗工具為Python 3.6。

3.1 小規(guī)模問題仿真實驗

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

圖2 Q-learning和Sarsa不同參數(shù)設(shè)定對比圖

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

3.2 大規(guī)模問題仿真實驗

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

表1 大規(guī)模問題實驗對比表

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

4 結(jié) 語

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