強(qiáng)化學(xué)習(xí)在運(yùn)籌學(xué)的應(yīng)用：研究進(jìn)展與展望

徐翔斌， 李志鵬

(華東交通大學(xué) 交通運(yùn)輸與物流學(xué)院，江西 南昌 330013)

0 引言

強(qiáng)化學(xué)習(xí)(Reinforcement Learning,以下簡稱RL)，又稱增強(qiáng)學(xué)習(xí)，在運(yùn)籌與控制理論領(lǐng)域稱為近似動態(tài)規(guī)劃，是統(tǒng)計(jì)學(xué)、心理學(xué)、運(yùn)籌學(xué)、信息論以及計(jì)算機(jī)科學(xué)等多學(xué)科交叉綜合的一門學(xué)科。RL是機(jī)器學(xué)習(xí)的一個(gè)重要分支，它是基于Agent與環(huán)境進(jìn)行交互，并從環(huán)境中獲得信息獎(jiǎng)賞并映射到動作的一種學(xué)習(xí)方式[1]，其主要思想是Agent與環(huán)境不斷交互和試錯(cuò)，接收反饋信號來進(jìn)行優(yōu)化決策[2]。RL更接近于自然界生物學(xué)習(xí)的本質(zhì)，因而在很多領(lǐng)域取得了成功的應(yīng)用，包括游戲[3,4]、機(jī)器人控制[5]、自然語言處理[6]以及計(jì)算機(jī)視覺[7]等。特別地，基于RL與深度學(xué)習(xí)[8]融合的AlphaGo[9]與新一代AlphaGo Zero圍棋程序?qū)L的理論和應(yīng)用研究推向了一個(gè)新的高度。

本文對RL在運(yùn)籌優(yōu)化領(lǐng)域中的應(yīng)用進(jìn)行文獻(xiàn)綜述，首先簡單介紹RL的基本原理及其算法分類，其次闡述RL在運(yùn)籌優(yōu)化領(lǐng)域應(yīng)用的研究框架，然后對RL在運(yùn)籌優(yōu)化領(lǐng)域的應(yīng)用進(jìn)行總結(jié)與評述，主要包括庫存控制、路徑優(yōu)化、裝箱配載以及車間作業(yè)調(diào)度等幾個(gè)經(jīng)典運(yùn)籌學(xué)問題，最后對RL在該領(lǐng)域的應(yīng)用研究進(jìn)行展望，指出幾個(gè)需要重點(diǎn)關(guān)注的研究方向。

1 強(qiáng)化學(xué)習(xí)簡介

RL基本結(jié)構(gòu)如圖1所示，在每個(gè)時(shí)間步長內(nèi)，Agent感知環(huán)境狀態(tài)st，并根據(jù)既定的策略采取行動at，得到執(zhí)行at所獲得的立即獎(jiǎng)賞rt，同時(shí)使環(huán)境由狀態(tài)st轉(zhuǎn)換為st+1。RL的目的是讓Agent學(xué)習(xí)到一種策略，實(shí)現(xiàn)狀態(tài)到動作的映射，Agent在該策略的指導(dǎo)下行動，獲得最大的獎(jiǎng)賞[10]。

圖1 RL的基本結(jié)構(gòu)

RL主要用于解決序貫決策問題，根據(jù)外部環(huán)境是否完全可知，可分為基于模型(Model-Based)的RL算法和無模型(Model-Free)的RL算法[1]?；谀Ｐ偷腞L核心思想是動態(tài)規(guī)劃，其實(shí)質(zhì)是從過去的經(jīng)驗(yàn)中學(xué)習(xí)并建立環(huán)境模型，再依據(jù)模型計(jì)算出值函數(shù)，根據(jù)值函數(shù)的迭代方式不同，又可將其分為值迭代以及策略迭代算法；基于模型的RL還包括GPS(Guided Policy Search)[11]和PILCO(Probabilistic Inference for Learning Control)[12]等算法。無模型RL直接與外部環(huán)境進(jìn)行交互和試錯(cuò)，以此達(dá)到學(xué)習(xí)的目的，它主要分為基于值函數(shù)的RL和基于直接策略搜索的RL兩大類：其中基于值函數(shù)的RL包括基于表格型的算法(主要有Q-學(xué)習(xí)[13]、蒙特卡羅(MC)[10,14]以及時(shí)序差分法(TD)[15]等)和值函數(shù)近似的RL，而值函數(shù)近似又可分為線性近似和神經(jīng)網(wǎng)絡(luò)近似兩種，其中深度RL(Deep Reinforcement Learning，以下簡稱DRL)[16]主要有DQN[3,4](Deep Q Network，以下簡稱DQN)和RUDDER(Return Decomposition for Delayed Rewards)[17]等。而基于直接策略搜索的RL主要包括REINFORCE[18]、演員-評論家(AC)[19]以及異步演員-評論家(A3C)[20]等算法，RL算法分類如圖2所示。

圖2 RL算法分類

2 基于強(qiáng)化學(xué)習(xí)的運(yùn)籌學(xué)研究框架

傳統(tǒng)運(yùn)籌學(xué)的研究方法通常分為兩步：首先建立待求問題的數(shù)學(xué)模型，包括目標(biāo)函數(shù)和約束條件等；其次設(shè)計(jì)算法求解該模型，如分支定界[21]、禁忌搜索[22]以及遺傳算法[23,24]等。對于大規(guī)模復(fù)雜系統(tǒng)來說，傳統(tǒng)運(yùn)籌學(xué)研究方法存在以下幾個(gè)方面的問題：(1)難以建立精確有效的數(shù)學(xué)模型，或者即使建立了數(shù)學(xué)模型，也是對實(shí)際問題的理想化處理；(2)無法解決較大規(guī)模問題，因?yàn)殡S著問題規(guī)模的增大會出現(xiàn)“組合爆炸”現(xiàn)象，計(jì)算的時(shí)間和空間復(fù)雜度呈指數(shù)級增長；(3)只能求解靜態(tài)確定性問題，難以考慮動態(tài)及隨機(jī)因素。

