齊 晗

基于多智能體強(qiáng)化學(xué)習(xí)的物流配送路徑調(diào)度策略

齊 晗

（安徽電子信息職業(yè)技術(shù)學(xué)院 經(jīng)濟(jì)管理學(xué)院，安徽 蚌埠 233030）

為優(yōu)化物流系統(tǒng)的配送路徑，課題組提出了基于多智能體強(qiáng)化學(xué)習(xí)的配送路徑調(diào)度（Multi-agent Reinforcement Learning based Routing Scheduling，MRLRS）策略。MRLRS策略將配送路徑調(diào)度視為路徑生成過程，采用了具有注意層的編碼器-解碼器框架來迭代生成物流的配送路徑，并為模型訓(xùn)練設(shè)計(jì)了一種具有無監(jiān)督輔助網(wǎng)絡(luò)的多智能體強(qiáng)化學(xué)習(xí)方法。使用模擬實(shí)驗(yàn)對MRLRS策略進(jìn)行評估，實(shí)驗(yàn)結(jié)果表明，提出的MRLRS策略的性能要優(yōu)于現(xiàn)有的方法。

物流配送；強(qiáng)化學(xué)習(xí)；路徑調(diào)度優(yōu)化

經(jīng)濟(jì)技術(shù)的發(fā)展和國際經(jīng)濟(jì)貿(mào)易往來的日益擴(kuò)大，促使全球物流需求快速增長，我國快遞市場在2021年獲得多達(dá)1083億份訂單。物流業(yè)的快速發(fā)展給物流管理和調(diào)度系統(tǒng)的實(shí)時(shí)運(yùn)行帶來了前所未來的挑戰(zhàn)。因此，研究物流系統(tǒng)配送路徑調(diào)度問題就成為一個(gè)重要課題。在物流配送中，多個(gè)客戶將由容量有限的車隊(duì)服務(wù)，車隊(duì)管理者的目標(biāo)是在特定服務(wù)約束下最小化服務(wù)成本。從倉庫出發(fā)的車隊(duì)需要在特定的時(shí)間窗口限制內(nèi)服務(wù)擁有不同需求的客戶。當(dāng)違反給定的時(shí)間窗口時(shí)，車隊(duì)管理者會受到相應(yīng)的處罰，所以配送路徑調(diào)度是一個(gè)復(fù)雜的問題，針對此類問題設(shè)計(jì)一種快速、可靠的解決方案是極具挑戰(zhàn)性的。當(dāng)前主流的啟發(fā)式算法難以在短時(shí)間內(nèi)解決需求激增的問題，導(dǎo)致這類算法無法支持大規(guī)模應(yīng)用?；跈C(jī)器學(xué)習(xí)的方法由于其出色的學(xué)習(xí)能力在眾多研究領(lǐng)域中受到越來越多的關(guān)注[1–2]。其中，由于深度強(qiáng)化學(xué)習(xí)算法能學(xué)習(xí)解空間特征并建立參數(shù)化計(jì)算圖來模擬原始問題的約束，因此其在解決復(fù)雜的時(shí)間相關(guān)問題方面表現(xiàn)出強(qiáng)大的能力[3]。深度強(qiáng)化學(xué)習(xí)為動態(tài)環(huán)境中的優(yōu)化決策提供了一個(gè)通用框架，有助于解決組合優(yōu)化問題[4]。

本文提出了基于多智能體強(qiáng)化學(xué)習(xí)的路徑調(diào)度（Multi-agent Reinforcement Learning based Routing Scheduling，MRLRS）策略，構(gòu)建了一個(gè)具有多頭注意力層的編碼器-解碼器框架，利用深度強(qiáng)化學(xué)習(xí)策略來確定模型參數(shù)。

1 多智能體模型

1.1 路徑調(diào)度優(yōu)化建模

1.2 MRLRS框架設(shè)計(jì)

其中，是表示時(shí)間步t除以車輛編號的余數(shù)，表示在時(shí)間步t為車輛選擇客戶的概率，是指已在時(shí)間步得到服務(wù)的客戶。

2 編碼器-解碼器框架設(shè)計(jì)

使用多個(gè)注意力層更新嵌入，每個(gè)注意力層執(zhí)行多頭注意力和前向操作。注意力機(jī)制可以解釋為圖中客戶之間的加權(quán)消息傳遞算法。客戶從其他客戶那里收到消息的權(quán)重取決于其查詢與其他客戶的密鑰的兼容性。單個(gè)注意函數(shù)由下式給出：

