基于需求不確定性的分層網絡設計研究

毛銘浩，邵荃*，于文斐

(1.南京航空航天大學民航學院，南京 211106；2.中國民航科學技術研究院，北京 100028)

隨著民航業的發展，航空公司均構建起了自身的航空運輸網絡。而如何使得航空公司的運輸網絡滿足其自身需求例如降低運輸成本、提高運輸效率，都需要對航空運輸網絡進行深入研究。隨著航空運輸網絡研究的不斷發展，也需要將真實世界的不確定性特點納入研究范疇。

關于分層運輸網絡設計的研究，Yaman[1]提出了基于單分配模型的分層運輸網絡，樞紐與非樞紐之上，增加了一級中心樞紐，并考慮到服務質量，將交付時間限制納入分層樞紐位置問題中，發現當施加時間限制時，網絡總成本略有增加，中心樞紐和樞紐的數量較小時，交付時間限制的影響更強。Lin[2]研究了面向雙業務的層次化輪輻網絡集成設計問題，為每項業務整合了與另一業務互斥的二級航線網絡，從而在滿足服務時間和運營限制的情況下，將總運營成本降至最低。并設計了基于鏈接的隱式枚舉算法，與傳統的專用二級路由網絡相比，該集成在每項的業務上大大降低了成本。Dukkanci等[3]提出了一個多層次的多模式樞紐網絡結構，并在此網絡基礎上定義了一個具有服務時間限制的樞紐覆蓋問題。分層網絡由三層組成，其中一層是環狀星形(ring-star-star, RSS)網絡。每一層可能有不同類型的車輛。還開發了一種基于次梯度法的啟發式求解算法，以在更合理的時間內求解問題。Khodemani-Yazdi等[4]提出了一個以樞紐設施為服務中心的雙目標層次樞紐定位問題。樞紐設施分為中心設施和本地設施。設施的排隊框架分別被認為是M/M/c和M/M/1。此外，關于移動時間和實體數的概率分布被假定為指數分布和泊松分布。采用一種新的博弈論變量鄰域模糊雜草優化算法(game theory variable neighborhood fuzzy invasive weed optimization, GVIWO)對所建立的數學模型進行求解，算法效果優于遺傳算法和模擬退火。Shang等[5]針對貨物配送系統構建了層次化的多式聯運輪輻配送網絡，該網絡涉及公路和航空兩種運輸方式，地面和機場兩種樞紐類型，以及相應的3個層次，建立了一種基于可靠性的模糊規劃模型，該模型描述了貨物配送系統運行時間和處理時間的不確定性，并提出兩階段啟發式算法求解。Esmizadeh 等[6]建立了多目標混合整數線性規劃來建模具有互補操作的層次式樞紐網絡上的冷鏈運輸，中心樞紐在網絡的第一級相互連接，并與較低級別樞紐的星形網絡連接，擾動被建模為隨機需求和多層次的時間窗，并提出了一種適合于大型網絡競爭的遺傳算法進行求解。Ghaffarinasab等[7]提出了p-hub 中心和p-hub最大覆蓋問題在分層情況下的混合整數線性規劃(mixed integer linear programming, MILP)模型，其中每個始末節點(origin/destination, O/D)對所對應的流量被劃分為不同的層，每個層都有特定的服務水平需求，并開發了相應的Benders分解算法來求解大型實例。

關于中樞輻射網絡的不確定性研究，2012年Alumur等[8]基于網絡規劃的長期性，以及模型輸入數據的不準確性，將樞紐開設成本和O/D對流量的不確定性引入中樞輻射網絡設計，分別針對單分配和多分配模型進行改進，分析了孤立的和組合的不同不確定性因素所導致的成本和網絡結構的變化。Azizi等[9]提出了一個在隨機需求和擁塞條件下設計輪軸輻射網絡的模型，使固定成本、運輸成本和擁堵成本之和最小化，樞紐被建模為空間分布的M/G/1隊列，并且使用樞紐設施的預期隊列長度來捕獲擁塞，結果表明，如果在設計階段就考慮到樞紐設施的擁塞，則可以通過總成本的小幅增加而大幅減少擁塞。Correia等[10]提出了一個多周期隨機容量下的多分配樞紐選址問題的建模框架，將規劃期劃分為多個時間段，假設需求的不確定性，決策涉及樞紐的位置、其初始容量、現有樞紐的容量擴展以及出發地和目的地對之間的運輸，目標是使總預期成本最小化，不確定性被有限的場景集和估計的概率表示。Hu等[11]提出了需求不確定條件下考慮樞紐容量均衡利用的單分配容量樞紐選址問題的隨機模型，假設需求是獨立的隨機變量，具有已知的正態概率分布，建立了具有聯合機會約束的隨機規劃模型，并將其轉化為二階混合整數規劃模型，結果表明：只需小幅提高傳統的運行成本，就可以大大降低樞紐容量的整體不平衡利用率。Rahmati等[12]針對需求不確定、穩定性水平受不確定性預算控制的無承載樞紐選址問題，提出了一種兩階段魯棒優化方法，第一階段確定樞紐設施的選址，第二階段確定樞紐設施的分配，采用加速Benders分解算法求解該問題，計算實驗表明，所提方法在迭代次數和計算時間方面都有較好的表現。Sener等[13]研究了松弛確定性運輸成本和需求假設的多分配樞紐覆蓋問題，使用L-Shaped算法，根據仿真數據生成并求解了幾個測試實例，結果表明：與期望值法的期望相比，將輪轂覆蓋問題建模為隨機優化模型的效率提高了13.05%。

