基于Petri網(wǎng)的艦載機出庫調度建模方法*

劉亞杰，李忠猛，謝 君

（海軍工程大學，武漢 430033）

基于Petri網(wǎng)的艦載機出庫調度建模方法*

劉亞杰，李忠猛，謝 君

（海軍工程大學，武漢 430033）

艦載機出庫作業(yè)調度效率是完成艦船作戰(zhàn)效能的重要保證。分析了艦載機出庫作業(yè)調度建模方法問題?；赑etri網(wǎng)技術理論，建立艦載機出庫邏輯關系Petri網(wǎng)模型?；跈C庫內艦載機出庫作業(yè)決策過程，建立艦載機出庫作業(yè)四階段決策的數(shù)學模型。最后給出優(yōu)化算法流程并進行驗證。

艦載機，調度，決策模型

0 引言

航母的絕大多數(shù)作戰(zhàn)使命都需要艦載機來承擔和完成，因此，艦載機的調度效率，對于提高航母的作戰(zhàn)效能具有極其重要的作用。機庫艦載機的出庫調度問題實際是在路徑安全的前提下，以最小的成本將調度需求目標飛機從機庫當前位置牽引至升降機并移到飛行甲板上。事實上，由于機庫布滿艦載機，安全路徑可能并不存在。在安全路徑不存在的情況下，需要不斷將該批次目標飛機附近的艦載機移出機庫（為了描述方便，本文將這種現(xiàn)象稱之為倒機），這將觸發(fā)了一個新的調度問題，直到機庫有足夠的空間使目標飛機能安全通行為止。因此，調度方案是一批次飛機出庫順序的編排；最優(yōu)調度方案則是合理的編排飛機出庫順序，使目標艦載機在最短的時間內調出機庫。

國外過去對于艦載機調度的做法一般是通過擺放模型，以指導調度艦載機的甲板活動，如在美軍航母上使用的“占卜板”［1］。近年來，一些航母上設置了飛行甲板通信系統(tǒng)，加強了飛行甲板各戰(zhàn)位之間的相互聯(lián)系。隨著計算機技術的發(fā)展，國外開始將計算機應用于艦載機調度方面的輔助決策。Jeffery［2］等人設計了一種航母艦載機甲板持續(xù)監(jiān)控系統(tǒng)，該系統(tǒng)結合了艦載機GPS定位，碰撞事故檢測等功能，為提高艦載機甲板作業(yè)效率和減少事故起到了一定的積極作用。

國內楊炳恒［3］等以俄航母艦載機機庫內調運作業(yè)為研究原型，創(chuàng)建了艦載機調運作業(yè)交通網(wǎng)絡，文章沒有研究艦載機出庫調度優(yōu)化問題。馮強［4］等將Multi-Agent技術應用到艦載機各甲板作業(yè)之間的協(xié)調，對調度方案的優(yōu)化作用不大。劉欽輝［5］等研究的是飛行甲板艦載機的艦面調度問題。

求解最優(yōu)的艦載機調度方案，首先應該選擇合理而有效的出庫調度建模方法。艦載機出庫調度建模的前提條件是機庫艦載機調運作業(yè)環(huán)境建模［6］以及對艦載機在機庫內的調運作業(yè)進行路徑規(guī)劃［7］。筆者在文獻［6-7］中已對調運問題的環(huán)境建模和路徑規(guī)劃問題進行了詳述，本文不再贅述。

在環(huán)境建模和路徑規(guī)劃的基礎上，本文首先建立了艦載機出庫邏輯關系模型，并利用Petri網(wǎng)對其關系進行表達；其次通過分析艦載機出庫作業(yè)調度計劃的制定過程，建立了艦載機出庫調度計劃數(shù)學模型；最后給出艦載機出庫調度優(yōu)化算法流程并對其進行驗證。

1 艦載機出庫邏輯關系建模

