基于多Agent的通航運(yùn)力資源協(xié)同調(diào)度

張紅穎，周子林，李 彪

(中國民航大學(xué)a.電子信息與自動化學(xué)院；b.航空工程學(xué)院，天津300300)

0 引 言

隨著近年來跨區(qū)域經(jīng)濟(jì)聯(lián)系的日益密切，通航業(yè)務(wù)規(guī)模穩(wěn)步增長，行業(yè)市場化程度不斷提升，對通航運(yùn)輸能力提出了更高的要求.傳統(tǒng)資源調(diào)度方法多建立在點(diǎn)對點(diǎn)的單向任務(wù)需求基礎(chǔ)上，應(yīng)對并行多任務(wù)、多資源的規(guī)模化協(xié)同調(diào)度問題能力不足[1]，難以保障日益增長的運(yùn)力需求，因此如何建立有效的、多位一體的通航運(yùn)力資源協(xié)同調(diào)度方法成為國內(nèi)外研究的熱點(diǎn)問題，國內(nèi)外學(xué)者主要利用啟發(fā)式算法和智能體算法進(jìn)行研究.啟發(fā)式算法方面，袁建國等[2]提出多目標(biāo)自適應(yīng)快速人工蜂群算法處理調(diào)度決策片面性的問題；王堅(jiān)浩等[3]提出一種基于入侵雜草蝙蝠混合算法的雙子群任務(wù)規(guī)劃方法.但啟發(fā)式算法迭代次數(shù)多，求解速率偏慢的問題并未完全解決.Rolka 等[4]采用智能體算法，建立基于黑板模式的分布式多Agent控制網(wǎng)絡(luò)任務(wù)調(diào)度模型，引入聯(lián)合約束懲罰算子強(qiáng)化底層Agent的效用值增益函數(shù)，提升了分配方案的計算速率；為增強(qiáng)系統(tǒng)調(diào)度能力，王沖[5]設(shè)計了相鄰Agent的信息協(xié)議增益矩陣，改善了調(diào)度模型耦合度，但智能體算法存在系統(tǒng)資源占用過多的問題，隨著并行任務(wù)數(shù)量的增加，計算時間呈指數(shù)級上升趨勢[6].

上述國內(nèi)外資源調(diào)度方法依然存在求解多任務(wù)模型速度較慢的不足之處，故本文提出一種基于多Agent的通航運(yùn)力資源協(xié)同調(diào)度方法，建立生產(chǎn)任務(wù)與運(yùn)力資源匹配模型以提升并行任務(wù)處理效率，在匹配性結(jié)果的基礎(chǔ)上設(shè)計資源調(diào)度數(shù)學(xué)模型及其求解算法，最后進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證該方法的合理性和有效性.

1 通航運(yùn)力資源協(xié)同調(diào)度框架

提出一種多級通航運(yùn)力資源協(xié)同調(diào)度框架，將問題分解為系統(tǒng)級并行任務(wù)與運(yùn)力資源的匹配過程，與分系統(tǒng)級運(yùn)力資源協(xié)同調(diào)度過程分別建模求解.

系統(tǒng)級匹配模型以運(yùn)力資源作業(yè)效率最大化為目標(biāo)，設(shè)計招標(biāo)式多Agent協(xié)商算法求得并行生產(chǎn)任務(wù)與通航運(yùn)力資源的匹配性結(jié)果.

分系統(tǒng)級資源調(diào)度模型以匹配性結(jié)果為主體，依據(jù)對應(yīng)的目標(biāo)函數(shù)及約束條件，構(gòu)建數(shù)學(xué)模型并求解，實(shí)現(xiàn)分系統(tǒng)內(nèi)資源協(xié)同調(diào)度過程.整體運(yùn)力資源協(xié)同調(diào)度模型框架如圖1所示.

圖1 基于招標(biāo)式多Agent 協(xié)商的協(xié)同調(diào)度算法基本框架Fig.1 Basic frame of collaborative schedule algorithm based on bidding multi-Agent negotiation

