求解外賣配送問題的深度強化學(xué)習(xí)算法

摘 要：以最小化騎手費用效益比為優(yōu)化目標(biāo)，采用最小比率旅行商問題對外賣配送問題進行建模。針對目前算法在求解該問題時計算精度低、算法穩(wěn)定性差等問題，設(shè)計一種基于深度強化學(xué)習(xí)的DRL-MFA算法。首先，定義外賣配送問題的馬爾可夫決策模型來模擬智能體與環(huán)境的交互過程；其次，在編碼階段設(shè)計多特征聚合嵌入子層，實現(xiàn)特征間的優(yōu)勢互補并提高模型對非線性問題的建模能力；最后，在解碼階段通過注意力機制和指針網(wǎng)絡(luò)計算解的概率分布，采用策略梯度算法對網(wǎng)絡(luò)模型進行訓(xùn)練。通過經(jīng)典算例和長春市仿真案例的相關(guān)實驗分析，結(jié)果表明該算法能夠有效地求解外賣配送問題，且與其他啟發(fā)式算法相比，具有更高的穩(wěn)定性和求解精度。此外，進行參數(shù)靈敏度實驗，考慮不同定價策略對外賣配送的影響，使研究結(jié)果更具現(xiàn)實意義。

關(guān)鍵詞：外賣配送問題；最小比率旅行商問題；深度強化學(xué)習(xí)；多特征嵌入；注意力機制

中圖分類號：TP18"" 文獻(xiàn)標(biāo)志碼：A

文章編號：1001-3695（2025）01-028-0205-09

doi： 10.19734/j.issn.1001-3695.2024.05.0179

Deep reinforcement learning approach for solving takeout delivery problem

Abstract：This paper took the minimization of the rider’s cost-benefit ratio as the optimization objective and used the minimum ratio traveling salesman problem to model the takeout delivery problem. Aiming at the issues of low accuracy and poor stability of current algorithms for solving this problem， this paper proposed a DRL-MFA algorithm based on deep reinforcement learning. Firstly， the algorithm defined the takeout delivery problem as a Markov decision model to simulate the process between agent and environment. Secondly， the algorithm used a multi-feature aggregation embedding sublayer in the encoder to achieve the advantageous complementarity among the features and improve the modelling ability of nonlinear problems. Finally， the algorithm calculated the probability distribution of the solution by the attention mechanism and pointer network in the decoder and used the strategy gradient to train the network. Through the experimental analysis of classic examples and simu-lation cases in Changchun， the results show that the proposed algorithm can effectively solve the takeout delivery problem， and has higher stability and accuracy than other heuristic algorithms. In addition， this paper conducted the sensitivity experiment to explore the impact of different pricing strategies on takeout delivery， which makes the research more realistic and practical.

Key words：takeout delivery; minimum ratio traveling salesman problem; deep reinforcement learning; multi-feature embedding; attention mechanism

0 引言

順應(yīng)當(dāng)今“互聯(lián)網(wǎng)+”時代的發(fā)展浪潮，人們的生活水平不斷提高，快節(jié)奏生活方式不斷普及，“餐飲外賣30分鐘內(nèi)送達(dá)”已然成為一種新的生活方式。近年來，外賣行業(yè)逐漸成為餐飲行業(yè)發(fā)展的重要力量，根據(jù)某外賣平臺2023年度財政報告及社會責(zé)任報告顯示，2023全年線上即時外賣配送訂單達(dá)219億筆，其中單日外賣訂單峰值高達(dá)7 800萬筆。外賣市場的蓬勃增長，帶動外賣行業(yè)迅速發(fā)展的同時，關(guān)于騎手權(quán)益與待遇的問題也開始受到廣泛關(guān)注。外賣配送作為外賣業(yè)務(wù)線上線下（online to offline， O2O）活動的關(guān)鍵環(huán)節(jié)，現(xiàn)階段的主要送餐方式還是通過騎手派送的形式把餐品送到顧客手中，國家多部門就曾要求相關(guān)企業(yè)保障騎手勞動收入，呼吁平臺建立與工作強度相匹配的收入分配機制等，以保障騎手相關(guān)權(quán)益[1]。

外賣配送行業(yè)中，外賣平臺、顧客和配送騎手之間的利益相互沖突，要想促進外賣行業(yè)良性發(fā)展就必須合理優(yōu)化外賣配送路徑以保證平臺的配送效率、顧客的服務(wù)質(zhì)量和騎手的配送收益[2]。隨著用戶數(shù)量和外賣平臺的迅速擴張，在配送過程中往往會出現(xiàn)大量訂單的囤積而導(dǎo)致延遲配送等問題，影響了消費者對配送服務(wù)滿意度的同時，也造成了外賣騎手收入直接下降[3]。外賣配送作業(yè)作為整個外賣運行模式中最重要的一環(huán)，配送路徑的選擇能夠直接改變用戶的就餐體驗感和騎手的工作效益。合理的配送路徑可以減少平臺的運營成本，提升顧客的服務(wù)體驗，并增加外賣騎手的收益水平。

外賣配送問題如圖1所示。外賣騎手從配送中心出發(fā)開始配送任務(wù)，每完成一份訂單的配送，就會獲得一定的配送收益，在服務(wù)完所有的顧客后，外賣騎手將回到配送中心并獲得配送中心提供的傭金收益，所有配送收益大小均取決于配送距離長短。外賣配送問題討論如何選擇一條完整的配送路徑，在保證服務(wù)每個顧客的同時，增加配送騎手獲得的配送收益。因此，結(jié)合外賣配送問題的具體實際應(yīng)用場景，本文將外賣配送路徑優(yōu)化問題歸納為最小比率旅行商問題（minimum ratio traveling salesman problem， MRTSP），并對其進行建模求解。

MRTSP是經(jīng)典旅行商問題（traveling salesman problem， TSP）的一種擴展形式[4]，在外賣配送問題上的應(yīng)用可以具體描述為：在給定一個配送中心、若干顧客和每對顧客之間的距離和收益情況下，令外賣騎手從配送中心出發(fā)，服務(wù)每位顧客一次并回到配送中心，確定一條最佳旅行路徑，使得該路徑的總路程和總收益之比最小化，即外賣騎手的費用效益比最小化。由于MRTSP同時考慮了顧客間的距離因素和配送收益因素，所以相比單純考慮距離最小的經(jīng)典旅行商問題，往往更具有研究的現(xiàn)實意義。

