蜂群無(wú)人機(jī)充電排隊(duì)優(yōu)化方法

王云哲，徐國(guó)寧,*，王生，李兆杰，蔡榕

1.中國(guó)科學(xué)院 空天信息創(chuàng)新研究院，北京 100094 2.中國(guó)科學(xué)院大學(xué)，北京 100049

近年來(lái)，蜂群無(wú)人機(jī)由于可以體現(xiàn)出蜂群的整體優(yōu)勢(shì)，完成較復(fù)雜的任務(wù)，相比單一無(wú)人機(jī)，蜂群可以對(duì)多無(wú)人機(jī)執(zhí)行任務(wù)帶來(lái)很多的優(yōu)勢(shì)，成為國(guó)內(nèi)外研究的熱點(diǎn)[1-3]。但是由于電源技術(shù)的水平和限制，現(xiàn)有無(wú)人機(jī)續(xù)航時(shí)間短，需要經(jīng)常充電，因此蜂群無(wú)人機(jī)快速充電以及充電排隊(duì)問(wèn)題成為制約其快速發(fā)展和大面積應(yīng)用的瓶頸技術(shù)，特別是充電排隊(duì)問(wèn)題影響著蜂群無(wú)人機(jī)執(zhí)行任務(wù)的效率和效果。據(jù)現(xiàn)有文獻(xiàn)查詢，蜂群無(wú)人機(jī)充電排隊(duì)的研究未曾報(bào)道，本文基于排隊(duì)理論對(duì)蜂群無(wú)人機(jī)充電排隊(duì)技術(shù)進(jìn)行研究。

在常規(guī)的電動(dòng)汽車(chē)排隊(duì)充電研究中，文獻(xiàn)[4]基于排隊(duì)理論建立了充電設(shè)施系統(tǒng)排隊(duì)模型，通過(guò)合理配置充電設(shè)施，提高了電網(wǎng)負(fù)荷率。文獻(xiàn)[5] 基于排隊(duì)理論對(duì)電動(dòng)汽車(chē)充電站的24小時(shí)充電負(fù)荷曲線進(jìn)行建模，使用隨機(jī)最優(yōu)潮流和模型預(yù)測(cè)控制方法研究了不確定性的影響。文獻(xiàn)[6]基于排隊(duì)理論中的M/M/s模型和流體方程，計(jì)算了高速公路充電站的電動(dòng)汽車(chē)到達(dá)率。文獻(xiàn)[7]針對(duì)電動(dòng)出租汽車(chē)充電站排隊(duì)系統(tǒng)，對(duì)M/G/k排隊(duì)模型和M/M/k排隊(duì)模型進(jìn)行了對(duì)比，分析了電動(dòng)汽車(chē)到站的荷電狀態(tài)對(duì)排隊(duì)系統(tǒng)的影響，并提出了提高系統(tǒng)服務(wù)能力的措施。文獻(xiàn)[8]利用排隊(duì)理論在服務(wù)系統(tǒng)優(yōu)化設(shè)計(jì)方面的優(yōu)勢(shì)，構(gòu)建了電動(dòng)汽車(chē)充電樁的最優(yōu)臺(tái)數(shù)設(shè)計(jì)模型，同時(shí)利用排隊(duì)理論分析了充電站的服務(wù)水平和運(yùn)行效率。文獻(xiàn)[9]采用基于排隊(duì)論的充電機(jī)配置方法，提出了布局最優(yōu)化的數(shù)學(xué)模型，并基于M/M/s模型，以平均等待時(shí)間為標(biāo)準(zhǔn)確定充電站的規(guī)模。文獻(xiàn)[10]利用電動(dòng)汽車(chē)充電站排隊(duì)論模型，研究了基于路徑需求和基于點(diǎn)需求下的充電站選址定容問(wèn)題。文獻(xiàn)[11]基于排隊(duì)理論進(jìn)行了充電站的容量?jī)?yōu)化配置。

在面向蜂群無(wú)人機(jī)充電時(shí)，由于其工作環(huán)境的特殊性，可能需要懸停等待充電，比常規(guī)充電工況多，因此需要加入系統(tǒng)容量的限制。即，當(dāng)某一充電平臺(tái)可容納的無(wú)人機(jī)數(shù)量達(dá)到限定值后，無(wú)人機(jī)將不再前往這一平臺(tái)，從而避免了無(wú)人機(jī)在懸停等待的隊(duì)列中將電量耗盡。

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

1 排隊(duì)系統(tǒng)基本理論

在排隊(duì)論中，通常采用6個(gè)特性，實(shí)現(xiàn)對(duì)一個(gè)排隊(duì)系統(tǒng)的分析[17]。它們的描述通常依據(jù)Kendall提出的方法[18]：

A/B/N/S/C/Z

式中：A為輸入過(guò)程；B為服務(wù)時(shí)間；N為服務(wù)員數(shù)量；S為系統(tǒng)容量；C為客源數(shù)量；Z為排隊(duì)規(guī)則[17-19]。

當(dāng)系統(tǒng)容量為固定值，且排隊(duì)規(guī)則為先到先服務(wù)時(shí)。依據(jù)Kendall提出的方法，該類(lèi)排隊(duì)模型可表示為