機庫艦載機出庫調度問題屬于典型的離散事件動態(tài)系統(tǒng)，對于離散事件動態(tài)系統(tǒng)的建模，Petri網(wǎng)已經(jīng)證明是一個較為理想的工具。Petri網(wǎng)能夠準確快速地反映系統(tǒng)實時調度的離散性與隨機性，與其他方法相結合在調度問題中得到了廣泛的應用［8-9］。

1.1 艦載機出庫邏輯關系確立

已知機庫內艦載機的布列形式，按照圖1所示的艦載機出庫調度邏輯關系算法流程圖，確定機庫中艦載機出庫時的邏輯先后關系，并建立艦載機出庫的優(yōu)先級。設立艦載機出庫優(yōu)先級的目的是快速安排一批次艦載機的出庫順序問題，提高算法的收斂速度。

1.2 艦載機出庫邏輯關系表達

艦載機出庫邏輯關系確定后，需要對其進行正確合理的建模表達。依據(jù)Petri網(wǎng)離散事件動態(tài)系統(tǒng)建模理論，建立艦載機出庫邏輯關系Petri網(wǎng)模型。以圖2所示的法國“戴高樂”航母機庫內艦載機的調運順序求解為例。艦載機分別用英文大寫字母A、B、C、D等表示，兩部升降機分別命名為升降機1和升降機2?？紤]升降機資源利用的均衡性，以防火分隔門為界，將機庫分為兩部分，分別記作機庫I部和機庫II部。

本文將Petri網(wǎng)技術中的賦時、隨機性結合起來，應用TSPN（賦時隨機Petri網(wǎng)）技術建立機庫艦載機出庫關系的Petri網(wǎng)模型，如圖3所示。

庫所pi∈P代表艦載機的位置，25架艦載機A、B、C、D、E、…、X、Y與庫所是一一對應關系。

位置pSi∈P，i=1,2代表艦載機被牽引至升降機事件。

位置f0、f1表示對調運任務的判斷分配，它瞬時保留到來的任務，根據(jù)di所聯(lián)系的實施謂詞或隨機開關來決定到來的任務放入哪一個隊列。

變遷屬性T包括時間變遷和瞬時變遷兩種，時間變遷用ti表示，ti∈T描述了艦載機牽引至升降機等可控事件，瞬時變遷用di表示，di∈T表示調運決策的執(zhí)行。d0表示調運任務的并行執(zhí)行；機庫I部和機庫II部的調運任務可并行執(zhí)行，一個并行網(wǎng)模型結構由兩個變遷來模擬，這兩個變遷在相同的標識中可獨立實施，一個變遷的實施不影響另一個變遷的實施。

1.3 Petri網(wǎng)模型的性能分析

1.3.1 可達性分析

可達樹和矩陣方程是對Petri網(wǎng)模型進行可達性分析的兩種方法［7］。由于可達樹分析具有一定的局限性，本文以矩陣方程為基礎對其可達性分析。

利用關聯(lián)矩陣，對Petri網(wǎng)的可達性分析如下：

①按照一定的軌跡運行，系統(tǒng)所能到達的狀態(tài)。

設初始標識為M0=［1 0 0 0 0 0 0 0 0 0 0 0］，求ti變遷被激發(fā)的標識M'，即p1位置的艦載機被牽引至升降機后，哪些位置的艦載機可以遷移。

這里T'=［1 0 0 0，0 0 0］，則

矩陣M'表示當ti變遷被激發(fā)后，位置p2、p3、p4的艦載機狀態(tài)可達（即可以被遷移）。

②從某一狀態(tài)出發(fā)，是否能夠到達某一既定狀態(tài)。

設初始標識為M0=［1 0 0 0 0 0 0 0 0 0 0 0］，判斷M''=［0 1 0 0 0 0 1 0 0 0 0］否可達，求如下方程：

解得T''=［1-1 1 0 0 0 0］

這里T''為非負整數(shù)，表示M''不可達，即位置p2，p7的艦載機狀態(tài)不可達（即前面有艦載機阻擋，需要進行倒機才可以調運出庫）。

1.3.2 沖突與等待

