三下標(biāo)模型的規(guī)模比四下標(biāo)模型小,，因此這里以三下標(biāo)模型的求解為例,，討論精確算法,。四下標(biāo)模型的求解算法可以仿照這里的算法進(jìn)行設(shè)計(jì),。由于各 0-D對的運(yùn)輸路線最多有2次中轉(zhuǎn)3個(gè)航節(jié)組成，在選定了樞組機(jī)場后,，可以首 先構(gòu)建一個(gè)四層網(wǎng)絡(luò)G’,，如圖3-18所示,，該網(wǎng)絡(luò)很適合計(jì)算O-D對（i,，j)之間的 最短路,。 四層網(wǎng)絡(luò)（/按下述方式構(gòu)造：對于ViEN，在第一層用i表示,，在第二層用i 表示,，在第三層用”表示，在第四層用”表示,。第一,、第四層包含了網(wǎng)絡(luò)G=(N， A)所有n個(gè)城市的節(jié)點(diǎn),，第二,、第三層僅包含候選樞紐機(jī)場集合M的節(jié)點(diǎn)。各層 同層內(nèi)的點(diǎn)不連接,，只有相鄰兩層之間的點(diǎn)才用邊連接,。

      具體的連接方式為，層與層之間對應(yīng)相同的城市直接連接,，邊長（航線運(yùn)輸成本)為0,；第一層的非樞紐城市和第二層的所有樞紐城市都連接，為匯運(yùn)邊,，邊長為XC,，；第一 層的樞紐城市只與第二層相同的樞紐城市連接,，邊長為0,；第二層的樞紐城市和編 三層的樞紐城市分別連接，為轉(zhuǎn)運(yùn)邊,，邊長為aCm,；第三層與第四層的連接方式與 第一層及第二層的連接方式類似，只是邊長變?yōu)镃m,。給出了G在INl三 7時(shí)的連接示意圖,，其中城市2、6,、7已選為樞組,，并給出了以城市1為起始城市的 連接方式，其他城市的連接情況類似,。這樣就得到了一個(gè)四層網(wǎng)絡(luò),，其中O-D對 （i,j)的運(yùn)輸路線將是>k’一m”一”，令C一表示i到j(luò)”的最短路長度,，則對應(yīng)的 最短路徑就是最優(yōu)運(yùn)輸路徑,，所有O-D對的最優(yōu)運(yùn)輸路徑構(gòu)成了該組樞紐機(jī)場情 況下的航線網(wǎng)絡(luò)。第一層的i和第四層的”表示同一個(gè)機(jī)場,，因此不允許組成O-D 對(i,，i")。 當(dāng)四層網(wǎng)絡(luò)G'中p個(gè)樞紐選定時(shí),，可用Floyd-Warshall最短路算法求解O-D 流間的最短路,，具體步驟如下。 

     步驟1計(jì)算C·=mig{aCu+aC,，},，VkEH，jEN,，Cw=0,，VkEH，式中只包含分運(yùn),，沒有匯運(yùn)的路徑,，其中H是已選為樞紐的力個(gè)機(jī)場組成的集合,。 

     步驟2計(jì)算C·=2ip（xCa+Cx·}，Vi,，jEN,，其中j”、”,、”均對應(yīng)N中的 j,。

     這個(gè)由網(wǎng)絡(luò)G求得的C，即網(wǎng)絡(luò)G中從i到j(luò)的最短路,。 利用四層網(wǎng)絡(luò)最短路算法,，可以找到任意給定的樞紐機(jī)場集合HCM情況下 的最優(yōu)航線網(wǎng)絡(luò)。下面給出求解無容量限制的樞組航線網(wǎng)絡(luò)優(yōu)化模型的計(jì)算 步驟,。 步驟1選取合適的城市屬性指標(biāo)體系和指標(biāo)權(quán)重,，通過多屬性決策方法對 各城市進(jìn)行排序。 步驟2根據(jù)對各城市的排序結(jié)果,，選出候選樞組城市集M,。 步驟3從城市集M中任選力個(gè)作為樞紐集H，利用上述Floyd-Warshall最 短路算法求解相應(yīng)的最短路問題,，如此反復(fù)計(jì)算,，則共得到Ci1個(gè)解，其中目標(biāo) 函數(shù)值最小的解即為所求（當(dāng)|Ml很小時(shí),，也可借助優(yōu)化軟件直接求解）,。 步驟4對最優(yōu)解進(jìn)行必要的評估，給出樞紐航線網(wǎng)絡(luò)的設(shè)計(jì)方案,。 以上給出的算法是枚舉法,。由于樞紐機(jī)場候選集較小(通常10個(gè)左右)，其可 能的組合也是有限的（三樞紐時(shí)不超過120個(gè)),，采用Floyd-Warshall最短路算法 對每個(gè)樞紐組合情況進(jìn)行網(wǎng)絡(luò)計(jì)算也是很有效的,。因此，枚舉法能夠在較短時(shí)間 內(nèi)求得最優(yōu)解,，這個(gè)最優(yōu)解是精確的全局最優(yōu)解,。