馬爾可夫決策過程(MDP)[25]是解決多階段序貫決策問題的重要方法，馬爾可夫特性是指系統(tǒng)的下一個(gè)狀態(tài)只與當(dāng)前狀態(tài)信息有關(guān)，而與更早之前的狀態(tài)無關(guān)。RL將運(yùn)籌學(xué)領(lǐng)域的序貫決策問題建模為MDP并進(jìn)行求解。MDP將待求解問題定義為一個(gè)六元組(S,A,P,R,γ,π),其中：S代表Agent的狀態(tài)集合，st∈S表示Agent在t時(shí)刻所處的狀態(tài)；A代表Agent可取的動作集合，at∈A表示Agent在t時(shí)刻采取的行動；P代表狀態(tài)轉(zhuǎn)移概率,P(st+1|st,at) 是Agent在st∈S狀態(tài)下，執(zhí)行動作at后，轉(zhuǎn)移到下一狀態(tài)st+1的概率；R代表獎(jiǎng)賞函數(shù)，rt代表t時(shí)刻采取行動at獲得的立即獎(jiǎng)賞；γ代表折扣因子，用來計(jì)算累計(jì)獎(jiǎng)賞，其中γ∈[0,1]；π表示策略，RL學(xué)習(xí)的目標(biāo)是讓Agent學(xué)習(xí)得到一個(gè)最優(yōu)策略π*，使其累計(jì)獎(jiǎng)賞最大；RL用狀態(tài)值函數(shù)V(s)或動作值函數(shù)Q(s,a)來衡量策略的優(yōu)劣，采用動態(tài)Bellman公式對V(s)或Q(s,a)進(jìn)行求解，如公式(1)和(2)所示。

Vπ(s)=Eπ[rt+1+γVπ(st+1)|st=s]

(1)

Qπ(s,a)=Eπ[rt+1+γQπ(st+1,at+1)|st=s,at=a]

(2)

RL能較好地克服傳統(tǒng)運(yùn)籌學(xué)建模方法的缺點(diǎn)：(1)在建模難、建模不準(zhǔn)確的問題方面，RL可以通過Agent與環(huán)境的不斷交互，學(xué)習(xí)到最優(yōu)策略；(2)在傳統(tǒng)方法難以解決高維度的問題方面，RL提供了包括值函數(shù)近似以及直接策略搜索等近似算法；(3)在難以求解動態(tài)與隨機(jī)型問題方面，RL可在Agent與環(huán)境之間的交互以及狀態(tài)轉(zhuǎn)移過程中加入隨機(jī)因素。RL的這些優(yōu)點(diǎn)使得其適合求解運(yùn)籌學(xué)領(lǐng)域的大規(guī)模動態(tài)、隨機(jī)決策問題，如庫存控制、路徑優(yōu)化、裝箱配載以及車間作業(yè)調(diào)度等問題，為運(yùn)籌優(yōu)化的研究提供一個(gè)新視角。

3 強(qiáng)化學(xué)習(xí)在運(yùn)籌學(xué)中的應(yīng)用

3.1 庫存控制

庫存控制的核心內(nèi)容包括訂貨時(shí)間、訂貨數(shù)量以及庫存水平等，其目的是在降低庫存的同時(shí)保證較高的客戶服務(wù)水平。實(shí)際庫存控制存在很大的不確定性，如客戶需求或訂貨提前期動態(tài)變化，特別地，在多階段供應(yīng)鏈庫存決策中，由于供應(yīng)鏈不協(xié)調(diào)容易造成“牛鞭”效應(yīng)，傳統(tǒng)的運(yùn)籌優(yōu)化方法難以優(yōu)化這類動態(tài)隨機(jī)型庫存控制問題。

庫存控制是一個(gè)典型的多階段序貫決策問題，在兩階段供應(yīng)鏈庫存決策方面，Van Roy[26]等早在1997年就將RL運(yùn)用于兩階段單一產(chǎn)品零售商庫存問題，并利用近似策略迭代算法與TD算法進(jìn)行求解，結(jié)果顯示該算法比傳統(tǒng)啟發(fā)式算法減少了10%左右的平均庫存成本。在此基礎(chǔ)上，Kim[27,28]等提出兩階段供應(yīng)鏈的自適應(yīng)庫存控制模型(集中式控制模型與分散式控制模型)，并設(shè)計(jì)了同步和異步獎(jiǎng)賞學(xué)習(xí)算法，結(jié)果表明該算法在兩種模型中均比傳統(tǒng)算法花費(fèi)更少的庫存成本，并且在運(yùn)行速度方面，異步算法要比同步動作獎(jiǎng)賞學(xué)習(xí)更快。Kwon[29]和Jiang[30]等將基于案例的推理技術(shù)與RL結(jié)合起來，用于處理較大狀態(tài)空間非穩(wěn)定需求的庫存控制問題；Giannoccaro[31]更進(jìn)一步將兩階段庫存決策模型擴(kuò)展至包括供應(yīng)商、制造商及分銷商的三階段模型，假定需求服從指數(shù)分布，同時(shí)考慮了訂貨成本、持有成本、缺貨成本及渠道成本，提出了一種名為SMART的平均獎(jiǎng)賞算法來求解模型；隨后Chaharsooghi[32]、Tongeren[33]以及Mortazavi[34]等以“啤酒游戲”為背景，構(gòu)建了由零售商、分銷商、批發(fā)商以及制造商組成的四階段供應(yīng)鏈模型，考慮動態(tài)交貨期以及非穩(wěn)定客戶需求，利用Q-學(xué)習(xí)方法來求解最優(yōu)庫存控制策略，結(jié)果表明該算法能更好地解決復(fù)雜環(huán)境下的庫存決策問題。

特別地，Oroojlooyjadid[35]等將最新的DQN算法引入“啤酒游戲”并開發(fā)了一種反饋機(jī)制下的合作框架，并利用遷移學(xué)習(xí)[36]實(shí)現(xiàn)Agent之間的知識轉(zhuǎn)移，仿真結(jié)果顯示當(dāng)零售商、分銷商、批發(fā)商和制造商中的一種角色使用DQN算法，其他角色使用strm-BS策略時(shí)，基于DQN算法的庫存成本都低于strm-BS策略，并且在DQN算法中引入遷移學(xué)習(xí)時(shí)，運(yùn)行時(shí)間可縮短94.6%，這表明DQN算法在庫存控制應(yīng)用中的有效性，特別是加入遷移學(xué)習(xí)的DQN算法求解效率更高。在此基礎(chǔ)上，Gijsbrechts[37]等將A3C算法應(yīng)用于雙源采購庫存決策問題，并引入具有實(shí)際訂單大小及成本參數(shù)的真實(shí)數(shù)據(jù)集進(jìn)行測試，結(jié)果顯示在不需要任何啟發(fā)式算法的情況下，A3C算法計(jì)算得到的庫存成本與最優(yōu)成本的差距在6%～7%，接近于最優(yōu)解。

