應急物資的無人機與車輛并行在線配送問題

余海燕，茍夢圓，吳騰宇

1.重慶交通大學 經濟與管理學院，重慶 400074

2.重慶口岸物流與航運發展研究中心，重慶 400074

3.智能物流網絡重慶市重點實驗室，重慶 400074

4.重慶郵電大學 經濟管理學院，重慶 400065

疫情的高傳播性使部分地區加強了道路管控措施，物資配送嚴重受阻，對于醫藥等應急物資如何高效、準確、安全地配送已是當務之急。其間無人機在“最后一公里”藥物配送中獲得亮眼表現，可見無人機在應急物資配送中的適用性。但是，無人機存在飛行半徑有限等短板，將其與車輛進行組合配送更適應現實場景。除此之外，在現實應急配送場景中，決策者往往必須在對未來一無所知或部分信息未知的情形下進行對全局有影響的決策。因此，需求產生的突發性、高度不可預見性及不確定性是應急物資配送難以組織實施的重要原因之一。然而，當前無人機與車輛并行配送領域中對需求不確定性研究較少，將此類動態因素引入車輛無人機并行配送問題，是該問題可行且有價值的發展方向。

考慮需求實時不確定性產生情形下的車輛無人機并行配送問題可以用車輛無人機并行在線配送問題描述。與一般車輛無人機并行配送問題相比，應急配送需求序貫出現，服務器只能實時獲知其相關信息，因此具有在線性。與一般車輛在線配送問題相比，無人機配送范圍有限、一單一送，且需考慮無人機與車輛之間協調問題。因此，提出車輛無人機并行在線配送問題。

對于車輛無人機并行配送問題，Chung 等[1]將目前該問題所涉及算法進行了歸納，發現多以車輛為主無人機為輔構建配送網絡，并設計相應的離線算法。Murry和Chu[2]將車輛無人機并行配送問題定義為PDSTSP（parallel drone scheduling traveling salesman problem）問題，并設計了車輛優先配送需求的啟發式算法。Dell’Amico 等[3]以總時間最小化為目標，提出了以分支定界算法為主的迭代啟發式算法。Nguyen 等[4]研究了以最小化總運營成本為目標的車輛無人機并行配送路徑優化問題。Saleu等[5]采用迭代兩步啟發式算法求解，通過雙準則最短路徑問題解碼及動態規劃實現。總體而言，此問題相關研究大多建立在所有信息已知的情形下，與現實場景中應急需求信息未知不符。除此之外，研究大多構建以車輛為主的配送網絡，現實場景中應急需求未知且緊迫，優先考慮無人機配送能明顯減少單個需求點的等待配送時間，因此考慮動態因素并設計無人機優先的在線算法具有現實意義。

對于車輛無人機并行配送問題涉及未知需求方面，任璇等[6]進行了文獻歸納總結。Ulmer 和Thomas[7]研究了需求在一天中任意時間釋放的“當日達”問題，采用了動態規劃進行解決。王新玉和趙志明[8]指出即時重優化也是常見的求解策略，通過基于最壞情形考慮的競爭分析法能有效、可靠度量動態問題的求解策略性能，且動態問題的解決方案不應該是靜態輸出，而是根據新到達的服務需求與系統當前狀態決定執行哪些調度操作。在線算法正是基于此思想進行策略設計，在線分析法則是圍繞所設計在線策略進行系統評估的方法。設計相應的在線算法并通過在線分析法進行算法優劣性衡量能夠有效解決需求信息未知的現實問題。