TSP是組合優(yōu)化中的經(jīng)典NP-hard問題，求解時的時間復(fù)雜度呈指數(shù)級增長。MRTSP作為TSP的擴展問題也屬于NP-hard問題，由于其目標(biāo)函數(shù)中包含非線性因素，相比TSP的求解也更為困難。目前MRTSP的解決方法主要包括精確算法和啟發(fā)式算法，且研究主要集中于啟發(fā)式算法上，包括模擬退火算法[4]、競爭決策算法[5]、大洪水算法[6]、蝙蝠算法[7]、蟻群優(yōu)化算法[8]、引力搜索算法[9]中心引力優(yōu)化算法[10]和陰陽平衡優(yōu)化算法[11]等智能優(yōu)化算法。這些研究為MRTSP的求解提供了不同的解決思路。但是精確算法的時間復(fù)雜度會隨著問題規(guī)模呈指數(shù)級增長，而啟發(fā)式算法在面對不同實例時需要進行相應(yīng)算法參數(shù)的調(diào)整，并通過不斷迭代的方式尋找問題的最優(yōu)解，存在計算精度不高、算法早熟收斂等缺點，使得問題容易陷入局部最優(yōu)，收斂速度較慢。且現(xiàn)有的研究成果中，通常只考慮小規(guī)模MRTSP的求解，并未在更大規(guī)模的MRTSP進行研究討論。

隨著人工智能的發(fā)展，深度強化學(xué)習(xí)算法開始逐步進入大眾視野。深度強化學(xué)習(xí)算法能夠有效地解決傳統(tǒng)算法的局限性，提升求解問題的規(guī)模和效果，已被證實可以運用于組合優(yōu)化問題的求解，如車間調(diào)度問題[12]和車輛路徑問題[13，14]等。深度強化學(xué)習(xí)以數(shù)據(jù)為驅(qū)動，具有強大的決策能力，能夠?qū)?shù)據(jù)的深層特征進行挖掘，并在與狀態(tài)環(huán)境的交互過程中達(dá)成回報最大化等目標(biāo)。相較于啟發(fā)式算法，基于深度強化學(xué)習(xí)的端到端模型（end-to-end）在處理復(fù)雜任務(wù)時，能夠從原始輸入中學(xué)習(xí)到更豐富的特征信息，從而提高決策的準(zhǔn)確性，生成解決方案更為高效。通過輸入節(jié)點的特征信息，利用強化學(xué)習(xí)方法訓(xùn)練深度神經(jīng)網(wǎng)絡(luò)，能夠直接輸出完整的節(jié)點訪問序列，模型收斂速度更快，泛化能力更高，實時求解能力更強，因此成為了近些年來的研究熱點。

近年來，已經(jīng)有部分學(xué)者嘗試使用深度強化學(xué)習(xí)的方法求解旅行商問題。Vinyals等人[15]借鑒seq2seq在自然語言處理方面的成果，提出了指針網(wǎng)絡(luò)（point network， PN），利用注意力機制計算輸入的節(jié)點序列與輸出的選擇概率值之間的關(guān)系，首次運用深度學(xué)習(xí)的方式實現(xiàn)經(jīng)典TSP的求解。Nazari等人[16]選擇以節(jié)點信息的特征嵌入取代指針網(wǎng)絡(luò)中的LSTM編碼器，并將其運用于車輛路徑規(guī)劃問題中，使模型能夠更有效地更新狀態(tài)變化后的特征嵌入。Ling等人[17]提出了一種將TSP轉(zhuǎn)換為計算機視覺問題的圖像表示方法，使用深度卷積神經(jīng)網(wǎng)絡(luò)在顧客節(jié)點信息和最優(yōu)解決方案之間建立映射，提高了模型的準(zhǔn)確性和泛化能力。Kool等人[18]在基于自注意力機制的Transformer模型架構(gòu)上進行改動，并使用REINFORCE的強化學(xué)習(xí)方法訓(xùn)練網(wǎng)絡(luò)，實現(xiàn)了TSP等其他路徑優(yōu)化問題的無監(jiān)督學(xué)習(xí)，是深度強化學(xué)習(xí)求解路徑問題一次里程碑式的研究。但目前已知的深度強化學(xué)習(xí)算法多應(yīng)用于計算具有線性目標(biāo)函數(shù)的TSP及其變形問題，而并未考慮具有非線性目標(biāo)函數(shù)的MRTSP的求解。

因此，本文根據(jù)深度強化學(xué)習(xí)算法的相關(guān)知識，提出一種基于Transformer算法架構(gòu)改進的DRL-MFA算法，構(gòu)建編碼器-解碼器結(jié)構(gòu)的深度神經(jīng)網(wǎng)絡(luò)模型，并使用強化學(xué)習(xí)的方式對該網(wǎng)絡(luò)進行無監(jiān)督訓(xùn)練。該模型能夠高效且快速地求解外賣配送問題，且當(dāng)輸入的特征信息產(chǎn)生變化時，模型依然能保持較強的魯棒性和泛化能力，為處理不同規(guī)模的MRTSP提供了有效可行的方法。

本文的主要工作如下：首先，將外賣配送問題看做是一個馬爾可夫決策過程，設(shè)計了在該問題下的狀態(tài)空間、動作空間、狀態(tài)轉(zhuǎn)移、獎勵函數(shù)等馬爾可夫決策要素。其次，利用MRTSP對外賣配送問題進行建模，采用基于Transformer改進的DRL-MFA模型作為算法架構(gòu)，在編碼過程中增加多特征聚合嵌入層，使模型能夠綜合考慮多特征對全局信息的影響，并利用注意力機制與指針網(wǎng)絡(luò)計算各節(jié)點與全局特征的相似度，訓(xùn)練策略網(wǎng)絡(luò)進行問題的求解。最后，經(jīng)過大量數(shù)值實驗，證明了所提出的DRL-MFA算法與已知啟發(fā)式算法相比有著更優(yōu)的求解效果和更高的算法精度，且該算法能夠被應(yīng)用于更大規(guī)模以及真實數(shù)據(jù)算例的外賣配送問題上，使實驗結(jié)果更具現(xiàn)實意義，為求解MRTSP提供新的求解思路。

1 外賣配送問題的數(shù)學(xué)模型

外賣配送問題的描述如下：存在一個配送中心，配送中心包含一位配送騎手，負(fù)責(zé)為多個顧客需求點配送外賣餐食，配送中心及顧客需求點的坐標(biāo)已知，目標(biāo)是通過最優(yōu)化騎手的配送路徑，使得該條路徑上騎手的總路程長度和總獲得收益之比最小化，即騎手費用效益比最小化。為了便于分析和研究，對問題作以下假設(shè)：

a）配送騎手速度恒定，以行駛距離作為騎手配送時間；

b）以歐氏距離計算騎手往返于顧客之間的行駛距離；

c）忽略配送騎手為每個顧客服務(wù)的停留時間因素；

d）每個顧客僅能被騎手服務(wù)一次；

e）騎手必須從配送中心出發(fā)完成配送任務(wù)，并最終回到配送中心；

f）騎手不設(shè)置載貨容量限制，能夠為所有顧客提供完整服務(wù)。

