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