鐵路網多流向超限貨物運輸路徑優化模型及算法

陳 皓， 王文憲， 李雪芹

（1．西南交通大學交通運輸與物流學院，四川成都610031；2．綜合交通運輸智能化國家地方聯合工程實驗室，四川成都610031）

鐵路網多流向超限貨物運輸路徑優化模型及算法

陳 皓1，2， 王文憲1， 李雪芹1

（1．西南交通大學交通運輸與物流學院，四川成都610031；2．綜合交通運輸智能化國家地方聯合工程實驗室，四川成都610031）

為了將鐵路網中具有不同去向的超限貨物合理地分配至各條路徑，以超限貨物的運輸路徑里程、運輸時間以及對既有線路正常運營組織干擾最小為目標，以路段運輸限界、通過能力和途經橋梁乘載能力為約束，建立多流向超限貨物運輸路徑選擇的多目標規劃模型．根據模型特點設計多目標混合遺傳算法進行求解，該算法采用自然數組編碼方式以及特殊的交叉、變異算子用以滿足約束條件，同時引入模擬退火策略提高鄰域搜索能力．實例結果表明，對于包含14個節點車站、23個路段的復雜鐵路網，利用本文模型算法獲得方案的目標函數值均優于遺傳算法和退火算法得到的方案，從而為鐵路網超限貨物運輸路徑選擇提供技術決策方法．

超限貨物；路徑優化；非線性混合整數規劃模型；混合遺傳算法

Key words：out-of-gauge freights；path optimization；nonlinear mixed integer programming model；ant colony algorithm

超限超重貨物多數是國家基礎建設設施或大型機械設備，具有長大、笨重的特征，且具有極高的價值．這就決定了超限超重貨物運輸的特點是高費用、高風險、高復雜度的作業過程．特別是在組織超限超重專列進行運輸時，其運輸過程需要調度、車輛、機務、工務、電務等多個鐵路運輸部門協同完成．這就使得超限超重貨物的運輸條件比普通貨物更嚴格［1-2］．本文對鐵路網多流向超限貨物運輸問題的界定是，將具有不同來源或去向的超限貨物分配在鐵路網中的不同運輸路徑上，其實質為貨物運輸路徑選擇問題．

針對該問題，國內外學者做過較多相關研究．文獻［3］用雙目標雙容量數學模型求解超限超重貨物的運輸路徑選擇，將該問題轉化成具有最大流限制的最短路徑問題，并設計了求解該問題的算法．文獻［4-5］綜合考慮限界、橋梁承載能力、車流平衡等約束，以對正常運輸組織干擾、運輸里程和費用最小化為目標，構建了超限超重貨物運輸路徑優化模型，設計了基于不斷修正規范化目標函數權重的實例匹配策略，構造了啟發式路徑搜索算法．文獻［6］深入分析了超限車運行決策優化問題，根據超限車裝載加固實例匹配原理，構建超限車運行決策網絡模型，并提出超限車運行決策優化算法，有效解決了超限車運行決策優化問題．文獻［7］采取層次分析法，對超限超重貨物運輸中的突出問題進行了權重分析，并針對這些問題建立了應急預案的基本框架和應急響應體系，提出了突發事件的應急措施、應急預案的編制與實施方法，對超限超重貨物運輸方案的設計過程實例進行了分析．文獻［8］建立了超限超重貨物運輸影響因素的模糊綜合評價模型，設計了優化算法的思想，應用模糊數學思想設計了單層和多層路徑決策模型，并給出了相應的單層和多層路徑決策優化算法．

上述研究主要是通過建立各種超限貨物路徑選擇模型，設計不同啟發式算法實現路網最優路徑的搜索．但隨著路網規模的擴大，以及線路區間運輸組織的復雜化，獲取該問題的精確解具有相當的難度．根據超限貨物運輸的特性及鐵路運輸狀況設計相應的高效啟發式算法，是提高求解效率的重要策略．遺傳退火算法是在遺傳算法的基礎上，用模擬退火策略以增強鄰域搜索能力的混合優化算法，即引入模擬退火Metropolics選擇機制作為另一個算子的改進算法．對于模擬退火的研究已有較多成果．文獻［9］使用混合遺傳-模擬退火算法對公交行車調度進行優化，表明該算法比標準遺傳算法具有更高的效率．文獻［10］提出改進遺傳模擬退火算法，對大件公路運輸路徑選擇問題進行優化，實例仿真驗證了該算法相對于其他算法的優越性．

