運(yùn)力受擾下的物流無人機(jī)干擾恢復(fù)模型

任新惠， 茍利珍， 武彤

(1.中國民航大學(xué)經(jīng)濟(jì)與管理學(xué)院， 天津 300300； 2.中國民航大學(xué)交通科學(xué)與工程學(xué)院， 天津 300300)

最后一公里配送被認(rèn)為是物流鏈中效率最低、污染最為嚴(yán)重的環(huán)節(jié)，為了實(shí)現(xiàn)綠色包裹交付，用無人機(jī)代替卡車運(yùn)輸，除了無人機(jī)電池充電外，很少涉及碳足跡，從運(yùn)輸時(shí)間、運(yùn)輸成本、碳排放進(jìn)行分析，無人機(jī)相對(duì)于卡車運(yùn)輸具有顯著優(yōu)勢[1]，國內(nèi)學(xué)者針對(duì)農(nóng)村物流配送場景，考慮無人機(jī)飛行能力、最大載重能力等規(guī)劃無人機(jī)調(diào)度路線[2],并結(jié)合當(dāng)前疫情防控的大背景，提出無人機(jī)和車輛聯(lián)合配送模式，與區(qū)域限制相結(jié)合，解決配送效率問題[3]。國外學(xué)者將無人機(jī)應(yīng)用于即時(shí)交付場景，考慮與有效載荷有關(guān)的飛行能耗，得到更貼合實(shí)際的任務(wù)分配方案[4]，同時(shí)設(shè)計(jì)相關(guān)算法，進(jìn)一步優(yōu)化配送成本問題[5]。但隨著無人機(jī)的廣泛應(yīng)用，運(yùn)行事故不斷增加。這些事件的顯著特點(diǎn)是發(fā)生時(shí)間的隨機(jī)性，發(fā)生位置的不確定性、影響程度的差異性和解決方案的特殊性。如何快速有效地對(duì)初始方案進(jìn)行調(diào)整，生成對(duì)原始配送系統(tǒng)擾動(dòng)最小的新方案，同時(shí)協(xié)調(diào)各方利益，這是無人機(jī)實(shí)際應(yīng)用中迫切需要解決的問題。

目前關(guān)于無人機(jī)飛行干擾研究，部分學(xué)者從無人機(jī)自身運(yùn)行安全出發(fā)，進(jìn)行風(fēng)險(xiǎn)分析和評(píng)估[6]，規(guī)劃最優(yōu)航路[7-8]，運(yùn)行故障概率分析[9]。也有學(xué)者關(guān)注無人機(jī)飛行階段的交付可靠性問題，通過考慮飛行故障概率來描述包裹交付的不確定性[10-13]。這些研究主要集中于事前決策，關(guān)于無人機(jī)干擾事件發(fā)生后的實(shí)時(shí)決策研究較少，而車輛物流中干擾管理理論為解決無人機(jī)干擾后的實(shí)時(shí)決策提供了理論依據(jù)。物流干擾管理不是全局重新規(guī)劃，而是以當(dāng)前計(jì)劃為基礎(chǔ)快速生成對(duì)系統(tǒng)擾動(dòng)最小的方案。國內(nèi)學(xué)者王旭坪等[14]針對(duì)車輛配送途中發(fā)生故障，不能繼續(xù)完成配送任務(wù)的情況，提出3種擾動(dòng)恢復(fù)策略。王清斌等[15]針對(duì)新增運(yùn)輸任務(wù)情況，以最小廣義費(fèi)用偏離目標(biāo)驗(yàn)證干擾管理方法的有效性。丁秋雷等[16]針對(duì)配送時(shí)間延遲場景，考慮客戶感知因素，將客戶終身價(jià)值、配送成本等作為擾動(dòng)度量函數(shù)，確定干擾后的客戶交付順序、交付位置、交付時(shí)間等決策參數(shù)。國外學(xué)者Wu等[17]針對(duì)易腐貨物的干擾交付問題，考慮貨物易腐性、交通流的時(shí)間依賴性，交通網(wǎng)絡(luò)的備選路徑，建立基于分批交付的干擾恢復(fù)模型。Tao等[18]基于同時(shí)取送貨的車輛路徑問題，從配送成本和時(shí)間窗偏差兩方面進(jìn)行擾動(dòng)度量，引入目標(biāo)逐級(jí)優(yōu)化的思想，建立基于客戶需求變化的兩階段干擾管理模型。

