基于無人機——騎手協同模式的即時配送優化研究

摘要

針對即時配送高峰期效率瓶頸，提出無人機—騎手協同配送模式。構建帶時間窗的混合整數規劃模型，設計改進遺傳算法：通過構造啟發式算法生成初始解，采用雙點交叉算子和成對交換變異算子增強搜索能力，結合局部搜索提升收斂速度。算例實驗表明，協同模式較傳統配送成本降低38.1%，有效緩解騎手工作負荷與時間窗違約風險。

關鍵詞

即時配送；無人機—騎手；協同配送；改進遺傳算法；路徑優化問題

Abstract

Aiming at the efficiency bottleneck during the peak period of instant delivery, a drone-rider collaborative distribution mode is proposed. A hybrid integer programming model with a time window is constructed, and an improved genetic algorithm is designed: the initial solution is generated by constructing a heuristic algorithm, and the search ability is enhanced by using a two-point crossover operator and a pairwise exchange mutation operator, and the convergence speed is improved by combining with local search. Numerical example experiments show that the collaborative mode reduces the cost by 38.1% compared with traditional distribution, which effectively alleviates the risk of rider workload and time window default.

Keywords

Instant delivery；Drone-rider； Cooperative delivery；Improved genetic algorithm；Path optimization problem

1 引言

近年來，電子商務的迅猛發展推動即時配送市場的快速擴張。2023年，中國即時配送市場規模達15254億元，用戶增至5.45億人，未來幾年仍將增長[1]。艾瑞咨詢預計，全球即時配送市場將以兩位數年復合增長率增長，2030年達到3.6萬億美元[2]。

隨著外賣市場規模擴張引發高峰期問題：高峰期訂單激增導致運力不足、成本上升及騎手違規。企業探索無人機配送作為補充方案，如美團通過無人機航線縮配送時40%[3]，京東/順豐同步優化運力。因此，無人機協助騎手成為潛力方案，但因訂單時效嚴苛、地理分散及騎手動態性，高效路徑規劃面臨挑戰。

即時配送屬車輛路徑問題拓展，需在規定時限完成“取貨—送貨”全流程。按訂單量可分為兩類模式：一對一配送（如醫療用品取送[4]）與并發訂單配送（外賣高頻場景）。學者們聚焦路徑優化與動態響應：徐菱等[5]建立需求可拆分模型提升響應效率；陳萍等[6]融合客戶滿意度指標改進算法；Ulmer[9]針對出餐隨機性構建馬爾可夫決策模型；Yildiz等[10]開發訂單打包的混合整數規劃模型；Reyes[11]則提出增量禁忌搜索算法增強求解能力。

無人機配送研究聚焦協同模式創新。Murray和Chu[12]開創車輛—無人機協同框架，提出FSTSP（車載平臺）與PDSTSP（倉庫平臺）兩類基礎問題。學者們在此基礎上持續拓展：吳廷映等[13]研究可收派件協同路徑；Zhang等[14]構建多目標優化模型；顏瑞等[15]探索限行禁飛約束下的配送方案；Poikonen等[16]突破單機約束研究多無人機調度。

即時配送研究在路徑優化與成本控制方面雖取得進展，但應對高峰期運力不足及復雜場景時存在明顯局限。現有方案主要通過增加騎手數量或提升單騎手訂單量補充運力，但高峰期與交通高峰重疊，傳統配送易因擁堵導致延遲，大幅增加時間窗懲罰成本。而提高單騎手訂單量易引發過度勞累增加配送事故風險。

本文提出一種無人機—騎手協同配送模式，引入無人機作運力補充，利用其快速響應與繞過擁堵的能力緩解效率瓶頸。該模式優先將客戶點分配給無人機處理短途高時效訂單，騎手服務超出無人機范圍的訂單，通過設定最大服務點數降低疲勞配送風險。無人機與騎手協同提升配送效率，也減少交通延誤帶來的懲罰成本，同時減輕騎手工作強度與安全隱患。為實現該模式，本文針對商圈配送特點設計虛擬節點處理方法，并結合時間窗約束建立優化模型。提出改進遺傳算法，采用構造啟發式初始解、雙點交叉算子等提升求解質量。實驗表明，該協同模式在高峰期顯著降低配送成本達38.1%，為即時配送可持續發展提供有效解決方案。

2 問題描述與數學模型

2.1問題描述

