求解外賣配送問題的深度強化學習算法

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

關鍵詞：外賣配送問題；最小比率旅行商問題；深度強化學習；多特征嵌入；注意力機制

中圖分類號：TP18"" 文獻標志碼：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 引言

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

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

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

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

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

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

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

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

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

1 外賣配送問題的數學模型

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

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

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

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

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

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

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

根據外賣配送問題的相關特點，可以將其歸納為最小比率旅行商問題進行求解。基于圖論的知識點，最小比率旅行商問題可以被具體描述如下：

考慮MRTSP為一個給定的賦權完全圖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），表示每對顧客節點之間的路程距離；矩陣P=（pij）n×n，pij=pji，pii=0，pijgt;0（i，j∈V），表示外賣騎手從一個顧客到另一個顧客得到的收益。MRTSP的數學模型表示為

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

2 最小比率旅行商問題的深度強化學習算法

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

2.1 馬爾可夫決策過程

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

MRTSP的狀態空間（state）、動作空間（action）、狀態轉移（transition）、獎勵函數（reward）[20]可以定義如下：

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

動作空間記作A，其中at∈A，表示外賣騎手在當前t時刻將選擇下一時刻訪問某個顧客的決策。騎手會根據環境狀態st－1，通過訓練策略網絡πθ（at|st－1）計算狀態st－1下采取的動作at的概率。

狀態轉移函數記作T（st，a），表示當前時刻外賣騎手選擇在狀態st下選擇動作a后，使得狀態st轉移到下一個新的狀態st+1的過程。根據概率鏈式法則[21]，通過狀態轉移，模型的隨機策略可以定義為式（3），表示在狀態s下，通過策略網絡πθ，選擇路徑方案π的概率。

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

2.2 策略網絡模型

本節介紹了基于Transformer改進的DRL-MFA算法模型，所提策略網絡的總體結構框架如圖3所示。

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

2.2.1 編碼器

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

其中：Wx、Wd、Wp、Wa、bx、bd、bp、ba是MFA層的可訓練網絡參數。

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

（a）多頭注意力子層MHA。MHA子層負責利用多頭注意力的計算來捕捉每個節點之間的特征依賴關系，獲取每個顧客節點的權重信息。MHA子層遵循經典Transformer架構，使用M個維度大小為dk=dh/M的注意力頭來計算自注意力分數，MHA子層的數學公式表達如下：

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

（b）前饋子層FF。FF子層負責執行非線性激活的功能，將MHA子層輸出的特征進行非線性轉換。它由兩層全連接線性網絡與一層激活函數ReLU層構成。首先節點特征進入第一層全連接網絡，將特征信息投射到512維的隱藏層；隨后經過一層ReLU層激活神經元，最后連接第二層全連接網絡，輸出整個前饋子層的計算結果，即

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

2.2.2 解碼器

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

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

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

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

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

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

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

2.3 策略網絡訓練方法

使用Adam優化器[25]與梯度下降法的方式對整個模型網絡進行訓練，具體訓練偽代碼如下：

算法1 帶有基線的REINFORCE強化學習算法

3 數值實驗

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

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

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

3.1 經典算例

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

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

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

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

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

考慮到算法每次運行結果存在偶然性，可能會對優化性能的分析判斷產生影響，所以每種算法會各自獨立運行20次，分別統計最優值、最劣值、平均值、標準差和平均值與最優值之間的差距GAP等指標，并計算每個算法在20次實驗中達到已知最優解的成功率。具體計算結果如表2所示。

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

除此之外，智能優化算法的結果受到迭代次數的影響，且在面對不同實例時，泛化能力較差；而深度強化學習網絡一旦完成訓練便可以當作求解器使用，不用進行算法迭代，即可直接輸出滿意解。

為進一步說明基于深度強化學習的DRL-MFA算法具有更好的優化性能，本文將擴大MRTSP的算例規模，并將其運用于現實真實數據案例中。

3.2 長春市外賣配送案例

本節所有實例均來自于第十九屆中國研究生數學建模競賽F題，數據包括長春市九個行政區的小區坐標節點信息。

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

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

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

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

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

3.3 靈敏度分析

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

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

3.3.1 遠距離配送定價

本節考慮遠距離配送定價對騎手配送收益所產生的影響，分別討論不同遠距離配送收費標準與目標函數值之間的關系，相關定價模型如表4所示。

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

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

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

3.3.2 近距離配送定價

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

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

3.3.3 起送費定價

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

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

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

4 結束語

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

參考文獻：

[1]國家七部委. 關于落實網絡餐飲平臺責任切實維護外賣送餐員權益的指導意見 [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]馮愛蘭， 周映雪， 龔艷茹， 等. 搶派結合模式下外賣配送問題研究 [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]趙強柱， 盧福強， 王雷震， 等. 無人機騎手聯合外賣配送路徑優化問題研究 [J]. 計算機工程與應用， 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]. 系統工程， 1998 （4）： 62-65. （Ma Liang. An algorithm for solving minimum ratio TSP [J]. Systems Engineering， 1998 （4）： 62-65.）

[5]寧愛兵， 馬良. 最小比率旅行商 （MRTSP） 問題競爭決策算法 [J]. 計算機工程與應用， 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]. 杭州師范大學學報： 自然科學版， 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]. 計算機應用研究， 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]. 小型微型計算機系統， 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]劉勇， 田澎. 求解最小比率旅行商問題的中心引力優化算法 [J]. 系統工程， 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]許秋艷， 馬良， 劉勇. 最小比率旅行商問題的陰陽平衡優化算法 [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]. 計算機應用研究， 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]. 計算機應用研究， 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深度強化學習的多車場車輛路徑優化 [J]. 計算機應用研究， 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]柯琳， 楊笑笑， 陳智斌. 一種帶泛化性能的動態混合模型求解大范圍TSP問題 [J]. 系統科學與數學， 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]王萬良， 陳浩立， 李國慶， 等. 基于深度強化學習的多配送中心車輛路徑規劃 [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.