由前面的分析已知出庫調運Petri網(wǎng)模型中，由于升降機的數(shù)量是有限的，并且艦載機出庫時互相阻擋，會造成資源及路徑的沖突。解決這些沖突的方法是排定響應它們發(fā)出請求的順序，即當沖突發(fā)生時，讓其中的一個過程享有此共享資源，而其他發(fā)出此請求的過程按照某種規(guī)則進行等待，當享有共享資源的過程完成之后，就釋放此共享資源，以響應下一個發(fā)出請求的過程，以此類推，就能夠解決沖突的問題。

如圖3所示，當位置p1的艦載機被調運至升降機后，位置p2、p3、p4的艦載機可以進行出庫調運作業(yè)，但因為升降機資源有限，只能有一個位置的變遷被激發(fā)，這時按照某種規(guī)則，其他兩個位置的艦載機就需要進行等待。

利用Petri網(wǎng)模型，求解艦載機的可達性問題和調運過程中發(fā)生的沖突、等待等問題，作為調度方案優(yōu)化過程中排序和倒機決策的依據(jù)。

2 艦載機出庫調度數(shù)學模型

一般意義下，艦載機出庫需求批量表Q可以定義如下：

機庫中存放的每一種型號的艦載機數(shù)量會大于或等于實際的需求量。根據(jù)需求信息Q表中的需求信息，在機庫中調度艦載機會有多種選擇。因此，需要根據(jù)艦載機出庫需求信息表，制定艦載機出庫作業(yè)調度的具體方案。艦載機出庫作業(yè)調度方案的制定過程可分為4個階段：第1階段是根據(jù)需求量及機庫內艦載機的資源信息，制定艦載機在機庫內部調運數(shù)量的分配方案；第2階段根據(jù)第1階段制定的分配方案，選擇出庫艦載機；第3階段對第2階段選出的艦載機進行排序；第4階段對排序的艦載機制定倒機方案，最后輸出艦載機出庫順序。艦載機出庫作業(yè)調度問題是一個四層決策問題，下層決策以上層決策為前提進行規(guī)劃。每一層決策又可以歸結為一個組合優(yōu)化問題，在當前條件下，從各種可行方案中選擇一個最優(yōu)方案。如何對艦載機出庫作業(yè)從整體上進行考慮，降低倒機次數(shù)，提高作業(yè)效率，是制定出庫調度方案的主要任務。

2.1 出庫艦載機數(shù)量分配模型

已知機庫內艦載機資源信息和具體的調運需求，假設機庫內配置兩部升降機，建立出庫艦載機數(shù)量分配模型如下：

其中各參數(shù)定義如下：

ni指Si型艦載機的需求量，n1i、n2i分別指Si型艦載機分配到機庫I部、II部的需求數(shù)量；

N指批量需求表Q中艦載機總需求量，N1、N2分別指分配到機庫I部、II部的艦載機需求量。

2.2 出庫艦載機選擇模型

確定機庫I部和II部各型艦載機的具體分配數(shù)量后，出庫艦載機的選擇過程分為兩步：

2.2.1 確定候選艦載機出庫作業(yè)集合

定義需求表Q中需求艦載機規(guī)格相符合的艦載機為候選艦載機，用U表示候選艦載機的集合，其中U1，U2分別表示機庫I部、機庫II部候選艦載機的集合，u1ij，u2ij分別指機庫I部、II部中與需求艦載機規(guī)格Si相符的艦載機集合，定義S（uij）為艦載機uij的規(guī)格。

其中，m1i、m2i分別表示機庫I部、II部中規(guī)格為Si的艦載機數(shù)量。

2.2.2 選擇出庫艦載機

根據(jù)需求艦載機的數(shù)量，分別從U1、U2中選擇出庫艦載機，用V表示出庫艦載機集合，其V1,V2分別為機庫I部、II部的出庫艦載機集合，則：

2.3 艦載機出庫排序模型

一批次艦載機調運出庫作業(yè)的邏輯性強，機庫內艦載機狀態(tài)隨著出庫作業(yè)過程的進行，不斷發(fā)生變化。符合需求的艦載機集合確定后，處于雜亂無序的狀態(tài)，因此，需要制定合理的艦載機出庫作業(yè)次序。