此外，Valluri[38]和Sun[39]利用RL研究了由客戶、零售商、批發(fā)商、分銷商和供應(yīng)商構(gòu)成的五階段供應(yīng)鏈模型，在此基礎(chǔ)上，Kim[40]等將供應(yīng)鏈模型由多階段擴(kuò)展至N階段，其中第一階段為零售商，其余階段均為供應(yīng)商，提出了一種多主體協(xié)同需求估計(jì)協(xié)議和分布式的動作獎(jiǎng)賞學(xué)習(xí)技術(shù)。另外還有學(xué)者研究了供應(yīng)商管理庫存(VMI)模式下庫存控制問題，Kwak[41]等提出了收斂速度更快的回顧性行動獎(jiǎng)賞算法，Yang[42]等用Q-學(xué)習(xí)算法選擇合適的安全庫存以應(yīng)對非穩(wěn)定性需求，同時(shí)還對需求預(yù)測過程中的牛鞭效應(yīng)進(jìn)行了分析。Zheng[43]等基于RL研究了一種由供應(yīng)商保留零售商庫存所有權(quán)，在零售商銷售商品之前庫存成本由供應(yīng)商承擔(dān)的VMI補(bǔ)貨策略。此外，Katanyukul[44]等基于GARCH(1,1)庫存模型對Sarsa[45]算法與rollout策略[46]進(jìn)行了比較分析，結(jié)果表明在持有成本與缺貨成本比率較高時(shí)，rollout策略更適用于該類問題的求解。值得注意的是，Kara[47]等運(yùn)用RL解決了考慮產(chǎn)品壽命的單階段庫存決策問題，以總庫存成本最小化為目標(biāo)，分別用Sarsa、Q-學(xué)習(xí)算法與遺傳算法進(jìn)行比較分析，實(shí)驗(yàn)表明在客戶需求變化大、產(chǎn)品壽命短的情況下，使用RL進(jìn)行學(xué)習(xí)可以獲得更好的結(jié)果。典型的基于RL的庫存決策文獻(xiàn)統(tǒng)計(jì)如表1所示。

總的來說，RL在供應(yīng)鏈庫存控制問題的研究成果豐碩，RL可充分考慮庫存決策過程中的多階段序貫決策和不確定性，進(jìn)而求解非平穩(wěn)需求下庫存控制問題。但目前大多數(shù)文獻(xiàn)仍然采用Q-學(xué)習(xí)、TD算法等傳統(tǒng)表格型算法求解，此類算法在收斂速度以及收斂性方面都表現(xiàn)得很不穩(wěn)定，特別是在問題比較復(fù)雜或規(guī)模較大的情況下，會出現(xiàn)“維數(shù)災(zāi)難”而無法求解，需研究可自動提取庫存系統(tǒng)關(guān)鍵特征的高效算法。

表1 RL應(yīng)用于庫存決策文獻(xiàn)匯總

3.2 路徑優(yōu)化

路徑優(yōu)化主要包括旅行商問題(TSP)和車輛路徑問題(VRP)[48]，都是經(jīng)典的NP-hard組合優(yōu)化問題[49]，傳統(tǒng)的運(yùn)籌優(yōu)化方法難以求解不確定性路徑優(yōu)化問題，路徑優(yōu)化問題的“不確定性”主要體現(xiàn)在信息演變和信息質(zhì)量變化[50]這兩個(gè)方面。信息演變是指決策者掌握的某些信息有可能會在實(shí)際中隨時(shí)間發(fā)生變化，比如車輛旅行時(shí)間受實(shí)時(shí)交通路況影響隨時(shí)發(fā)生變化以及在配送服務(wù)時(shí)可能有新的顧客產(chǎn)生新的需求等；而信息質(zhì)量變化是指某些信息存在不確定性，比如決策者只能得知顧客的實(shí)際需求是按照某種概率分布存在但無法明確預(yù)知客戶的需求。學(xué)者們將前者稱為動態(tài)路徑優(yōu)化問題，后者稱為隨機(jī)路徑優(yōu)化問題，路徑優(yōu)化問題也是典型的多階段序貫決策問題，可以利用RL進(jìn)行求解。

3.2.1 旅行商問題(TSP)