注意力層的其余部分是帶有跳躍連接的前饋操作：

在解碼器部分，需要定義狀態(tài)、動作空間和獎勵，并通過深度神經(jīng)網(wǎng)絡(luò)對每個(gè)代理進(jìn)行建模。將車輛視為從環(huán)境和彼此感知狀態(tài)的代理，車輛根據(jù)通過感知獲得的知識來決定一個(gè)動作序列。采取的行動會影響環(huán)境，因此會改變代理所處的狀態(tài)。DRL系統(tǒng)中的每個(gè)代理都有一個(gè)必須達(dá)到的目標(biāo)狀態(tài)，代理的目標(biāo)是通過學(xué)習(xí)一個(gè)好的策略來最大化長期獎勵。

2.1 狀態(tài)

2.2 動作

通過softmax函數(shù)計(jì)算在時(shí)間步為車輛選擇客戶的概率，即：

2.3 獎勵

獎勵函數(shù)是強(qiáng)化學(xué)習(xí)問題的目標(biāo)，其獎勵函數(shù)如下式所示：

3 實(shí)驗(yàn)評估

在10×10的范圍內(nèi)隨機(jī)生成了倉庫的位置，客戶的數(shù)量分別為[20，50，100]，車輛的容量分別設(shè)置為[60，150，300]，時(shí)間窗口分別服從[0，10]、[0，20]和[0，40]的均勻分布。早到和遲到的懲罰系數(shù)分別服從[0，0.2]和[0，1]的均勻分布。每個(gè)客戶對兩輛車的需求服從[0，10]的均勻分布，對三輛車的需求服從[0，15]的均勻分布，四輛車的需求服從[0，25]的均勻分布，五輛車的需求服從[0，25]的均勻分布。實(shí)例的數(shù)量為1000。

實(shí)驗(yàn)部分將MRLRS與兩種經(jīng)典的啟發(fā)式方法（即遺傳算法和局部搜索算法）[5]和主流的ortools優(yōu)化工具[6]進(jìn)行比較。遺傳算法（GA）是一種基于類似于生物進(jìn)化的自然選擇過程來解決有約束和無約束優(yōu)化問題的方法。遺傳算法從當(dāng)前人口中隨機(jī)選擇個(gè)體作為父代，并使用父代產(chǎn)生下一代。采用兩組參數(shù)：GA-100的種群大小為100，最大迭代次數(shù)為300；GA-300的種群大小為300，最大迭代次數(shù)為1000。交叉率設(shè)置為0.80，突變率設(shè)置為0.05。局部搜索算法（LS）從一個(gè)可能的解決方案迭代地移動到相鄰的解決方案，直到獲得可能的最佳結(jié)果集。局部搜索算法可以避免陷入局部最優(yōu)。采用兩組參數(shù)：LS-100的最大迭代次數(shù)為100，LS-500的最大迭代次數(shù)為500。ortools是一個(gè)用于優(yōu)化的開源軟件套件，是一種廣泛使用的車輛路徑問題和約束優(yōu)化求解器。

在訓(xùn)練MRLRS的過程中，將學(xué)習(xí)率設(shè)置為0.0001，使用隨機(jī)生成的數(shù)據(jù)對模型進(jìn)行了 100個(gè)epoch的訓(xùn)練。每個(gè)epoch處理了64000個(gè)實(shí)例，批處理大小設(shè)置為 512。實(shí)驗(yàn)環(huán)境的配置為：具有11GB內(nèi)存的NVIDIA GeForce RTX 2080Ti Founders Edition，具有96GB內(nèi)存，處理器為英特爾志強(qiáng)E5-2673。MRLRS模型是使用Pytorch實(shí)現(xiàn)。編碼器中初始客戶嵌入層的維度設(shè)置為128，層數(shù)為3，注意頭數(shù)為8。

圖2展示了不同規(guī)模下每種方法的總成本和時(shí)間。由結(jié)果可知，在小規(guī)模場景中（客戶數(shù)量為20），所有方法的成本相差不大。但是，當(dāng)問題規(guī)模增大（客戶數(shù)量增加）時(shí)，與其他算法相比，GA的性能越來越差，ortools的性能僅次于MRLRS，LS的整體性能均優(yōu)于GA。在大多數(shù)情況下，提出的MRLRS在降低總成本和提高計(jì)算效率方面都要優(yōu)于其他方法。