目前分層網絡研究主要集中于地對分層運輸網絡理論建模，以及在基礎模型上更多地納入現實運輸網絡的特點。不確定性研究主要針對需求(O/D流量)、運輸成本、樞紐開設成本等。然而，在以往研究中，考慮不確定性時總是在經典的單分配和多分配模型上進行改進，而缺少對新的航空運輸網絡類型進行不確定性分析。

為此，結合現有分層航空運輸網絡研究和不確定性理論，以文獻[1]的確定型分層運輸網絡模型為主干，使用文獻[8]將需求不確定性引入單分配和多分配中樞輻射網絡模型時的思想，設置需求場景集合包含多種可能的需求場景，優化需求場景集合下網絡運輸成本的數學期望最小。以此為基礎提出基于需求不確定性的分層運輸網絡設計模型，同時給出網絡中O/D路由的求解方法。然后以某年中國的實際航空運輸數據為例，針對需求確定型分層運輸網絡、期望需求表征不確定性的分層運輸網絡和不確定型分層運輸網絡，對比它們在4種需求情景下的運輸成本表現情況，計算分析所提出的分層運輸網絡模型成本在需求不確定影響下的成本魯棒性、最大運輸距離和樞紐擁堵水平方面的表現。

1 基于需求不確定性的分層網絡設計模型

1.1 問題描述

分層運輸網絡設計屬于網絡樞紐選址問題，在分層運輸網絡中，節點分為出發地/目的地(O/D)節點，樞紐節點，中央樞紐節點。邊包括非樞紐與樞紐，樞紐與中央樞紐，中央樞紐之間的連接。分層運輸網絡設計問題即是給定n個離散的節點位置，兩兩節點對之間形成O/D對，O/D對之間有運輸需求(流量)和單位流量運輸成本。從n個節點中選出h個樞紐，從h個樞紐中選出h0個中央樞紐，然后將h-h0個樞紐分配給h0個中央樞紐，將n-h個樞紐分配給h個樞紐，實現總網絡運輸成本最小。

但由于航線網絡規劃的長期性，以及模型輸入數據的不準確性，需要將需求(流量)的不確定性引入分層網絡設計，以提高分層運輸網絡對抗不確定性擾動的能力，表現為在多種可能的需求情況下，所得出運輸網絡的運輸成本與各需求場景最小運輸成本的平均差值最小。

1.2 模型建立

以文獻[1]的確定型分層網絡運輸模型為主干，使用文獻[8]改進單分配和多分配中樞輻射網絡模型的思路建立分層運輸網絡模型。

(1)模型假設如下。①中央樞紐間完全互聯，單一連接；②非樞紐之間，樞紐之間不直接交互；③非樞紐-樞紐，樞紐-中央樞紐，中央樞紐之間的運行成本有折扣因子；④運輸成本滿足三角不等式。

(2)集合。設I為網絡節點集合，H?I為可能的樞紐節點集合，C?H為可能的中央樞紐節點集合，S為不確定性需求(流量)場景集合。

基于需求不確定性的分層運輸網絡數學模型如下。

(1)

(2)

zijl≤zjjl, ?i∈I；j∈H{i}；l∈C

(3)

(4)

(5)

(6)

(7)

(8)

?i∈I,l∈C,s∈S

(9)

?i∈I,j∈H,l∈C{j},s∈S

(10)

zljl=0, ?j∈H,l∈C{j}

(11)

(12)

(13)

zijl∈{0,1}, ?i∈I,j∈H,l∈C

(14)

(1)目標函數。式(1)求場景集合S下，網絡總成本的數學期望，網絡總成本包括非樞紐-樞紐、樞紐-中心樞紐、中心樞紐之間的運輸成本。

