鐵路網檢衡車組作業站點序列優化模型及算法

馬樹峰，安愛民，王　龍，李學寶，王　穎

(1.中國鐵道科學研究院 標準計量研究所，北京　100081；2.中國鐵路經濟規劃研究院 運輸研究所，北京　100038)

軌道衡和超偏載檢測裝置作為重要的鐵路貨運計量安全檢測設備，在保證鐵路運輸安全、提高運輸效率和質量等方面發揮了重要作用。檢衡車是檢定軌道衡和超偏載檢測裝置的計量標準器，是保證軌道衡和超偏載檢測裝置量值傳遞準確和統一的基礎。根據相關規定，檢衡車組(由5輛不同重量的檢衡車固定編組而成)每年須在安裝軌道衡和超偏載檢測裝置的車站(簡稱作業站點)進行1次檢定作業。

近10年來，隨著鐵路對貨運計量安全檢測設備投資建設力度的加大，全路軌道衡的數量增長了50%，超偏載檢測裝置的數量增長了4倍，而檢衡車組卻一直未增加，導致檢衡車組的運用非常緊張。因此，合理安排檢衡車組在鐵路網中進行檢定作業的路徑，即優化檢衡車組經由各作業站點進行軌道衡、超偏載檢測裝置檢定的作業次序(簡稱檢衡車組作業站點序列)，對于縮短檢衡車組進行檢定作業的時間、提高檢衡車組的運用效率具有重要現實意義。由于文獻[1—5]僅研究了檢衡車組在站內檢定工作的步驟和流程，因此筆者基于運籌學旅行商問題的建模思想，進行檢衡車組作業站點序列優化的研究。

1　單組檢衡車作業站點序列優化模型

受檢衡車組數量的制約，在人工編制檢衡車組運用計劃時，通常根據擁有的檢衡車組數量將全國路網劃分為等量區域路網，并預先為每個區域路網分配1組檢衡車。在執行具體檢定任務時，每個區域路網又被分成若干個子區域路網，且檢衡車組進入和離開子區域路網的起止站點一般是固定的，因此為實現單組檢衡車在子區域路網內的廣義走行時間最小化和檢衡車組運用效率的最大化，可以將檢衡車組作業站點序列的優化問題等價為運籌學中的旅行商問題(TSP)，并基于TSP的建模原理構造子區域路網內檢衡車組作業站點序列優化的模型。

以1組檢衡車在所負責子區域路網內的廣義走行時間最小為目標，建立的單組檢衡車作業站點序列優化模型M1為

(1)

s.t.

(2)

(3)

(4)

(5)

ui-uj+nxij≤n-1i≠j≠s，i≠e

(6)

xij∈{0，1}

(7)

式中：N為某子區域路網內檢衡車組作業站點的集合；s為所配屬檢衡車組進入該子區域路網內進行檢定作業的第1個作業站點，s∈N；e為所配屬檢衡車組在該子區域路網內進行檢定作業的最后1個作業站點，即檢衡車組要離開該子區域路網時所在的作業站點，e∈N；xij和ui為0—1決策變量，i和j為子區域路網內的兩相鄰作業站點且i，j∈N；tij為檢衡車組自作業站點i至j的廣義走行時間，由于檢衡車組在作業站點i完成檢定作業之后需要連掛特定車次的貨物列車前往作業站點j，因此，可能會在作業站點i以及途經各站產生一定的等待時間，故tij不僅包括檢衡車組自i站至j站的運行時間，還包括在i站及沿途各站的等待時間，d；n為子區域路網內檢衡車組作業站點的數量。

作為式(1)的約束條件，式(2)表示檢衡車組在子區域路網內去往除s以外的其他作業站點時只能由1個作業站點出發；式(3)表示檢衡車組在子區域路網內從除e以外的其他作業站點出發后只能到達1個作業站點；式(4)表示對于s站，檢衡車組在子區域路網內只能從該站出發而不能到達該站；式(5)表示對于e站，檢衡車組在子區域路網內只能到達該站而不能從該站出發；式(6)為檢衡車組走行徑路不構成回路的約束條件；式(7)表示當檢衡車組在作業站點i完成檢定作業后的下一個作業站點為j時，xij取1，否則取0。

2　單組檢衡車作業站點序列優化模型的求解算法

作者采用收斂速度快、計算精度高的粒子群算法[6-8]對模型M1進行求解。該算法采用速度—位置搜索模式，以每個粒子的位置作為待解決問題的可能解集，以目標函數作為適應值來判斷群體中每個粒子的優劣；通過跟蹤個體最優值和全局最優值(即全部粒子個體極值的最優者)的粒子，不斷更新其在解空間的位置，從而找到問題的最優解。