根據(jù)外賣配送問題的相關(guān)特點，可以將其歸納為最小比率旅行商問題進行求解?；趫D論的知識點，最小比率旅行商問題可以被具體描述如下：

考慮MRTSP為一個給定的賦權(quán)完全圖G=（V，E）。其中V=（1，2，…，n）表示為頂點集合，代表顧客的具體位置；E={（i，j），i≠j，i，j∈V}表示邊集合，代表顧客之間的路徑；矩陣D=（dij）n×n，dij=dji，dii=+，dijgt;0（i，j∈V），表示每對顧客節(jié)點之間的路程距離；矩陣P=（pij）n×n，pij=pji，pii=0，pijgt;0（i，j∈V），表示外賣騎手從一個顧客到另一個顧客得到的收益。MRTSP的數(shù)學(xué)模型表示為

其中：式（1）是MRTSP的目標(biāo)函數(shù)，令騎手所經(jīng)過回路路徑的總行程與總收益之比最小，即最小化騎手的費用效益比；式（2）的第一個約束條件表示外賣騎手在任意顧客只會出發(fā)一次，第二個約束條件表示外賣騎手只會進入每個顧客節(jié)點一次，即在一次配送路徑上所有的顧客都要被訪問且僅被訪問一次；第三個約束條件表示在選擇的配送路徑中不會產(chǎn)生任何的子回路；第四個約束條件中，xij為0-1決策變量，當(dāng)xij=1時，表示從顧客點i出發(fā)前往顧客點j，即路徑i，j包含在當(dāng)前的最優(yōu)路徑上，否則xij=0。當(dāng)同時滿足以上的約束條件時，MRTSP就會構(gòu)成一條哈密爾頓回路。

2 最小比率旅行商問題的深度強化學(xué)習(xí)算法

深度強化學(xué)習(xí)算法結(jié)合了深度神經(jīng)網(wǎng)絡(luò)與強化學(xué)習(xí)各自的優(yōu)點，使得算法模型具有很強的特征提取能力，同時也擅長在與環(huán)境交互的過程中學(xué)習(xí)獲取最大獎勵的動作。首先，針對最小比率旅行商問題，本文提出的深度強化學(xué)習(xí)模型將MRTSP建模為一個馬爾可夫決策過程[19]；其次，提出了基于Transformer改進的編碼器-解碼器深度強化學(xué)習(xí)模型，通過策略梯度強化學(xué)習(xí)的方式訓(xùn)練網(wǎng)絡(luò)模型，并采用不同的動作選擇策略獲取訓(xùn)練結(jié)果。

2.1 馬爾可夫決策過程

馬爾可夫決策過程（Markov decision process， MDP）是指一個隨機過程中，未來狀態(tài)的條件概率只依賴于當(dāng)前時刻的狀態(tài)，與之前任意時刻無關(guān)。求解MRTSP的過程可以視為一個智能體在與環(huán)境的交互中，逐點選擇旅行中的下一個訪問節(jié)點的馬爾可夫決策過程。MRTSP的馬爾可夫決策過程如圖2所示。

MRTSP的狀態(tài)空間（state）、動作空間（action）、狀態(tài)轉(zhuǎn)移（transition）、獎勵函數(shù)（reward）[20]可以定義如下：

狀態(tài)空間記作S，其中st∈S，表示當(dāng)前t時刻環(huán)境的描述，在MRTSP中，狀態(tài)空間包括所有顧客節(jié)點的坐標(biāo)信息、節(jié)點之間的距離信息、所有節(jié)點到其他節(jié)點所獲得的收益信息以及所有節(jié)點的訪問狀態(tài)，其中所有節(jié)點的訪問狀態(tài)為動態(tài)特征。

動作空間記作A，其中at∈A，表示外賣騎手在當(dāng)前t時刻將選擇下一時刻訪問某個顧客的決策。騎手會根據(jù)環(huán)境狀態(tài)st－1，通過訓(xùn)練策略網(wǎng)絡(luò)πθ（at|st－1）計算狀態(tài)st－1下采取的動作at的概率。

狀態(tài)轉(zhuǎn)移函數(shù)記作T（st，a），表示當(dāng)前時刻外賣騎手選擇在狀態(tài)st下選擇動作a后，使得狀態(tài)st轉(zhuǎn)移到下一個新的狀態(tài)st+1的過程。根據(jù)概率鏈?zhǔn)椒▌t[21]，通過狀態(tài)轉(zhuǎn)移，模型的隨機策略可以定義為式（3），表示在狀態(tài)s下，通過策略網(wǎng)絡(luò)πθ，選擇路徑方案π的概率。

獎勵函數(shù)記作R，每個時刻外賣騎手作出一次動作，就會獲得相關(guān)動作產(chǎn)生的距離成本和收益獎勵。針對MRTSP而言，目標(biāo)函數(shù)為最小化費用效益比（即總距離與總收益的比值），因此獎勵函數(shù)可以被定義為式（4）。

2.2 策略網(wǎng)絡(luò)模型

本節(jié)介紹了基于Transformer改進的DRL-MFA算法模型，所提策略網(wǎng)絡(luò)的總體結(jié)構(gòu)框架如圖3所示。

模型包括了編碼器和解碼器部分：編碼器負(fù)責(zé)捕捉輸入特征的關(guān)鍵信息將其映射到更高維度，并計算得到完整的圖嵌入特征信息；解碼器負(fù)責(zé)根據(jù)每個時刻輸出的動作概率進行選擇，并更新狀態(tài)信息直至獲得完整配送路徑。考慮到MRTSP多特征因素的特點，DRL-MFA模型框架在編碼器部分添加了一個多特征聚合嵌入子層（multi-features aggregation， MFA）。本節(jié)將詳細(xì)描述算法編碼器和解碼器的具體結(jié)構(gòu)。

2.2.1 編碼器

提出的編碼器結(jié)構(gòu)如圖4所示，由一層多特征聚合嵌入子層（MFA）與L層的相同結(jié)構(gòu)但網(wǎng)絡(luò)參數(shù)相互獨立的自注意力子層（self-attention， SA）組成。編碼器將顧客位置信息xi∈X、顧客之間的距離信息dij∈D以及對應(yīng)路徑可獲得的收益信息pij∈P三部分作為輸入特征，利用編碼器對輸入特征進行深度信息的提取，并輸出每個節(jié)點對應(yīng)的特征嵌入信息hi和全局圖嵌入信息H0。

其中：Wx、Wd、Wp、Wa、bx、bd、bp、ba是MFA層的可訓(xùn)練網(wǎng)絡(luò)參數(shù)。