現(xiàn)有研究致力于無人機(jī)正常運(yùn)行條件下的配送調(diào)度問題，對(duì)于其交付可靠性的重視程度不高，大部分沒有考慮服務(wù)中斷情況，都假設(shè)能夠?qū)崿F(xiàn)完美交付，這一情況是不符合實(shí)際的。在運(yùn)輸過程中，不確定時(shí)刻下的運(yùn)力變化，需求時(shí)間窗、需求位置、需求量變化將使得問題變得復(fù)雜，一旦發(fā)生事故后不能快速提供一個(gè)有效的解決方案，客戶對(duì)于配送風(fēng)險(xiǎn)會(huì)表現(xiàn)出厭惡心理，物流配送企業(yè)將會(huì)受到重大的打擊，物流動(dòng)態(tài)干擾下的調(diào)度恢復(fù)是末端配送所要解決的重點(diǎn)問題。當(dāng)前的無人機(jī)技術(shù)和應(yīng)用仍處于不斷發(fā)展階段，技術(shù)的不成熟和政策的不完善決定了事故風(fēng)險(xiǎn)概率，這是未來無人機(jī)發(fā)展面臨的挑戰(zhàn)，鑒于在動(dòng)態(tài)環(huán)境下的無人機(jī)飛行系統(tǒng)易受到突發(fā)事件、機(jī)身故障和極端天氣等影響，使得初始調(diào)度方案的執(zhí)行變得困難，因此干擾事件發(fā)生前預(yù)先考慮無人機(jī)飛行故障概率、階段能耗，優(yōu)先服務(wù)高價(jià)值、高需求的客戶訂單，減少向客戶交付失敗的需求損失，同時(shí)考慮配送成本，建立預(yù)調(diào)度模型；而實(shí)際干擾發(fā)生后，將干擾管理理論與無人機(jī)配送結(jié)合，充分考慮運(yùn)行環(huán)境中不確定因素，以偏差時(shí)間和擾動(dòng)成本最小為目標(biāo)，建立干擾恢復(fù)模型，采用蟻群算法快速生成擾動(dòng)最小的應(yīng)對(duì)方案，實(shí)現(xiàn)靜態(tài)動(dòng)態(tài)模型相結(jié)合，事前和事后決策相結(jié)合，彌補(bǔ)單一靜態(tài)模型與實(shí)際運(yùn)行情況存在不符情況的不足。

1 問題描述及假設(shè)

1.1 無人機(jī)服務(wù)模式及問題描述

無人機(jī)服務(wù)被描述為無人機(jī)的交付功能，根據(jù)末端客戶的服務(wù)時(shí)間、物流服務(wù)商的金錢成本和不確定環(huán)境影響，利用相關(guān)方法匹配出最優(yōu)的交付方案，完成包裹從起始端運(yùn)輸?shù)侥┒说慕桓度蝿?wù)，包括初始計(jì)劃的制定、干擾路線的調(diào)整、交付功能。無人機(jī)末端服務(wù)模式如圖1所示，針對(duì)末端物流配送時(shí)車輛不方便或無法進(jìn)行配送的場景，采用小型無人機(jī)來完成物流包裹的配送工作。物流服務(wù)商收到需求點(diǎn)的配送要求，從配送中心安排一定數(shù)量的無人機(jī)運(yùn)輸貨物，無人機(jī)垂直起飛降落，依次完成任務(wù)，最后空載回到配送中心。

圖1 無人機(jī)服務(wù)模式Fig.1 UAV service mode

