發布時間：2022-03-19所屬分類：計算機職稱論文瀏覽：1次
摘 要： 摘要: 研究聚焦區域公鐵軸輻式交通網絡優化問題，首先在剖析國內外關于軸輻式網絡優化研究成果的基礎上，給出區域多樞紐單分配混合公鐵軸輻式交通網絡拓撲結構，然后構建以包括運輸總費用和運輸總時間在內的運輸廣義費用最小的公鐵軸輻式交通網絡優化模型，設計了一種
摘要: 研究聚焦區域公鐵軸輻式交通網絡優化問題，首先在剖析國內外關于軸輻式網絡優化研究成果的基礎上，給出區域多樞紐單分配混合公鐵軸輻式交通網絡拓撲結構，然后構建以包括運輸總費用和運輸總時間在內的運輸廣義費用最小的公鐵軸輻式交通網絡優化模型，設計了一種基于全局搜索和局部搜索的改進遺傳算法求解。最后以中國的川藏鐵路為例，構建川藏鐵路沿線公鐵軸輻式交通網絡優化模型，并完成樞紐選址方案和節點連通方案的優化。結果表明，川藏鐵路建成運營后，選擇 4 個鐵路節點作為軸輻式網絡中的樞紐節點，并將其他非樞紐節點與其合理連接可以優化區域運輸總費用，采用改進遺傳算法求解得到的網絡總出行廣義運輸費用比標準遺傳算法和模擬退火算法得到的結果更優。
關鍵詞: 交通網絡規劃;公鐵軸輻式交通網絡;改進遺傳算法;川藏鐵路
1 引言
軸輻式綜合交通網絡[1]，就是將軸輻式網絡理論應用于綜合交通網絡中，構建起以交通樞紐樞紐節點和非樞紐節點相連相通的網絡形態主要研究核心是確定交通樞紐節點選取和節點之間的連通關系。研究軸輻式綜合交通網絡優化理論與方法對支撐交通運輸組織，尤其是區域交通網絡規劃具有重要意義。
軸輻式網絡的概念是在 1987 年 O’kelly[2]等人在研究美國城市群網絡關系中被首次提出，并給出了軸輻式網絡樞紐設施選址模型。國外的學者 Campbell[3], Ernst[4], Carello[5]等人在軸輻式網絡樞紐選址模型基礎上，設計算法研究以網絡運輸成本最小為目標的選址優化模型，Gelareh 等人[6]提出了多樞紐單分配無容量限制的樞紐設施選址模型，采用啟發式算法實現求解;Puerto 等人[7]提出多樞紐單分配有容量限制的樞紐設施選址模型，通過實際數據完成求解;Alder 等人[8]提出航空聯盟網絡中的軸輻式網絡收益優化策略，結合博弈論得到利益分配;Jeong 等人[9]構建以鐵路運輸為主導的軸輻式物流配送網絡，并以網絡總成本最小為目標建立整數線性規劃模型。我國關于軸輻式網絡研究起步相對較晚，研究在快遞網絡規劃、多式聯運轉運點選址、航空網絡樞紐選址及公共交通樞紐選址方面取得了許多成果，傅少川等[10]建立了無容量限制的多樞紐單分配混合整數規劃模型，并采用改進的禁忌搜索算法求解;楊立乾[11]根據軸輻式海上運輸航線結構和車輛路徑問題研究理論，構建了基于軸輻理論的集裝箱支線運輸多船型調度模型，并用粒子群算法求解;魏素豪等[12]構建以居民出行費用最小的公共交通軸輻式網絡優化模型，并確定了樞紐選址和節點連通方案;徐小峰等[13]以物流網絡總成本最小為目標，構建基于軸輻式配送網絡優化和車輛路徑優化一體的數學模型，設計基于三層編碼的遺傳算法求解。趙晉等[14]將基于全局優化的視角構建了允許直達的混合軸幅式快遞網絡規劃決策模型，并對其中的指派關系決策構建了遺傳算法。
目前國內外關于軸輻式網絡的應用普遍都集中在在物流領域，研究主要是多樞紐單分配型的軸輻式網絡優化，構建不同環境下的網絡優化模型和設計改進算法求解。但是在交通規劃領域應用較少，即使應用于交通領域也是屬于單一交通環境(如公共交通等)。軸輻式網絡理論應用于綜合交通網絡規劃的研究目前國內外的研究尚無，本文研究區域多樞紐單分配混合軸輻式綜合交通網絡優化方法具有這樣一些創新點：(1)在軸輻式網絡中考慮了多種交通方式(鐵路和公路)，并研究以鐵路為樞紐主導的公鐵軸輻式交通網絡構建及優化方法;(2)設計了一種改進遺傳算法，該算法是結合了全局搜索和基于爬山算法的局部搜索策略，對解決此類問題具有適用性和優越性;(3)選擇未來川藏鐵路建成后的川藏地區公鐵聯運網絡優化問題為案例對象，為未來川藏地區綜合交通網絡規劃提供理論支撐。
2 公鐵軸輻式交通網絡優化模型
2.1 問題描述
公鐵軸輻式交通網絡是由站點-路徑-樞紐組成的區域多樞紐單分配混合軸輻式交通網絡系統，通過客流量在樞紐間軸線運輸上的高度聚集，擴大軸線運輸規模經濟效益。公鐵軸輻式交通網絡基本結構如圖 1 所示，假設出行者選擇出行始發地為 3 S ，目的地為 9 S ，在該網絡中，出行者首先選擇公路運輸經過 3 1 S H 到達樞紐節點 1 H ，在樞紐節點 1 H 換乘鐵路運輸經過 1 3 H H 到達樞紐節點 3 H ，在樞紐節點 3 H 換乘公路運輸經過 3 9 H S 到達目的地 9 S ，即總體遵循 3 1 3 9 S H H S 出行路徑。
公鐵軸輻式交通網絡具有三種特性：①公鐵軸輻式交通網絡屬于多樞紐軸輻式網絡，在整個網絡中需要選取多個節點擴建為樞紐節點，每個樞紐均有特定的覆蓋區，覆蓋區中的客流量在樞紐節點實現集中換乘，只有同時擁有多個樞紐才能滿足整個區域的客流運輸需求; ②公鐵軸輻式交通網絡是單分配網絡，一個非樞紐交通節點最多只能與一個樞紐節點相連接，一個樞紐節點可以與多個非樞紐交通節點連接;③公鐵軸輻式交通網絡是局域混合軸輻式網絡，即非樞紐交通節點與樞紐節點連接的同時可以與其他非樞紐交通節點相連接，但是只允許覆蓋區內的非樞紐交通節點相連接，不存在不同覆蓋區的非樞紐交通節點相連接。
具體研究問題需要滿足以下假設條件：
(1)各節點的運輸能力均可以滿足覆蓋區域內的居民出行需求，即公鐵軸輻式交通網絡中的所有節點均不存在容量約束限制;(
2)樞紐點之間任意兩點都可以直達，若非樞紐節點之間不存在直達線路時，非樞紐節點之間的連接只能通過兩個樞紐節點實現跨區域運輸;
(3)網絡中的客流量在任意兩個節點間的移動路徑是唯一的，不能將客流量分成兩個部分;
(4)網絡中的任意兩個節點之間都存在可達路徑，且往返路徑都有且僅有相同的一條;
(5)假設樞紐節點之間均為鐵路運輸，非樞紐節點之間、非樞紐節點和樞紐節點之間均為公路運輸;
(6)網絡中出行廣義費用包括的出行交通費用是由在途客運費用、樞紐節點換乘費用和樞紐建設費用共同組成，出行時間費用包括在途運輸時間和樞紐換乘時間，按照地區人均單位時間價值成本折算為費用。
2.2 參數說明
本研究中使用的符號和模型參數如表 1 所示。
3 改進遺傳算法
研究針對區域公鐵軸輻式交通網絡優化模型提出一種改進的遺傳算法來求解近似最優解，但不同于遺傳算法模擬生物進化的簡單過程，改進遺傳算法在全局搜索過程中添加了局部搜索，并在其中增加一個選擇性突變，以此來解決復雜的問題，這個思路類似文化基因算法，模擬自然進化的過程。因此，研究中設計的改進遺傳算法也可以稱之為改進文化基因算法。該算法使用遺傳算法來探索全局空間，使用局部搜索方法來搜索局部區域，這在計算時間上比傳統的全局搜索算法更有優勢。
(1)染色體編碼
改進遺傳算法-染色體編碼的示意圖如圖 2 所示。
(2)適應性函數
區域公鐵軸輻式交通網絡求解的是最小化問題，其目標是使經濟目標和服務目標的加權和最小。
(3)遺傳算子
1)選擇本研究采用輪盤賭選擇算子對一次所得到的結果進行判斷選擇，在交配池中的染色體根據適應性函數各自確定評估概率。
2)交叉在公鐵軸輻式交通網絡中的改進遺傳算法交叉過程示意圖如圖 3 所示。
3)突變在公鐵軸輻式交通網絡中的改進遺傳算法突變過程示意圖如圖 4 所示。
(4)局部搜索過程局部搜索算法策略是為了在局部內搜索和全局中搜索中獲得平衡，局部搜索過程本研究的設計如下：
1)在單個進化周期內運用局部搜索方法;
2)在改進遺傳算法的交叉和變異之后進行局部搜索;
3)局部搜索方法可以用于每一批種群里面最優的群體;
4)改進遺傳算法中的局部搜索方法主要采用的是爬山算法。
爬山算法就是在特定的搜索區域內通過使用移位和交換兩種不同的搜索方法來確定更好的種群個體，局部搜索的爬山算法中的兩種方法實現過程如圖 5 所示。
4 案例分析
中國的川藏鐵路工程預計建設工期6-8年，工程建設大多地處高原高寒地區，交通基礎設施建設薄弱，根據中國鐵路工程院相關規劃建設資料，全線擬規劃建設鐵路車站 23 座，未來沿線共建設有 63 個公路節點[15]。考慮研究選取的網絡對象對真實網絡，但是相關數據因為涉及中國工程單位、企業單位等的隱私，不便公開，部分客流數據采用一定范圍內的合理假設。并且為了便于直觀研究，只選取 9 個鐵路節點和 12 個交通節點進行案例分析。研究將公路和鐵路節點的布局圖抽象為如下圖 6 所示，涉及到的節點具體名稱已標注用數字替代，其中需要說明的是始發地和目的地成都、拉薩以數字 1 和 9 代替，既可以表示公路節點又可以表示鐵路節點。
4.1 數據整理與參數設置
研究目標是優化川藏鐵路建成后地區以公路運輸和鐵路運輸為主的軸輻式交通網絡，研究所需的數據包括：川藏地區 21 個交通節點之間的客流、選擇兩種交通方式的交通費用和出行時間。關于客流相關數據，我們通過中鐵一局集團有限公司 2019 年的工程勘察和交通勘察，預測得到了川藏地區 2040 年的客流量。客流量數據整理如表 2 和表 3 所示，客流量的單位為萬人次，節點間的距離數據見表 4 所示，距離單位為公里，參數設置見表 5 所示。
4.2 計算結果分析
本研究設計的算法在 Matlab2012b 軟件中進行編程，研究中的所有數值分析實驗過程都是在Windows 10工作站上進行的，該工作站采用Intel(R)Core(TM) i7-7700HQ CPU @ 2.5Ghz and 16GB。將改進遺傳算法參數設置為：種群規模為 200，最大迭代次數為 1000，交叉和突變的概率分別為 0.5 和 0.3。通過改進遺傳算法確定最佳樞紐選址個數，選址位置和節點連接分配。由于鐵路樞紐節點在本案例中只選取了 9 個，因此樞紐選址數量最多為 9，考慮數量不多，因此研究將樞紐選址數量分別從 1 到 9 時網絡的運輸廣義總費用變化數據結果整理成表 6 所示(為了便于計算，運輸費用和運輸時間的單位已做取整處理)
相關期刊推薦：《工業工程與管理》(雙月刊)創刊于1996年，由上海交通大學主辦。應用性與學術性兼顧。介紹工業工程(IE)學科的基礎知識和國外最新研究成果，IE如何促進企業的發展和繁榮;IE在我國的研究狀況和對企業富有啟發性的研究成果，IE在各類企業中得到成功應用和推廣的實例：促進企業體制改革，為企業提高經濟效益、增強活力與競爭能力和建立現代企業制度獻計獻策：促進企業界、政府部門和學術界的交流利合作。
從表 6 的結果可以看出，當公鐵軸輻式交通網絡中的樞紐選址數量為 4 個時，網絡中的運輸廣義費用最小，為 7870529965 元。還可以看出，樞紐數量從 1 到 9 變化過程中，廣義運輸費用近似呈現“V”字型變化，總運輸時間折算費用對整個網絡總運輸廣義費用幾乎沒有影響。研究設計的改進遺傳算法不僅可以找到最優的樞紐選址數量，還可以找到使得網絡中運輸廣義費用最少的非樞紐節點與樞紐節點連接方案，表 7 和表 8 分別表示非樞紐節點與樞紐節點之間的連通結果和非樞紐節點之間的連通結果，兩表只給出節點間是相連通的結果。
4.3 算法比較
為了證明研究提出的改進遺傳算法的適用性和有效性，研究將該算法與模擬退火算法和標準遺傳算法進行對比。在模擬退火算法參數設置中，給出初始溫度為 1000，終止溫度為 0.05，降溫系數 0.8，步長為 5，規定當溫度低至 0.5 時即可停止迭代，最大迭代次數為 1000;在遺傳算法參數設置中，給出初始種群規模為 200，交叉概率為 0.8，變異概率為 0.2，最大迭代次數為 1000。根據表 9 可以觀察到，改進遺傳算法和標準遺傳算法的性能比模擬退火算法好得多(通過下降速率反映)，并且改進遺傳算法優于其他兩種算法，其迭代次數少，運行時間短，且得到的目標函數值結果最小。綜上所述，本研究設計的改進遺傳算法在求解公鐵軸輻式交通網絡優化模型上具有適用性和優越性。
5 結論
通過本文研究具體得到以下結論：
(1)在考慮網絡廣義運輸費用最小以及允許樞紐覆蓋區內部非樞紐節點直達條件下構建的多樞紐單分配混合公鐵軸輻式交通網絡優化模型對解決實際問題具有可行性;
(2)在公鐵軸輻式交通網絡中客運總費用主要與樞紐選址數量相關，與區域客流總出行時間帶來的費用影響較小，因此考慮科學合理確定樞紐數量有助于優化區域運輸總成本;
(3)研究中設計的改進遺傳算法是具有有效性和普適性的，通過全局搜索和局部搜索相結合可以更快速地得到最優化方案，該方法可以建議應用于其他類型的軸輻式網絡優化問題研究中;
(4)川藏鐵路建成運營后，川藏地區將形成的以鐵路主導的軸輻式綜合交通網絡，為了使軸輻式交通網絡中所有出行者出行總費用最小，應該選取雅安、理塘、昌都和貢嘎作為 4 個鐵路樞紐節點，其他鐵路節點和公路節點與其合理連接能夠優化區域運輸成本;
此外，需要說明的是本研究給出的川藏鐵路沿線公鐵軸輻式交通網絡總出行廣義費用最小為 7870529965 元是作者基于預測和部分假設數據得到的，在實際出行過程中出行者是具有有限理性出行行為特征的，會影響網絡總運輸廣義費用，因此該數據不具真實性，但是關于公鐵軸輻式交通網絡的優化方法在實際中具有指導意義。研究下一步計劃將從網絡中的費用、時間和客流需求不確定的角度優化區域公鐵軸輻式交通網絡。——論文作者：徐君翔 1，郭靜妮 1，張 錦1*,2,3
參考文獻
[1] Adler N. Hub-Spoke Network Choice Under Competition with an Application to Western Europe[J]. Transportation Science. 2005, 39(1): 58-72.
[2] E O M, A M E. Quadratic integer program for the location of interacting hub facilities[J]. European Journal of Operational Research. 1987, 32(3): 393-404.
[3] Campbell J F. Hub location and the p-hub median problem[J]. Location Science. 1997, 5(3): 203.
[4] Ernst A T, Krishnamoorthy M. Solution algorithms for the capacitated single allocation hub location problem[J]. Annals of Operations Research. 1999, 86: 141-159.
[5] Carello G, Croce F D, Ghirardi M, et al. Solving the Hub location problem in telecommunication network design: A local search approach[J]. Networks. 2004, 44(2): 94-105.
[6] Gelareh S, Neamatian M R, Nickel S. Multi-period hub location problems in transportation[J]. Transportation Research Part E. 2015, 75: 67-94.
[7] Puerto J, Ramos A B, Rodriguez-chia A M, et al. Ordered Median Hub Location Problems with Capacity Constraints[J]. Transportation Research Part C Emerging Technologies. 2015, 70: 142-156.
[8] Adler N, Smilowitz K. Hub-and-spoke network alliances and mergers: Price-location competition in the airline industry[J]. Transportation Research Part B. 2016, 41(4): 409.
[9] Jeong S J, Lee C, Bookbinder J H. The European freight railway system as a hub-and-spoke network[J]. Transportation Research Part A Policy & Practice. 2016, 41(6): 536.
[10] 傅少川，胡夢飛，唐方成. 禁忌搜索算法在單分配多樞紐軸輻式物流網絡中的應用[J]. 中國管理科學. 2012, 20(3): 145-151.
SCISSCIAHCI