已有學(xué)者運(yùn)用RL對動態(tài)隨機(jī)型TSP問題進(jìn)行研究，Secomandi[51]將基于啟發(fā)式的rollout策略應(yīng)用于考慮隨機(jī)旅行時(shí)間的TSP問題，仿真表明該策略的求解結(jié)果優(yōu)于循環(huán)啟發(fā)式算法，Toriello[52]等研究了隨機(jī)成本的動態(tài)TSP問題，將其建模為近似動態(tài)規(guī)劃模型，提出了一種價(jià)格導(dǎo)向的rollout策略。然而，一般RL算法只能解決特定的具體問題，Bello[53]等指出可以用神經(jīng)網(wǎng)絡(luò)與RL結(jié)合的框架來求解TSP問題，并提出了基于策略梯度的兩種變體方法：一種是帶提前訓(xùn)練的RL，利用期望回報(bào)作為目標(biāo)函數(shù)，使用與A3C[20]相類似的訓(xùn)練算法對指針網(wǎng)絡(luò)[54]進(jìn)行優(yōu)化，另一種是主動搜索，不需要提前訓(xùn)練，仿真測試結(jié)果顯示該方法在三種不同規(guī)模下的TSP問題均優(yōu)于監(jiān)督學(xué)習(xí)算法以及啟發(fā)式算法，并且該方法的求解結(jié)果與最優(yōu)解的差距均在1%以內(nèi)。在此基礎(chǔ)上，Dai[55]等進(jìn)一步指出同一類型的組合優(yōu)化問題具有相同的結(jié)構(gòu)，只是在具體問題中的數(shù)據(jù)表現(xiàn)不同，于是提出了一種利用RL與圖嵌入網(wǎng)絡(luò)相組合的端到端的學(xué)習(xí)框架，具體來說，以圖形嵌入網(wǎng)絡(luò)來表示優(yōu)化策略，并運(yùn)用NFQ(Neural Fitted Q Iteration)[56]與多步Q-學(xué)習(xí)[10]組合的方式來學(xué)習(xí)，以最小頂點(diǎn)覆蓋問題、最大切割問題以及TSP問題為例進(jìn)行實(shí)驗(yàn)，結(jié)果表明該框架可以應(yīng)用于各類組合優(yōu)化問題，并且該框架在求解1200個(gè)節(jié)點(diǎn)的TSP問題時(shí)，與最優(yōu)解的差距在10%左右，具有較好的泛化能力[57]。隨后Emami[58]等又提出了一種基于Sinkhorn[59]策略梯度和AC結(jié)合的RL算法來求解TSP問題。值得關(guān)注的是，Kool[60]和Deudon[61]等在文獻(xiàn)[53]的基礎(chǔ)上進(jìn)一步進(jìn)行研究，將深度學(xué)習(xí)中的注意力機(jī)制引入了RL算法用于求解TSP問題，利用REINFORCE[18]算法對確定性最優(yōu)策略進(jìn)行訓(xùn)練，該方法在TSP20/50/100問題的測試結(jié)果與最優(yōu)解差距分別為0.32%、1.71%和4.43%，求解質(zhì)量很高，并在同等條件下比文獻(xiàn)[53]更快收斂?？偟膩碚f，利用RL研究TSP問題具有很大的潛力。典型的RL在TSP問題中的應(yīng)用文獻(xiàn)統(tǒng)計(jì)如表2所示。

表2 RL應(yīng)用于TSP問題文獻(xiàn)匯總

3.2.2 車輛路徑問題(VRP)

與傳統(tǒng)運(yùn)籌優(yōu)化方法相比，RL更適合求解不確定的動態(tài)VRP問題，動態(tài)VRP問題主要包括：(1)隨機(jī)客戶需求VRP(VRPSD)，指的是在服務(wù)之前無法得知客戶真實(shí)需求量，只有到達(dá)客戶的位置，才可得知需求量；(2)隨機(jī)客戶請求VRP(VRPSR)，指的是在服務(wù)的過程中，可能會出現(xiàn)無法預(yù)期的潛在客戶請求，這些客戶可能在不同的時(shí)間和地點(diǎn)出現(xiàn)；(3)隨機(jī)服務(wù)時(shí)間VRP(VRPST)，指的是客戶服務(wù)時(shí)間的不確定性。傳統(tǒng)運(yùn)籌學(xué)方法在求解VRPSD時(shí)一般采用兩階段先驗(yàn)路徑的方法[21,62]，首先在未知顧客需求的情況下設(shè)計(jì)好預(yù)定路線，然后在顧客需求逐漸已知的過程中，再進(jìn)一步調(diào)整該路線。鑒于傳統(tǒng)的方法難以考慮問題的實(shí)時(shí)性，諸多學(xué)者開始用RL來求解VRPSD，Dror[63]最先將VRPSD建模為MDP，但并未給出計(jì)算實(shí)例。由于rollout策略可在基本啟發(fā)式算法的基礎(chǔ)上得到最優(yōu)值函數(shù)，學(xué)者們更多地利用該策略來求解VRPSD，Secomandi[64]以最小化最短距離期望為目標(biāo)函數(shù)，分別比較了樂觀近似策略迭代與rollout策略這兩種策略的RL算法在單一車輛VRPSD中的表現(xiàn)，結(jié)果表明后者比前者更為健壯。Novoa[65]等將rollout策略由一步更新拓展至兩步更新，在保證解的質(zhì)量前提下，用MC算法來計(jì)算更新后的基策略的期望成本，以此大幅減少計(jì)算時(shí)間。為進(jìn)一步減輕rollout策略的計(jì)算量，Goodson[66]和Bertazzi[67]等將前向動態(tài)規(guī)劃以及可變鄰域搜索技術(shù)(VNS)[68]嵌入rollout策略，F(xiàn)an[69]則提出以先驗(yàn)路徑與rollout策略相結(jié)合的方式來求解多車輛VRPSD。

還有學(xué)者利用其它RL算法對VRPSD進(jìn)行求解，婁山佐[70]等構(gòu)建了徑向基網(wǎng)絡(luò)模型，利用最小二乘時(shí)序差分法(LSTD)確定權(quán)系數(shù)，交叉熵確定隱含層參數(shù)的方法來求解VRPSD問題，Zhang[71]等以基于有界表格查找的改進(jìn)Q-學(xué)習(xí)算法來求解VRPSD，結(jié)果表明該算法在求解質(zhì)量與計(jì)算時(shí)間兩方面都要優(yōu)于rollout策略。值得一提的是，Nazari[72]等將文獻(xiàn)[53]提出的RL優(yōu)化框架推廣應(yīng)用于需求可拆分VRP問題，并以循環(huán)神經(jīng)網(wǎng)絡(luò)結(jié)合注意力機(jī)制的方式代替指針網(wǎng)絡(luò)來增強(qiáng)該框架的魯棒性，通過與Clarke-Wright節(jié)約法以及Google’s OR工具比較發(fā)現(xiàn)，該算法求解結(jié)果接近于最優(yōu)解，其中在VRP10以及VRP20問題中，該方法與最優(yōu)解的差距分別處于10%和13%以內(nèi)，在此基礎(chǔ)上，Kool[60]等繼續(xù)改進(jìn)帶注意力機(jī)制的DRL算法，并將其應(yīng)用于上述問題，所得結(jié)果與最優(yōu)解差距均處于5%以內(nèi)，且均優(yōu)于文獻(xiàn)[72]的測試結(jié)果。