本文研究的即時配送問題如圖1所示：騎手從配送中心出發服務取貨點和客戶點，遵循“先取后送”規則；無人機從機場完成取貨后配送并返回。圖中內圈為商圈范圍，外圈為無人機服務范圍，機場設于商圈中心。服務范圍內客戶點可由騎手或無人機配送，范圍外僅由騎手配送。采用軟時間窗約束，超時產生懲罰成本。對于取貨點服務多客戶點情況，采用虛擬節點（如109）處理。為保障騎手權益，限制其最大服務客戶數。

圖 1“無人機—騎手”協同配送模式下的車輛路徑優化問題示意

2.2模型假設與符號定義

2.2.1模型假設

根據實際配送過程，設定以下假設：（1）客戶、商家及配送中心的位置與距離已知，客戶時間窗和需求量已知；（2）騎手、無人機及取貨員速度恒定；（3）僅考慮運輸時間，忽略備餐、取餐和交付等待時間；（4）忽略貨物重量對無人機性能的影響；（5）騎手不受載重限制，僅約束其最大服務客戶數。

2.2.2符號定義

本文模型所需符號的定義如表1所示。

表1模型符號定義表

2.3數學模型

本文基于混合整數規劃法構建了以下數學優化模型：

式（1）為目標函數，最小化總配送成本，包括騎手、無人機和取貨員的路徑成本及時間窗懲罰成本；式（2）確保所有客戶點均被服務；式（3）和式（4）定義無人機服務節點標記與限制；式（5）為騎手服務客戶點數上限；式（6）和式（7）保證取貨點與對應客戶點服務一致性；式（8）計算時間窗懲罰成本；式（9）~（11）為騎手、取貨員和無人機的路徑返回約束；式（12）~（14）為進出守恒約束；式（15）和式（16）為先取后送約束；式（17）為0~1決策變量約束。

3 算法設計

無人機—騎手協同配送屬NP-Hard問題，傳統遺傳算法存在不可行解多、局部搜索弱等缺陷。本文提出改進遺傳算法(IGA)：（1）構造啟發式初始解優先分配無人機訂單；（2）雙點交叉算子保持路徑連續性；（3）成對交換變異維持“先取后送”規則；（4）局部搜索優化短途—長途協同路徑。改進遺傳算法的具體流程圖如下：

圖 2 改進遺傳算法流程圖

3.1解的編碼

本文設計的改進遺傳算法采用自然數編碼，操作如下：首先將客戶點隨機排列；然后以騎手最大服務客戶點數為間隔（這里設置為4），插入0節點進行分割，來表示不同騎手的服務節點；最后，將取貨點插入其對應的客戶點前面，完成染色體的編碼。

圖 3 染色體編碼示意

3.2構造啟發式算法

本文算法思路如下：考慮無人機配送模式成本上的優越性，優先將可分配給無人機的客戶分配給無人機配送以降低配送成本；而后將未被分配給無人機的客戶指派騎手配送；最后按照染色體的編碼方式，采用隨機生成的方法得到初始解。本文對于取貨員最優路徑的求解采用最近鄰算法。

偽代碼如圖4所示：

圖 4構造啟發式算法偽代碼

3.3選擇算子

在算子的選擇上，本文采用精英保留策略和輪盤賭策略。

3.4雙點交叉算子

本文在交叉算子的選擇上，采用雙點交叉算子，采用前向交叉方法，具體操作如圖5所示：

圖 5雙點交叉算子示意

3.5成對交換變異算子

針對即時配送中取貨點與客戶點配對的特點，傳統變異算子易產生大量不可行解。為此，本文設計成對交換變異算子：隨機選取兩取貨點及其對應客戶點，交換取貨與客戶點組合，生成新子代。該方法在增強解多樣性的同時，顯著減少不可行解產生。

3.6修復算子

在修復算法運行前，需評估染色體的可行性。本文設計的改進遺傳算法在交叉變異時采用雙點交叉，這可能導致部分子代染色體違反“先取后送”或“同騎手服務”約束。為此，本文設計修復算子，通過交換、刪除和插入節點來修復不可行染色體。修復算子流程如下：①可行性評估：檢查子代染色體是否滿足約束。②節點調整：將不可行節點進行刪除、插入操作。③順序修復：檢查每對客戶—取貨點順序，若不符則交換位置。

3.7局部搜索算子

本文改進遺傳算法時加入了局部搜索算子，以概率選擇染色體進行精細搜索，提升解質量與收斂速度。以染色體c1為例：先按0節點分割為片段c11、c12；分別提取各片段內的客戶點和取貨點；將取貨點隨機排序后插入，再插入對應客戶點（確保位于取貨點之后）；最后合并片段，獲得新染色體c2。