A/B/N/S

第2節(jié)中，將著重對(duì)M/M/1/m和M/M/n/m2種排隊(duì)模型進(jìn)行分析。其中M表示顧客之間的到達(dá)時(shí)間間隔和服務(wù)員為顧客提供服務(wù)的時(shí)間服從指數(shù)分布[19]；m代表排隊(duì)系統(tǒng)中的系統(tǒng)容量;n代表排隊(duì)系統(tǒng)中的服務(wù)員數(shù)量

2 2種排隊(duì)模型

2.1 M/M/1/m模型

M/M/1/m模型的狀態(tài)轉(zhuǎn)移圖如圖1所示，圖中：λ和μ為上述指數(shù)分布對(duì)應(yīng)的參數(shù)。

圖1 M/M/1/m模型狀態(tài)轉(zhuǎn)移圖Fig.1 State transition diagram of M/M/1/m model

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

(1)

式中：Pk為系統(tǒng)中有k位顧客時(shí)的概率。定義M/M/1/m模型中系統(tǒng)的服務(wù)強(qiáng)度為

(2)

經(jīng)過(guò)推導(dǎo)，可以得到M/M/1/m模型，隊(duì)列中顧客的平均數(shù)量為

(3)

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

(4)

2.2 M/M/n/m模型

M/M/n/m模型也可采用如圖2所示的狀態(tài)轉(zhuǎn)移圖求解概率分布。

圖2 M/M/n/m模型狀態(tài)轉(zhuǎn)移圖Fig.2 State transition diagram of M/M/n/m model

由圖2可列出平衡方程為

(5)

定義M/M/n/m模型中系統(tǒng)的服務(wù)強(qiáng)度為

(6)

通過(guò)推導(dǎo)，可得到M/M/n/m模型中的平均隊(duì)列長(zhǎng)度為

(7)

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

(8)

3 2種排隊(duì)充電方式解析

3.1 分布式充電方式

面向蜂群無(wú)人機(jī)的分布式充電的示意圖如圖3所示。

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

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

(10)

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

(11)

Td=

(12)

3.2 集中式充電方式

針對(duì)蜂群無(wú)人機(jī)的集中式充電的示意圖如圖5 所示，n個(gè)充電平臺(tái)集中放置在一起。無(wú)人機(jī)到達(dá)后，在單一共享的隊(duì)列中等待充電。依據(jù)3.1節(jié) 所述，M/M/1/m模型可用于描述其中一個(gè)充電平臺(tái)。因此，在集中式充電的背景下，n個(gè)充電平臺(tái)可等效為M/M/n/nm模型。

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

基于本文2.2節(jié)對(duì)M/M/n/m模型的分析，經(jīng)計(jì)算可得到，集中式充電的平均隊(duì)列長(zhǎng)度Lc和平均等待時(shí)間Tc分別為

(13)

Tc=

(14)

(15)

(16)

4 數(shù)值計(jì)算及結(jié)果分析

基于第3節(jié)的公式推導(dǎo)以及對(duì)分布式充電的等效，如式(17)所示，2種排隊(duì)充電方式的服務(wù)強(qiáng)度相等。而針對(duì)蜂群無(wú)人機(jī)，服務(wù)強(qiáng)度即為：“單位時(shí)間返回充電平臺(tái)的無(wú)人機(jī)數(shù)量與單位時(shí)間離開(kāi)充電平臺(tái)的無(wú)人機(jī)數(shù)量的比值”。在下文中，將使用無(wú)量綱量ρ來(lái)表述這一相等的服務(wù)強(qiáng)度。

(17)

本文基于MATLAB軟件，對(duì)2種排隊(duì)方式的平均隊(duì)列長(zhǎng)度和平均等待時(shí)間進(jìn)行計(jì)算。具體的參數(shù)設(shè)置如表1所示。

表1 參數(shù)設(shè)置Table 1 Parameter setting

4.1 平均隊(duì)列長(zhǎng)度

當(dāng)系統(tǒng)容量設(shè)定為6時(shí)，隨著服務(wù)強(qiáng)度和充電平臺(tái)數(shù)量的變化，2種充電方式的平均隊(duì)列長(zhǎng)度對(duì)比如圖6所示。

依據(jù)圖6可以看出，在服務(wù)強(qiáng)度的區(qū)間為[0,2]時(shí)，若以平均隊(duì)列長(zhǎng)度作為評(píng)價(jià)充電方式優(yōu)劣的指標(biāo)。隨著服務(wù)強(qiáng)度的增加，兩者的隊(duì)列長(zhǎng)度均隨之增長(zhǎng)，但存在一個(gè)分界點(diǎn)。即分布式充電的隊(duì)列長(zhǎng)度曲線會(huì)與集中式充電的隊(duì)列長(zhǎng)度曲線產(chǎn)生交叉點(diǎn)，在交叉點(diǎn)前，服務(wù)強(qiáng)度較小時(shí)，分布式充電的隊(duì)列長(zhǎng)度高于集中式充電的隊(duì)列長(zhǎng)度。在這一交叉點(diǎn)后，分布式充電的隊(duì)列長(zhǎng)度低于集中式充電的隊(duì)列長(zhǎng)度。下面，將系統(tǒng)容量依次設(shè)置為7、8和9時(shí)，繼續(xù)對(duì)比2種充電方式的平均隊(duì)列長(zhǎng)度。