更新粒子速度和位置的傳統表達式為

(8)

(9)

因為式(8)和式(9)為連續問題的求解式，在用于求解離散的TSP問題時，需要對其進化算子進行重新定義如下。

(1)位置：定義任意粒子的位置X代表檢衡車組遍歷子區域路網內作業站點的次序，即根據模型M1中決策變量xij的值推算出的檢衡車組在子區域路網內進行檢定作業時到達作業站點的次序。

(2)速度：定義任意粒子的速度V為粒子位置的交換集，它是由1組交換構成置換序列的有序列表，其表達形式為

V={(i，j)h|h=1，2，…，P}

式中：P表示該速度所含交換的數目，交換按順序依次執行。

(3)位置與速度相加：將1組置換序列依次作用于某個粒子的位置，生成1個新的位置；例如，位置X1=(1，3，2，5，4，6)表示檢衡車組的作業站點序列為1→3→2→5→4→6(數字為作業站點的編號)，相當于在模型M1中，n=6且x13=1，x32=1，x25=1，x54=1和x46=1，其余決策變量值均為0；速度V1={(5，2)，(3，2)}表示先進行檢衡車組第5與第2序位作業站點的交換，再進行第3第與2序位作業站點的交換，則X1+V1=(1，2，4，5，3，6)，相當于經過位置與速度的加和后，決策變量的值變更為：x12=1，x24=1，x45=1，x53=1和x36=1，其余決策變量值均為0，檢衡車組的作業站點序列調整為1→2→4→5→3→6。

(4)位置與位置相減：該操作的結果是得到1組置換序列，即速度；例如，位置X1=(1，3，2，5，4，6)，位置X2=(1，2，4，5，3，6)，則X2-X1={(5，2)，(3，2)}。

(5)速度與速度相加：對2個置換序列進行合并，可得到1個新的置換序列(即1個新的速度)作為指導檢衡車組的作業站點序列優化調整的原則。例如，速度V1={(5，2)，(3，2)}，速度V2={(1，4)}，則V1+V2={(5，2)，(3，2)，(1，4)}。

(6)實數與速度相乘：設實數r為(0，1)區間內的隨機數，速度V為包含P個交換的序列，則r與V相乘的結果為由V中前r×P(取整)個交換構成1組新的置換序列。例如，V={(1，3)，(2，5)，(4，1)，(3，2)}，則當r=0.6時，r×V={(1，3)，(2，5)}。

由此，針對用模型M1求解離散TSP問題，對式(8)和式(9)進行變換，得

(10)

(11)

式中：α和β為加速常數，一般在(0，1)區間內取值，α和β決定了后面的交換被用到幾個，α和β即為r×P下的取整。

基于粒子群算法的模型M1求解步驟如下。

Step 1：先設定粒子的數量(本文取30)，每個粒子代表1個解，即檢衡車組作業站點序列的1個方案；Lmax為最大迭代次數(可取為1 000)。

Step 2：隨機生成每個粒子的初始位置和初始速度，計迭代次數l=1。

Step 3：根據式(10)和式(11)對所有粒子的位置進行更新，并用式(1)計算每個粒子的適應值，即所對應檢衡車組作業站點序列方案下檢衡車組在各站點間的廣義走行時間。

Step 4：判斷每個粒子的適應值是否優于其自身已經歷過的個體極值，若是，更新其個體極值(即用該粒子當前的適應值替換其個體極值)，否則，其個體極值不變。

Step 5：判斷每個粒子的個體極值是否優于當前的全局極值，若是，更新全局極值，否則全局極值不變。l=l+1。

Step 6：判斷是否滿足l

Step 7：結束尋優操作，輸出計算結果。

3　多組檢衡車作業站點序列優化

前文研究了由1組檢衡車擔任1個子區域路網內各相關作業站點檢定任務時的作業站點序列優化問題。考慮到今后將增配檢衡車組，每個區域路網有可能配備多組檢衡車進行檢定作業的情況，并且從全局優化的角度分析，由于依照人工經驗所劃分的子區域路網并不能保證多組檢衡車分別對所負責子區域路網內各作業站點進行檢定作業而消耗的總的廣義走行時間最少，以及各組檢衡車的工作負荷基本均衡等要求，因此，作者再從全局優化的角度出發，將某一區域路網視為一個整體，打破以往1組檢衡車獨立負責一個區域的“分片負責”的固定檢定范圍模式，在鎖定各組檢衡車進入和離開所負責檢定區域路網內作業站點的情況下，研究多組檢衡車聯合開展某一區域路網作業站點檢定作業時檢衡車組作業站點序列綜合優化的問題。

