張紅穎，周子林，李 彪

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

0 引 言

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

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

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

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

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

分系統(tǒng)級(jí)資源調(diào)度模型以匹配性結(jié)果為主體，依據(jù)對(duì)應(yīng)的目標(biāo)函數(shù)及約束條件，構(gòu)建數(shù)學(xué)模型并求解，實(shí)現(xiàn)分系統(tǒng)內(nèi)資源協(xié)同調(diào)度過(guò)程.整體運(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)級(jí)多Agent運(yùn)力匹配模型

2.1 模型架構(gòu)

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

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

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

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

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

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

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

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

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

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

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

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

3.1 模型設(shè)計(jì)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 算例分析

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

本文所提出的通航運(yùn)力資源協(xié)同調(diào)度方法基于java/JADE(version1.8)平臺(tái)進(jìn)行開(kāi)發(fā)測(cè)試，硬件配置為Intel Core i7 CPU，內(nèi)存16 G.首先，在JADE平臺(tái)創(chuàng)建任務(wù)、航空器、機(jī)組Agent與中央調(diào)度Agent模型；其次，開(kāi)發(fā)實(shí)現(xiàn)所設(shè)計(jì)的Agent協(xié)作法則；最后，導(dǎo)入表1和表2所示國(guó)內(nèi)某大型通航公司實(shí)時(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í)庫(kù)具體數(shù)據(jù)，以及任務(wù)招標(biāo)書(shū)Xn與航空器適航矩陣Zn具體表達(dá)形式，查閱民航局所發(fā)布CCAR-121部條例可得m1、m2值，以便仿真模型計(jì)算求解.

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

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

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

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

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

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

圖6 匹配性結(jié)果與實(shí)際運(yùn)行數(shù)據(jù)對(duì)比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所示，限于篇幅，此處給出整個(gè)作業(yè)周期(30 d)內(nèi)部分日期的機(jī)組作業(yè)時(shí)長(zhǎng).

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

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

針對(duì)參數(shù)作業(yè)時(shí)長(zhǎng)均方差進(jìn)行分析，本文提出算法在作業(yè)時(shí)長(zhǎng)均方差方面相比人工蜂群算法調(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ù)對(duì)比結(jié)果Table7 Comparison of simulation parameters

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

圖7 求解計(jì)算時(shí)間對(duì)比Fig.7 Comparisons of calculating time

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

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

5 結(jié) 論

針對(duì)并行式多任務(wù)通航資源調(diào)度問(wèn)題，建立基于多Agent協(xié)商的運(yùn)力資源協(xié)同調(diào)度模型，在運(yùn)力匹配環(huán)節(jié)設(shè)計(jì)基于招投標(biāo)機(jī)制的求解模型算法以提高處理并行任務(wù)的匹配能力與效率；設(shè)計(jì)并行式資源調(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)配問(wèn)題.