制定無人機(jī)交付計(jì)劃，需要滿足無人機(jī)載重量、載容量、電池能耗、客戶時(shí)間窗等限制，每個(gè)任務(wù)點(diǎn)在時(shí)間窗條件限制下只訪問一次。考慮到無人機(jī)在飛行過程中受到多種不確定性因素，可能造成故障墜落、故障備降、故障延誤等情況，使得訂單需求損失增大、客戶滿意度降低。針對(duì)故障墜落場景，當(dāng)無人機(jī)配送任務(wù)執(zhí)行到T0時(shí)刻，有一架或多架無人機(jī)發(fā)生故障墜落，失去運(yùn)力，同時(shí)認(rèn)為所載貨物已經(jīng)發(fā)生損壞，直接導(dǎo)致調(diào)度任務(wù)中斷不能按照原始配送方案執(zhí)行，此時(shí)需要快速及時(shí)地生成新的解決方案，并使其與原始配送方案的偏離程度最小。

1.2 問題假設(shè)

(1)所有無人機(jī)都在同一配送中心出發(fā)，完成送貨后返回原配送中心。

(2)無人機(jī)開始配送任務(wù)時(shí)電量已經(jīng)充滿，不考慮中途的充電問題。

(3)無人機(jī)的飛行速度已知，且保持勻速飛行。

(4)每個(gè)客戶只能被一架無人機(jī)服務(wù)。

(5)無人機(jī)發(fā)生故障墜落，造成貨物損壞，貨物不同質(zhì)，只能重新調(diào)度新無人機(jī)。

(6)如果貨物沒有在客戶要求的時(shí)間窗內(nèi)達(dá)到，將取消訂單。

1.3 變量說明

根據(jù)相關(guān)問題描述進(jìn)行變量定義說明如表1所示。

表1 模型參數(shù)設(shè)置Table 1 Parameter setting of model

2 物流無人機(jī)干擾恢復(fù)模型構(gòu)建

2.1 不確定飛行故障下的無人機(jī)預(yù)調(diào)度模型

無人機(jī)在正常運(yùn)行情況下，以交付成本最小作為優(yōu)化目標(biāo)，并根據(jù)客戶需求、電池、無人機(jī)自身特性進(jìn)行模型約束。實(shí)際運(yùn)行過程中，可能遭遇來自系統(tǒng)故障、氣象環(huán)境、人為操縱等干擾，導(dǎo)致包裹不能在指定時(shí)間內(nèi)送至目的地，造成需求損失，因此，在原始交付模型中，增加無人機(jī)飛行故障概率[9]，優(yōu)先為高價(jià)值、高需求客戶提供服務(wù)，減少預(yù)期需求損失。假設(shè)無人機(jī)運(yùn)行中發(fā)生故障的概率為p，不發(fā)生故障的概率q=1-p，無人機(jī)k服務(wù)第i個(gè)客戶途中發(fā)生故障的概率為Fik，發(fā)生故障后對(duì)應(yīng)剩余貨物價(jià)值為Di。

Fik=pq(i-1)

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

式(3)為無人機(jī)不確定故障條件下對(duì)應(yīng)的最小需求損失；式(4)為無人機(jī)的固定成本；式(5)為無人機(jī)在全部需求點(diǎn)的服務(wù)成本；式(6)為無人機(jī)在全部需求點(diǎn)的等待成本；式(7)和式(8)分別為無人機(jī)運(yùn)載成本和空載成本。

針對(duì)客戶訂單，同時(shí)考慮有效載重量和飛行時(shí)間2個(gè)因素。認(rèn)為載重量越大、運(yùn)輸時(shí)間越長，消耗電池的能耗總成本就越高，借鑒Dorling等[19]推導(dǎo)的線性能耗模型，即

(9)

式(9)中：a為運(yùn)載1 kg的電池和訂單需要的功率；b為沒有有效載荷重量或電池重量時(shí)，無人機(jī)保持懸停狀態(tài)所需要的功率。

根據(jù)上述目標(biāo)函數(shù)描述，建立模型如下。

min(Z1+Z2+Z3+Z4+Z5+Z6)

(10)

(11)

(12)

uij-uje=wj, ?i,e∈N0,?j∈N,i≠j,j≠e

(13)

xijk+xjik≤1, ?i,j∈N,i≠j,?k∈M

(14)

(15)

(16)

?k∈M,i≠j

(17)

?k∈M

(18)