本文在上述研究的基礎上，綜合考慮路段區間的鐵路限界、橋梁承載能力與線路通過能力等約束，以及對正常運輸組織的干擾，對運營里程、運輸時間進行綜合優化，建立多流向超限超重貨物運輸徑路綜合優化模型．在融合遺傳算法并行計算能力以及模擬退火算法鄰域搜索優勢的基礎上，設計改進的混合算法求解模型，從而快速確定各流向超限超重貨物的運輸路徑．

1 模型構建

超限貨物運輸網絡是運輸路徑優化的基礎，鐵路網

中，鐵路網中的車站節點和連接線路分別為網絡頂點和有向弧．

車站節點集

I表示車站節點的數量；連接車站節點i和j的線路集

線路的能力屬性集

包括線路的綜合最小建筑限界、橋梁檢定承載系數以及通過能力；線路的廣義運輸屬性集

包括線路的運輸密度、運輸里程以及運輸速度．鐵路網超限貨物運輸路徑優化模型M1為

式中：fst為s→t流向的超限貨物運量；

K為超限貨物列車的平均編成輛數；

sLst為超限貨物裝載后在直線線路上的輪廓；

sCst為超限貨物裝載后在曲線線路上的輪廓；

Qst為超限貨物列車通過橋梁的運行活載；

δkij為某流向超限貨物的運輸路徑與區間i→j的關聯系數，取1表示區間i→j在其運輸路徑上，取0為否；

bLij為區間i→j上的最小直線建筑限界；

bCij為區間i→j上的最小曲線建筑限界；

mij為區間i→j的最小橋梁承載系數；

Cij為區間i→j的通過能力；

cij為區間i→j的原有列車數；

Dij為區間i→j的運輸密度；

vLij為超限貨車在區間i→j的限速；

lij為區間i→j的里程；

Tij為區間i→j的單位運輸時間；

xkst為0-1決策變量，取1時表示s→t流向的超限貨物選取路徑pkst，取0為否，

Pst為s→t流向超限貨物的可行路徑集．

式（1）表示對正常運輸組織干擾最小的目標函數．由于開行超限超重的貨運列車，需要鐵路多部門的合作協調，運輸組織極為復雜．例如，超限等級或重心較高時，有嚴格的限速且不能會車等，這些因素會對原有線路運輸車輛的正常運營造成極大的影響．所以開行這類超限超重貨車，需要盡量避開主要干線或繁忙線路，盡可能地減少對現有線路運輸組織的影響．在此用對線路正常情況下運輸密度的干擾程度來表示開行超限超重貨車對正常運輸組織的影響，干擾程度與超限貨車的限速有關，限速越小，干擾越大［13］．

式（2）表示運輸里程短的目標函數．在盡可能滿足約束條件的前提下，最短運輸路徑是指相對較短，而非絕對的最短路徑．

式（3）表示運輸時間短的目標函數．在一些線路條件較差的地方，如果進行超限超重貨物列車的運輸，由于超限等級、線路線間距、曲線半徑等因素的限制，超限貨物列車需要限速通過．

超限超重貨物由于其運輸貨物的特殊性，對運輸路徑選擇的要求更為苛刻，為保障運輸安全，除了要滿足一般貨物運輸所需考慮的車流平衡和站線能力約束，還應考慮其它安全方面的約束要求［11-12］．

式（4）和（5）表示限界限制約束條件．運輸限界限制了該線路允許通過車輛的尺寸范圍，尤其是超寬、超高、超長的貨物運輸，在直線或曲線線路上，貨物任意位置的尺寸必須嚴格地與實際建筑限界保持一定的距離．

式（6）表示橋梁承載能力限制約束條件．橋梁的承載能力應以橋梁的檢定承載系數表示，車輛在通過橋梁或線路時，車輛重量必須小于或等于該段線路或橋梁所允許的檢定承載系數．

式（7）表示區間通過能力限制約束條件．超限貨物列車通過某區間，與該區間原有車流量的總和不得超過該區間的通過能力．

2 混合遺傳算法設計

在上述多目標優化問題中，這些子目標之間并非正相關，很難找到一組解使多目標優化模型的各子目標同時達到最優，通常只能求得模型的非劣解，即Pareto最優解．

2．1 多目標優化的概念

對于具有α個子目標的多目標優化問題

如果u、v分別為該問題的兩個可行解，其對應的各子目標的目標函數值記為