在Sleator和Tarjian[9]正式提出在線問題及在線分析法后，在線配送問題開始受到關注。車輛與無人機并行在線算法的研究重點在于需求分配及路徑規劃，這一方面可通過在線理論進行分析處理。Ausiello等[10]最早使用在線理論分析TSP（traveling salesman problem）問題，證明得出一般網絡上Eventually Replan算法競爭比為2。馬衛民和王刊良[11]證明局內封閉式車輛調度問題車輛數為1 時重新計劃策略的競爭比為3.5。戴敏等[12]證明局內開放式多車輛調度問題重新計劃策略的競爭比為3.5。Jaillet 和Lu[13]研究具有實時服務可選擇性的在線旅行商問題，并證明所提出策略在正半軸競爭比為2.5。馬軍平等[14]提出具有服務時長和服務可選擇性的車輛調度問題，并設計了相應的在線算法。吳騰宇等[15]運用在線分析法衡量了非對稱網絡下JPⅠ-rd（judge the path increment with release date）等算法的性能。與現有的車輛在線調度問題研究不同，車輛無人機并行在線配送問題還需考慮無人機不同于車輛的特性，如裝載量、速度、服務范圍等。

綜上所述，將車輛與無人機并行配送應用于應急配送領域是有效且可行的。通過與現有研究比較可知（見表1），車輛與無人機并行配送領域的算法研究有一定基礎，但針對需求不確定性考慮較少，與現實場景結合不夠緊密，設計相應的在線算法具有現實意義，且如何設計相應的在線算法，衡量算法的性能及適用性，目前尚未有相關的研究。

表1 車輛無人機并行配送問題研究對比Table 1 Research comparison of truck-drone parallel delivery problem

基于此，本文研究在需求實時產生的情況下，如何分配需求并規劃路徑使得最長配送時間盡可能少的車輛無人機并行在線配送問題。該問題可通過在線分析法有效解決。首先給出問題描述和基本定義，然后通過競爭分析得出所研究的在線問題下界及所設計在線均衡策略競爭比，從而衡量在線均衡策略的性能；通過建立離線問題模型，設計離線算法，運用MATLAB 將CPLEX 最優解與離線算法結果進行比較，為在線均衡算法內容作支撐；通過對在線均衡算法的仿真分析，驗證在線均衡算法的有效性。

1 符號說明及問題描述

1.1 符號說明

V：網絡頂點集合，V={x0,x1,…,xk} ；

E：網絡邊集合，E={e0,e1,…,ek} ；

d(u,v)：頂點u,v間邊的權，其中u,v∈V；

G：配送網絡，G=(V,E)，以配送站作為原點，原點唯一令其為頂點o∈V，網絡滿足u,v,w∈V,d(u,v)+d(v,w)≥d(w,u)；

ri：兩元數組，ri=(ti,xi)，代表在ti時刻于xi處產生需求，其中ti表示服務請求的發布時間，xi表示服務請求的發布位置；

R：需求組成的序列集合，R={r1,r2,…,rm} ，其中需求按釋放時間先后排列；

I：需求序號集合，I={1 ,2,…,n} ；

J：配送網絡頂點序號集合，J={0 ,1,…,n} ，其中0為配送站；

S：無人機的最遠飛行半徑；

k：無人機飛行速度，其中k>1；

δ：一個任意小的正數；

L*(t,o,R)：在時刻t由原點o開始完成R中的所有服務需求并回到原點o所花費的最短時間；

Rd：按最優調度L*(t,X,R)分配給無人機的需求序列集合；

Rv：按最優調度L*(t,X,R)分配給車輛的需求序列集合；

Rsv：車輛需求序列中待服務需求集合，Rsv?Rv；

tid：無人機配送需求ri所花費時間；

tij：車輛從需求ri位置到需求rj位置所花費時間；

Pv(t)：在t時刻車輛的位置；

Td：無人機配送總時間；

Tv：車輛配送總時間；

T：總服務時間，其中T=max{Td,Tv} ；

xij：車輛從需求ri到需求rj則等于1，否則等于0；

yi：無人機配送第i個需求則等于1，否則等于0。

1.2 問題描述

