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

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

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

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

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