蜂群無人機充電排隊優化方法

王云哲，徐國寧,*，王生，李兆杰，蔡榕

1.中國科學院 空天信息創新研究院，北京 100094 2.中國科學院大學，北京 100049

近年來，蜂群無人機由于可以體現出蜂群的整體優勢，完成較復雜的任務，相比單一無人機，蜂群可以對多無人機執行任務帶來很多的優勢，成為國內外研究的熱點[1-3]。但是由于電源技術的水平和限制，現有無人機續航時間短，需要經常充電，因此蜂群無人機快速充電以及充電排隊問題成為制約其快速發展和大面積應用的瓶頸技術，特別是充電排隊問題影響著蜂群無人機執行任務的效率和效果。據現有文獻查詢，蜂群無人機充電排隊的研究未曾報道，本文基于排隊理論對蜂群無人機充電排隊技術進行研究。

在常規的電動汽車排隊充電研究中，文獻[4]基于排隊理論建立了充電設施系統排隊模型，通過合理配置充電設施，提高了電網負荷率。文獻[5] 基于排隊理論對電動汽車充電站的24小時充電負荷曲線進行建模，使用隨機最優潮流和模型預測控制方法研究了不確定性的影響。文獻[6]基于排隊理論中的M/M/s模型和流體方程，計算了高速公路充電站的電動汽車到達率。文獻[7]針對電動出租汽車充電站排隊系統，對M/G/k排隊模型和M/M/k排隊模型進行了對比，分析了電動汽車到站的荷電狀態對排隊系統的影響，并提出了提高系統服務能力的措施。文獻[8]利用排隊理論在服務系統優化設計方面的優勢，構建了電動汽車充電樁的最優臺數設計模型，同時利用排隊理論分析了充電站的服務水平和運行效率。文獻[9]采用基于排隊論的充電機配置方法，提出了布局最優化的數學模型，并基于M/M/s模型，以平均等待時間為標準確定充電站的規模。文獻[10]利用電動汽車充電站排隊論模型，研究了基于路徑需求和基于點需求下的充電站選址定容問題。文獻[11]基于排隊理論進行了充電站的容量優化配置。

在面向蜂群無人機充電時，由于其工作環境的特殊性，可能需要懸停等待充電，比常規充電工況多，因此需要加入系統容量的限制。即，當某一充電平臺可容納的無人機數量達到限定值后，無人機將不再前往這一平臺，從而避免了無人機在懸停等待的隊列中將電量耗盡。

目前充電方法包括集中式充電和分布式充電2種，其中集中式充電(Concentrated Charging，文中用下標“c”表示)將充電平臺集中在一處，對蜂群無人機進行充電。而分布式充電(Distributed Charging，文中用下標“d”表示)將充電平臺分散放置。本文基于M/M/1/m[12]模型和M/M/n/m[13-16]模型對多充電平臺的2種排布方式展開研究。

1 排隊系統基本理論

在排隊論中，通常采用6個特性，實現對一個排隊系統的分析[17]。它們的描述通常依據Kendall提出的方法[18]：

A/B/N/S/C/Z

式中：A為輸入過程；B為服務時間；N為服務員數量；S為系統容量；C為客源數量；Z為排隊規則[17-19]。

當系統容量為固定值，且排隊規則為先到先服務時。依據Kendall提出的方法，該類排隊模型可表示為

A/B/N/S

第2節中，將著重對M/M/1/m和M/M/n/m2種排隊模型進行分析。其中M表示顧客之間的到達時間間隔和服務員為顧客提供服務的時間服從指數分布[19]；m代表排隊系統中的系統容量;n代表排隊系統中的服務員數量

2 2種排隊模型

2.1 M/M/1/m模型

M/M/1/m模型的狀態轉移圖如圖1所示，圖中：λ和μ為上述指數分布對應的參數。

圖1 M/M/1/m模型狀態轉移圖Fig.1 State transition diagram of M/M/1/m model

由圖1可以列出平衡方程為

(1)

式中：Pk為系統中有k位顧客時的概率。定義M/M/1/m模型中系統的服務強度為

(2)

經過推導，可以得到M/M/1/m模型，隊列中顧客的平均數量為

(3)

因此，借助Little定理[20-21]，可以求得顧客在隊列中等待的時間為

(4)

2.2 M/M/n/m模型

M/M/n/m模型也可采用如圖2所示的狀態轉移圖求解概率分布。

圖2 M/M/n/m模型狀態轉移圖Fig.2 State transition diagram of M/M/n/m model

由圖2可列出平衡方程為

(5)

定義M/M/n/m模型中系統的服務強度為

(6)

通過推導，可得到M/M/n/m模型中的平均隊列長度為

(7)

基于Little定理，可以計算出M/M/n/m模型中，顧客在隊列中等待的時間為

(8)

3 2種排隊充電方式解析

3.1 分布式充電方式

面向蜂群無人機的分布式充電的示意圖如圖3所示。

圖3 分布式充電示意圖Fig.3 Schematic diagram of distributed charging

圖4 分布式充電等效圖Fig.4 Equivalent diagram of distributed charging

(10)

基于2.1節對M/M/1/m的分析，以及式(10)，可以計算出分布式充電的平均隊列長度Ld和平均等待時間Td分別為