和

定義1 Pareto占優．當且僅當?δ＝1，2，…，α，fρ（u）≤fρ（v），且?β＝1，2，…，α，fβ（u）＜fβ（v）時，可行解u對于可行解v占優．

定義2 Pareto最優．設u*為可行解，其目標函數為｛f1（u*），f2（u*），…，fα（u*）｝，對于所有u，不存在fρ（u）＜fρ（u*），則稱可行解u*為Pareto最優解．

2．2 算法設計

遺傳退火算法的基本思路是，首先隨機產生初始種群，執行完基本遺傳算子后，按照某種策略生成鄰域種群，然后針對兩種群個體分別執行Metropolics選擇，并下降溫度．本文借鑒SA-GA（simulated annealing-genetic algorithm）算法機理，對算子進行適當修改，應用于求解鐵路網超限貨物運輸路徑決策問題．

（1）編碼方式

一般來說，運用遺傳算法解決組合優化問題時，應將該問題的解編碼為一個具有某種設計規則的自然數組［14］．本文用向量Schrom＝（p1，p2，…，pm）作為一個染色體來表示從1～m流向超限貨物的各運輸路徑，其中，染色體中的每個基因片段pi（i＝1，2，…，m）都對應該流向超限貨物所經過的路徑，即pi＝（r1，r2，…，rn）．

（2）適應度函數

個體適應度主要由目標函數值決定，在本文中，每條染色體都具有3個適應度值，即對正常運輸組織干擾、運輸里程與運輸時間的適應度分別為

式中：z1～z3為模型M1的目標函數．．

對于超出限界限制的區段，引入懲罰系數M和階躍函數J（x）．定義

將式（8）代入目標函數，即

可采用上述方法將橋梁承載與區間通過能力限制約束條件轉化為虛擬路段能力．

（3）選擇方式

本文采取保留精英的選擇策略，首先根據適應度函數選擇種群中具有最優適應度的個體直接進入子代，再對當前種群執行隨機遍歷抽樣，直至子代種群規模與父代相同．

（4）交叉方式

交叉方式如圖1所示．在染色體中隨機選擇兩個不同流向超限貨物所選路徑的代表基因片段（n1，n2，…，nn）和，并隨機選擇它們之間的某個公共節點，即ni＝n′i，交換兩個基因片段在該節點后的部分染色體，從而得到兩個新的染色體：

圖1 交叉方式Fig．1 Cross mode

（5）變異方式

在對染色體進行變異時，首先隨機選擇某個流向超限貨物所代表的基因片段，然后在｛1，2，…，k｝中隨機產生一個整數i，再尋找一條從節點ni～nI的路徑

從而得到一條新的染色體

（6）模擬退火策略

在混合遺傳算法中，遺傳算法控制全局的尋優方向，模擬退火的Metropolics鄰域搜索策略提高算法的鄰域搜索能力，兩者結合使算法的求解性能得到提高．

每次迭代時，在執行完遺傳策略的子代種群中，隨機選擇一個當前個體Schromi并按照變異的方式產生其鄰域個體Schromj，然后按照Metropolics策略對當前個體進行替換：

式中：p（i→j）為當前個體Schromi被鄰域個體Schromj替換的概率；

f1（i）、f2（i）為當前個體Schromi的適應度；

T為當前溫度．

用遺傳算法求解超限貨物運輸路徑優化問題的流程如下．

步驟1 設定參數，種群大小為popsikze，交叉概率調整參數為pc，變異概率為pm，最大迭代次數為Gmax；

步驟2 按照本節文染色體編碼方式生成初始種群pop，當前代數g←1；

步驟3 計算當前種群中各染色體的適應度，根據本節設計的選擇規則生成父代種群；

步驟4 根據本節設計的交叉方式，對種群進行交叉操作；

步驟5 根據前文設計的變異方式，對種群進行變異操作；

步驟6 在子代種群隨機選擇一個染色體生成其鄰域解，按式（10）對兩者進行選擇，更新當前迭代次數g←g＋1；

步驟7 算法終止判定，若g≤Gmax，轉步驟3循環計算，否則輸出當前種群中最優染色體，并解碼為最優運輸路徑方案．

3 算例分析

以我國某地區局部鐵路網拓撲結構圖為例，采用模擬OD車流數據，利用本文構建的優化模型進行配流和路徑優化，驗證模型及算法的適應性．