圖2 不同規(guī)模下每種方法的總成本和時(shí)間

接下來分析了編碼器中初始客戶嵌入的維度和編碼器層數(shù)對MRLRS的影響。通過將客戶嵌入的維度分別設(shè)置為64和256來重新訓(xùn)練網(wǎng)絡(luò)，并評估相應(yīng)的性能，結(jié)果如圖3所示。由于低維空間可能會忽略有用信息，因此隨著嵌入維度的增加，模型能更快地收斂。

圖3 客戶嵌入維度對訓(xùn)練的影響

本文分別將編碼器層數(shù)設(shè)置為2、3、4進(jìn)行重新訓(xùn)練，獎勵曲線如圖4所示。由結(jié)果可知，層數(shù)較少的編碼器難以捕捉客戶之間的信息，而層數(shù)較多的編碼器并不一定可以獲得較好的結(jié)果。

圖4 編碼器層數(shù)對訓(xùn)練的影響

4 結(jié)論

本研究提出了MRLRS，一種用于配送路徑調(diào)度的強(qiáng)化學(xué)習(xí)算法。由模擬實(shí)驗(yàn)結(jié)果可知，與現(xiàn)有方法相比，提出的MRLRS能獲得最好的性能，同時(shí)具有最低的開銷，這表明提出的MRLRS在解決方案的質(zhì)量和效率方面都具有優(yōu)越的性能。在未來的研究工作中，將擴(kuò)展MRLRS，使其適應(yīng)具有多個(gè)站點(diǎn)、多個(gè)周期和異構(gòu)車隊(duì)等的應(yīng)用場景，并優(yōu)化MRLRS以提高解決大規(guī)模路徑調(diào)度問題的效率。

[1]Shinde P P, Shah S. A review of machine learning and deep learning applications[C]//2018 Fourth international conference on computing communication control and automation （ICCUBEA）. IEEE, 2018: 1–6.

[2] Avola D, Cinque L, Foresti G L, et al. VRheab: a fully immersive motor rehabilitation system based on recurrent neural network[J]. Multimedia Tools and Applications, 2018, 77（19）: 24955–24982.

[3] Zhang C, Patras P, Haddadi H. Deep learning in mobile and wireless networking: A survey[J]. IEEE Communications surveys & tutorials, 2019, 21（3）: 2224–2287.

[4] 孫長銀, 穆朝絮. 多智能體深度強(qiáng)化學(xué)習(xí)的若干關(guān)鍵科學(xué)問題[J]. 自動化學(xué)報(bào), 2020, 46（7）: 1301–1312.

[5] Katoch S, Chauhan S S, Kumar V. A review on genetic algorithm: past, present, and future[J]. Multimedia Tools and Applications, 2021, 80(5): 8091–8126.

[6]Sarkar C, Paul H S, Pal A. A scalable multi-robot task allocation algorithm[C]// 2018 IEEE International Conference on Robotics and Automation （ICRA）. IEEE, 2018: 5022–5027.

Logistics Distribution Route Scheduling Strategy Based on Multi-Agent Reinforcement Learning

QI Han

（School of Economics and Management, Anhui Vocational College of Electronics & Information Technology, Bengbu, Anhui 233030, China）

Aiming at the distribution route optimization problem in the logistics system, the paper proposes a Multi-agent Reinforcement Learning based Routing Scheduling (MRLRS) strategy. The MRLRS strategy regards delivery route scheduling as a route generation process, proposes an encoder-decoder framework with attention layers to iteratively generate logistics delivery routes, and designs a multi-agent reinforcement with unsupervised auxiliary network for model training study method. The MRLRS strategy is evaluated using simulation experiments, and the experimental results show that the proposed MRLRS strategy outperforms the existing methods.

logistics distribution; reinforcement learning; route scheduling optimization

TP391 文獻(xiàn)志識碼：A

2095-9249（2021）06-0077-04

2021-12-10

安徽省人文社科重點(diǎn)項(xiàng)目（SK2021A1062）；安徽省質(zhì)量工程項(xiàng)目（2020SJJXSFK0238）

齊晗（1984—），男，安徽樅陽人，講師，碩士，研究方向：現(xiàn)代物流管理。

〔責(zé)任編校：吳侃民〕