(11)

Td=

(12)

3.2 集中式充電方式

針對蜂群無人機的集中式充電的示意圖如圖5 所示，n個充電平臺集中放置在一起。無人機到達后，在單一共享的隊列中等待充電。依據3.1節 所述，M/M/1/m模型可用于描述其中一個充電平臺。因此，在集中式充電的背景下，n個充電平臺可等效為M/M/n/nm模型。

圖5 集中式充電示意圖Fig.5 Schematic diagram of concentrated charging

基于本文2.2節對M/M/n/m模型的分析，經計算可得到，集中式充電的平均隊列長度Lc和平均等待時間Tc分別為

(13)

Tc=

(14)

(15)

(16)

4 數值計算及結果分析

基于第3節的公式推導以及對分布式充電的等效，如式(17)所示，2種排隊充電方式的服務強度相等。而針對蜂群無人機，服務強度即為：“單位時間返回充電平臺的無人機數量與單位時間離開充電平臺的無人機數量的比值”。在下文中，將使用無量綱量ρ來表述這一相等的服務強度。

(17)

本文基于MATLAB軟件，對2種排隊方式的平均隊列長度和平均等待時間進行計算。具體的參數設置如表1所示。

表1 參數設置Table 1 Parameter setting

4.1 平均隊列長度

當系統容量設定為6時，隨著服務強度和充電平臺數量的變化，2種充電方式的平均隊列長度對比如圖6所示。

依據圖6可以看出，在服務強度的區間為[0,2]時，若以平均隊列長度作為評價充電方式優劣的指標。隨著服務強度的增加，兩者的隊列長度均隨之增長，但存在一個分界點。即分布式充電的隊列長度曲線會與集中式充電的隊列長度曲線產生交叉點，在交叉點前，服務強度較小時，分布式充電的隊列長度高于集中式充電的隊列長度。在這一交叉點后，分布式充電的隊列長度低于集中式充電的隊列長度。下面，將系統容量依次設置為7、8和9時，繼續對比2種充電方式的平均隊列長度。

圖6 系統容量為6時的平均隊列長度對比Fig.6 Comparison of average queuing length when system capacity is 6

從圖7～圖9中可以看到，隨著服務強度的增加，將會觀察到與系統容量為6時一樣的現象。通過數值分析中的二分法，取區間為(0.7,0.9)，精度為0.000 1，可以求解出每一個交叉點的橫坐標，如表2所示。綜合上述曲線，可以觀察到，服務強度較低時，在以平均隊列長度作為評判指標時，集中式充電比較有優勢，但隨著服務強度的增加，分布式充電的優勢逐漸體現。

圖7 系統容量為7時的平均隊列長度對比Fig.7 Comparison of average queuing length when system capacity is 7

圖8 系統容量為8時的平均隊列長度對比Fig.8 Comparison of average queuing length when system capacity is 8

圖9 系統容量為9時的平均隊列長度對比Fig.9 Comparison of average queuing length when system capacity is 9

表2 2種充電方式平均隊列長度曲線的交叉點Table 2 Intersection of average queuing length curves of two charging methods

4.2 平均等待時間

觀察3.1節的式(12)和3.2節的式(14)，其中均有共同的因子λ的倒數。將其消去后，如式(18)和式(19)所示。因此，可以通過計算td和tc之間的大小關系，實現對2種充電方式的比較。

(18)

(19)

與4.1節處理方法一致，首先將系統容量設定為6。繪制2種充電方式的平均等待時間，即td和tc隨服務強度及平臺數量變化的曲線圖，如圖10所示。

依據圖10可以發現，在服務強度的區間為[0,2]時，隨著服務強度的增長，2種充電方式的平均等待時間隨之增長。服務強度較小時，集中式充電的平均等待時間低于另一者。但兩者在服務強度為1附近產生交叉點，在這一交叉點后，集中式充電的平均等待時間會高于另一者。

圖10 系統容量為6時的平均等待時間對比Fig.10 Comparison of average waiting time when system capacity is 6

從圖11～圖13中可以看到，隨著服務強度的增加，與4.1節類似。服務強度較低時，若以平均等待時間作為評判指標，集中式充電比較有優勢。但隨著服務強度的增加，分布式充電的優勢逐漸體現。通過數值分析中的二分法，取區間為(1.000 1,1.125)，精度為0.000 1，可以求解出每一個交叉點的橫坐標，如表3所示。

圖11 系統容量為7時的平均等待時間對比Fig.11 Comparison of average waiting time when system capacity is 7

圖12 系統容量為8時的平均等待時間對比Fig.12 Comparison of average waiting time when system capacity is 8

表3 2種充電方式平均等待時間曲線的交叉點Table 3 Intersection of average waiting time curves of two charging methods

5 結 論

1) 在服務強度的區間為[0,2]時，隨著服務強度的增強，評價指標對應的曲線存在交叉點。交叉點前，即服務強度較低的情形下，集中式充電的兩項評價指標優于分布式充電。但在交叉點后，隨著服務強度的增大，分布式充電的兩項評價指標優于集中式充電。

2) 對于不同充電平臺數量和系統容量給出了選擇集中式充電和分布式充電的交叉參考點，對蜂群無人機充電排隊提供重要的參考。