假設所有需求ri隨機分布在網絡圖G上，且均為同一類型物資，需求量均為1，實時產生、序貫而出、不能拒絕。配送站使用無人機及車輛并行配送，其中無人機與車輛數目均為1，初始時刻無人機與車輛均處于配送站，服務過程中經過需求點即該需求點配送完成，配送完成后需返回配送站。無人機運載量為1，最遠飛行半徑為S，以k(k>1) 個單位速度移動；車輛運載量為∞，最遠里程為∞，以為1的單位速度移動。由于運載量限制，無人機需于配送站取貨，而車輛無需。

對于d(o,xm)≤S的需求點，可使用無人機或車輛進行配送；對于d(o,xm)>S的需求點，只能由車輛進行配送。令Td為無人機配送總時間，Tv為車輛配送總時間。總服務時間由無人機或車輛最晚返回配送站的時間決定，求如何安排配送方式及規劃路線使總服務時間最小化。

如圖1所示，在t時刻同時新增兩個需求點，此時原本由無人機配送的需求改為由車輛進行配送，由此車輛及無人機的路徑改變。

圖1 問題描述示意圖Fig.1 Schematic diagram of problem description

對于該研究問題，可用競爭分析法衡量所設計在線算法的優劣性。競爭分析是衡量動態問題求解策略性能的方法之一，是在線對手與離線對手之間的博弈過程。在這個博弈過程中，離線對手釋放需求序列，其釋放的需求會盡可能利于離線對手而不利于在線對手。從而，離線對手從0 時刻便知曉全部需求信息，而在線對手未知。對于同樣的輸入序列θ，令在線對手采用策略β服務輸入序列θ所得解為Conline(θ)，離線對手采用最優策略服務輸入序列θ所得解為COPT(θ)。對于任意的θ，都存在常數ρ與γ使得Conline(θ)≤ρ×COPT(θ)+γ成立，則策略β的競爭比為ρ。若不存在小于競爭比ρ的在線策略，稱ρ為該問題下界。當ρ越趨近于1 時，策略性能越好。

2 車輛無人機并行配送在線問題下界

定理1對于車輛無人機并行配送在線問題，其下界為1.5。

證明以直線為例，不失一般性。在直線的正半軸上，需求ri的位置xi，即該點到原點的距離；在直線的負半軸上，需求ri的位置xi取絕對值，即該點到原點的距離。假設無人機、車輛的服務序列中存在最遠需求點(ti,|s|)、(ti,|y|)，車輛最遠配送需求點與配送站距離大于無人機最遠配送需求點。于-δ時刻釋放需求r1=(-δ,s)。需求r1在無人機與車輛配送范圍內，在線對手可采用無人機或車輛進行配送。在線對手于t時刻開始服務需求r1，下面對t的取值分情況討論。

情形1當ts/k。同理，若y時刻在線車位于?處，則需求r2=(y,-y)。在線對手在獲知需求r2后，由于 |y|>|s|，超出無人機配送范圍，只能由車輛進行配送。對于離線對手，若需求r2=(y,y)，無人機不參與配送，從0時刻開始車輛沿正半軸運動。若需求r2=(y,-y)，則0時刻開始車輛沿負半軸運動，無人機沿正半軸運動。Conline≥max{3y+?,( 3s)/k-δ} =3y+?;COPT=2y,ρ=Conline/COPT ≥( 3 y+? )/( 2y )≥( 3y )/( 2y)。對于情形1，ρ≥1.5。

情形2當t≥s/k時，則離線對手不再釋放新需求。離線對手從0 時刻開始無人機服務需求r1。此時COPT=2s/k，Conline≥3s/k-δ；ρ=Conline/COPT≥(3s/k-δ)(2s/k)。

對于情形2，取δ→0，ρ≥1.5。

因此，直線上策略的競爭比下界為1.5。證畢。

定理1表明對于車輛無人機并行配送調度問題，考慮最壞情形下任意的在線策略目標值與離線策略最優目標值的比值下界為1.5。

3 車輛無人機并行配送在線策略