(2)網絡結構約束。式(2)約束表示對于?i∈I，非樞紐節點只能分配給一個樞紐和一個中央樞紐。式(3)約束非樞紐節點的分配條件，i∈I分配給j∈H時，要求j為樞紐。式(4)約束樞紐的分配條件，j∈H分配給l∈C時，要求l為中央樞紐。式(5)表示中央樞紐至少被一個樞紐連接。式(6)表示樞紐至少被一個非樞紐連接。式(7)約束樞紐的數量為h。式(8)約束中央樞紐的數量為h0。

(4)變量特征約束。式(11)非必要，但可以減少計算時的變量數量、松弛問題。式(12)和式(13)是變量的非負約束，式(14)約束分配示性因子為0-1變量。

分配示性因子zijl只表征非樞紐-樞紐-中央樞紐的分配情況，分層運輸網絡模型的O/D路由求解方法為：已知分層運輸網絡的節點分配，設節點i的分配為(i,ji,li)，節點m的分配為(m,jm,lm)，括號內元素依次為非樞紐節點、樞紐、中央樞紐。①若ji=jm=j，必有li=lm=l，則O/D路由為i-j-m；②若ji≠jm，且li=lm=l，則O/D路由為i-ji-l-jm-m；③若ji≠jm，且li≠lm，則O/D路由為i-ji-lj-lm-jm-m。

2 實例計算及結果分析

2.1 計算數據及參數設置

使用文獻[14]中2012年中國15個主要城市的航空運輸數據進行計算，包括城市對的運輸需求(O/D流)，城市對的運輸成本。計算結果中城市的代表序號如表1所示。

表1 城市的代表序號

設置可能的樞紐節點集合、可能的中央樞紐節點集合與網絡節點集合相同，即I=H=C。設置常量αH=0.9，αC=0.8，h=5，h0=2。

對3種分層網絡設計方法進行計算比較：①方法一，需求確定，使用確定型分層網絡模型進行計算；②方法二，需求不確定，先計算場景集合需求的數學期望以表征不確定性，然后使用確定型分層網絡模型進行計算；③方法三，需求不確定，使用本文模型計算。

通過Lingo18.0求解3種網絡設計方法的非樞紐-樞紐-中央樞紐分配情況，以及4種需求場景下的最佳網絡運輸成本，然后將3種網絡設計方法的分配方式應用于4種需求場景。計算分析3種方法所得的分層運輸網絡在3個方面的特性。

(1)網絡運輸成本的魯棒性。文獻[8]將成本魯棒性定義為所采取方案得到的成本與可能情景下最優成本之間差值的平均值。因此，采用每種方法在4種需求場景下的可得成本與最優成本之間差值的平均值代表每種方法的魯棒性。

(2)最大運輸距離。當航空器速度一定、不考慮機場內轉運時間的情況下，航空運輸距離可代表航空運輸時間，航空運輸作為一種服務產品，航空運輸時間與服務質量相關。通過所提出的分層運輸網絡O/D路由求解方法，累加O/D流在分層運輸網絡中的各段運輸距離，計算O/D城市對之間最大運輸距離。

(3)擁堵水平。根據文獻[15]，樞紐的擁堵水平可表示為

f(u)=aub

(15)

式(15)中：u為樞紐的流量；a、b為正的常量，且b≥1，當a=b=1，通過樞紐的流量就表示樞紐的擁堵水平。

通過所提出的分層運輸網絡O/D路由求解方法，計算O/D路由，確定匯入各樞紐的流量，然后設置a=b=1，用式(15)計算各樞紐的擁堵水平然后求平均，得出分層運輸網絡的平均樞紐擁堵水平。

2.2 計算分析

首先，計算3種方法的分層網絡結構如表2所示。

表2 3種方法的分配結果

由表3可知，①中央樞紐的選擇方面：3種方法所得的樞紐分配方案都將中央樞紐選在15個城市中相對靠中心位置的長沙、南京、鄭州3個城市，這表明為便于協助周邊區域的樞紐完成轉運，中央樞

紐會分布于機場群中相對靠中心的位置；②樞紐的選擇方面：由于未考慮政策、民航產業發展情況、機場中轉能力等因素，實際的樞紐北京、上海、廣州由于地理區位過于靠北、靠東、靠南，因此只作為第二級的樞紐而未能成為中央樞紐，這表明第二級樞紐承擔非樞紐和中央樞紐的溝通，大多分布于機場群邊緣區域的中心；③非樞紐的連接方面：仍有很多非樞紐節點直接連接中央樞紐，這表明若樞紐-中央樞紐、中央樞紐之間運輸的折扣因子未能有效減少成本，則模型在分配非樞紐時，會使得非樞紐節點直接連接中央樞紐，通過減少轉運次數和運輸距離，從而降低運輸成本。