也有學(xué)者利用RL研究VRPSR和VRPST問題，Meisel[73]等以固定時(shí)間內(nèi)最大化服務(wù)客戶數(shù)量為目標(biāo)，將客戶分為必須服務(wù)的客戶和隨機(jī)出現(xiàn)的客戶兩部分，利用RL求解VRPSR。Ulmer等[74,75]將rollout算法用于求解VRPSR，還有學(xué)者利用基于動態(tài)表格查找的RL算法研究VRPSR，文獻(xiàn)[76]將動態(tài)表格查找的方法運(yùn)用于多周期的VRPSR中。RL在VRPST中的應(yīng)用主要集中在緊急醫(yī)療領(lǐng)域，這類VRP問題的隨機(jī)服務(wù)時(shí)間主要是指救護(hù)車到達(dá)救護(hù)現(xiàn)場對病人進(jìn)行預(yù)處理的時(shí)間，譬如文獻(xiàn)[77,78]研究了考慮隨機(jī)服務(wù)時(shí)間的救護(hù)車調(diào)度部署問題。典型的RL在VRP問題中的應(yīng)用文獻(xiàn)統(tǒng)計(jì)如表3所示。

綜上所述，相對傳統(tǒng)的運(yùn)籌優(yōu)化方法，RL在解決隨機(jī)、動態(tài)的車輛路徑問題具有一定的優(yōu)勢。但是當(dāng)前研究也存在一些問題，比如RL對考慮單一隨機(jī)因素的動態(tài)VRP問題的研究較多，但是對考慮多重隨機(jī)因素的VRP問題的研究較少，此外大多數(shù)文獻(xiàn)并未考慮車輛的異質(zhì)性，并且在算法方面，大部分文獻(xiàn)局限于采用rollout策略或基于表格型的RL算法進(jìn)行研究。

表3 RL在VRP問題中的應(yīng)用文獻(xiàn)匯總

3.3 裝箱配載

有關(guān)背包問題[79]和裝箱配載問題[80]的研究成果頗豐，但大多都集中在精確算法[81]以及啟發(fā)式算法[82]。背包和裝箱配載也可視為序貫決策問題，Kleywegt[83]等定義并研究了一類具有相同物品尺寸的動態(tài)隨機(jī)背包問題，隨后又將其拓展至物品大小隨機(jī)的背包問題，并將其建模為MDP，在以最大化價(jià)值為目標(biāo)的情況下，分別研究了該算法在有限時(shí)域和無限時(shí)域下隨機(jī)背包問題的表現(xiàn)，并得到了最優(yōu)裝箱策略[84]。Mastin[85]通過對rollout策略與基策略在背包問題的表現(xiàn)進(jìn)行比較分析，發(fā)現(xiàn)rollout策略嚴(yán)格優(yōu)于基策略，Bello[53]等還利用基于指針網(wǎng)絡(luò)與RL結(jié)合的框架求解三種規(guī)模的背包問題，結(jié)果顯示基于預(yù)先訓(xùn)練的RL的算法與最優(yōu)解的差距在1%以內(nèi)，且基于主動搜索的RL算法可求得最優(yōu)解。Kong[86]等嘗試構(gòu)建基于RL求解線性組合優(yōu)化問題的統(tǒng)一框架，并以背包問題為例求解，結(jié)果與最優(yōu)解差距小于5%。值得一提的是，Bertsimas[87]等以多維背包問題為背景，提出了參數(shù)化及非參數(shù)化的近似值函數(shù)的RL方法，并檢驗(yàn)其在大規(guī)模整數(shù)規(guī)劃問題上的可行性，實(shí)驗(yàn)表明其能在較短時(shí)間內(nèi)得到比遺傳算法、CPLEX求解器更好的解。Perry[88]等利用隨機(jī)動態(tài)規(guī)劃來求解動態(tài)隨機(jī)多重背包的多周期資源配置問題，Hua[89]等利用RL研究了二次背包問題，并引入兩種啟發(fā)式算法來近似值函數(shù)，另外，Goodson[90]等提出了一種基于rollout的策略框架，并利用隨機(jī)動態(tài)多重背包問題驗(yàn)證了框架的有效性。

經(jīng)典裝箱問題以最小化箱子數(shù)量為優(yōu)化目標(biāo)，而Hu[91]等以最小化箱子表面積為優(yōu)化目標(biāo)，首次將DRL引入三維裝箱問題，考慮物品的裝入順序、裝入方向以及箱子的空余空間等因素對表面積的影響，設(shè)計(jì)了一種啟發(fā)式算法來對物品的裝入方向及箱子的剩余空間進(jìn)行遍歷搜索，并用基于指針網(wǎng)絡(luò)[54]的DRL框架選擇物品的裝入順序，該方法計(jì)算得到箱子表面積該比啟發(fā)式算法少5%左右，且與最優(yōu)解的差距在6%以內(nèi)。在此基礎(chǔ)上，文獻(xiàn)[92]進(jìn)一步提出一種基于多任務(wù)選擇學(xué)習(xí)的框架，并引入了深度學(xué)習(xí)的注意力機(jī)制，在BIN10和BIN12的仿真實(shí)驗(yàn)中，求解結(jié)果優(yōu)于傳統(tǒng)DRL和啟發(fā)式算法。最近，Laterre[93]等設(shè)計(jì)了一種基于獎(jiǎng)勵(lì)排序(Ranked Reward)的算法應(yīng)用于二維裝箱問題，并以最小化裝入物品邊界為優(yōu)化目標(biāo)，利用深度神經(jīng)網(wǎng)絡(luò)以及蒙特卡羅樹搜索(MCTS)[94]進(jìn)行策略評估與策略改善，該算法的核心思想在于使用最近的獎(jiǎng)賞進(jìn)行排名，只有超過最新的最優(yōu)解才能獲得獎(jiǎng)賞，以此自我提升訓(xùn)練的難度，在一定程度上緩解了對訓(xùn)練數(shù)據(jù)的需求，求解結(jié)果優(yōu)于MCTS、監(jiān)督學(xué)習(xí)和A3C等算法，并在排序比例為75%時(shí)，測試效果最優(yōu)。典型的RL求解裝箱配載問題的文獻(xiàn)統(tǒng)計(jì)如表4所示。