定義機庫I部、II部排序后的艦載機集合為：

2.4 艦載機倒機決策模型

由于機庫內艦載機布列緊湊，根據(jù)調度需求，從機庫中調運艦載機x1ij出庫，如果該架艦載機不能直接調出，則首先需對阻擋其出路的艦載機進行調運作業(yè)，即進行包含調度x1ij以及由此產(chǎn)生的倒機作業(yè)的決策過程。

倒機作業(yè)應遵循倒機架次最少的原則進行，即尋找艦載機最佳的出庫序列。對于排序后的艦載機集合X1、X2，根據(jù)Petri網(wǎng)模型及可達矩陣，即可求出X1、X2中需要倒機的艦載機，從而得出滿足調運需求的艦載機出庫集合。

定義機庫I部、II部出庫艦載機集合為：

2.5 艦載機出庫作業(yè)目標函數(shù)

對于艦載機牽引移動部門來說，減少作業(yè)過程中的倒機次數(shù)，縮短調運作業(yè)行程，力求作業(yè)時間最短，以節(jié)約作業(yè)成本是其首要目標。定義F（Z）為完成艦載機出庫方案時的最短作業(yè)時間，其中F1（Z1）、F2（Z2）分別為機庫I部、機庫II部艦載機完成出庫方案的作業(yè)時間，機庫I部、II部中調運時間最長的時間就是艦載機出庫調運作業(yè)時間，即艦載機出庫作業(yè)計劃的目標函數(shù)表示為：

3 出庫作業(yè)調度方案求解算法

根據(jù)建立的出庫調度關系模型和出庫調度計劃數(shù)學模型，艦載機出庫優(yōu)化算法設計可分兩步進行優(yōu)化。

步驟1：利用相關決策知識理論實現(xiàn)艦載機數(shù)量分配功能。即已知調運需求信息Q，機庫每個部分的機型、數(shù)量及其之間的邏輯關系等信息，求艦載機機型及出庫數(shù)量在機庫I和機庫II的優(yōu)化分配方案。

步驟2：采用遺傳算法等智能算法對調運方案進行求解。

①實現(xiàn)艦載機選擇功能。確定機庫中出庫艦載機可行解空間，生成初始種群，每個基因對應一架艦載機，每條染色體即是一個艦載機出庫方案集合V。

②實現(xiàn)排序決策功能。根據(jù)優(yōu)先級規(guī)則對V中艦載機出庫作業(yè)進行排序，從而得到最優(yōu)出庫方案的艦載機調度序列X。

③實現(xiàn)艦載機倒機決策功能。根據(jù)艦載機之間的邏輯關系及其機庫基本作業(yè)規(guī)則，基于Petri網(wǎng)的可達性，找出需要倒機的艦載機并根據(jù)一定規(guī)則進行整理得到艦載機出庫集合Z。通過遺傳算法對解空間進行遍歷，目標函數(shù)值為調運所用時間最短，從而得到最優(yōu)出庫組合方案Z。

具體求解算法流程如下頁圖4所示。

4 應用案例

設定艦載機在機庫中的一種布列方式，對艦載機出庫方案的優(yōu)化算法進行驗證。

4.1 問題描述

該機庫配備兩部升降機，一道防火分隔門將機庫分為兩部分，記作機庫I部，機庫II部，機庫I部、機庫II部分別與升降機1，升降機2對應，即機庫I部的艦載機通過升降機1調運至甲板，機庫II部的艦載機通過升降機II調運至甲板。機庫內擁有艦載機的機型為4種，共計26架。試驗過程中設計4張不同的艦載機需求批量表Q1～Q4，每張批量表中包含4種機型的需求艦載機，艦載機數(shù)量分別為6、8、11、12。批量表中艦載機需求情況和各機型艦載機的在庫數(shù)量如表1所示。

4.2 遺傳算法參數(shù)設定

