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

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

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

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

1　單組檢衡車作業(yè)站點序列優(yōu)化模型

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

以1組檢衡車在所負責子區(qū)域路網(wǎng)內的廣義走行時間最小為目標，建立的單組檢衡車作業(yè)站點序列優(yōu)化模型M1為

(1)

s.t.

(2)

(3)

(4)

(5)

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

(6)

xij∈{0，1}

(7)

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

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

2　單組檢衡車作業(yè)站點序列優(yōu)化模型的求解算法

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

更新粒子速度和位置的傳統(tǒng)表達式為

(8)

(9)

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

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

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

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

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

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

(6)實數(shù)與速度相乘：設實數(shù)r為(0，1)區(qū)間內的隨機數(shù)，速度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)

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

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

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

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

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

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

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

Step 6：判斷是否滿足l

Step 7：結束尋優(yōu)操作，輸出計算結果。

3　多組檢衡車作業(yè)站點序列優(yōu)化

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

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

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

(12)

s.t.

(13)

(14)

(15)

(16)

(17)

(18)

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

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

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

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

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

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

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

4　實例驗證

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

圖2　哈爾濱鐵路局管內路網(wǎng)作業(yè)站點布局圖

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

4.1　單組檢衡車作業(yè)站點序列的優(yōu)化

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

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

4.2　多組檢衡車作業(yè)站點序列的優(yōu)化

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

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

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

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

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

5　結　語

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

[1]馬樹峰，王穎.關于強化鐵路貨車超偏載檢測裝置運用管理工作的探討[J].鐵道運輸與經(jīng)濟，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]王穎.強化貨運計量安全檢測監(jiān)控系統(tǒng)運用管理的思考[J].鐵道運輸與經(jīng)濟，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].鐵道技術監(jiān)督，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].鐵道技術監(jiān)督，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]徐鋒.動態(tài)檢衡車運用專家系統(tǒng)初探[J].鐵道技術監(jiān)督，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].計算機與現(xiàn)代化，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問題的離散粒子群優(yōu)化算法[J].系統(tǒng)工程理論與實踐，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]高尚，韓斌，吳小俊，等.求解旅行商問題的混合粒子群優(yōu)化算法[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]楊國興.一種多出發(fā)點多旅行商問題到旅行商問題的轉換[J].系統(tǒng)工程理論方法應用，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)