通過分析可知，多組檢衡車在某區域路網內進行檢定作業時的作業站點序列優化問題可類比為多個旅行商的走行徑路優化問題(即MTSP問題)。

基于MTSP問題的建模思想，可構建多組檢衡車作業站點序列優化模型M2為

(12)

s.t.

(13)

(14)

(15)

(16)

(17)

(18)

式(12)為模型M2的目標函數，表示配屬給某鐵路局的多組檢衡車在該鐵路局管內路網范圍內總的廣義走行時間最小；式(13)表示檢衡車組k在該鐵路局管內路網范圍內去往除sk以外的其他作業站點時只能由1個作業站點出發；式(14)表示檢衡車組k在該鐵路局管內路網范圍內從除ek以外的其他作業站點出發后只能到達1個作業站點；式(15)表示檢衡車組k只從sk站出發而不能到達該站；式(16)表示檢衡車組只到達ek站而郴能從該站出發；式(17)中，Ω為消去支路的約束[8-9]，即消去構成不完整徑路的解，以避免在每次遍歷當中產生多于1個的互不連通路徑。

為了便于模型M2的求解，本文根據文獻[9]，通過設置虛擬弧費用(即檢衡車組經由虛擬弧的廣義走行時間)，將求解模型M2的MTSP問題轉換為TSP問題。下面以2組檢衡車負責某一鐵路局管內路網各作業站點的檢定任務為例，給出虛擬弧的具體設置方法(見圖1)如下。

(1)因為2組檢衡車的起點作業站之間不能有連接弧相連，所以設連接它們起點作業站的連接弧的弧費用為無窮大。

(2)同理，由于在2組檢衡車的終點作業站之間也不能有連接弧，因此設連接它們終點作業站的連接弧的弧費用也為無窮大。

(3)因為其中1組檢衡車(假定該組檢衡車的編號k為1)的終點作業站必須與另1組檢衡車(假定該組檢衡車的編號k為2)的起點作業站相連，所以設對應該連接弧的弧費用為負值。

由此，即可構建求解MTSP問題的虛擬路網結構，從而實現MTSP問題向TSP問題的轉化；然后，調用本文給出的對進化算子重新定義的粒子群算法求解離散TSP問題，即可實現等價條件下MTSP問題的求解。

圖1　2組檢衡車情況下虛擬弧費用的設置

4　實例驗證

以哈爾濱鐵路局管內路網的檢衡車組作業站點序列優化為例，驗證本文模型和算法的有效性。如圖2所示，哈爾濱鐵路局管內路網內共有89個車站點安裝了軌道衡和超偏載檢測裝置，并假定配備了2組檢衡車負責這些作業站點的軌道衡和超偏載裝置的檢定任務。

圖2　哈爾濱鐵路局管內路網作業站點布局圖

在既有的檢衡車組運用方案中，將哈爾濱鐵路局管內路網劃分為2個作業區，如圖2中右側虛線框內為檢衡車組1的作業區，檢衡車組1由溫春站進入、從五常站離開自己的作業區；路網的其余部分為檢衡車組2的作業區，檢衡車組2從臥里屯站進入、從哈爾濱南站駛離自己的作業區。

4.1　單組檢衡車作業站點序列的優化

按照既有檢衡車組運用方案，基于模型M1，對檢衡車組1的作業站點序列進行優化，所獲得的檢衡車組1的作業站點序列見表1。

表1對應的檢衡車組1在其作業區內總的廣義走行時間為80.5 d，而按檢衡車組1的既有運用計劃則需要93 d(如果考慮檢衡車組的廠修、段修和周期檢定所需要的時間，以此效率推算，每一檢衡車組大概平均僅能完成其全年檢定計劃的80%)；由此可知，采用本文的單組檢衡車作業站點序列優化模型及求解算法可節省12.5d，即檢衡車組1的運用效率提高了13.44%。

4.2　多組檢衡車作業站點序列的優化

在檢衡車組1由溫春站進入、從五常站離開哈爾濱鐵路局管內路網，以及檢衡車組2從臥里屯站進入、從哈爾濱南站離開哈爾濱鐵路局管內路網的前提條件下，按照求解MTSP問題的思路，打破既有檢衡車組運用方案對檢衡車組1和檢衡車組2作業區的限制，基于模型M2對檢衡車組1和檢衡車組2的走行徑路進行整體優化，所獲得的這2組檢衡車的作業站點序列分別見表2和表3。