盡管很多文獻(xiàn)利用RL研究經(jīng)典0-1背包、多維背包以及多重背包等更復(fù)雜的背包問題，但是較少考慮物品的重量、價(jià)值和尺寸等隨機(jī)因素對裝箱問題的影響，并且較少文獻(xiàn)利用RL解決裝箱與車輛路徑協(xié)同優(yōu)化問題。此外在算法方面，大多文獻(xiàn)仍使用傳統(tǒng)的值函數(shù)近似算法對問題進(jìn)行求解。

表4 RL在裝箱配載問題中的應(yīng)用文獻(xiàn)匯總

3.4 車間作業(yè)調(diào)度(JSP)

JSP問題也是典型的序貫決策問題，根據(jù)調(diào)度環(huán)境的不同，JSP問題可分為靜態(tài)JSP問題和動態(tài)JSP問題。Zhang[95]等很早就將RL引入到NASA航天飛機(jī)的生產(chǎn)調(diào)度JSP問題中，提出了一種新的基于迭代修復(fù)的方法，利用TD(λ)對狀態(tài)值函數(shù)進(jìn)行估計(jì)并使用隨機(jī)貪婪策略選擇動作。然而工件和機(jī)器的多樣性以及機(jī)器故障等隨機(jī)因素導(dǎo)致實(shí)際調(diào)度環(huán)境是實(shí)時(shí)動態(tài)變化的，因此相對于靜態(tài)JSP問題，RL更多被用于求解這類動態(tài)隨機(jī)的JSP問題，Riedmiller[96]等利用基于神經(jīng)網(wǎng)絡(luò)的RL來求解最小化總延遲的JSP問題，結(jié)果表明該方法能夠在短時(shí)間內(nèi)得到較為滿意的近似解；在此基礎(chǔ)上，Aydin[97]等應(yīng)用改進(jìn)的Q-學(xué)習(xí)算法來求解由仿真環(huán)境和Agent兩部分組成的動態(tài)JSP問題。此外，還有學(xué)者將Q-學(xué)習(xí)與其它方法相結(jié)合來研究動態(tài)JSP問題，魏英姿[98]和Chen[99]等分別提出了多目標(biāo)多機(jī)器的組合調(diào)度規(guī)則，隨后魏英姿[100]又研究基于遺傳算法與Q-學(xué)習(xí)機(jī)制相結(jié)合的RL方法，來平衡RL學(xué)習(xí)過程中的“利用”與“探索”。特別地，Shahrabi[101]等將VNS[68]引入考慮作業(yè)隨機(jī)到達(dá)與機(jī)器故障的動態(tài)JSP問題，利用Q-學(xué)習(xí)算法來得到合適的VNS參數(shù)以更新優(yōu)化策略。由于單Agent方法難以求解大規(guī)模復(fù)雜JSP問題，學(xué)者們又將基于多Agent分散決策融入JSP問題的研究中，在分散化決策的前提下，每個(gè)Agent都遵循各自的策略求解一部分子系統(tǒng)調(diào)度決策，再通過Agent之間的溝通機(jī)制協(xié)調(diào)各部分決策，以達(dá)到整體最優(yōu)，研究表明分散式?jīng)Q策可應(yīng)對調(diào)度過程中的突發(fā)情況，大大提高了JSP調(diào)度系統(tǒng)的健壯性[102～104]。

值得注意的是，Mao[105]等利用DRL框架對計(jì)算集群中的JSP問題進(jìn)行了研究，并以最小化遲交率(Job Slowdown)為優(yōu)化目標(biāo)，利用改進(jìn)的REINFORCE算法對神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練，仿真結(jié)果顯示，當(dāng)平均集群負(fù)載率為190%且作業(yè)規(guī)模為10時(shí)，基于DRL框架的平均遲交率為5左右，遠(yuǎn)低于其它算法；此后有許多學(xué)者在此基礎(chǔ)上進(jìn)行改進(jìn)，拓展DRL框架在JSP問題上的應(yīng)用研究，Chen[106]等將其拓展為多資源多機(jī)器JSP問題，并在獎(jiǎng)賞的設(shè)置以及特征提取這兩個(gè)方面對模型進(jìn)行了改進(jìn)，該模型所得的平均遲交率相較于文獻(xiàn)[105]又降低了8.57%，并當(dāng)輸入層使用卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行特征提取時(shí)，雖然平均遲交率降低幅度有所減少，但算法收斂速度有所提升。Waschneck[107]等也嘗試?yán)肈QN優(yōu)化半導(dǎo)體制造企業(yè)的生產(chǎn)調(diào)度問題，為縮短訓(xùn)練時(shí)間以及保證訓(xùn)練的穩(wěn)定性，采用兩階段的訓(xùn)練方式對Agent進(jìn)行訓(xùn)練。最近，Chen[108]等提出將JSP問題表述為重寫(rewrite)問題，其思路是通過不斷迭代現(xiàn)有解決方案以至最優(yōu)，用A3C算法對重寫器進(jìn)行訓(xùn)練，結(jié)果顯示基于重寫的DRL求解得到的平均遲交率比文獻(xiàn)[105]中的算法減少50%以上。

此外也有學(xué)者利用Q-學(xué)習(xí)對單機(jī)JSP問題進(jìn)行研究，Wang[109]等以最小化平均延遲時(shí)間為優(yōu)化目標(biāo)對單機(jī)JSP問題的選擇調(diào)度規(guī)則進(jìn)行研究。在此基礎(chǔ)上，王世進(jìn)[110]等利用Q-學(xué)習(xí)研究了的三種調(diào)度規(guī)則的動態(tài)JSP問題，結(jié)果表明Q-學(xué)習(xí)方法能提高Agent的適應(yīng)能力，Xanthopoulos[111]等利用RL研究了隨機(jī)加工時(shí)間和完工時(shí)間的JSP問題，并對15種調(diào)度規(guī)則進(jìn)行了測試。針對Q-學(xué)習(xí)方法在“維數(shù)災(zāi)”問題上的局限性，王國磊[112]提出一種基于系統(tǒng)狀態(tài)聚類的Q-學(xué)習(xí)方法來求解動態(tài)單機(jī)JSP問題，結(jié)果表明該算法可有效地降低系統(tǒng)狀態(tài)的維數(shù)并提高收斂速度。典型的基于RL的車間作業(yè)調(diào)度問題中的文獻(xiàn)如表5所示。