然后，使用確定型樞紐網絡模型計算4種場景的最小運輸成本。根據所提出的OD路由計算方法，得到方法一、方法二和方法三的城市OD對路由，然后計算應用方法一、方法二和方法三時4種場景的運輸成本，如表3所示。

由表3可知：①場景1的最小運輸成本與使用方法一時相同，其原因為方法一是使用原數據計算得到的確定型分層網絡結構方案，場景1的需求數據與原數據相同，計算結果相同；②場景2的最小運輸成本與使用方法三時相同，場景3的最小運輸成本與使用方法二時相同，其原因為雖然方法二和方法三都融入了不確定因素考量，但是算例中城市數量較少，能實現較小網絡運輸成本的分層網絡結構較為有限，不同方法產生的網絡結構形成重疊。若是選取被廣泛運用于航線網絡設計問題算例的包含美國25個城市的CAB數據庫，則一般能避免此情況的發生。

表3 4種場景在3種方法下的運輸成本

計算4種場景的最小運輸成本與3種方法下的運輸成本差值如表4和圖1所示。

結合表4和圖1可得，方法三與4種場景最小運輸成本的平均差值最小，方法二與4種場景最小運輸成本的平均差值最大。這表明在面對可能發生的多種需求情景時，直接采用確定型分層網絡運輸模型或是直接使用可能需求情景的數學期望來帶入計算并不能很好地處理需求不確定性對成本

圖1 運輸成本差值

表4 運輸成本差值

的影響。而本文提出的基于需求不確定性的分層網絡魯棒設計模型給出的方案在面對多種可能的需求情景下，與各場景最優運輸成本的平均差值最小，具有較好的成本魯棒性。

求解3種方法所得網絡結構的O/D路由，累加O/D對之間在分層運輸網絡中的各段運輸距離，計算3種方法所得的分層運輸網絡最大運輸距離如圖2所示。

在3種方法中，最大運輸距離都出現在烏魯木齊—沈陽的運輸路徑上。由圖2可知，所提出的模型方法三的最大運輸距離最長。因為目標函數是針對網絡總運行成本，而且約束條件也未兼顧到運輸距離/運輸時間。未來的研究可在本文模型的基礎上添加運輸距離約束，或者將該問題設置為運輸成本和運輸距離最小的多目標優化問題，從而降低運輸距離和運輸時間。

圖2 最大運輸距離

計算O/D路由，確定匯入各樞紐的流量，計算各樞紐的擁堵水平然后求平均值，3種方法所得的分層運輸網絡中平均樞紐擁堵水平如圖3所示。

圖3 平均樞紐擁堵水平

由圖3可知，方法三的平均樞紐流量除場景3外總是小于方法一和方法二，表示方法三有著最低的平均樞紐擁堵水平。雖然本文目標函數的含義為求多種需求(流量)場景下的網絡運行成本期望最小，并未專門針對平衡流量降低擁堵而進行的網絡結構優化配置，但是從結構上對比3種方法所得的分層運輸網絡樞紐和非樞紐的分布特征可以發現，本文模型所得的網絡結構中，各個樞紐、中央樞紐所連非樞紐節點的數量恰好相同，非樞紐節點在樞紐節點的末端分布較為平均，因此能夠得到較低的平均樞紐擁堵水平。

3 結論

結合現有分層航空運輸網絡模型研究和不確定性理論，以確定型分層網絡運輸模型為主干，建立需求集合包含多種可能的需求場景，將優化目標設置為需求場景集合下運輸成本期望最小。提出基于需求不確定性的分層網絡設計模型，同時給出網絡中O/D路由的求解方法。然后以某年中國城市的實際航空運輸數據為例，針對需求確定型分層運輸網絡、需求期望表征不確定性的分層運輸網絡和不確定型分層運輸網絡，對比它們在均勻分布產生的需求情景集合下的運輸成本表現情況，以衡量不同分層運輸網絡設計模型在需求不確定影響下的成本魯棒性表現。計算結果表明，所提出的基于需求不確定性的分層運輸網絡魯棒設計模型與各需求場景最小運輸成本的平均差值最小，表明在面對多種可能的需求情景下仍能表現出較小的網絡運輸成本，具有較好的成本魯棒性。研究工作可為航空運輸企業在面對需求不確定環境下的運輸網絡設計方面提供參考。