b）自注意力子層SA。將MFA子層的聚合特征嵌入h^i作為初始輸入，傳遞到后續(xù)的L層SA子層，每個SA子層都由一個多頭注意力子層（multi-head attention， MHA）[22]和前饋子層（feed forward， FF）組成，每層MHA和FF層都包含一個殘差鏈接（skip-connection）和批量歸一化層（batch-normalization，BN），SA層將上一層輸出的特征hil－1更新為hil，其中上標(biāo)l∈［1，L］，表示第l層自注意力子層，如式（10）（11）所示。

（a）多頭注意力子層MHA。MHA子層負(fù)責(zé)利用多頭注意力的計算來捕捉每個節(jié)點之間的特征依賴關(guān)系，獲取每個顧客節(jié)點的權(quán)重信息。MHA子層遵循經(jīng)典Transformer架構(gòu)，使用M個維度大小為dk=dh/M的注意力頭來計算自注意力分?jǐn)?shù)，MHA子層的數(shù)學(xué)公式表達(dá)如下：

度為－；對相似度使用softmax激活函數(shù)可以得到注意力權(quán)重aij∈0，1；將注意力權(quán)重aij與值vi做點積運算，便可得到完整的節(jié)點嵌入特征h′i。對每個注意力頭重復(fù)以上步驟，并最后根據(jù)式（16）進行多頭特征的融合，得到最終的節(jié)點注意力特征，其中Wm為多頭注意力特征融合的可訓(xùn)練網(wǎng)絡(luò)參數(shù)。

（b）前饋子層FF。FF子層負(fù)責(zé)執(zhí)行非線性激活的功能，將MHA子層輸出的特征進行非線性轉(zhuǎn)換。它由兩層全連接線性網(wǎng)絡(luò)與一層激活函數(shù)ReLU層構(gòu)成。首先節(jié)點特征進入第一層全連接網(wǎng)絡(luò)，將特征信息投射到512維的隱藏層；隨后經(jīng)過一層ReLU層激活神經(jīng)元，最后連接第二層全連接網(wǎng)絡(luò)，輸出整個前饋子層的計算結(jié)果，即

其中：WFF1、bFF1為第一層全連接層的可訓(xùn)練參數(shù)；WFF2、bFF2為第二層全連接層的可訓(xùn)練參數(shù)。

2.2.2 解碼器

提出的解碼器模型架構(gòu)如圖5所示。解碼器將編碼器得到的節(jié)點特征嵌入作為輸入，在每個時間步驟t=1，2，…，n內(nèi)，解碼器會根據(jù)上一時刻的狀態(tài)信息st－1獲得上下文變量，并利用該向量輸出MRTSP下一時刻訪問各節(jié)點的動作概率，通過不同策略選擇下一步動作，直至遍歷完所有的顧客節(jié)點。

a）全連接層FC。全連接層將上下文特征變量作為輸入，本文使用類似于Kool等人[18]提出上下文特征（context）變量來表示當(dāng)前的環(huán)境狀態(tài)信息。context變量由完整的圖嵌入H0、第一個訪問節(jié)點的特征嵌入hfirst以及上一個訪問節(jié)點的特征嵌入hlast水平拼接組成。在每個t時刻，編碼器都會根據(jù)狀態(tài)變化生成新的context變量，即

其中：圖嵌入H0是編碼器輸出節(jié)點嵌入的平均值；在t=1時刻，由于路徑還未選擇節(jié)點，所以采用兩個可訓(xùn)練的占位符參數(shù)evoid、fvoid替代后兩項特征嵌入；Wc、bc為解碼器全連接層的可學(xué)習(xí)參數(shù)。模型在每次調(diào)用解碼器時，只會對context發(fā)送信息以更新環(huán)境狀態(tài)，以此提高模型整體的工作效率。

b）多頭注意力層MHA。該層將context變量的嵌入映射為查詢qc，節(jié)點編碼嵌入映射為鍵ki和值vi，組成全新的三元組{qc，ki，vi}來計算注意力分?jǐn)?shù)，以獲取當(dāng)前t時刻的上下文特征變量與各個顧客節(jié)點的嵌入信息之間的特征依賴關(guān)系，即

c）單頭注意力層SHA。SHA用于控制最終輸出的節(jié)點選擇概率分布。將MHA層計算得出的特征嵌入hc作為SHA層的查詢向量qhc，所有顧客節(jié)點的節(jié)點編碼嵌入向量hi作為SHA層的鍵ki，進行查詢與鍵之間相似度的計算，采用tanh激活函數(shù)將結(jié)果縮放到［－C，C］（C=10），并通過softmax函數(shù)歸一化處理，得到當(dāng)前時刻下每個節(jié)點的選擇概率，即

根據(jù)輸出的選擇概率分布，利用不同的搜索策略進行下一個訪問節(jié)點的動作選擇，直至所有的顧客節(jié)點均被服務(wù)一次，則解碼完成，即可獲得MRTSP由DRL-MFA模型計算得出的完整路徑結(jié)果。

d）動作選擇策略。根據(jù)概率分布，本文參考王萬良等人[23]的研究，主要采用兩種搜索策略進行動作選擇：貪婪搜索（greedy rollout）、采樣搜索（sample rollout）。貪婪搜索從解碼器輸出的概率分布中直接選擇最大概率值對應(yīng)的動作；采樣搜索則以解碼器輸出的概率分布作為搜索基礎(chǔ)，根據(jù)概率分布采樣選擇相應(yīng)動作。由于采樣搜索會根據(jù)概率分布選擇不同的節(jié)點進行訪問，在DRL-MFA模型的訓(xùn)練階段，采用采樣搜索的動作選擇策略可以擴大解的搜索范圍，引入更多的隨機性，防止模型訓(xùn)練過擬合。而在測試階段，采用貪婪搜索策略選擇訪問節(jié)點，能夠更加快速地求解MRTSP，并獲得最優(yōu)路線。

2.3 策略網(wǎng)絡(luò)訓(xùn)練方法

使用Adam優(yōu)化器[25]與梯度下降法的方式對整個模型網(wǎng)絡(luò)進行訓(xùn)練，具體訓(xùn)練偽代碼如下：

算法1 帶有基線的REINFORCE強化學(xué)習(xí)算法

3 數(shù)值實驗

本章對DRL-MFA算法解決MRTSP的有效性進行實驗驗證。實驗共分成三個部分：首先，針對現(xiàn)有MRTSP的經(jīng)典算例進行DRL-MFA算法的對比實驗，比較其與現(xiàn)有啟發(fā)式算法的求解性能；其次，結(jié)合真實的數(shù)據(jù)信息，生成不同規(guī)模大小的外賣配送問題真實算例，并驗證DRL-MFA算法在該數(shù)據(jù)集上的實驗效果；最后，對MRTSP的相關(guān)參數(shù)進行靈敏度分析實驗。