利用RL的JSP問題研究成果頗豐，已有的文獻(xiàn)充分考慮了JSP問題的隨機(jī)性與動態(tài)性，并從單機(jī)調(diào)度逐漸向動態(tài)、多目標(biāo)和多機(jī)器調(diào)度發(fā)展；從Agent角度來看，研究也由單Agent向多Agent協(xié)同優(yōu)化逐步發(fā)展，但目前大多數(shù)文獻(xiàn)都是采用Q-學(xué)習(xí)方法進(jìn)行模型求解，并且在基于Agent協(xié)作的RL方面的研究較少。

表5 RL在車間作業(yè)調(diào)度中的應(yīng)用文獻(xiàn)匯總

3.5 基于DRL的運(yùn)籌優(yōu)化

傳統(tǒng)RL在只能求解簡單、小規(guī)模的運(yùn)籌優(yōu)化問題，但現(xiàn)實(shí)中的運(yùn)籌優(yōu)化問題往往都比較復(fù)雜，其狀態(tài)空間和動作空間維數(shù)很大，傳統(tǒng)RL難以求解。近年來，隨著深度學(xué)習(xí)的興起，深度學(xué)習(xí)與強(qiáng)化學(xué)習(xí)的結(jié)合研究也受到了很多關(guān)注，深度強(qiáng)化學(xué)習(xí)(DRL)將深度學(xué)習(xí)的強(qiáng)大感知能力融入傳統(tǒng)RL算法，形成了人工智能領(lǐng)域新的研究熱點(diǎn)，相比于傳統(tǒng)低維度表格型的RL，DRL融合了深度學(xué)習(xí)的優(yōu)點(diǎn)：(1)深度學(xué)習(xí)可自動提取高維度問題的特征，可讓RL直接在更原始的狀態(tài)下進(jìn)行學(xué)習(xí)；(2)深度學(xué)習(xí)可利用其強(qiáng)大的擬合能力對值函數(shù)或策略函數(shù)進(jìn)行近似；(3)深度學(xué)習(xí)為RL增強(qiáng)了泛化能力[57]；(4)高級別的API(如Keras和Tensor Flow等)和仿真環(huán)境(如Openai等)為DRL提供了很多優(yōu)秀的實(shí)驗(yàn)平臺，并輔助一些強(qiáng)大的硬件設(shè)施，這使得DRL能在可以接受的時(shí)間內(nèi)取得更為顯著的優(yōu)化效果。近年來學(xué)者們已開始將DRL運(yùn)用于運(yùn)籌優(yōu)化領(lǐng)域，在一些經(jīng)典的運(yùn)籌優(yōu)化問題上取得一定的研究成果，DRL與傳統(tǒng)算法的優(yōu)化效果分析如表6所示。

表6 基于DRL算法的應(yīng)用對比分析

傳統(tǒng)RL一般采用離線學(xué)習(xí)策略，利用神經(jīng)網(wǎng)絡(luò)來近似值函數(shù)，并自舉采樣數(shù)據(jù)來訓(xùn)練神經(jīng)網(wǎng)絡(luò)，由于在訓(xùn)練神經(jīng)網(wǎng)絡(luò)要求數(shù)據(jù)是獨(dú)立同分布，而自舉采樣得到的數(shù)據(jù)之間存在時(shí)序和狀態(tài)關(guān)聯(lián)性，導(dǎo)致訓(xùn)練神經(jīng)網(wǎng)絡(luò)的數(shù)據(jù)不是獨(dú)立同分布，在訓(xùn)練神經(jīng)網(wǎng)絡(luò)會出現(xiàn)模型不收斂、不穩(wěn)定的現(xiàn)象，會極大地影響RL學(xué)習(xí)的效率、穩(wěn)定性和收斂性。DRL本質(zhì)上是深度神經(jīng)網(wǎng)絡(luò)和Q-學(xué)習(xí)強(qiáng)化學(xué)習(xí)的結(jié)合，它利用經(jīng)驗(yàn)回放的方法來訓(xùn)練神經(jīng)網(wǎng)絡(luò)，即Agent先將收集得到的數(shù)據(jù)存儲到一個(gè)臨時(shí)數(shù)據(jù)庫中，再利用均勻隨機(jī)采樣的方法從該數(shù)據(jù)庫中抽取數(shù)據(jù)來訓(xùn)練神經(jīng)網(wǎng)絡(luò)，這種經(jīng)驗(yàn)回放可以打破數(shù)據(jù)之間的關(guān)聯(lián)性，最大限度地保證數(shù)據(jù)獨(dú)立同分布，提高學(xué)習(xí)的穩(wěn)定性；此外傳統(tǒng)RL中在利用神經(jīng)網(wǎng)絡(luò)進(jìn)行值函數(shù)近似時(shí)，計(jì)算TD目標(biāo)的動作值函數(shù)所用的網(wǎng)絡(luò)參數(shù)與梯度計(jì)算中要逼近的值函數(shù)所用的網(wǎng)絡(luò)參數(shù)相同，也容易導(dǎo)致數(shù)據(jù)之間存在關(guān)聯(lián)性，使得訓(xùn)練不穩(wěn)定，DRL則利用一個(gè)單獨(dú)的目標(biāo)網(wǎng)絡(luò)來計(jì)算目標(biāo)Q值，并且用于動作值函數(shù)逼近的網(wǎng)絡(luò)單步更新，而用于計(jì)算目標(biāo)Q值的網(wǎng)絡(luò)則每隔固定的步數(shù)更新一次，來減少目標(biāo)值與當(dāng)前值的相關(guān)性，進(jìn)一步提高模型的穩(wěn)定性；最后DRL可以利用圖嵌入等技術(shù)來自動提取特征，這種自動特征提取技術(shù)可以減少對專業(yè)領(lǐng)域知識的依賴，實(shí)現(xiàn)一種端到端的學(xué)習(xí)，大大提高了學(xué)習(xí)效率。

4 研究展望

