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

齊 晗

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

齊 晗

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

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

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

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

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

1 多智能體模型

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

1.2 MRLRS框架設(shè)計

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

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

使用多個注意力層更新嵌入，每個注意力層執(zhí)行多頭注意力和前向操作。注意力機制可以解釋為圖中客戶之間的加權(quán)消息傳遞算法?？蛻魪钠渌蛻裟抢锸盏较⒌臋?quán)重取決于其查詢與其他客戶的密鑰的兼容性。單個注意函數(shù)由下式給出：

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

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

2.1 狀態(tài)

2.2 動作

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

2.3 獎勵

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

3 實驗評估

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

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

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

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

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

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

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

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

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

4 結(jié)論

本研究提出了MRLRS，一種用于配送路徑調(diào)度的強化學(xué)習(xí)算法。由模擬實驗結(jié)果可知，與現(xiàn)有方法相比，提出的MRLRS能獲得最好的性能，同時具有最低的開銷，這表明提出的MRLRS在解決方案的質(zhì)量和效率方面都具有優(yōu)越的性能。在未來的研究工作中，將擴展MRLRS，使其適應(yīng)具有多個站點、多個周期和異構(gòu)車隊等的應(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] 孫長銀, 穆朝絮. 多智能體深度強化學(xué)習(xí)的若干關(guān)鍵科學(xué)問題[J]. 自動化學(xué)報, 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 文獻志識碼：A

2095-9249（2021）06-0077-04

2021-12-10

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

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

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