任新惠， 茍利珍， 武彤

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

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

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

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

1 問題描述及假設

1.1 無人機服務模式及問題描述

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

圖1 無人機服務模式Fig.1 UAV service mode

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

1.2 問題假設

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

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

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

(4)每個客戶只能被一架無人機服務。

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

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

1.3 變量說明

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

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

2 物流無人機干擾恢復模型構建

2.1 不確定飛行故障下的無人機預調度模型

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

Fik=pq(i-1)

(1)

(2)

(3)

(4)

(5)

(6)

(7)

(8)

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

針對客戶訂單，同時考慮有效載重量和飛行時間2個因素。認為載重量越大、運輸時間越長，消耗電池的能耗總成本就越高，借鑒Dorling等[19]推導的線性能耗模型，即

(9)

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

根據(jù)上述目標函數(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)是廣義總費用最?。皇?11)保證每個需求點只有一架無人機服務；式(12)保證無人機從配送中心出發(fā)，服務完最后一個需求點后返回配送中心；式(13)為無人機飛行到任意階段對應有效載重量和需求點訂單重量之間的關系；式(14)消除子回路，任意兩個需求點之間最多只有一條路徑；式(15)、式(16)分別為無人機最大載重、載容限制；式(17)為無人機飛行最大能耗限制；式(18)為任意需求點的時間窗要求。

2.2 無人機干擾墜落后的恢復模型

針對包裹配送過程中無人機墜落場景，從客戶服務和配送成本2個角度進行擾動度量，建立干擾恢復模型為

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

2.3 改進蟻群算法設計

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

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

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

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

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

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

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

圖3 算法收斂情況對比Fig.3 Algorithm convergence comparison

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

3 數(shù)值實驗及結果分析

參考Solomon關于VRPTW的經(jīng)典基準算例對上述模型的有效性進行驗證。該算例中沒有涉及貨物的體積、貨物的價值，在運算中這部分數(shù)據(jù)隨機生成，考慮到無人機和車輛運輸?shù)南嚓P參數(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個客戶為例，根據(jù)預調度模型得出初始最優(yōu)配送方案，無人機1：0→1→7→18→12→0；無人機2：0→19→8→10；無人機3：0→11→9→20→0；無人機4：0→23→22→24→0；無人機5：0→16→17→13→0；無人機6：0→6→2→25→3→0；無人機7：0→5→14→15→0；無人機8：0→4→21→0。為了驗證不確定干擾對配送方案結果的影響，設置對照實驗，服務偏移擾動目標和擾動成本目標隨權重變化的結果如圖4所示。

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

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

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

表2 結果比較Table 2 Comparison of results

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

(2)干擾情境2。受擾客戶25和3，原始配送路徑和新救援路徑為0→25→0。干擾發(fā)生時刻較晚，重新調度無人機不能在客戶3的時間窗完成配送服務，最終取消該客戶，而直接新派無人機服務客戶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ù)量較多，新方案中的調整空間較大，以成本增加16.48%的代價使得客戶的服務時間偏移值減少74.69%。

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

4 結論

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

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

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

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