式(10)是廣義總費(fèi)用最?。皇?11)保證每個(gè)需求點(diǎn)只有一架無人機(jī)服務(wù)；式(12)保證無人機(jī)從配送中心出發(fā)，服務(wù)完最后一個(gè)需求點(diǎn)后返回配送中心；式(13)為無人機(jī)飛行到任意階段對(duì)應(yīng)有效載重量和需求點(diǎn)訂單重量之間的關(guān)系；式(14)消除子回路，任意兩個(gè)需求點(diǎn)之間最多只有一條路徑；式(15)、式(16)分別為無人機(jī)最大載重、載容限制；式(17)為無人機(jī)飛行最大能耗限制；式(18)為任意需求點(diǎn)的時(shí)間窗要求。

2.2 無人機(jī)干擾墜落后的恢復(fù)模型

針對(duì)包裹配送過程中無人機(jī)墜落場景，從客戶服務(wù)和配送成本2個(gè)角度進(jìn)行擾動(dòng)度量，建立干擾恢復(fù)模型為

min Lex:

(19)

(20)

(21)

(22)

ej-Δtj≤S′jk≤lj+Δtj, ?j∈N′

(23)

waitik+t′ik=S′ik, ?i∈N′,?k∈M′

(24)

T0+t0j+α+waitjk-D(1-x0jk)≤S′jk,

?j∈N′,?k∈M′

(25)

S′ik+tij+si+α+waitjk-D(1-xijk)≤S′jk,

?i,j∈N′, ?k∈M′

(26)

式(19)、式(20)為目標(biāo)函數(shù)，式(19)表示原始方案和新方案中顧客的開始服務(wù)時(shí)間偏差最小，且盡可能使所有顧客都能得到服務(wù)，同時(shí)采用客戶分級(jí)策略區(qū)分不同客戶的影響程度，客戶的重要程度用該客戶的貨物價(jià)值占配送貨物總價(jià)值的比重表示；式(20)表示物流服務(wù)商的成本擾動(dòng)，考慮新增無人機(jī)的固定成本、能耗成本、取消客戶懲罰成本；式(21)表示未受干擾影響的需求點(diǎn)仍由原始無人機(jī)執(zhí)行配送任務(wù)；式(22)表示受干擾的每個(gè)需求點(diǎn)訪問一次，或者采取取消策略不訪問該需求點(diǎn)；式(23)表示干擾發(fā)生后，很難在期望時(shí)間窗范圍內(nèi)完成配送，新增時(shí)間容忍度，形成新的時(shí)間窗要求；式(24)、式(25)、式(26)表示時(shí)間變量關(guān)系。

2.3 改進(jìn)蟻群算法設(shè)計(jì)

所構(gòu)建的基于帶時(shí)間窗訂單的無人機(jī)調(diào)度模型屬于NP優(yōu)化問題，設(shè)計(jì)蟻群算法進(jìn)行求解，根據(jù)無人機(jī)飛行中能量損耗和貨物損失量的不同，在算法中加入分段能耗計(jì)算方法；考慮到基本蟻群算法的轉(zhuǎn)移概率公式包含特征信息較少，導(dǎo)致算法搜索能力不足，收斂速度慢，將客戶需求時(shí)間窗和達(dá)到等待時(shí)間加入狀態(tài)轉(zhuǎn)移公式當(dāng)中。同時(shí)為了避免算法陷入局部最優(yōu)解和隨機(jī)解，對(duì)揮發(fā)因子ρ進(jìn)行動(dòng)態(tài)調(diào)整。

步驟1解決無人機(jī)在正常運(yùn)行條件下的配送問題，最小化配送成本，利用蟻群算法得出原始最佳配送方案。

步驟2當(dāng)無人機(jī)干擾發(fā)生時(shí)刻，受擾無人機(jī)尚未服務(wù)的客戶是受擾客戶，其余正常運(yùn)行無人機(jī)的客戶不受干擾，按原始計(jì)劃繼續(xù)配送。對(duì)于受擾客戶采用取消策略和新增無人機(jī)策略進(jìn)行服務(wù)，首先需要判斷受擾客戶是否取消服務(wù)。客戶i的需求服務(wù)時(shí)間窗[ei+Δti，li+Δti],開始服務(wù)時(shí)間S′ik,當(dāng)S′ik>li+Δti，取消客戶訂單，轉(zhuǎn)步驟3。

