已經(jīng)介紹了空運航班串的兩種基本生成方法，即時(shí)空網(wǎng)絡(luò )法和空運航班連接 網(wǎng)絡(luò )法。對手工編制空運航班串都很有效，只要空運航班量不是太大，都可以獲得必需的航班串。在手工編制時(shí)，一般并不找出所有可行的空運航班串，而是根據經(jīng)驗找到能覆蓋 所有空運航班的若干空運航班串即可。這樣得到的空運航班串一般不能保證最優(yōu)，如果想獲得 最優(yōu)的空運航班串，應當給出所有可行的空運航班串，然后建立數學(xué)模型并設計有效算法， 通過(guò)優(yōu)化計算，從中找出最優(yōu)的一組。 空運航班環(huán)是由一條或多條空運航班串連接而成的，所以生成空運航班環(huán)首先要生成空運航班 串。對于大規模空運航班問(wèn)題，要得到所有的空運航班環(huán)，必須采用計算機輔助生成系統。 下面討論計算機輔助生成空運航班環(huán)的方法。
計算機輔助生成空運航班環(huán)需給定以下數據：
①空運航班計劃；
②基地機場(chǎng)；
③過(guò)夜機場(chǎng)和過(guò)夜飛機。
在生成空運航班串的同時(shí)必須考慮如下限制條件。
(1)適航規定：最小銜接時(shí)間、執勤小時(shí)和飛行小時(shí)限制。
（2)公司規定：一個(gè)值勤期的最大、最小空運航班數等。
為便于算法設計，采用空運航班連接網(wǎng)絡(luò )，則空運航班環(huán)按以下步驟生成。
（1)對每種機型執行的空運航班子集，按空運航班出發(fā)機場(chǎng)，再分成出發(fā)空運航班子集。
（2)構造各機場(chǎng)出發(fā)空運航班樹(shù)，即以各出發(fā)機場(chǎng)為根節點(diǎn)，用銜接邊連接從它出 發(fā)的各空運航班節點(diǎn)，分裂各空運航班節點(diǎn)成出發(fā)和到達兩個(gè)機場(chǎng)節點(diǎn)，之間用空運航班邊連 接，形成空運航班節線(xiàn)。
(3)從基地機場(chǎng)出發(fā)空運航班樹(shù)開(kāi)始，將各空運航班節線(xiàn)的到達機場(chǎng)節點(diǎn)與從該機場(chǎng) 出發(fā)的空運航班樹(shù)的根節點(diǎn)合并，刪除銜接時(shí)間短于最小銜接時(shí)間的銜接邊和空運航班
（4)重復上述步驟直到各空運航班節線(xiàn)無(wú)可銜接的空運航班，得到以各基地機場(chǎng)為根 節點(diǎn)（網(wǎng)絡(luò )的源或發(fā)點(diǎn)）的空運航班連接樹(shù)，它的葉節點(diǎn)是基地機場(chǎng)或過(guò)夜機場(chǎng)、
（5)在空運航班連接樹(shù)中加上終止機場(chǎng)節點(diǎn)(基地機場(chǎng)，是網(wǎng)絡(luò )的匯或收點(diǎn)），用終 止邊將葉節點(diǎn)和所有到達機場(chǎng)是基地/過(guò)夜機場(chǎng)的空運航班節線(xiàn)連接到終止機場(chǎng)節點(diǎn)， 然后在每條空運航班節線(xiàn)的空運航班邊上標注飛行時(shí)間，在每條銜接邊上標注銜接(過(guò)站） 時(shí)間，這樣就形成了空運航班連接網(wǎng)絡(luò )。
（6）從基地機場(chǎng)節點(diǎn)開(kāi)始，采用寬度優(yōu)先或深度優(yōu)先搜索或混合搜索的方法。 搜索空運航班連接網(wǎng)絡(luò )的每一條路經(jīng)，每條路經(jīng)都是一個(gè)空運航班串。在搜索過(guò)程中不斷 緊加路徑上的飛行時(shí)間和值勤時(shí)間（飛行時(shí)間再加上過(guò)站時(shí)間是值勤時(shí)回，翻器 到某節點(diǎn)處，飛行時(shí)間或執勤時(shí)間已違反了適航規定，就放棄該路徑。最后得到的 是符合適航規定的可行空運航班串，其中終止在基地機場(chǎng)的就是由一條空運航班串構成的 空運航班環(huán)。
（7）對于最后終止在過(guò)夜機場(chǎng)的空運航班串，再把第二天從該過(guò)夜機場(chǎng)出發(fā)的航 班串與其連接成多天的空運航班串。如果這樣新連接的空運航班串最后回到了基地，則得 到一條多天的空運航班環(huán)。 試用上述步驟為例53給出的空運航班計劃構造機組空運航班環(huán)(任務(wù)配對)。 解按照本節所給構造步驟。
步驟1該空運航班計劃共有9個(gè)空運航班，服務(wù)四個(gè)城市A、B、C、D，將9個(gè)空運航班按 照這四個(gè)機場(chǎng)的出發(fā)空運航班進(jìn)行分割，即 步驟2構造基地機場(chǎng)A的出發(fā)空運航班樹(shù)如，構造其他機場(chǎng)的出發(fā) 空運航班。 步驟3對于空運航班0、1和6，分別連接機場(chǎng)B、D、B的出發(fā)空運航班，并判斷出空運航班 3和5不能銜接空運航班6，刪除這兩個(gè)空運航班節線(xiàn)，然后再分裂相應的空運航班節點(diǎn) 步驟4這就是表5-3的空運航班計劃的空運航班連 接樹(shù)，為方便辨認，每條空運航班邊上給出了空運航班號。 步驟5增加基地機場(chǎng)終止節點(diǎn)，連接生成空運航班連接網(wǎng)絡(luò )。對空運航班連接網(wǎng)絡(luò )的每條空運航班邊給出飛行時(shí)間，每條銜接邊給出過(guò)站時(shí)間。 步驟6進(jìn)行深度搜索或寬度搜索，得到該樹(shù)的每一條路經(jīng)，結果與的相同，共14條，它們都是可能的空運航班串。該例中每個(gè)空運航班串的終止機場(chǎng)都是基 地機場(chǎng)，因此它們又都是空運航班環(huán)。搜索過(guò)程計算累計飛行時(shí)間和過(guò)站時(shí)間。FT和ET分別表示飛行時(shí)間和執勤時(shí)間，發(fā)現所有空運航班串 《環(huán)）都符合類(lèi)于懂勤期時(shí)間的適航規定，如果公司對值勤期的空運航班數無(wú)規定，則 14個(gè)空運航班環(huán)都是可行的。 需要注意的是，各空運航班環(huán)質(zhì)量可能不同。例如，表5-4中的S、S與S、S. 相比，飛行時(shí)間短了，但執勤時(shí)間更長(cháng)了。因為飛行員的生產(chǎn)力體現在空中飛行，而不是待在地面。飛行時(shí)間短而執勤時(shí)間長(cháng)就意味著(zhù)空運航班串的質(zhì)量低。
可以用飛行時(shí)間與執勤時(shí)間的比刀來(lái)表示空運航班環(huán)的質(zhì)量，稱(chēng)為機組工作效率，比值 越大越好。本例的空運航班環(huán)質(zhì)量已列在最后一行。可以按照刀從大到小給 航語(yǔ)環(huán)排序，當7相同時(shí)，以飛行時(shí)間從大到小排序，那么排在前面的是質(zhì)量需的 空運航班環(huán)。