簡化后的鐵路網結構如圖2所示，圖2中有14個節點車站、23個路段．各流向超限貨物量為：

1→13流向為82車；

1→14流向為94車；

12→13流向為103車；

12→14流向為97車．超限貨物列車的平均編成輛數為K＝50，總載重4 000 t．超限貨物裝載后在直線與曲線上的輪廓分別為2 320和2 400 mm，屬于超級超限情況．各路段的線路參數如表1所示．

圖2 鐵路網示意圖Fig．2 Schematic diagram of railway network

表1 各個路段的線路參數參考值Tab．1 Reference values of line parameters for different road sections

利用本文模型，經過試算和調整，最終確定各個參數值：種群大小為60，交叉概率

變異概率

初始溫度

結束溫度

溫度衰減參數

最大迭代次數

每次均包括算法對超限貨物運輸路徑的尋優和對出發時間的調整．

當種群執行完選擇、交叉、變異算子后，遺傳操作停止，進入模擬退火Metropolics選擇．整個計算求解過程基于Matlab7．0軟件運行，最終得到目標函數最優的染色體為

解碼后得到各流向超限貨物的運輸路徑如表2所示．整個鐵路網輸送超限貨物對正常運輸組織的干擾程度為53．83，運輸里程為871 km，運輸時間為29．13 h．

表2 各流向路徑選擇結果Tab．2 Results of path selection in different flow directions

針對同一鐵路網多流向超限貨物運輸路徑優化問題，將本文方法與基本遺傳算法和模擬退火算法的求解結果進行對比分析．在基本遺傳算法的種群大小、迭代次數、編碼、交叉與變異方式，以及模擬退火算法的溫度衰減參數均與混合遺傳算法相同的情況下，分別運行上述3種算法各6次，計算結果的對比如表3所示．

表3 仿真結果比較Tab．3 Comparison of simulation results

從表3可知，經過6次迭代后，本文設計的遺傳模擬退火算法得到的3個目標平均結果優于遺傳算法和模擬退火算法的平均結果，且在迭代過程中3次得到了該問題的最優解．可見，利用本文設計的改進遺傳模擬退火算法，可以方便有效地求得多約束條件下的鐵路網多流向超限貨物運輸徑路優化問題的最優解或近似最優解．

4 結束語

作為超限超重貨物運輸調度的核心內容之一，路徑方案的決策需要考慮其整體性與復雜性．本文綜合考慮超限超重貨物的運輸里程、時間，以及對既有線路正常運營的干擾程度，在此基礎上構建了多流向超限超重貨物徑路優化模型，用于確定不同流向超限貨物的運輸路徑，并基于模型特點設計了遺傳退火算法進行求解．通過14個節點車站、23個路段構造的鐵路網算例，以及大量的仿真試驗計算，獲得以下結論：

（1）在該算法的設計和實現方面，采用組合序列編碼方法產生初始種群，通過對交叉、變異等遺傳算子的適應性設計，保證每個染色體的可行性，通過引入模擬退火策略，克服了不成熟的收斂，并增加了算法的鄰域搜索能力．

（2）在算法性能方面，以某地區局部鐵路網為例，分別采用遺傳算法、模擬退火算法和遺傳退火算法進行求解，通過對徑路選擇結果對比分析發現，遺傳退火算法具有更好的全局尋優能力，同時驗證了本文提出的遺傳模擬算法在求解超限貨物運輸徑路優化問題的優越性，具有重要的理論和現實意義．

［1］ 王花蘭，李偉，張婷．鐵路闊大貨物裝載加固方案比選方法的研究［J］．蘭州鐵道學報，2002，21（6）：112-115．WANG Hualan，LI Wei，ZHANG Ting．Study on the method of making choices from railway long heavy goods' loading and firming schemes［J］．Journal of Lanzhou Railway University，2002，21（6）：112-115．

［2］ 鐘喜云．闊大貨物裝載加固方案評價［D］．成都：西南交通大學，2009．

［3］ 雷定猷．貨物裝運優化理論與應用研究［D］．長沙：中南大學，2005．

［4］ 湯波．鐵路超限超重貨物運輸優化研究［D］．長沙：中南大學，2012．

［5］ 湯波．鐵路超限超重貨物運輸徑路綜合優化模型與算法［J］．計算機應用研究，2012，29（8）：2876-2881．TANG Bo．Integrated optimizing model and algorithms of transportation route in out-of-gauge and overweight freights of railway［J］．Application Research of Computers，2012，29（8）：2876-2881．