2 系統(tǒng)級多Agent運(yùn)力匹配模型

2.1 模型架構(gòu)

針對通航并行任務(wù)與運(yùn)力資源的匹配過程，建立如圖2所示的系統(tǒng)級Agent 模型.嵌入基于招投標(biāo)機(jī)制的多Agent 協(xié)商模塊，設(shè)立中央調(diào)度Agent作為招標(biāo)管理者，完成競標(biāo)資源層與招標(biāo)任務(wù)層的信息交換，實(shí)現(xiàn)任務(wù)與運(yùn)力資源之間的匹配性關(guān)系.

圖2 系統(tǒng)級多Agent 運(yùn)力匹配模型Fig.2 Matching model of system-level multi-Agent

整體模型中，各運(yùn)力資源Agent擁有均等機(jī)會發(fā)布自身屬性信息的競標(biāo)模式?jīng)Q定著該協(xié)商算法能夠同時訪問多類候選資源，并依據(jù)判決條件選取任務(wù)的最佳執(zhí)行者，即最優(yōu)解.該方法在算法機(jī)制上提升了協(xié)同調(diào)度多類資源匹配并行任務(wù)的處理能力.

2.2 任務(wù)招標(biāo)

定義任務(wù)Agent 集合為{T1,T2,…,Tn} ，集合中共有n個任務(wù)Agent 元素；航空器Agent 集合為{P1,P2,…,Pi} ，集合中共有i個航空器Agent元素；機(jī)組Agent 集合為{C1,C2,…,Cj} ，集合中共有j個機(jī)組Agent元素.任務(wù)Tn向中央調(diào)度Agent廣播招標(biāo)書并申請資源Pi和Cj，招標(biāo)書向量Xn=(tn,Vn,An,Sn,Mn,Qi,Wj)，其中，tn為任務(wù)作業(yè)需求時間，Vn為任務(wù)需求速率，An為任務(wù)海拔得分，Sn為任務(wù)坡度得分，Mn為任務(wù)氣象得分，Qj、Wj分別為0-1二值化航空器、機(jī)組狀態(tài)變量，變量為0表示處于適航狀態(tài)，變量為1 表示處于不適航狀態(tài).以上數(shù)據(jù)信息存儲于狀態(tài)知識庫中，在本文討論范疇中視為已知條件.

2.3 運(yùn)力資源競標(biāo)

中央調(diào)度Agent接收招標(biāo)書Xn后轉(zhuǎn)發(fā)至運(yùn)力資源層中的各Pi；滿足數(shù)據(jù)變量An、Sn與Mn且狀態(tài)變量Qi為0 的Pi，向狀態(tài)知識庫查詢機(jī)型對應(yīng)且狀態(tài)變量Wj為0 的Cj，向中央調(diào)度Agent 返回包含機(jī)組、航空器編號與作業(yè)速率的競標(biāo)書向量xn=(Pi,Cj,vij)；否則返回競標(biāo)書為空.

2.4 任務(wù)評標(biāo)

接收競標(biāo)書應(yīng)答的中央調(diào)度Agent 篩選滿足任務(wù)需求速率Vn的最大值vij，宣布對應(yīng)的競標(biāo)單位Pi、Cj中標(biāo)，完成任務(wù)Tn與航空資源的匹配成組過程.任務(wù)資源匹配性算法流程圖如圖3所示.

圖3 任務(wù)資源匹配算法流程圖Fig.3 Workflow of tasks matching with resources

求解系統(tǒng)級匹配模型所得到的匹配性結(jié)果包含在任務(wù)Agent單元內(nèi)輸出，便于資源調(diào)度分系統(tǒng)繼承對應(yīng)數(shù)據(jù).

3 分系統(tǒng)級多Agent運(yùn)力資源調(diào)度模型

3.1 模型設(shè)計

分系統(tǒng)級多Agent 資源調(diào)度模型如圖4所示，以任務(wù)Tn為主體，所匹配運(yùn)力資源Pi、Cj為被控對象，在繼承對應(yīng)匹配性結(jié)果的條件下，建立資源調(diào)度數(shù)學(xué)模型并求解最優(yōu)解.