3.1 在線均衡策略設計

假設現有一個明確的離線算法，可根據當前任意輸入得到對應的較優解。

在線均衡策略：當新需求釋放時，進行即時重優化，按離線算法將此時已獲知的全部需求重新分配給車輛與無人機服務，形成各自新的服務序列，其中已服務需求不再服務，車輛按當前位置規劃最優路徑，并依次服務待服務需求。

3.2 在線均衡策略性能分析

根據1.1 節中的符號定義，顯然Rd∪Rv=R,Rd∩Rv=?。現假設最后一個服務請求為rm(tm,xm)。通過競爭分析，考慮需求產生的最壞情形，可證明在相同情形下在線均衡策略所得結果與離線對手最優結果之比的上界。

引理1對于d(o,xm)≤S，即新需求可由車輛或無人機進行服務，該不等式成立COPT≥max{L*( 0 ,o,R),tm+d(o,xm)/k}；對于d(o,xm)>S，即新需求只能由車輛服務，此時COPT≥max{L*( 0 ,o,R),tm+d(o,xm)}。

證明 情形1當d(o,xm)≤S，即新服務需求加入無人機或車輛需求序列中。

由于在需求尚未釋放前不能對其進行服務，因此對于最后一個服務請求為rm(tm,xm)，可有COPT(R)≥tm+T(o,xm)，其中T(o,xm)表示返程時間。當由無人機進行服務時，由于無人機飛行速度為k，則有T(o,xm)=d(o,xm)/k。當由車輛進行服務時，由于車輛行駛速度為1，那么T(o,xm)=d(o,xm)/1=d(o,xm)。由于存在所有需求僅由無人機配送的可能性，因此COPT≥max{L*( 0 ,o,R)，tm+d(o,xm)k} 。

情形2當d(o,xm)>S，即新服務需求加入車輛需求序列中。同理，由于車輛行駛速度為1，存在T(o,xm)=d(o,xm)/1=d(o,xm)。因此，COPT≥max{L*( 0 ,o,R),tm+d(o,xm)}。

綜上，引理1得證。證畢。

引理2當新需求rm(tm,xm)釋放時，可有L*( 0 ,o,R)≥L*(tm,o,Rsv)，0

證明當配送需求序列相同且出發點相同時，出發時間越晚，所獲得的已知信息將會越多，從而所得到的規劃路線越優。因此，當0

由于新需求rm(tm,xm)釋放時，采用離線算法重新規劃，tm時刻車輛新服務序列Rv與離線算法所得車輛服務序列相等，Rsv表示車輛需求序列中待服務需求集，易知Rsv?Rv?R。需求點相同的情況下，所服務需求數量越少所花費時間越短，因此L*(tm,o,R)≥L*(tm,o,Rv)≥L*(tm,o,Rvs)。引理2得證。證畢。

引理3在無新需求釋放情況下，該不等式成立

證明假設車輛存在待服務需求，車輛新服務序列為Rv={rv1,rv2,…,rvn}，其中需求點rvi=(tvi，xiv),tvi

定理2在線均衡策略競爭比為2.5。

證明對于產生的任何一個新需求，只有由無人機配送或車輛配送兩種策略選擇，因此考慮以下兩種情形：

情形1由離線算法，新需求由無人機配送。令U={u1,u2,…,un} 為tm時刻無人機n個待服務需求各自的配送時長，n≥0，有該不等式成立：d(o,xm)/k。

情形1.1假設車輛不存在待服務需求，則有Tv≤tm+d(Pv(tm),o) ，即可得該不等式成立：Conline(R)≤易知tm+根據引理1，可得COPT≥tm+d(o,xm)/k。此時假設W={w1,w2,…,wn} 為離線對手無人機服務序列各需求配送時長。由于采用離線算法，對于相同的輸入序列與算法，離線對手與在線對手此時結果相同，因此集合U?W。COPT=