［6］ 王新宇．鐵路超限車運行組織優化研究［D］．長沙：中南大學，2012．

［7］ 尹曄飛．超限超重貨物運輸方案研究［D］．長沙：中南大學，2009．

［8］ 徐盛，雷定猷，張英貴．超限超重貨物運輸路徑決策模型和算法［J］．鐵道貨運，2009（8）：31-35．XU Sheng，LEI Dingyou，ZHANG Yinggui．The model and algorithm of route decision in out-of-gauge and enhanced-load freight transportation［J］．Railway Freight Transport，2009（8）：31-35．

［9］ 任傳祥，張海，范躍祖．混合遺傳-模擬退火算法在公交智能調度中的應用［J］．系統仿真學報，2005，17（9）：2075-2078．REN Chuanxiang，ZHANG Hai，FAN Yuezu．Optimizing dispatching of public transit vehicle［J］．Journal of System Simulation，2005，17（9）：2075-2078．

［10］ 程博，楊育，劉愛軍，等．基于遺傳模擬退火算法的大件公路運輸路徑選擇優化［J］．計算機集成制造系統，2013，19（4）：779-787．CHENG Bo，YANG Yu，LIU Aijun，et al．Highway transportation route selection optimization based on improved genetic annealing algorithm［J］．Computer Integrated Manufacturing Systems，2013，19（4）：779-787．

［11］ 蔣卓強．基于遺傳模擬退火算法的靜態路徑規劃研究［D］．重慶：重慶大學，2007．

［12］ 張東杰，牛瑤婷．鐵路超限貨物運輸可行徑路選擇［J］．鐵道運營技術，2010，16（3）：53-55．ZHANG Dongjie，NIU Yaoting．Railway out-of-gauge goods transportation behavior way choice［J］．Railway Operation Technology，2010，16（3）：53-55．

［13］ 劉勝，朱曉寧．超限車合理徑路的選擇方法研究［J］．物流技術，2011，30（6）：139-143．LIU Sheng，ZHU Xiaoning．Study on route selection for out-of-gauge trains［J］．Logistics Technology，2011，30（6）：139-143．

［14］ 王海星，海濤，李振江．鐵路危險貨物運輸徑路的選擇策略［J］．北京交通大學學報，2009，33（6）：27-30．WANG Haixing，HAI Tao，LI Zhenjiang．Pathway selection process of dangerous goods railway transportation［J］．Journal of Beijing Jiaotong University，2009，33（6）：27-30．

（中文編輯：秦萍玲 英文編輯：蘭俊思）

Routing Optimization Model and Algorithm for Out-of-Gauge Freights in Multiple Flow Railway Network

CHEN Hao1，2， WANG Wenxian1， LI Xueqin1
（1．School of Transportation and Logistics，Southwest Jiaotong University，Chengdu 610031，China；2．National United Engineering Laboratory of Integrated and Intelligent Transportation，Chengdu 610031，China）

In order to distribute the out-of-gauge freights reasonably to paths in railway network，a multi-objective optimization model was built for route selection of multi-direction out-of-gauge freights．In the model，the minimum transport route mileage，the minimum haulage time，and the minimum interference to the normal operation of the existing railway lines were taken as targets；and the distance between railway out-of-gauge freights and structure gauge，the railway transport capacity，and the loading capacity of the bridge along the way were used as constraints．According to the model characteristics，a multi-objective hybrid genetic algorithm was proposed to solve the model．In the algorithm，the natural array coding mode，together with cross and mutation operators，were designed to fit the constraints，and a simulated annealing strategy was introduced to enhance its neighborhood search capability．In addition，the proposed method was applied to the complex network containing 14 node stations and 23 sections to verify its validity．The application results show that the objective function values obtained by the proposed model and algorithm are superior to those obtained by genetic algorithm and annealing algorithm．Therefore，this method provides a technical measure for the decision-making of path selection in out-of-gauge freights transportation．

U294．6

A

0258-2724（2016）01-0145-07

10．3969／j．issn．0258-2724．2016．01．021

2014-09-27

中國鐵路總公司重點資助項目（2014S14022）

陳皓（1986—），男，博士研究生，研究方向為運輸組織優化理論與方法，電話：13568953471，E-mail：490646541＠qq．com

陳皓，王文憲，李雪芹．鐵路網多流向超限貨物運輸路徑優化模型及算法［J］．西南交通大學學報，2016，51（1）：145-151．