本文使用如下環(huán)境對MRTSP實例進行訓(xùn)練和求解，操作系統(tǒng)：Windows 10，CPU： IntelXeon Gold 6348 CPU @ 2.60 GHz，GPU： NVIDIA A40。本章所有實驗均通過PyTorch實現(xiàn)，每次訓(xùn)練周期epoch設(shè)置為200個，每個epoch的訓(xùn)練集batch設(shè)置為500個，驗證集batch為200個，每個batch包括512個實例數(shù)據(jù)。訓(xùn)練過程中每50次迭代會記錄模型的運行效果。算法其他參數(shù)設(shè)置如表1所示。

考慮到實驗所用GPU的內(nèi)存壓力，隨著問題規(guī)模的不斷擴大，節(jié)點信息的嵌入維度會根據(jù)實驗規(guī)模縮小至64，batch大小也會根據(jù)實驗規(guī)模減少至256。

3.1 經(jīng)典算例

本節(jié)對最小比率旅行商問題的三個經(jīng)典算例[11]進行仿真實驗。

算例1 設(shè)給定對稱賦權(quán)完全圖G=（V，E），距離矩陣D和收益矩陣P定義如下：

算例2 設(shè)給定對稱賦權(quán)完全圖G=（V，E），距離矩陣D和收益矩陣P定義如下：

算例3 設(shè)給定對稱賦權(quán)完全圖G=（V，E），距離矩陣D和收益矩陣P定義如下：

為測試DRL-MFA算法的性能，與引力搜索算法（gravitational search algorithm， GSA）[26]、生物地理學(xué)優(yōu)化算法（biogeography-based optimization， BBO）[27]、最有價值球員算法（most valuable player algorithm， MVPA）[28]、粒子群優(yōu)化算法（particle swarm optimization， PSO）[29]以及遺傳算法（genetic algorithm， GA）[30]等啟發(fā)式算法進行比較，算法根據(jù)文獻(xiàn)[26～30]進行參數(shù)設(shè)置。由于經(jīng)典算例直接提供距離矩陣而無節(jié)點坐標(biāo)，所以DRL-MFA算法在編碼器的MFA子層僅考慮距離矩陣D和收益矩陣P兩個特征的聚合嵌入。

考慮到算法每次運行結(jié)果存在偶然性，可能會對優(yōu)化性能的分析判斷產(chǎn)生影響，所以每種算法會各自獨立運行20次，分別統(tǒng)計最優(yōu)值、最劣值、平均值、標(biāo)準(zhǔn)差和平均值與最優(yōu)值之間的差距GAP等指標(biāo)，并計算每個算法在20次實驗中達(dá)到已知最優(yōu)解的成功率。具體計算結(jié)果如表2所示。

通過分析表2的結(jié)果可以發(fā)現(xiàn)：首先，對于最小規(guī)模的算例1而言，在相同的評價指標(biāo)下，六種算法均能計算到目前已知的最優(yōu)解；其次，對于算例2的計算結(jié)果，DRL-MFA和貪婪算法均能計算出優(yōu)于目前已知的最優(yōu)解的計算結(jié)果，且得到的最優(yōu)解經(jīng)實驗驗證為一條有效路徑，而其他的算法均陷入局部最優(yōu)，無法獲得此解；最后，面對更大規(guī)模的算例3而言，即使其他的五種智能優(yōu)化算法均有機會找到目前已知的最優(yōu)值，但是在其他的評價指標(biāo)上，與DRL-MFA算法的結(jié)果存在明顯差距。由此可見，DRL-MFA算法在計算精度方面，具有更優(yōu)于其余五種智能優(yōu)化算法的求解性能。

除此之外，智能優(yōu)化算法的結(jié)果受到迭代次數(shù)的影響，且在面對不同實例時，泛化能力較差；而深度強化學(xué)習(xí)網(wǎng)絡(luò)一旦完成訓(xùn)練便可以當(dāng)作求解器使用，不用進行算法迭代，即可直接輸出滿意解。

為進一步說明基于深度強化學(xué)習(xí)的DRL-MFA算法具有更好的優(yōu)化性能，本文將擴大MRTSP的算例規(guī)模，并將其運用于現(xiàn)實真實數(shù)據(jù)案例中。

3.2 長春市外賣配送案例

本節(jié)所有實例均來自于第十九屆中國研究生數(shù)學(xué)建模競賽F題，數(shù)據(jù)包括長春市九個行政區(qū)的小區(qū)坐標(biāo)節(jié)點信息。

由于在現(xiàn)實生活中，距離與收益幾乎成正比（即配送距離越遠(yuǎn)所收獲的利潤越高），為了使實例數(shù)據(jù)的利潤分布更符合真實情況，且更具有現(xiàn)實研究意義，利潤部分不采用隨機生成的方式，而是參考包括各大外賣配送平臺、同城急送平臺在內(nèi)的成熟企業(yè)的現(xiàn)有配送定價策略，建立距離和收益之間的數(shù)學(xué)關(guān)系：起送費不論距離均為8元，此后配送距離超過3 km但不超過5 km的部分每千米增加1元，配送距離超過5 km的部分則每千米增加2元，即

根據(jù)數(shù)據(jù)來源，本節(jié)對不同顧客規(guī)模的實例（35/50/85/100）進行了隨機生成數(shù)據(jù)和真實算例數(shù)據(jù)的相關(guān)仿真實驗，這些數(shù)據(jù)集分別被命名為C35/C50/C85/C100。真實算例取自長春市各個不同行政區(qū)內(nèi)相關(guān)小區(qū)的真實節(jié)點數(shù)據(jù)：C35的真實節(jié)點信息在汽開區(qū)內(nèi)隨機選取，C50的真實節(jié)點信息在凈月區(qū)內(nèi)隨機選取，C85的真實節(jié)點信息為長春新區(qū)（高新）的所有小區(qū)節(jié)點，C100的真實節(jié)點信息在朝陽區(qū)內(nèi)隨機選?。浑S機生成的節(jié)點數(shù)據(jù)組則均滿足在各行政區(qū)范圍內(nèi)均勻分布。

為測試DRL-MFA算法在上述數(shù)據(jù)集中的性能表現(xiàn)，并驗證多特征聚合嵌入層MFA對網(wǎng)絡(luò)計算結(jié)果所產(chǎn)生的影響。本節(jié)采用小規(guī)模算例中表現(xiàn)較好的粒子群優(yōu)化算法[29]、遺傳算法[30]和同樣基于深度強化學(xué)習(xí)的AM算法[18]與所提出的DRL-MFA網(wǎng)絡(luò)模型進行對比實驗，結(jié)果如表3所示。其中，Obj為目標(biāo)函數(shù)值，表示距離收益的費用效益比，比值越低說明外賣騎手獲得的平均收益越高，GAP表示與當(dāng)前已知最優(yōu)目標(biāo)函數(shù)Obj之間的差距大小。