圖4 分系統(tǒng)級資源調(diào)度模型Fig.4 Model of subsystem resource scheduling

3.2 設(shè)定目標(biāo)函數(shù)

通航實(shí)際電力巡檢作業(yè)過程中，機(jī)組作業(yè)質(zhì)量與作業(yè)時長具有正相關(guān)性，因此選取參數(shù)單機(jī)日利用率作為分系統(tǒng)n優(yōu)化目標(biāo).定義分系統(tǒng)n中單機(jī)日利用率Dn向量表達(dá)式為

式中：tn為任務(wù)Tn的需求作業(yè)時間值，總計天數(shù)為t；Bk為長度為t的機(jī)組飛行時長向量，元素bk表示第k天機(jī)組的作業(yè)時長(h).

單機(jī)日利用率Dn是對向量Bk元素求和所得總飛行時長與tn的比值，反映了任務(wù)Tn中航空資源Pi和Cj的使用效率.實(shí)際作業(yè)過程中，天氣、管制等外界因素造成的客觀不適航性對航空資源指派造成一定的影響，需要對分系統(tǒng)目標(biāo)函數(shù)作規(guī)劃調(diào)整.定義航空器適航矩陣Zn為

式中：矩陣Zn為t×t的對角線矩陣，主對角線元素為第t天航空器的適航性，適航則元素為1，不適航則元素為0.將適航矩陣右乘飛行時長矩陣Bk后結(jié)合式(1)可得到修正后的目標(biāo)函數(shù)為

3.3 構(gòu)建約束條件

分系統(tǒng)數(shù)學(xué)模型約束條件源自航空運(yùn)輸業(yè)的規(guī)章條例，從安全因素與任務(wù)計劃兩方面對運(yùn)力資源實(shí)現(xiàn)約束.

安全因素約束體現(xiàn)在航空器與機(jī)組勞動強(qiáng)度均受到客觀條件限制：航空器各機(jī)型續(xù)航時間不超過m1h，機(jī)組的工作時長不可超過m2h以避免疲勞生產(chǎn)，m1、m2具體數(shù)值可查閱相關(guān)規(guī)章條例，安全因素約束為

式(4)表示飛行時長向量Bk中的每個元素均小于等于m1，即航空器日均作業(yè)時長受到限制；式(5)表示飛行時長向量Bk中值不為0的元素不超過m2，即保證機(jī)組的工作天數(shù)在正常范圍內(nèi).

任務(wù)計劃約束體現(xiàn)在每日需完成基礎(chǔ)均攤?cè)蝿?wù)量，方可保證按期完成生產(chǎn)任務(wù).任務(wù)量約束條件為

式(6)表示機(jī)組每日結(jié)算的總作業(yè)里程數(shù)均滿足總?cè)蝿?wù)量的進(jìn)度要求，即保證可按計劃完成任務(wù)需求.

3.4 改進(jìn)遺傳算法求解

遺傳算法處理并行任務(wù)能力強(qiáng)，穩(wěn)定性高[7]，適合求解包含并行多任務(wù)的資源調(diào)度模型，但需針對傳統(tǒng)遺傳算法后期收斂速度慢的缺點(diǎn)進(jìn)行改進(jìn).輪盤賭選擇算子根據(jù)個體適應(yīng)度來分配選擇概率，具有精英保留的特點(diǎn)，在此方法上加入基于進(jìn)化代數(shù)的催熟機(jī)制，提升后期種群的選擇壓力以保證后期收斂速度，改進(jìn)后的輪盤賭選擇算子個體被選概率表達(dá)式為

式中：Pind為種群個體被選概率；Find為個體適應(yīng)度值；o為當(dāng)前第r代的種群大小，e為當(dāng)前進(jìn)化代數(shù)，E為總進(jìn)化代數(shù).