RL理論研究開始較早且已取得了豐碩的成果，但國內(nèi)基于RL的運(yùn)籌優(yōu)化應(yīng)用研究起步相對較晚。本文僅對RL在庫存決策、路徑優(yōu)化、裝箱配載以及車間作業(yè)調(diào)度等經(jīng)典問題中的應(yīng)用進(jìn)行綜述，可以看出，RL在求解隨機(jī)動態(tài)型多階段序貫決策問題方面具有一定的優(yōu)勢，但是相對于日益復(fù)雜的生產(chǎn)、物流及管理系統(tǒng)來說，基于RL的研究仍處于起步階段，為推進(jìn)RL在運(yùn)籌優(yōu)化領(lǐng)域的應(yīng)用研究，提出以下幾點(diǎn)值得深入探討的研究方向。

(1)逐步提升基于MDP模型的精準(zhǔn)度，使模型更加符合日趨復(fù)雜的動態(tài)系統(tǒng)的需要?？梢詮囊韵聝蓚€(gè)方面進(jìn)行考慮：1)由于RL是基于交互和獎(jiǎng)賞的學(xué)習(xí)方式，獎(jiǎng)賞的定義對其至關(guān)重要，為避免人為主觀規(guī)定的不確定性，可以研究如何以更加科學(xué)的方式來定義獎(jiǎng)賞，如可以增加稀疏獎(jiǎng)勵(lì)來評估中間的成就；2)在隨機(jī)動態(tài)模型下，需要綜合考慮多重而非單一隨機(jī)性因素對系統(tǒng)的影響，即考慮多種隨機(jī)因素的協(xié)同優(yōu)化，以此為實(shí)際生產(chǎn)運(yùn)營提供理論支撐和實(shí)踐參考。

(2)與其它各類算法的結(jié)合。RL算法的優(yōu)勢在于通過交互獲取環(huán)境的動態(tài)信息，從而解決大規(guī)模復(fù)雜系統(tǒng)性的問題，但其存在收斂效率不高、速度過慢、不穩(wěn)定等問題。因此，可以考慮用其它啟發(fā)式優(yōu)化算法指導(dǎo)RL進(jìn)行更有效率的學(xué)習(xí)，如遺傳算法等，也可考慮在RL中加入人類專家領(lǐng)域的知識、經(jīng)驗(yàn)和高質(zhì)量數(shù)據(jù)等，以此來提高RL的學(xué)習(xí)效率以及降低學(xué)習(xí)難度，從而使得RL在處理具體問題時(shí)更具準(zhǔn)確性與穩(wěn)健性。

(3)加強(qiáng)DRL算法在運(yùn)籌優(yōu)化中的應(yīng)用。傳統(tǒng)的表格型RL不足以解決更為復(fù)雜的運(yùn)籌學(xué)領(lǐng)域序貫決策問題，DRL本質(zhì)上屬于值函數(shù)近似中非線性近似的一種，其優(yōu)勢在于利用深度神經(jīng)網(wǎng)絡(luò)對狀態(tài)的特征進(jìn)行自動提取，在很大程度上避免了人工定義特征的不準(zhǔn)確性，并且能夠提取系統(tǒng)關(guān)鍵特征，使得Agent可以在更加原始的狀態(tài)上進(jìn)行學(xué)習(xí)，能夠求解更為復(fù)雜的運(yùn)籌優(yōu)化問題。另外，隨著序列的不斷增長，可考慮在DRL中加入深度學(xué)習(xí)中的注意力機(jī)制，讓其聚焦于與求解問題密切相關(guān)的信息上，提高運(yùn)籌優(yōu)化問題的求解質(zhì)量。

(4)增強(qiáng)RL在不同運(yùn)籌學(xué)問題上的泛化能力?？煽紤]進(jìn)一步將元學(xué)習(xí)[117]、遷移學(xué)習(xí)[36]、多任務(wù)學(xué)習(xí)[92]以及終生學(xué)習(xí)等方法引入RL并應(yīng)用于運(yùn)籌優(yōu)化領(lǐng)域，使其能在面對新問題時(shí)能快速發(fā)現(xiàn)問題的本質(zhì)，并能遷移以往的學(xué)習(xí)經(jīng)驗(yàn)來加速RL的學(xué)習(xí)進(jìn)程。同時(shí)，由于許多運(yùn)籌學(xué)問題都是多目標(biāo)決策問題，可考慮將多任務(wù)學(xué)習(xí)機(jī)制引入RL，同時(shí)求解多個(gè)目標(biāo)的優(yōu)化決策問題。

(5)擴(kuò)大RL的應(yīng)用范圍。很多運(yùn)籌優(yōu)化問題都可以視為序貫決策問題，如物流選址、自動倉庫的貨物揀選、客戶需求量預(yù)測以及物流網(wǎng)絡(luò)布局等問題，這類問題也是典型的隨機(jī)型動態(tài)決策問題，可以考慮如何利用RL的方法進(jìn)行優(yōu)化求解。

5 結(jié)束語

RL作為一門有較長發(fā)展歷史的機(jī)器學(xué)習(xí)方法，在現(xiàn)代計(jì)算機(jī)計(jì)算能力極大提升的背景下，已成為人工智能領(lǐng)域的研究熱點(diǎn)，RL在求解隨機(jī)型動態(tài)序貫決策問題方面具有一定的優(yōu)勢，特別適合運(yùn)籌優(yōu)化領(lǐng)域中各類問題的求解。近年來基于RL的運(yùn)籌優(yōu)化在國外已經(jīng)形成了研究熱點(diǎn)，并取得了豐碩的成果，而在國內(nèi)，無論是理論研究還是應(yīng)用實(shí)踐，尚處于起步階段，本文介紹了RL基本原理與算法分類，闡述了RL研究方法與傳統(tǒng)建模方法的不同，重點(diǎn)介紹了RL在運(yùn)籌優(yōu)化領(lǐng)域的典型問題中的應(yīng)用，如庫存控制、車輛路徑、裝箱配載以及作業(yè)車間調(diào)度等。特別希望國內(nèi)的學(xué)者能結(jié)合中國的生產(chǎn)、物流和管理的實(shí)際問題開展關(guān)于RL的應(yīng)用研究，在解決實(shí)際問題的同時(shí)也為RL的理論研究提出新的挑戰(zhàn)和問題，進(jìn)一步豐富這一研究領(lǐng)域。