已經(jīng)介紹了空運航班串的兩種基本生成方法,，即時空網(wǎng)絡(luò)法和空運航班連接 網(wǎng)絡(luò)法,。對手工編制空運航班串都很有效，只要空運航班量不是太大,，都可以獲得必需的航班串,。在手工編制時,，一般并不找出所有可行的空運航班串，而是根據(jù)經(jīng)驗找到能覆蓋 所有空運航班的若干空運航班串即可,。這樣得到的空運航班串一般不能保證最優(yōu),，如果想獲得 最優(yōu)的空運航班串，應(yīng)當(dāng)給出所有可行的空運航班串,，然后建立數(shù)學(xué)模型并設(shè)計有效算法,， 通過優(yōu)化計算，從中找出最優(yōu)的一組,。 空運航班環(huán)是由一條或多條空運航班串連接而成的,，所以生成空運航班環(huán)首先要生成空運航班 串。對于大規(guī)模空運航班問題,，要得到所有的空運航班環(huán),，必須采用計算機(jī)輔助生成系統(tǒng)。 下面討論計算機(jī)輔助生成空運航班環(huán)的方法,。 

計算機(jī)輔助生成空運航班環(huán)需給定以下數(shù)據(jù)：

    ①空運航班計劃,；

    ②基地機(jī)場；

    ③過夜機(jī)場和過夜飛機(jī),。 

在生成空運航班串的同時必須考慮如下限制條件,。

     (1)適航規(guī)定：最小銜接時間、執(zhí)勤小時和飛行小時限制,。 

    （2)公司規(guī)定：一個值勤期的最大,、最小空運航班數(shù)等。

 為便于算法設(shè)計,，采用空運航班連接網(wǎng)絡(luò),，則空運航班環(huán)按以下步驟生成。 

    （1)對每種機(jī)型執(zhí)行的空運航班子集,，按空運航班出發(fā)機(jī)場,，再分成出發(fā)空運航班子集。 

    （2)構(gòu)造各機(jī)場出發(fā)空運航班樹,，即以各出發(fā)機(jī)場為根節(jié)點,，用銜接邊連接從它出 發(fā)的各空運航班節(jié)點，分裂各空運航班節(jié)點成出發(fā)和到達(dá)兩個機(jī)場節(jié)點,，之間用空運航班邊連 接,，形成空運航班節(jié)線。

     (3)從基地機(jī)場出發(fā)空運航班樹開始,，將各空運航班節(jié)線的到達(dá)機(jī)場節(jié)點與從該機(jī)場 出發(fā)的空運航班樹的根節(jié)點合并,，刪除銜接時間短于最小銜接時間的銜接邊和空運航班 

    （4)重復(fù)上述步驟直到各空運航班節(jié)線無可銜接的空運航班，得到以各基地機(jī)場為根 節(jié)點（網(wǎng)絡(luò)的源或發(fā)點）的空運航班連接樹,，它的葉節(jié)點是基地機(jī)場或過夜機(jī)場,、 

    （5)在空運航班連接樹中加上終止機(jī)場節(jié)點(基地機(jī)場，是網(wǎng)絡(luò)的匯或收點）,，用終 止邊將葉節(jié)點和所有到達(dá)機(jī)場是基地/過夜機(jī)場的空運航班節(jié)線連接到終止機(jī)場節(jié)點,， 然后在每條空運航班節(jié)線的空運航班邊上標(biāo)注飛行時間，在每條銜接邊上標(biāo)注銜接(過站） 時間,，這樣就形成了空運航班連接網(wǎng)絡(luò),。

     （6）從基地機(jī)場節(jié)點開始，采用寬度優(yōu)先或深度優(yōu)先搜索或混合搜索的方法,。 搜索空運航班連接網(wǎng)絡(luò)的每一條路經(jīng),，每條路經(jīng)都是一個空運航班串,。在搜索過程中不斷 緊加路徑上的飛行時間和值勤時間（飛行時間再加上過站時間是值勤時回,，翻器 到某節(jié)點處,，飛行時間或執(zhí)勤時間已違反了適航規(guī)定，就放棄該路徑,。最后得到的 是符合適航規(guī)定的可行空運航班串,，其中終止在基地機(jī)場的就是由一條空運航班串構(gòu)成的 空運航班環(huán)。

     （7）對于最后終止在過夜機(jī)場的空運航班串,，再把第二天從該過夜機(jī)場出發(fā)的航 班串與其連接成多天的空運航班串,。如果這樣新連接的空運航班串最后回到了基地，則得 到一條多天的空運航班環(huán),。 試用上述步驟為例53給出的空運航班計劃構(gòu)造機(jī)組空運航班環(huán)(任務(wù)配對),。 解按照本節(jié)所給構(gòu)造步驟。 

      步驟1該空運航班計劃共有9個空運航班,，服務(wù)四個城市A,、B、C,、D,，將9個空運航班按 照這四個機(jī)場的出發(fā)空運航班進(jìn)行分割，即 步驟2構(gòu)造基地機(jī)場A的出發(fā)空運航班樹如,，構(gòu)造其他機(jī)場的出發(fā) 空運航班,。 步驟3對于空運航班0、1和6,，分別連接機(jī)場B,、D、B的出發(fā)空運航班,，并判斷出空運航班 3和5不能銜接空運航班6,，刪除這兩個空運航班節(jié)線，然后再分裂相應(yīng)的空運航班節(jié)點 步驟4這就是表5-3的空運航班計劃的空運航班連 接樹,，為方便辨認(rèn),，每條空運航班邊上給出了空運航班號。 步驟5增加基地機(jī)場終止節(jié)點,，連接生成空運航班連接網(wǎng)絡(luò),。對空運航班連接網(wǎng)絡(luò)的每條空運航班邊給出飛行時間，每條銜接邊給出過站時間,。 步驟6進(jìn)行深度搜索或?qū)挾人阉?，得到該樹的每一條路經(jīng)，結(jié)果與的相同,，共14條,，它們都是可能的空運航班串,。該例中每個空運航班串的終止機(jī)場都是基 地機(jī)場，因此它們又都是空運航班環(huán),。搜索過程計算累計飛行時間和過站時間,。FT和ET分別表示飛行時間和執(zhí)勤時間，發(fā)現(xiàn)所有空運航班串 《環(huán)）都符合類于懂勤期時間的適航規(guī)定,，如果公司對值勤期的空運航班數(shù)無規(guī)定,，則 14個空運航班環(huán)都是可行的。 需要注意的是,，各空運航班環(huán)質(zhì)量可能不同,。例如，表5-4中的S,、S與S,、S. 相比，飛行時間短了,，但執(zhí)勤時間更長了,。因為飛行員的生產(chǎn)力體現(xiàn)在空中飛行，而不是待在地面,。飛行時間短而執(zhí)勤時間長就意味著空運航班串的質(zhì)量低,。

  可以用飛行時間與執(zhí)勤時間的比刀來表示空運航班環(huán)的質(zhì)量，稱為機(jī)組工作效率,，比值 越大越好,。本例的空運航班環(huán)質(zhì)量已列在最后一行?？梢园凑盏稄拇蟮叫〗o 航語環(huán)排序,，當(dāng)7相同時，以飛行時間從大到小排序,，那么排在前面的是質(zhì)量需的 空運航班環(huán),。