步驟3針對(duì)受擾需服務(wù)的客戶，以客戶服務(wù)偏移擾動(dòng)和成本擾動(dòng)最小為目標(biāo)函數(shù)，使用步驟1中的算法對(duì)未受擾客戶重新規(guī)劃配送方案。

步驟4進(jìn)一步優(yōu)化配送成本。在S′ikQ2，步驟3的配送方案為最優(yōu)方案。算法流程如圖2所示。

圖2 蟻群算法流程圖Fig.2 Flow chart of ant colony algorithm

為了驗(yàn)證算法的收斂性，使用標(biāo)準(zhǔn)Solomon數(shù)據(jù)庫的中r201數(shù)據(jù)，利用MATLAB R2019b進(jìn)行編程，實(shí)驗(yàn)環(huán)境為處理器Intel(R) Core(TM) i5-8300H CPU @ 2.30GHz,內(nèi)存8 GB，Window10操作系統(tǒng)，設(shè)置迭代次數(shù)為100，種群規(guī)模為100，算法收斂情況對(duì)比如圖3所示。

圖3 算法收斂情況對(duì)比Fig.3 Algorithm convergence comparison

由圖3結(jié)果可知，改進(jìn)蟻群算法有更好的收斂性，收斂時(shí)間會(huì)隨著問題規(guī)模的增大而增大，時(shí)間復(fù)雜度增大，但隨著螞蟻數(shù)的增加，收斂時(shí)間逐漸減小，即時(shí)間復(fù)雜度減小。

3 數(shù)值實(shí)驗(yàn)及結(jié)果分析

參考Solomon關(guān)于VRPTW的經(jīng)典基準(zhǔn)算例對(duì)上述模型的有效性進(jìn)行驗(yàn)證。該算例中沒有涉及貨物的體積、貨物的價(jià)值，在運(yùn)算中這部分?jǐn)?shù)據(jù)隨機(jī)生成，考慮到無人機(jī)和車輛運(yùn)輸?shù)南嚓P(guān)參數(shù)性能不同，需求時(shí)間窗和貨物重量做相應(yīng)調(diào)整。參考杭州迅蟻公司的旋翼物流無人機(jī)性能參數(shù)，設(shè)置最大載重5單位，最大載容64單位，最大飛行能量1 800單位，成本參數(shù)C1=15、C2=0.1、C3=0.1、C4=0.1、C5=0.05。

以數(shù)據(jù)r201的25個(gè)客戶為例，根據(jù)預(yù)調(diào)度模型得出初始最優(yōu)配送方案，無人機(jī)1：0→1→7→18→12→0；無人機(jī)2：0→19→8→10；無人機(jī)3：0→11→9→20→0；無人機(jī)4：0→23→22→24→0；無人機(jī)5：0→16→17→13→0；無人機(jī)6：0→6→2→25→3→0；無人機(jī)7：0→5→14→15→0；無人機(jī)8：0→4→21→0。為了驗(yàn)證不確定干擾對(duì)配送方案結(jié)果的影響，設(shè)置對(duì)照實(shí)驗(yàn)，服務(wù)偏移擾動(dòng)目標(biāo)和擾動(dòng)成本目標(biāo)隨權(quán)重變化的結(jié)果如圖4所示。

圖4 目標(biāo)函數(shù)隨權(quán)重變化曲線圖Fig.4 Change curve of objective function values with weights

由圖4可知，隨著服務(wù)偏移擾動(dòng)目標(biāo)權(quán)重w1的逐漸增大，配送結(jié)果的服務(wù)偏移呈現(xiàn)波動(dòng)遞減趨勢，同時(shí)配送成本呈現(xiàn)波動(dòng)遞增的趨勢，實(shí)驗(yàn)結(jié)果顯示，w1=0.6的配送方案表現(xiàn)結(jié)果最好，選取權(quán)重比：服務(wù)擾動(dòng)權(quán)重w1=0.6,成本擾動(dòng)權(quán)重w2=0.4。