由表3可知，無論是隨機生成算例或是真實算例實驗，在面對不同規(guī)模大小的MRTSP時，經(jīng)過訓(xùn)練的基于深度強化學(xué)習(xí)的DRL-MFA算法，計算結(jié)果都優(yōu)于貪婪算法、粒子群優(yōu)化算法和AM算法，證明了DRL-MFA算法在處理具有多特征嵌入的MRTSP時，具有更高的計算精度。同時，本文DRL-MFA算法得到了明顯優(yōu)于無MFA加持的深度強化學(xué)習(xí)算法的計算結(jié)果，且隨著問題規(guī)模不斷擴大，結(jié)果差異越顯著，證明了MFA模塊可以更有效地提取不同輸入特征之間的重要信息，從而加速模型的整體收斂速度。

為更直觀地表現(xiàn)各深度強化學(xué)習(xí)算法在面對不同規(guī)模的MRTSP時的訓(xùn)練過程，圖6分別展示了AM和DRL-MFA算法在各個不同規(guī)模實例上的訓(xùn)練學(xué)習(xí)曲線。由圖可知，在訓(xùn)練初始階段，模型的平均費用效益比較高；隨著訓(xùn)練次數(shù)的增加，模型的目標(biāo)函數(shù)值大幅下降，后逐漸趨向于收斂。無MFA層加持的深度強化學(xué)習(xí)算法，在進行網(wǎng)絡(luò)訓(xùn)練時極易陷入局部最優(yōu)，使得算法無法收斂到最優(yōu)解。AM算法僅考慮單一節(jié)點輸入特征，在面對更大規(guī)模的MRTSP時，前期收斂速度明顯降低。而MFA模塊在編碼時考慮了包括收益矩陣在內(nèi)的所有特征，這使得DRL-MFA算法能夠更充分地考慮全局信息，獲得更快的收斂速度和更高質(zhì)量的解。隨著問題規(guī)模的不斷擴大，算法對模型起到的收斂作用更加明顯。

3.3 靈敏度分析

對于本文研究的外賣配送問題，兩個顧客節(jié)點之間的距離矩陣和收入矩陣會直接影響目標(biāo)函數(shù)總行程和總收益的比值。由于上述實驗均基于真實節(jié)點數(shù)據(jù)信息，節(jié)點坐標(biāo)之間的距離不會產(chǎn)生變化，所以本節(jié)不考慮距離矩陣的變化，而是考慮定價策略（即收益矩陣）對算法結(jié)果可能產(chǎn)生的影響。

根據(jù)MRTSP的定義，目標(biāo)函數(shù)值會根據(jù)收益矩陣的變化呈現(xiàn)出反比式地同步變化。例如，當(dāng)收益矩陣元素值變大時，目標(biāo)函數(shù)所代表的費用效益比則會變小。本節(jié)以真實算例中的C35數(shù)據(jù)組為例，進行靈敏度實驗，具體分析定價策略發(fā)生變化時，目標(biāo)函數(shù)值的變化情況。根據(jù)本文提出的定價策略，本節(jié)將從遠(yuǎn)距離配送定價（5 km以上）、近距離配送定價（3～5 km）、起送費定價（3 km以內(nèi)）三個角度對外賣配送問題進行靈敏度分析實驗。

3.3.1 遠(yuǎn)距離配送定價

本節(jié)考慮遠(yuǎn)距離配送定價對騎手配送收益所產(chǎn)生的影響，分別討論不同遠(yuǎn)距離配送收費標(biāo)準(zhǔn)與目標(biāo)函數(shù)值之間的關(guān)系，相關(guān)定價模型如表4所示。

具體實驗結(jié)果如圖7所示，當(dāng)超過5 km的收費標(biāo)準(zhǔn)降低至每千米增收1元時，平均目標(biāo)函數(shù)值會上升，此時費用效益比變高，外賣騎手每千米平均收益減少。當(dāng)超過5 km的收費標(biāo)準(zhǔn)提高至每千米增收3元或每千米增收4元時，平均目標(biāo)函數(shù)值會下降，此時費用效益比變低，外賣騎手每千米平均收益增加。

收益矩陣的變化除了會對目標(biāo)函數(shù)值帶來變化之外，還會影響具體節(jié)點的訪問順序和路徑軌跡。同樣，以C35數(shù)據(jù)集對應(yīng)的真實算例為例，討論其在各不同的定價模型下的最優(yōu)目標(biāo)函數(shù)值以及最優(yōu)路徑軌跡圖之間的差異。

如圖8所示，8/1/1和8/1/2定價模型的最優(yōu)路徑雖然相同，但遠(yuǎn)距離配送收益的減少，造成總收益值的減少，導(dǎo)致目標(biāo)函數(shù)值增加至0.274 9，外賣騎手的費用效益比升高；與8/1/2定價模型最優(yōu)路徑相比，8/1/3定價模型的最優(yōu)路徑則交換了部分節(jié)點之間的訪問順序，使得總距離從83.851 8 km增長至84.453 2 km，總收益從315元增長至328元，目標(biāo)函數(shù)值從0.266 2下降至0.257 5；與8/1/2和8/1/3定價模型最優(yōu)路徑相比，8/1/4定價模型的最優(yōu)路徑變化更加明顯，總距離和總收益均發(fā)生了一定程度上的增長，總距離增長至92.879 3 km，總收益增長至381元，因為收益增幅大于路徑距離增幅，其目標(biāo)函數(shù)降低至0.243 8。由于8/1/3和8/1/4定價模型的遠(yuǎn)距離配送收益發(fā)生了不同程度的增加，所以騎手會更青睞于選擇遠(yuǎn)距離配送策略，使得問題目標(biāo)函數(shù)值下降，外賣騎手的費用效益比降低。

3.3.2 近距離配送定價

在3.3.1節(jié)8/1/3定價模型的基礎(chǔ)之上，本節(jié)考慮近距離配送定價對騎手配送收益所產(chǎn)生的影響，分別討論近距離配送時，每公里增收0.5元、1元、2元的定價情況，并根據(jù)不同的收費標(biāo)準(zhǔn)，將其命名為8/0.5/3定價模型、8/1/3定價模型、8/2/3定價模型。

經(jīng)過實驗對比發(fā)現(xiàn)，與8/1/3定價模型最優(yōu)路徑相比，由于8/0.5/3定價模型的近距離配送收益變小，使得遠(yuǎn)距離配送可獲得的平均收益相對上漲，于是8/0.5/3定價模型會盡可能選擇遠(yuǎn)距離配送策略，使得最優(yōu)路徑發(fā)生明顯的變化，最優(yōu)配送路線的總路徑距離增長至92.879 3 km，總收益增長至352元，由于收益增幅小于路徑距離增幅，使得目標(biāo)函數(shù)值從0.257 5上升至0.263 9，外賣騎手的費用效益比增加；而8/2/3定價模型和8/1/3定價模型的最優(yōu)路徑雖然相同，但由于近距離配送收益的增長，騎手總收益增長至343元，目標(biāo)函數(shù)值減少至0.246 2，使得外賣騎手的費用效益比降低。