圖6 系統(tǒng)容量為6時(shí)的平均隊(duì)列長(zhǎng)度對(duì)比Fig.6 Comparison of average queuing length when system capacity is 6

從圖7～圖9中可以看到，隨著服務(wù)強(qiáng)度的增加，將會(huì)觀察到與系統(tǒng)容量為6時(shí)一樣的現(xiàn)象。通過(guò)數(shù)值分析中的二分法，取區(qū)間為(0.7,0.9)，精度為0.000 1，可以求解出每一個(gè)交叉點(diǎn)的橫坐標(biāo)，如表2所示。綜合上述曲線，可以觀察到，服務(wù)強(qiáng)度較低時(shí)，在以平均隊(duì)列長(zhǎng)度作為評(píng)判指標(biāo)時(shí)，集中式充電比較有優(yōu)勢(shì)，但隨著服務(wù)強(qiáng)度的增加，分布式充電的優(yōu)勢(shì)逐漸體現(xiàn)。

圖7 系統(tǒng)容量為7時(shí)的平均隊(duì)列長(zhǎng)度對(duì)比Fig.7 Comparison of average queuing length when system capacity is 7

圖8 系統(tǒng)容量為8時(shí)的平均隊(duì)列長(zhǎng)度對(duì)比Fig.8 Comparison of average queuing length when system capacity is 8

圖9 系統(tǒng)容量為9時(shí)的平均隊(duì)列長(zhǎng)度對(duì)比Fig.9 Comparison of average queuing length when system capacity is 9

表2 2種充電方式平均隊(duì)列長(zhǎng)度曲線的交叉點(diǎn)Table 2 Intersection of average queuing length curves of two charging methods

4.2 平均等待時(shí)間

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

(18)

(19)

與4.1節(jié)處理方法一致，首先將系統(tǒng)容量設(shè)定為6。繪制2種充電方式的平均等待時(shí)間，即td和tc隨服務(wù)強(qiáng)度及平臺(tái)數(shù)量變化的曲線圖，如圖10所示。

依據(jù)圖10可以發(fā)現(xiàn)，在服務(wù)強(qiáng)度的區(qū)間為[0,2]時(shí)，隨著服務(wù)強(qiáng)度的增長(zhǎng)，2種充電方式的平均等待時(shí)間隨之增長(zhǎng)。服務(wù)強(qiáng)度較小時(shí)，集中式充電的平均等待時(shí)間低于另一者。但兩者在服務(wù)強(qiáng)度為1附近產(chǎn)生交叉點(diǎn)，在這一交叉點(diǎn)后，集中式充電的平均等待時(shí)間會(huì)高于另一者。

圖10 系統(tǒng)容量為6時(shí)的平均等待時(shí)間對(duì)比Fig.10 Comparison of average waiting time when system capacity is 6

從圖11～圖13中可以看到，隨著服務(wù)強(qiáng)度的增加，與4.1節(jié)類(lèi)似。服務(wù)強(qiáng)度較低時(shí)，若以平均等待時(shí)間作為評(píng)判指標(biāo)，集中式充電比較有優(yōu)勢(shì)。但隨著服務(wù)強(qiáng)度的增加，分布式充電的優(yōu)勢(shì)逐漸體現(xiàn)。通過(guò)數(shù)值分析中的二分法，取區(qū)間為(1.000 1,1.125)，精度為0.000 1，可以求解出每一個(gè)交叉點(diǎn)的橫坐標(biāo)，如表3所示。

圖11 系統(tǒng)容量為7時(shí)的平均等待時(shí)間對(duì)比Fig.11 Comparison of average waiting time when system capacity is 7

圖12 系統(tǒng)容量為8時(shí)的平均等待時(shí)間對(duì)比Fig.12 Comparison of average waiting time when system capacity is 8

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

5 結(jié) 論

1) 在服務(wù)強(qiáng)度的區(qū)間為[0,2]時(shí)，隨著服務(wù)強(qiáng)度的增強(qiáng)，評(píng)價(jià)指標(biāo)對(duì)應(yīng)的曲線存在交叉點(diǎn)。交叉點(diǎn)前，即服務(wù)強(qiáng)度較低的情形下，集中式充電的兩項(xiàng)評(píng)價(jià)指標(biāo)優(yōu)于分布式充電。但在交叉點(diǎn)后，隨著服務(wù)強(qiáng)度的增大，分布式充電的兩項(xiàng)評(píng)價(jià)指標(biāo)優(yōu)于集中式充電。

2) 對(duì)于不同充電平臺(tái)數(shù)量和系統(tǒng)容量給出了選擇集中式充電和分布式充電的交叉參考點(diǎn)，對(duì)蜂群無(wú)人機(jī)充電排隊(duì)提供重要的參考。