4 實驗分析

本文使用所有算法部分的設計通過MATLAB進行編寫，使用版本為MATLAB2020b，在Windows 10 系統下運行。電腦處理器為Intel(R)Core(TM) i5-8250U ，有1.60 GHz 和8.00 GB RAM內存。

4.1算例設計

為驗證無人機—騎手協同配送模型和改進遺傳算法的有效性，本文基于三種規模的15組算例進行實驗。數據來自美國外賣公司與佐治亞理工學院2018年公開在GitHub上的算例集，本文進行改進，使其適用本文所研究無人機-騎手協同配送問題。本文使用三組不同訂單規模的算例組，每組算例包含五組獨立的小算例。instance20_1到instance20_5訂單規模為20，instance35_1到instance35_5訂單規模為35，instance50_1到instance50_5訂單規模為50。

算例參數設置如表2所示。

表2 算例參數信息表

4.2算例實驗

為測試算法性能，本文使用改進遺傳算法進行數學模型求解，為綜合評價算法性能，本文還使用傳統遺傳（GA）算法與貪婪算法在15組算例下進行對比實驗。

改進遺傳算法與GA算法參數設置相同，本文設置種群規模 N=100，交叉概率pc= 0.9，變異概率pm= 0.1為兩種算法的輸入，對于改進遺傳算法局部搜索概率ps= 0.1，模擬退火策略初始溫度T0 = le5，降溫速率q=0.6，精英個體保留概率m=0.2，兩算法迭代次數均設置為800次。

表3為各組實驗下優化情況總體匯總，由該表可以看出，客戶規模分別為20、35、50時，改進遺傳算法比遺傳算法求解時間分別縮短8.2%、5.7%、4.8%；總成本求解上，改進遺傳算法在三個算例規模上比GA算法分別降低了26.4%、38.4%、32.1%，比貪婪算法分別降低了41.6%、52.9%、41.7%。這表明本文設計算法實現了更好的優化效果，迭代速度相較傳統遺傳算法更快。

表3 各算例結果整合表

為更好展示改進遺傳算法的優化表現，本文以instance20_1、instance35_1和instance50_1為例，繪制了改進遺傳算法與遺傳算法在優化目標上的收斂表現。如圖6-圖8可以看出改進遺傳算法相較于傳統的遺傳算法在求解無人機-騎手協同配送問題時，在優化表現上更好，并且具有更強的跳出局部最優能力。

圖6 instance20_1迭代對比圖 圖7 instance35_1迭代對比圖

圖8instance50_1迭代對比圖

4.3模式對比

以實例instance35_1分析無人—騎手協同與傳統配送模式成本，由表4和表5可知，協同模式顯著降低成本并優化線路。該模式將遠距離或高時效訂單交由無人機完成，減輕騎手負荷，縮短配送時間，高峰期可靈活擴展運力，在效率和經濟性上具有明顯優勢，適用于復雜場景。

表 4傳統模式下騎手配送方案

表 5無人機-騎手協同配送模式下配送方案

表 6 配送效果對比分析

由表6可知，無人機—騎手協同配送模式較傳統模式成本降低38.01%。該模式下，騎手路徑成本與時間窗懲罰成本得到優化：無人機分擔配送任務，減少騎手長途奔波，降低路徑成本；同時無人機高效覆蓋提升了準時配送率，減少了延遲懲罰。該模式通過資源優化配置，實現了效率與成本更優平衡。

5 結論

面對電子商務快速增長所帶來的城市末端配送需求壓力，本文提出了一種無人機與騎手協同的即時配送模式，并構建了以成本最小化為目標的混合整數規劃模型。為解決該優化問題，設計了一種改進遺傳算法，在不同配送場景下實現配送效率和成本的平衡。通過無人機和騎手的協同優勢，模型在路徑優化和運力配置上取得了顯著提升。

算例實驗結果表明，在城市場景中，無人機-騎手協同模式在配送效率和成本控制方面表現出顯著優勢。與傳統騎手模式相比，協同模式能降低約38%的配送成本，在高峰期有效提升響應速度，降低時間窗懲罰成本，改善客戶服務體驗。

本研究尚有不足，如假設無人機續航不受載重影響，但實際上續航會隨載重增加而下降；商家出餐時間存在不確定性；未來可研究訂單需求、配送路況不確定條件下的配送模型構建。

作者簡介

牛國棟，武漢科技大學碩士研究生

王鑫鑫，武漢科技大學管理學院教授

參考文獻