基于無人機——騎手協(xié)同模式的即時配送優(yōu)化研究

摘要

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

關(guān)鍵詞

即時配送；無人機—騎手；協(xié)同配送；改進遺傳算法；路徑優(yōu)化問題

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 引言

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

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

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

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

即時配送研究在路徑優(yōu)化與成本控制方面雖取得進展，但應(yīng)對高峰期運力不足及復(fù)雜場景時存在明顯局限。現(xiàn)有方案主要通過增加騎手?jǐn)?shù)量或提升單騎手訂單量補充運力，但高峰期與交通高峰重疊，傳統(tǒng)配送易因擁堵導(dǎo)致延遲，大幅增加時間窗懲罰成本。而提高單騎手訂單量易引發(fā)過度勞累增加配送事故風(fēng)險。

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

2 問題描述與數(shù)學(xué)模型

2.1問題描述

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

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

2.2模型假設(shè)與符號定義

2.2.1模型假設(shè)

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

2.2.2符號定義

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

表1模型符號定義表

2.3數(shù)學(xué)模型

本文基于混合整數(shù)規(guī)劃法構(gòu)建了以下數(shù)學(xué)優(yōu)化模型：

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

3 算法設(shè)計

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

圖 2 改進遺傳算法流程圖

3.1解的編碼

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

圖 3 染色體編碼示意

3.2構(gòu)造啟發(fā)式算法

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

偽代碼如圖4所示：

圖 4構(gòu)造啟發(fā)式算法偽代碼

3.3選擇算子

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

3.4雙點交叉算子

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

圖 5雙點交叉算子示意

3.5成對交換變異算子

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

3.6修復(fù)算子

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

3.7局部搜索算子

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

4 實驗分析

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

4.1算例設(shè)計

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

算例參數(shù)設(shè)置如表2所示。

表2 算例參數(shù)信息表

4.2算例實驗

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

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

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

表3 各算例結(jié)果整合表

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

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

圖8instance50_1迭代對比圖

4.3模式對比

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

表 4傳統(tǒng)模式下騎手配送方案

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

表 6 配送效果對比分析

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

5 結(jié)論

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

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

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

作者簡介

牛國棟，武漢科技大學(xué)碩士研究生

王鑫鑫，武漢科技大學(xué)管理學(xué)院教授

參考文獻