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

摘要

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

關(guān)鍵詞

即時(shí)配送；無(wú)人機(jī)—騎手；協(xié)同配送；改進(jìn)遺傳算法；路徑優(yōu)化問(wèn)題

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

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

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

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

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

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

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

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

2.1問(wèn)題描述

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

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

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

2.2.1模型假設(shè)

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

2.2.2符號(hào)定義

本文模型所需符號(hào)的定義如表1所示。

表1模型符號(hào)定義表

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

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

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

3 算法設(shè)計(jì)

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

圖 2 改進(jìn)遺傳算法流程圖

3.1解的編碼

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

圖 3 染色體編碼示意

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

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

偽代碼如圖4所示：

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

3.3選擇算子

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

3.4雙點(diǎn)交叉算子

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

圖 5雙點(diǎn)交叉算子示意

3.5成對(duì)交換變異算子

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

3.6修復(fù)算子

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

3.7局部搜索算子

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

4 實(shí)驗(yàn)分析

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

4.1算例設(shè)計(jì)

為驗(yàn)證無(wú)人機(jī)—騎手協(xié)同配送模型和改進(jìn)遺傳算法的有效性，本文基于三種規(guī)模的15組算例進(jìn)行實(shí)驗(yàn)。數(shù)據(jù)來(lái)自美國(guó)外賣公司與佐治亞理工學(xué)院2018年公開(kāi)在GitHub上的算例集，本文進(jìn)行改進(jìn)，使其適用本文所研究無(wú)人機(jī)-騎手協(xié)同配送問(wèn)題。本文使用三組不同訂單規(guī)模的算例組，每組算例包含五組獨(dú)立的小算例。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í)驗(yàn)

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

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

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

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

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

圖6 instance20_1迭代對(duì)比圖 圖7 instance35_1迭代對(duì)比圖

圖8instance50_1迭代對(duì)比圖

4.3模式對(duì)比

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

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

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

表 6 配送效果對(duì)比分析

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

5 結(jié)論

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

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

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

作者簡(jiǎn)介

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

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

參考文獻(xiàn)