算法中設最大遺傳代數(shù)Gen max=200，種群空間Pop max=50，變異率Pm=0.02，交叉率Pc=0.06。算法執(zhí)行過程中，往往會在沒有達到最大遺傳代數(shù)的情況下得到最優(yōu)解。為降低算法的執(zhí)行時間，GA算法中設置一個閾值flag，flag表示每代種群個體的平均適應度值與當前最優(yōu)適應度值的比值，如式（1）所示。

設定flag=0.9，如果flag值超過0.9，就可以認為截止到當前己經(jīng)取得問題的全局最優(yōu)解。

4.3 試驗結果及分析

在算法運行過程中，優(yōu)化算法表現(xiàn)出較好的收斂性，需求Q1～Q4的求解時間分別為12 s、13 s、15 s和16 s，滿足實時性要求。圖5為需求Q1的求解結果。

5 結束語

本文主要研究艦載機出庫調度方案建模方法問題。首先基于Petri網(wǎng)技術理論，建立了艦載機出庫邏輯關系Petri網(wǎng)模型。利用Petri網(wǎng)模型，可以求解艦載機的可達性問題和調運過程中發(fā)生的沖突、等待等問題，作為調度方案優(yōu)化過程中排序和倒機決策的依據(jù)。然后通過對機庫內艦載機出庫作業(yè)決策過程進行分析，將艦載機出庫調度過程抽象為四階段決策過程，并建立了相應的數(shù)學模型。從保障調度工作效率的角度出發(fā)，以出庫作業(yè)時間最短為優(yōu)化目標，建立了出庫作業(yè)調度作業(yè)目標函數(shù)。最后給出了艦載機出庫優(yōu)化算法流程，并進行求解驗證。

［1］漁翁.美國航母航空部門的組織管理［J］.艦船知識，2006，17（9）：36-37.

［2］Jerrrey S.Feasibility Study of Global-positioning-System-Based Aircraft-Carrier Flight-Deck Persistent Monitoring System［C］//Journal of Aircraft，2010：5-6.

［3］楊炳恒，畢玉泉，徐偉勤.一種艦載機調運作業(yè)流程優(yōu)化模型［J］.艦船科學技術，2011,24（1）：118-121.

［4］馮強，曾聲奎，康銳.基于MAS的艦載機動態(tài)調度模型［J］.航空學報，2009,21（11）：2109-2125.

［5］劉欽輝，邱長華，王能健.考慮空間約束的艦載機作業(yè)調度模型研究［J］.哈爾濱工程大學學報，2012,23（11）：1435-1439.

［6］劉亞杰，翁輝，陳曉山.一種基于“矢柵結合”的機庫艦載機調運作業(yè)環(huán)境建模方法［J］.裝甲兵工程學院學報，2014，28（2）：75-78.

［7］劉亞杰，李忠猛，陳曉山.考慮空間約束的機庫艦載機調運路徑規(guī)劃方法［J］.海軍工程大學學報，2014，26（3）：100-103.

［8］謝楠.基于Petri網(wǎng)的可重組制造系統(tǒng)建模、調度及控制方法研究［D］.上海：同濟大學，2006.

［9］袁崇義.Petri網(wǎng)原理與應用［M］.北京：電子工業(yè)出版社，2005.

Method of Carrier-borne Aircrafts Exporting Scheduling Modeling Based on Petri Net

LIU Ya-jie，LI Zhong-meng，XIE Jun
（Naval University of Engineering，Wuhan 430033，China）

The carrier-borne aircrafts exporting scheduling is important for guaranteeing the battle performances.The method of carrier-borne aircrafts exporting scheduling modeling is analyzed.Based on the theory of Petri net，the Petri net model of exporting scheduling logical relations is established. Based on the decision process of exporting scheduling,the four-process-decision mathematical models are established.The flow optimization algorithm is given and validated.

carrier-borne aircrafts，operation scheduling，decision models

TP208

A

1002-0640（2015）09-0152-05

2014-08-09

2014-09-17

軍隊科研計劃項目

劉亞杰（1975- ），女，遼寧朝陽人，博士，講師。研究方向：復雜系統(tǒng)建模與仿真。