由表2和表3得到的檢衡車組1和檢衡車組2在哈爾濱鐵路局管內路網內共同進行檢定作業所用的廣義走行時間合計為120.5 d，而按檢衡車組1和檢衡車組2的既有運用計劃則共計需要141 d；由此可知，采用本文的多組檢衡車作業站點序列優化模型可節省20.5d的廣義走行時間，檢衡車組的整體運用效率提高了14.54%。此外，相對于預先固定每組檢衡車的作業區的傳統檢衡車組運用方案，基于MTSP問題求解思路的模型M2對同一路網內多組檢衡車的作業站點序列進行整體優化，不但能夠使各組檢衡車的作業負荷更具均衡性，而且總體上檢衡車組的廣義走行時間也更加節省。

表1　基于TSP問題求解的檢衡車組1的作業站點序列

表2　基于MTSP問題求解的檢衡車組1的作業站點序列

表3　基于MTSP問題求解的檢衡車組2的作業站點序列

5　結　語

本文基于運籌學旅行商問題的求解思路，針對檢衡車組作業站點序列優化問題，分別構建了單組和多組檢衡車作業站點序列優化模型，設計了基于改進的粒子群算法對模型進行求解；并以哈爾濱鐵路局管內路網的檢衡車組作業站點序列優化為例，驗證了模型和算法的有效性。

[1]馬樹峰，王穎.關于強化鐵路貨車超偏載檢測裝置運用管理工作的探討[J].鐵道運輸與經濟，2011,33(12)：30-33.

(MA Shufeng，WANG Ying.On Strengthening the Management of Railway Wagon Super Partial Load Detection Device Using Work[J]. Railway Transport and Economy，2011,33(12)：30-33.in Chinese)

[2]王穎.強化貨運計量安全檢測監控系統運用管理的思考[J].鐵道運輸與經濟，2010,32(4)：79-81.

(WANG Ying.Thoughts on Strengthening Utilization Management for Measurement Safety Monitoring System for Freight Traffic[J]. Railway Transport and Economy，2010,32(4)：79-81. in Chinese)

[3]何小菊. 超偏載檢測裝置檢定工作介紹[J].鐵道技術監督，2009,37(8):23-24.

(HE Xiaoju. Introduction of the Calibration Equipment of Overloading and Unbalanced Loading Detecting Device[J]. Railway Quality Control, 2009,37(8):23-24. in Chinese)

[4]段小軍.T7型檢衡車使用、維護及檢定情況概述[J].鐵道技術監督，2007,35(10):42-43.

(DUAN Xiaojun.General Introduction of the Utilization, Maintenance and Calibration of T7Type of Weight Bridge Test Car[J]. Railway Quality Control, 2007,35(10):42-43. in Chinese)

[5]徐鋒.動態檢衡車運用專家系統初探[J].鐵道技術監督，2006,34(9):33-34.

(XU Feng. Exploration on Applying Expert System on Dynamic Weight Bridge Test Car[J]. Railway Quality Control, 2006,34(9):33-34. in Chinese)

[6]馬曉慧，王紅. 改進的PSO在TSP中的應用[J].計算機與現代化，2011(9):5-7,11.

(MA Xiaohui, WANG Hong. Application of Improved PSO in TSP[J]. Computer and Modernization, 2011(9):5-7,11. in Chinese)

[7]鐘一文，楊建剛，寧正元.求解TSP問題的離散粒子群優化算法[J].系統工程理論與實踐，2006,16(6):88-94.

(ZHONG Yiwen, YANG Jiangang, NING Zhengyuan. Discrete Particle Swarm Optimization Algorithm for TSP Problem[J]. System Engineering Theory & Practice, 2006,16(6):88-94. in Chinese)

[8]高尚，韓斌，吳小俊，等.求解旅行商問題的混合粒子群優化算法[J].控制與決策，2004,19(11):1286-1289.

(GAO Shang, HAN Bin, WU Xiaojun, et al. Solving Traveling Salesman Problem by Hybrid Particle Swarm Optimization Algorithm[J]. Control and Decision, 2004,19(11):1286-1289. in Chinese)

[9]楊國興.一種多出發點多旅行商問題到旅行商問題的轉換[J].系統工程理論方法應用，1993,2(3):66-68.

(YANG Guoxing. A Transformation of the Multi-Depot Multi-Salesmen Problem to the Standard Traveling Salesman Problem[J]. Systems Engineering Theory Methodology Applications, 1993,2(3):66-68. in Chinese)