為了驗(yàn)證干擾恢復(fù)方案的有效性，隨機(jī)選取3組受擾情境。干擾情境1：無人機(jī)6在服務(wù)第一個(gè)客戶途中；干擾情境2：無人機(jī)6已服務(wù)完第二個(gè)顧客，正前往第三個(gè)顧客途中；干擾情境3：無人機(jī)1和無人機(jī)6在前往第一個(gè)客戶途中；在上述干擾場景下將本文干擾恢復(fù)方案結(jié)果與原始配送方案比較，如表2所示。

表2 結(jié)果比較Table 2 Comparison of results

(1)干擾情境1。原始配送路徑0→6→2→25→3→0；新救援路徑0→6→3→0，0→2→25→0；由于無人機(jī)發(fā)生干擾墜落時(shí)間較早，能在時(shí)間窗內(nèi)完成配送服務(wù)，因此沒有取消的客戶，新方案使用了兩架無人機(jī)進(jìn)行服務(wù)，配送成本增加了15.87%，客戶服務(wù)滿意度提高了3.42%，由于新增無人機(jī)服務(wù)的客戶數(shù)較少，成本代價(jià)較大。

(2)干擾情境2。受擾客戶25和3，原始配送路徑和新救援路徑為0→25→0。干擾發(fā)生時(shí)刻較晚，重新調(diào)度無人機(jī)不能在客戶3的時(shí)間窗完成配送服務(wù)，最終取消該客戶，而直接新派無人機(jī)服務(wù)客戶25。

(3)干擾情境3。原始配送路徑0→1→7→18→12→0，0→6→2→25→3→0；新救援路徑0→7→18→3→0，0→12→25→0，0→6→1→2→0。干擾發(fā)生時(shí)刻較早，同時(shí)受擾客戶數(shù)量較多，新方案中的調(diào)整空間較大，以成本增加16.48%的代價(jià)使得客戶的服務(wù)時(shí)間偏移值減少74.69%。

由上面干擾調(diào)度發(fā)現(xiàn)干擾發(fā)生位置不同，受擾時(shí)刻越晚，允許調(diào)整的時(shí)間越少；受擾客戶數(shù)越少，滿足約束的調(diào)整方案也越少，很難有明顯的優(yōu)化效果，所以本文方法針對(duì)多受擾客戶、早干擾時(shí)刻場景的適應(yīng)性更好。針對(duì)干擾后的客戶，增派新無人機(jī)按照新的配送方案服務(wù)，更好地權(quán)衡成本和客戶服務(wù)，從長遠(yuǎn)利益考慮，短期的成本代價(jià)換取客戶的長期信賴，能獲得更大的價(jià)值。

4 結(jié)論

無人機(jī)執(zhí)行配送任務(wù)過程是處在一個(gè)高動(dòng)態(tài)、高復(fù)雜的不確定低空環(huán)境當(dāng)中，這些多種不確定因素可能會(huì)導(dǎo)致物流無人機(jī)的配送任務(wù)中斷。研究中斷后的恢復(fù)方案，得到以下結(jié)論。

(1)綜合考慮無人機(jī)垂直起降時(shí)間、飛行階段能耗、最大載重載容量、需求時(shí)間窗、貨物價(jià)值等多因素約束；基于不確定故障下構(gòu)建無人機(jī)配送預(yù)調(diào)度模型，減少了需求損失。

(2)建立的恢復(fù)模型可以在控制支出成本下，維護(hù)客戶的服務(wù)滿意度，當(dāng)干擾發(fā)生時(shí)刻早、受擾客戶多時(shí)，僅以16.48%的成本代價(jià)，使得客戶滿意度提高74.69%，同時(shí)快速生成干擾后的應(yīng)對(duì)方案，有效提高物流無人機(jī)運(yùn)輸系統(tǒng)的干擾處理能力。

(3)根據(jù)干擾對(duì)無人機(jī)機(jī)身造成的破壞強(qiáng)度、貨物完好性、持續(xù)時(shí)間的不同，將無人機(jī)飛行能力受到干擾情況細(xì)分了3種場景：墜落貨損、故障備降、干擾延誤。此次以墜落貨損場景展開研究，今后將進(jìn)一步完善無人機(jī)多受擾場景下的調(diào)度決策。