式(7)保證適應(yīng)度值越高的個體被選中的概率越大，且隨著進(jìn)化代數(shù)的增加，優(yōu)秀個體的權(quán)重也獲得提高，從而在保留適應(yīng)度值高的個體的同時加速了后期算法收斂.改進(jìn)遺傳算法求解資源調(diào)度模型主要步驟如下：

Step 1以Bk向量為實(shí)數(shù)編碼形式隨機(jī)生成n個分系統(tǒng)的初始種群.

Step 2以式(3)為種群適應(yīng)度值評價函數(shù)進(jìn)行計算.

Step 3依據(jù)式(4)～式(6)進(jìn)行個體淘汰，未淘汰個體依據(jù)式(7)進(jìn)行選擇操作，適應(yīng)度值較高的個體組成新種群.

Step 4對并行n個種群進(jìn)行變異交叉操作生成下一代完整種群.

Step 5若進(jìn)化代數(shù)達(dá)到終止進(jìn)化代數(shù)，算法結(jié)束，輸出結(jié)果；否則重復(fù)Step 2～Step 4.

求解算法流程圖如圖5所示.求解資源調(diào)度模型所得結(jié)果Bk通過調(diào)度Agent 發(fā)送至Pi和Cj來指導(dǎo)通航資源的作業(yè)時長.

圖5 資源調(diào)度模型求解算法流程示意圖Fig.5 Flow chart of resource scheduling model

4 算例分析

4.1 仿真平臺及先驗(yàn)數(shù)據(jù)

本文所提出的通航運(yùn)力資源協(xié)同調(diào)度方法基于java/JADE(version1.8)平臺進(jìn)行開發(fā)測試，硬件配置為Intel Core i7 CPU，內(nèi)存16 G.首先，在JADE平臺創(chuàng)建任務(wù)、航空器、機(jī)組Agent與中央調(diào)度Agent模型；其次，開發(fā)實(shí)現(xiàn)所設(shè)計的Agent協(xié)作法則；最后，導(dǎo)入表1和表2所示國內(nèi)某大型通航公司實(shí)時運(yùn)行數(shù)據(jù)，以及表3所示由氣象、管制等限制因素形成的適航屬性表.

表1 任務(wù)數(shù)據(jù)信息Table1 Task data

表2 運(yùn)力資源數(shù)據(jù)信息Table2 Transport resources data

由表1～表3可得任務(wù)、航空器、機(jī)組狀態(tài)知識庫具體數(shù)據(jù)，以及任務(wù)招標(biāo)書Xn與航空器適航矩陣Zn具體表達(dá)形式，查閱民航局所發(fā)布CCAR-121部條例可得m1、m2值，以便仿真模型計算求解.

4.2 仿真結(jié)果及分析

4.2.1 系統(tǒng)級運(yùn)力匹配性結(jié)果

仿真所得系統(tǒng)級運(yùn)力匹配結(jié)果如表4所示.將匹配性結(jié)果與實(shí)際生產(chǎn)運(yùn)行數(shù)據(jù)進(jìn)行對比，如表5所示.

表3 航空器適航性Table3 Airworthiness of aircraft

實(shí)驗(yàn)所含數(shù)據(jù)信息表如圖6所示。對比結(jié)果可得：使用協(xié)同調(diào)度算法所得匹配性結(jié)果同比實(shí)際運(yùn)行結(jié)果在平均機(jī)組作業(yè)速率上提升1.6 km/h，運(yùn)力資源作業(yè)能力更強(qiáng)；單任務(wù)計算求解模型時間控制在2.3 s 內(nèi)，求解速率受并行任務(wù)數(shù)量影響較小，體現(xiàn)出較好的并行多任務(wù)處理能力.

表4 系統(tǒng)級運(yùn)力匹配結(jié)果Table4 System-level matching results

圖6 匹配性結(jié)果與實(shí)際運(yùn)行數(shù)據(jù)對比Fig.6 Comparisons between matching results and actual operation data

4.2.2 運(yùn)力資源調(diào)度結(jié)果