情形1.2假設車輛存在待服務需求，在tm時刻，車輛從當前位置出發服務新服務序列中待服務需求集，則Tv≤tm+L*(tm,Pv(tm),Rvs)≤tm+L*(tm+Pv(tm),o,Rsv)+Pv(tm)。 由 引 理3，L*(tm+Pv(tm),o,Rvs)+Pv(tm)≤由引理因此，Tv≤tm+COPT(R)+( 1/2)COPT(R)≤( 5/2)COPT(R)。又

情形2由離線算法，新需求由車輛配送，即車輛存在待服務需求。由情形1.2 知，Tv≤tm+L*(tm+同理，令U={u1,u2,…,un}為tm時刻無人機新服務序列中n個待服務需求配送時長，n≥0，有2COPT(R)。Conline(R)=max{Td,Tv} ≤( 5/2)COPT(R)。

綜上所述，該策略競爭比為2.5。證畢。

針對3.1 節中在線均衡算法所調用的離線算法，可通過研究其對應的離線問題得到，由此產生第4 章內容。

4 車輛無人機并行配送離線策略分析

4.1 離線模型建立

相對于車輛無人機并行在線配送問題，對應的離線問題與其區別僅在于離線問題從初始時刻便已知所有需求點的所有信息，其余問題描述一致。基于該問題，可建立如下模型：

目標函數（1）表示總服務時間由無人機或車輛最晚返回配送站的時間決定；約束（2）表示無人機所耗費時間為無人機服務序列中各需求所耗費時間之和；約束（3）表示車輛所耗費時間為車輛服務序列中各段路程所耗費時間之和；約束（4）表示無人機與車輛所服務需求點之和與總服務需求數相等，即Rd∪Rv=R；約束（5）、（6）表示各需求只能由無人機或車輛進行服務，即Rd∩Rv=?，且為節點平衡約束，表示各需求只服務一次；約束（7）表示如果車輛從0 點出發則必然會回到0點；約束（8）避免車輛路徑形成子環；約束（9）表示模型中決策變量的取值范圍。

4.2 離線算法提出

對于該問題是否能求出最優解，需考慮其時間、空間復雜度。該規劃模型屬于匹配模型與TSP 模型結合。由于TSP 問題屬于NP 難問題，其又包含于車貨匹配問題中，因此該問題也屬于NP難問題，無法在有效時間內求出最優解，可采用啟發式算法進行求解。

針對該問題，結合均衡算法、插入法思想提出無人機優先均衡算法。令Rex為d(o,xm)>S的需求集合，=Td-Tv,Tmseitnus為差值集合且初始為空集，其余參數見1.1節。以下為無人機優先均衡算法偽代碼。

其中1～8行求出初始解，9～22行通過迭代選擇得出最終解。

4.3 離線算法性能分析

無人機優先均衡算法的時間復雜度為O(n3)。假設n是需求點數量，該算法的時間復雜度主要由初始解生成與迭代選擇兩部分決定。在初始解生成中，所涉及以配送時長最短為目標的遺傳算法時間復雜度為O(n3)，j∈I循環的時間復雜度為O(n)，其余代碼時間復雜度為常量，因此整個初始解生成部分時間復雜度為O(n)+O(n3)。在迭代選擇過程中，主要對rj∈Rd進行循環，其時間復雜度為O(m?n3)，其中m為Rd集合中需求點數，m≤n，因此迭代選擇部分時間復雜度為O(m?n3)。綜上所述，無人機優先均衡算法的時間復雜度為O(n3)+O(m?n3)=O(n3)。

除此之外，對于同樣的輸入，通過比較無人機優先均衡算法所求解與CPLEX最優解可有效驗證離線算法的性能。針對離線模型，通過MATLAB 2018a 調用CPLEX 及YALMⅠP 工具箱進行求解。引入變量T3，由目標函數minT=max{Td,Tv} ，令Td≤T3、Tv≤T3，將4.1節中的模型轉化為線性規劃模型。

仿真初始設置為：車輛行駛速度為1，無人機飛行速度為2，無人機飛行半徑為8，由于問題重點在于無人機飛行范圍內的需求分配，為達到更好的展示效果，令需求一半在無人機飛行半徑內隨機產生，一半無限制。

所設計離線算法與CPLEX運行結果對比見表2，其中最優值保留三位小數。由表2可知，所設計離線算法結果與CPLEX最優值相比，隨著需求點數量的增加，計算時間明顯小于CPLEX 的計算時間，且結果偏差在合理范圍內。由此說明了離線算法的有效性。

表2 離線算法與CPLEX對比結果Table 2 Comparison results of offline algorithm and CPLEX

5 在線算法仿真分析

對于隨機生成的需求點坐標及釋放時間，通過計算在線算法所得結果與離線最優下界值之比，進行在線算法關于輸入參數的仿真分析。與4.3節中需求于0時刻一同釋放不同，此時離線解同樣受需求釋放的限制，計算較為復雜，與其下界值相比不影響在線算法性能判斷。離線最優下界取值方法見3.2節中引理1。

初始設置為需求點個數為10，無人機與車輛速度之比為1.5，需求點坐標最大值與無人機飛行半徑之比為2，釋放時間上限為50 min，每次獨立測試50 次所得結果分別取平均值，得以下結果，如表3 所示。由于理論分析是基于最壞情形分析之下所得，而實際場景下不一定是最壞情形，因此結果中所得實際比值明顯小于理論分析所得競爭比。

表3 仿真分析結果Table 3 Simulation analysis results

將需求點個數設為20，其余參數與本節初始設置相同，得在線結果示意圖（如圖2）、離線結果示意圖（如圖3）、結果比較表（見表4）。其中需求1代表配送站，各需求點序號按釋放先后排列，離線結果示意圖建立在所有需求信息在0時刻已知情形下。

圖2 在線結果示意圖Fig.2 Schematic diagram of online results

圖3 離線結果示意圖Fig.3 Schematic diagram of offline results

表4 結果比較表Table 4 Results comparison table

分析運行結果可知：

（1）隨著需求點數量增加，在線均衡策略仍舊適用，但在線均衡策略結果與離線結果差距增加。需求個數不變情形下，釋放時間上限提高，需求釋放時間間隔增加，在線均衡策略結果與離線結果差距減小。因此，所提出的在線均衡策略更適用于需求點數量較少、釋放時間間隔較長的情形。

（2）在現實場景中，對于車輛與無人機并行在線配送問題，無人機方面有以下建議。在無人機選用方面，選用服務范圍更廣、相對車輛速度更快的無人機能減小在線結果與離線下界比值，即使得在線均衡策略表現更優。在無人機配送方面，當出現接近無人機飛行限制范圍的需求時，使用車輛進行服務，從而使無人機能更好地服務近距離需求，在更短時間內滿足更多應急需要。

6 結語

本文研究了在應急配送背景下，基于需求實時產生的無人機與車輛并行配送在線優化問題。綜合考慮了現實場景中需求實時產生，無人機服務半徑有限、載重量有限、速度快等問題特征以及并行配送的服務模式，通過競爭分析法證明了該問題下界為1.5，并基于重規劃思想設計了在線均衡算法，通過最壞情形分析法證明了在線算法的競爭比為2.5。由于所設計的在線算法調用了離線算法，因此對離線問題進行了描述、建模并設計了相應算法，通過與CPLEX 結果比較得出所設計的離線算法速度快，偏差低。最后，通過調整不同的輸入參數，得出不同參數改變下在線算法依舊有效。通過所設計的在線均衡算法，可對車輛與無人機平行應急物資配送實時優化領域作理論補充。未來的研究方向可從混合在線配送進行考慮，混合在線配送指在部分信息未知情形下采用兩種以上配送模式進行配送服務。