3.3.3 起送費定價

本節(jié)考慮起送費定價對騎手配送收益所產(chǎn)生的影響，在3.3.1節(jié)8/1/3定價模型的基礎(chǔ)之上，分別討論起送費征收6元、8元、12元的定價情況，并根據(jù)不同的收費標(biāo)準(zhǔn)，將其命名為6/1/3定價模型、8/1/3定價模型、12/1/3定價模型。

經(jīng)過實驗對比發(fā)現(xiàn)，由于6/1/3定價模型的起送費較低，前3 km平均配送收益約為2元，小于遠(yuǎn)距離的配送收益3元每km，使得遠(yuǎn)距離配送可獲得的平均收益更多，于是相比較8/1/3定價模型而言，6/1/3定價模型會使騎手考慮平均收益更高的遠(yuǎn)距離配送策略，使得騎手的配送距離發(fā)生明顯的增長。最優(yōu)配送路線的總路徑距離增長至92.879 3 km，但起送費的減少使得總收益縮減至289元，由于收益增幅小于路徑距離增幅，6/1/3定價模型使得目標(biāo)函數(shù)值上升，外賣騎手的費用效益比增加。而12/1/3定價模型則大幅增長了前3 km的平均配送收益至每千米4元，高于遠(yuǎn)距離配送收益的每千米3元，因此騎手會選擇近距離配送路線，行駛總距離縮短至83.851 8 km，但起送費的增加，使得騎手總收益值增長至465元，目標(biāo)函數(shù)值從0.257 5減少至0.180 3，外賣騎手的費用效益比降低。

綜合來看，改變定價策略就是在改變近距離配送平均費用效益比和遠(yuǎn)距離配送平均費用效益比之間的關(guān)系，并討論該行為會對最優(yōu)配送路線產(chǎn)生的影響。經(jīng)靈敏度實驗證明：在遠(yuǎn)距離配送定價降低、近距離配送定價增加、起送費定價增加的情況下，近距離配送能使配送騎手獲得更高的平均收益，減少騎手的費用效益比，從而實現(xiàn)騎手自身配送利益的最大化，且每種配送定價的變化幅度越大，對路徑選擇產(chǎn)生的影響越多；當(dāng)遠(yuǎn)距離配送定價增長、近距離配送定價降低、起送費定價降低時，相對近距離配送而言，遠(yuǎn)距離配送的每千米平均收益更高，外賣騎手會因為被遠(yuǎn)距離高收益的定價策略所吸引，從而主動選擇在一定程度上增加自己的平均配送距離，以謀求更高的配送收益，減少自身的費用效益比。

4 結(jié)束語

針對目前外賣配送問題中訂單數(shù)量多、騎手收益低等現(xiàn)實問題，本文研究如何幫助外賣騎手選擇一條完整的配送路徑，既能夠保證為每個顧客提供配送服務(wù)，同時又能夠增加外賣騎手獲得的配送收益。根據(jù)外賣配送路徑優(yōu)化問題的特征，本文將其歸納為最小比率旅行商問題并對其進行分析討論，提出了基于Transformer架構(gòu)改進的DRL-MFA算法模型。通過MRTSP經(jīng)典算例及大量的數(shù)值仿真實驗，結(jié)果表明DRL-MFA算法具有比啟發(fā)式算法更高的模型計算精度，驗證了深度強化學(xué)習(xí)算法求解MRTSP的可行性和有效性。后續(xù)研究可以進一步討論該模型算法在考慮顧客等待時間情況下的求解能力；此外，本文考慮單一騎手完成外賣配送任務(wù)的情況，可以考慮在配送中心設(shè)置多個配送騎手進行外賣配送任務(wù)。

參考文獻(xiàn)：

[1]國家七部委. 關(guān)于落實網(wǎng)絡(luò)餐飲平臺責(zé)任切實維護外賣送餐員權(quán)益的指導(dǎo)意見 [EB/OL]. （2021-07-26） [2024-05-13] . http：//www. gov. cn/xinwen/2021-07/26/content_5627462. htm. （Seven National Ministries of China. Guiding opinions on implementing the responsibility of online catering platforms and effectively safeguarding the rights and interests of delivery workers [EB/OL]. （2021-07-26） [2024-05-13]. http：//www. gov. cn/xinwen/2021-07/26/content_5627462. htm.）

[2]馮愛蘭， 周映雪， 龔艷茹， 等. 搶派結(jié)合模式下外賣配送問題研究 [J/OL]. 控制與決策. （2023-10-08） [2024-05-13]. https：//doi. org/10. 13195/j. kzyjc. 2022. 1420. （Feng Ailan， Zhou Yingxue， Gong Yanru， et al.Research on takeout distribution based on the combination mode of order dispatching and grabbing [J/OL]. Control and Decision. （2023-10-08） [2024-05-13]. https：//doi. org/10. 13195/j. kzyjc. 2022. 1420.）

[3]趙強柱， 盧福強， 王雷震， 等. 無人機騎手聯(lián)合外賣配送路徑優(yōu)化問題研究 [J]. 計算機工程與應(yīng)用， 2022， 58 （11）： 269-278. （Zhao Qiangzhu， Lu Fuqiang， Wang Leizhen， et al.Research on drones and riders joint take-out delivery routing problem [J]. Computer Engineering and Applications， 2022， 58 （11）： 269-278.）

[4]馬良. 求解最小比率TSP的一個算法 [J]. 系統(tǒng)工程， 1998 （4）： 62-65. （Ma Liang. An algorithm for solving minimum ratio TSP [J]. Systems Engineering， 1998 （4）： 62-65.）

[5]寧愛兵， 馬良. 最小比率旅行商 （MRTSP） 問題競爭決策算法 [J]. 計算機工程與應(yīng)用， 2005，41 （11）： 30-32， 59. （Ning Ai-bing， Ma Liang. Competitive decision algorithms for minimum ratio traveling salesman problem [J]. Computer Engineering and Applications， 2005，41 （11）： 30-32， 59.）

[6]盛虹平. 求解最小比率旅行商問題的大洪水算法 [J]. 杭州師范大學(xué)學(xué)報： 自然科學(xué)版， 2010， 9 （6）： 401-405. （Sheng Hongping. A great deluge algorithm for solving the minimum ratio traveling salesman problem [J]. Journal of Hangzhou Normal University： Natural Science Edition， 2010， 9 （6）： 401-405.）

[7]李枝勇， 馬良， 張惠珍. 求解最小比率旅行商問題的離散蝙蝠算法 [J]. 計算機應(yīng)用研究， 2015， 32 （2）： 356-359. （Li Zhiyong， Ma Liang， Zhang Huizhen. Discrete bat algorithm for solving minimum ratio traveling salesman problem [J]. Application Research of Computers， 2015， 32 （2）： 356-359.）