5 類并行任務(wù)運(yùn)力資源調(diào)度結(jié)果如表6所示，限于篇幅，此處給出整個作業(yè)周期(30 d)內(nèi)部分日期的機(jī)組作業(yè)時長.

由表6中資源調(diào)度數(shù)據(jù)可得，本文所提出的調(diào)度方法求得每日作業(yè)小時數(shù)結(jié)果均優(yōu)于實(shí)際運(yùn)行數(shù)據(jù).

為驗(yàn)證本文方法的資源調(diào)度能力，選取單機(jī)日利用率和作業(yè)時長均方差兩類關(guān)鍵參數(shù)，與文獻(xiàn)[3]中人工蜂群算法、文獻(xiàn)[4]中分布式多Agent調(diào)度網(wǎng)絡(luò)模型實(shí)驗(yàn)結(jié)果進(jìn)行對比，所得仿真對比數(shù)據(jù)如表7所示.

由表7中數(shù)據(jù)可得協(xié)同調(diào)度算法資源調(diào)度結(jié)果在單機(jī)日利用率方面相比人工蜂群算法調(diào)度結(jié)果平均提升0.27 h/d，相比分布式多Agent 調(diào)度網(wǎng)絡(luò)模型調(diào)度結(jié)果平均提升0.19 h/d，有效增加了運(yùn)力資源作業(yè)時長.

針對參數(shù)作業(yè)時長均方差進(jìn)行分析，本文提出算法在作業(yè)時長均方差方面相比人工蜂群算法調(diào)度結(jié)果平均降低0.12 h，相比分布式多Agent 調(diào)度網(wǎng)絡(luò)模型調(diào)度結(jié)果降低0.03 h，證明本文算法提升了作業(yè)穩(wěn)定性.

表6 并行多任務(wù)運(yùn)力資源調(diào)度結(jié)果Table6 Capacity resources scheduling results of parallel multi-task

表7 仿真參數(shù)對比結(jié)果Table7 Comparison of simulation parameters

為驗(yàn)證本文提出方法的計算效率，將資源調(diào)度算法與傳統(tǒng)遺傳算法及文獻(xiàn)[5]中所提出的多Agent 耦合算法計算時間數(shù)據(jù)繪制如圖7所示，其中遺傳算法的種群迭代次數(shù)設(shè)為50代.

圖7 求解計算時間對比Fig.7 Comparisons of calculating time

由圖7可得，本文提出的資源調(diào)度算法因加入了基于進(jìn)化代數(shù)的催熟機(jī)制，相比傳統(tǒng)遺傳算法求解速率提升了26.1%；而與多Agent 耦合算法相比，對于單個任務(wù)的計算時間雖然有所增加，但隨著并行任務(wù)數(shù)量的增長，在計算速度方面的優(yōu)勢逐漸顯著.

結(jié)合對比仿真實(shí)驗(yàn)結(jié)果可以看出，所提出的基于多Agent 通航運(yùn)力資源協(xié)同調(diào)度算法通過細(xì)化運(yùn)力匹配流程、建立資源調(diào)度模型與綜合考量各類限制條件等方法，有效提升了多任務(wù)通航資源作業(yè)質(zhì)量與穩(wěn)定性，并能在較快時間內(nèi)完成求解過程.

5 結(jié) 論

針對并行式多任務(wù)通航資源調(diào)度問題，建立基于多Agent協(xié)商的運(yùn)力資源協(xié)同調(diào)度模型，在運(yùn)力匹配環(huán)節(jié)設(shè)計基于招投標(biāo)機(jī)制的求解模型算法以提高處理并行任務(wù)的匹配能力與效率；設(shè)計并行式資源調(diào)度分系統(tǒng)模型繼承匹配性結(jié)果，并提出相應(yīng)的目標(biāo)函數(shù)與約束檢驗(yàn)規(guī)則進(jìn)行求解.仿真結(jié)果證明，所提出的基于多Agent的通航運(yùn)力資源協(xié)同調(diào)度方法能有效求解通航運(yùn)輸業(yè)并行多任務(wù)資源調(diào)配問題.