[8]Ma Liang， Cui Xueli， Yao Jian. Finding the minimum ratio traveling salesman tour by artificial ants [J]. Journal of Systems Enginee-ring and Electronics， 2003， 14 （3）： 24-27.

[9]劉勇， 馬良. 最小比率旅行商問題的引力搜索算法求解 [J]. 小型微型計算機系統(tǒng)， 2013， 34 （4）： 847-849. （Liu Yong， Ma Liang. Gravitational search algorithm for minimum ratio traveling salesman problem [J]. Journal of Chinese Computer Systems， 2013， 34 （4）： 847-849.）

[10]劉勇， 田澎. 求解最小比率旅行商問題的中心引力優(yōu)化算法 [J]. 系統(tǒng)工程， 2016， 34 （3）： 117-123. （Liu Yong， Tian Peng. Central force optimization algorithm for solving minimum ratio traveling salesman problem [J]. Systems Engineering， 2016， 34 （3）： 117-123.）

[11]許秋艷， 馬良， 劉勇. 最小比率旅行商問題的陰陽平衡優(yōu)化算法 [J]. 計算機仿真， 2022， 39 （8）： 356-362. （Xu Qiuyan， Ma Liang， Liu Yong. Yin-yang pair optimization algorithm for minimum ratio traveling salesman problem [J]. Computer Simulation， 2022， 39 （8）： 356-362.）

[12]紀(jì)志勇， 袁逸萍， 巴智勇， 等. 基于多動作深度強化學(xué)習(xí)的紡機制造車間調(diào)度方法 [J]. 計算機應(yīng)用研究， 2023， 40 （11）： 3247-3253. （Ji Zhiyong， Yuan Yiping， Ba Zhiyong， et al.Multi-action deep reinforcement learning based scheduling method for spinning machine manufacturing shop floor [J]. Application Research of Computers， 2023， 40 （11）： 3247-3253.）

[13]伍康， 夏維， 王子源. 一種基于圖神經(jīng)網(wǎng)絡(luò)的改進鄰域搜索算法 [J]. 計算機應(yīng)用研究， 2024， 41 （5）： 1402-1408. （Wu Kang， Xia Wei， Wang Ziyuan. Improved neighborhood search algorithm based on graph neural network [J]. Application Research of Computers， 2024， 41 （5）： 1402-1408.）

[14]雷坤， 郭鵬， 王祺欣， 等. 基于end-to-end深度強化學(xué)習(xí)的多車場車輛路徑優(yōu)化 [J]. 計算機應(yīng)用研究， 2022， 39 （10）： 3013-3019. （Lei Kun， Guo Peng， Wang Qixin， et al.End-to-end deep reinforcement learning framework for multi-depot vehicle routing problem [J]. Application Research of Computers， 2022， 39 （10）： 3013-3019.）

[15]Vinyals O， Fortunato M， Jaitly N. Pointer networks [C]// Proc of the 28th International Conference on Neural Information Processing Systems. Cambridge， MA： MIT Press， 2015： 2692-2700.

[16]Nazari M， Oroojlooy A， Snyder L V，et al.Reinforcement learning for solving the vehicle routing problem [EB/OL]. （2018-05-21） [2024-05-13]. http：//arxiv. org/pdf/1802. 04240. pdf.

[17]Ling Zhengxuan， Zhang Yu， Chen Xi. A deep reinforcement learning based real-time solution policy for the traveling salesman problem [J]. IEEE Trans on Intelligent Transportation Systems， 2023， 24 （6）： 5871-5882.

[18]Kool W， Van Hoof H， Welling M. Attention， learn to solve routing problems！ [EB/OL]. （2019-02-07）[2024-05-13]. http：//arxiv. org/pdf/1803. 08475. pdf.

[19]柯琳， 楊笑笑， 陳智斌. 一種帶泛化性能的動態(tài)混合模型求解大范圍TSP問題 [J]. 系統(tǒng)科學(xué)與數(shù)學(xué)， 2024， 44 （1）： 31-44. （Ke Lin， Yang Xiaoxiao， Chen Zhibin. A dynamic hybrid model with generalization performance to solve large-scale TSP [J]. Journal of Systems Science and Mathematical Sciences， 2024， 44 （1）： 31-44.）

[20]Zhang Zizhen， Liu Hong， Zhou Mengchu，et al.Solving dynamic tra-veling salesman problems with deep reinforcement learning [J]. IEEE Trans on Neural Networks and Learning Systems， 2023， 34 （4）： 2119-2132.

[21]Sutskever I， Vinyals O， Le Q V. Sequence to sequence learning with neural networks [EB/OL]. （2014-12-14） [2024-05-13]. http：//arxiv. org/pdf/1409. 3215. pdf.

[22]Vaswani A， Shazeer N， Parmar N，et al.Attention is all you need [C]// Proc of the 31st International Conference on Neural Information Processing Systems. Red Hook，NY： Curran Associates Inc.， 2017： 6000-6010.

[23]王萬良， 陳浩立， 李國慶， 等. 基于深度強化學(xué)習(xí)的多配送中心車輛路徑規(guī)劃 [J]. 控制與決策， 2022， 37 （8）： 2101-2109. （Wang Wanliang， Chen Haoli， Li Guoqing， et al.Deep reinforcement learning for multi-depot vehicle routing problem [J]. Control and Decision， 2022， 37 （8）： 2101-2109.）

[24]Sutton R S， McAllester D A， Singh S P，et al.Policy gradient me-thods for reinforcement learning with function approximation [C]// Proc of the 12th International Conference on Neural Information Processing Systems. Cambridge， MA： MIT Press， 2000： 1057-1063.

[25]Kingma D P， Ba J. Adam： a method for stochastic optimization [EB/OL]. （2017-01-30） [2024-05-13]. http：//arxiv. org/pdf/1412. 6980. pdf.

[26]Rashedi E， Nezamabadi-Pour H， Saryazdi S. GSA： a gravitational search algorithm [J]. Information Sciences， 2009， 179 （13）： 2232-2248.

[27]Simon D. Biogeography-based optimization [J]. IEEE Trans on Evolutionary Computation， 2008， 12（6）： 702-713.

[28]Bouchekara H. Most valuable player algorithm： a novel optimization algorithm inspired from sport [J]. Operational Research， 2020， 20 （1）： 139-195.

[29]Bratton D， Kennedy J. Defining a standard for particle swarm optimization [C]// Proc of IEEE Swarm Intelligence Symposium. Pisca-taway，NJ：IEEE Press， 2007： 120-127.

[30]Holland J H. Adaptation in natural and artificial systems： an introductory analysis with applications to biology control and artificial intelligence [M]. Cambridge，MA： MIT Press， 1992.