郭 然,韓寶明,王福田

(北京交通大學交通運輸學院,北京100044)

整數型鐵路線路養(yǎng)護維修計劃優(yōu)化模型

郭 然,韓寶明*,王福田

(北京交通大學交通運輸學院,北京100044)

制定鐵路線路養(yǎng)護維修計劃既要保證線路充分維修,又要兼顧經濟效益.為此,以區(qū)域路網為研究對象,建立了基于整數規(guī)劃的鐵路線路養(yǎng)護維修計劃優(yōu)化模型.模型考慮了路網中線路之間維修資源的約束,以維修時間和股道占用狀態(tài)為決策變量,以股道占用費用、維修費用及懲罰費用總和最小化為目標,通過集中安排線路中各項養(yǎng)護維修活動節(jié)省維修支出,減少維修活動對股道的占用時間進而達到優(yōu)化目的.基于啟發(fā)式算法設計了模型求解方法,仿真實驗結果表明,模型具有較好的實用性,能夠為編制鐵路線路年度養(yǎng)護維修計劃提供決策支持.

鐵路運輸;養(yǎng)護維修計劃;整數規(guī)劃;優(yōu)化模型;啟發(fā)式算法

1 引 言

鐵路線路作為機車車輛和列車運行的基礎,是列車安全、平穩(wěn)和不間斷運行的重要保障.隨著鐵路向高速、重載方向發(fā)展,列車運行速度和密度越來越高,線路設備養(yǎng)護維修工作量不斷增加,維修費用逐年上升[1].如何在充分做好線路設備養(yǎng)護維修工作的同時,尋求與維修資金投入之間的最佳平衡是各國鐵路部門面臨的重要課題.制定高效、合理的鐵路線路養(yǎng)護維修計劃,對于確保鐵路線路高可靠性,保障正常運輸組織秩序,節(jié)省維修費用,合理配置維修資源具有非常重要的意義.

鐵路基礎設施的養(yǎng)護維修計劃編制問題一直備受關注,目前,國內外學者的研究方法主要有兩類:以設備狀態(tài)為中心的維修計劃編制方法(Conditional Maintenance,CM)和以設備可靠性為中心的維修計劃編制方法(Reliability Centered Maintenance,RCM).第一類方法以設備狀態(tài)監(jiān)測數據為支撐,通過建立劣化模型預測設備狀態(tài)變化情況并安排維修[2-5],但該方法主要應用于鐵路軌道養(yǎng)護維修計劃編制,且需要積累大量的軌道狀態(tài)檢測數據以預測軌道狀態(tài)變化;第二類方法通過建立設備壽命分布模型,以維修費用或設備可靠度為優(yōu)化目標來安排維修,在鐵路接觸網懸掛系統和牽引供電系統維修計劃編制領域有廣泛應用[6-9],并設計了基于RCM的鐵路基礎設施維修管理系統[10].但對于鐵路線路設備養(yǎng)護維修計劃,RCM通常以特定設備類型為研究對象,只能制定單一養(yǎng)護維修活動(如軌枕更換)的實施計劃[11-13].鐵路線路是包含多種設備的復雜系統,難以全面掌握各類設備的狀態(tài)監(jiān)測數據,同時,線路養(yǎng)護維修活動類型多,各項活動相互影響,上述兩類計劃編制方法尚未直接應用于制定鐵路線路養(yǎng)護維修計劃.

針對上述問題,荷蘭學者Budai提出了一種鐵路線路預防性養(yǎng)護維修計劃編制模型(Preventive Maintenance Scheduling Model,PMSM),在已知線路預防性養(yǎng)護維修活動及其周期的前提下,盡可能集中安排各項活動,以減少股道占用時間,并降低維修費用[14].但PMSM僅針對具體的一條鐵路線路,無法編制包含多條線路的路網線路養(yǎng)護維修計劃.

因此,本文基于PMSM,提出了區(qū)域路網鐵路線路養(yǎng)護維修計劃編制模型并設計了求解算法.文中首先根據鐵路線路養(yǎng)護維修活動的特點和模型的適用條件進行了相關的定義及假設;然后,考慮了路網內多條鐵路線路之間維修資源分配的約束,以養(yǎng)護維修時間與股道占用情況為決策變量,以股道占用費用、維修費用及懲罰費用總和最小化為目標,構建了基于整數規(guī)劃的區(qū)域路網線路年度養(yǎng)護維修計劃優(yōu)化模型;最后,設計了模型求解的啟發(fā)式算法并進行了仿真研究.

2 相關定義及假設

綜合文獻[15,16],進行如下定義:

定義一 圍繞線路設備養(yǎng)護維修工作所進行的各種活動統稱為修理活動,并劃分修理活動為維修活動和施工活動.

定義二 維修活動指股道占用時間短、執(zhí)行頻繁的周期性修理活動,主要包括線路設備周期性人工外觀檢查、儀器檢測,以及定期整修和更換失效零部件等[16].對于設備發(fā)生故障或病害后采取的事后維修(又稱為糾錯性維修)不屬于本文定義的維修活動范疇.

維修活動的執(zhí)行周期從每月幾次到幾個月一次不等,且由于運營繁忙程度的差異,同一項維修活動在干線鐵路執(zhí)行頻率高于非干線鐵路.

定義三 施工活動指持續(xù)時間長、作業(yè)量大、影響范圍廣的修理活動,如:線路全面搗固、成段更換鋼軌、成組更換道岔和軌枕等[16].

施工活動需借助大型養(yǎng)路機械,并根據通過總重及鋼軌累計疲勞傷損率確定線路施工時間,一般2～3年安排一次[15].

模型假設如下:

(1)區(qū)域路網中每條線路需安排的維修活動與施工活動已確定,模型只考慮如何在年度計劃中安排已知修理活動使總費用最小;

(2)所有維修活動在計劃時間范圍內按照固定周期執(zhí)行;

(3)線路運營過程中的糾錯性維修,不會影響計劃中維修活動和施工活動的安排.

3 模型構建

3.1 模型框架

區(qū)域路網線路養(yǎng)護維修計劃優(yōu)化模型(OptimizingModelofMaintenancePlanningfor Regional Railway Network,OMMP-RRN)框架如圖1所示.

圖1 模型整體架構圖Fig.1 Diagram of model structure

模型輸入條件包括:路網中各線路的維修活動集合,及各項維修活動的執(zhí)行周期、距離最近一次維修的時間、單位時間維修費用;路網中各線路的施工活動集合,及各項施工活動可能開始時間、持續(xù)時間、單位時間施工費用.模型約束包括可同時安排執(zhí)行的活動約束,該約束使活動盡可能的集中執(zhí)行,最大程度節(jié)省股道占用時間,提高資源利用率,此外,模型還考慮了區(qū)域路網的維修資源約束及年度中無法進行施工的時間約束.模型的輸出結果為以“周”為時間單位的區(qū)域路網年度線路養(yǎng)護維修計劃時間表.

3.2 模型符號說明

文中以RN=(SN,RL)表示區(qū)域路網,SN= {s1,s2,…,smax}與RL={l1,l2,…,lmax}分別表示RN中關鍵節(jié)點和線路的集合.RN的年度線路養(yǎng)護維修計劃日期范圍用H表示,T為該范圍內以“周”為單位的時間集合.模型中其他的參數定義如下:

PAl——線路l的施工活動集合,l∈RL;

RAl——線路l的維修活動集合,l∈RL;

Al——PAl∪RAl,線路l的所有修理活動集合,l∈RL;

Cl——可合并(即可在單位時間內同時安排執(zhí)行)的修理活動集合,{(m,n)|修理活動m可與n合并,?m,n∈Al};

Lal——線路l維修活動a的執(zhí)行周期,l∈RL,a∈RAl;

Gal——線路l維修活動a最近一次執(zhí)行完成后到計劃開始日期所經歷的時間,l∈RL,a∈RAl;

LCal——{t∈T|1+H-Lal≤t≤H}?T,計劃范圍內線路l維修活動a最后一個周期內的時間集合,l∈RL,a∈RAl;

從時間t到計劃結束的剩余時間與線路l的維修活動a執(zhí)行周期的比,t∈

線路l的施工活動p可能開執(zhí)行的時間集合,l∈RL,p∈PAl;

Tn——Tn?T,年度養(yǎng)護維修計劃日期范圍內禁止線路進行施工的時間集合;——線路l的施工活動p持續(xù)實施時間,l∈RL,p∈PAl;

模型中的決策變量定義如下:

3.3 目標函數及約束

區(qū)域路網線路養(yǎng)護維修計劃優(yōu)化模型(OMMP-RRN)如下:

模型約束中,式(2)為當前計劃中維修活動首次執(zhí)行時間約束,表示在計劃開始后,每一項維修活動首次安排執(zhí)行的時間范圍;式(3)約束了路網中每項維修活動都按固定周期執(zhí)行;式(4)表示各線路中不能合并的修理項目禁止在同一單位時間安排執(zhí)行;式(5)、式(6)表示路網中每一項施工活動在時間范圍H內只安排一次,且當施工活動開始后,其持續(xù)實施的時間長度為Dpl;式(7)為路網中禁止施工的時間約束,由于大型養(yǎng)路機械作業(yè)軌溫限制及對正常運輸的較大干擾,夏季(7～8月)、冬季(11～1月)禁止施工[3];考慮到可作業(yè)的大型養(yǎng)路機械資源有限,式(8)約束了路網中可同時進行的施工活動數量的上限;式(9)表示t時刻,若線路股道由于進行修理活動被占用,則該線路上至少安排了一項修理活動;式(10)表示模型中決策變量均為0-1整數型變量.

4 啟發(fā)式求解算法

本文基于MFWF(Most Frequent Work First Heuristic)方法[14]提出了求解OMMP-RRN模型的啟發(fā)式算法,算法設計遵循以下原則:

(1)考慮到線路間維修活動的執(zhí)行互不影響,首先,分別安排各線路的維修活動,使每條線路的維修活動盡可能集中.對于任意一條線路,按照周期遞增的順序排列各項維修活動并依次進行安排.

(2)確定各線路維修活動執(zhí)行時間后,根據施工活動的最早可能開始時間,遞增排列路網中所有施工活動并依次安排,使每一項施工活動與同線路中已安排的維修活動在時間上盡量集中,且路網所有線路內同時進行的施工活動數量不能超過所規(guī)定的上限.

算法流程如圖2所示,具體步驟如表1所示.

圖2 模型啟發(fā)式算法流程圖Fig.2 Flow chart of heuristic algorithm for the model

表1 模型啟發(fā)式算法詳細步驟Table 1 The detailed steps of heuristic algorithm for the model

5 案例研究

5.1 案例描述

本節(jié)設計了區(qū)域路網用于案例研究,應用OMMP-RRN模型編制以“周”為基本時間單位的路網年度(H=52)養(yǎng)護維修計劃.設計路網中包含6條鐵路線路,假設線路l1、l2、l3、l4為路網中主要干線,l5、l6為非干線.假設計劃中需安排執(zhí)行的活動包括10種不同類型的維修活動Ri與5種施工活動Pj,線路與修理活動的對應關系如表2所示.符號表示在年度養(yǎng)護維修計劃中當前線路需安排該種類型的修理活動.

表2 設計路網線路修理活動列表Table 2 List of maintenance activities in designed railway network

根據模型中的約束,設置下列求解條件:路網中的每一條線路上,單位時間內任意兩項施工活動不能同時執(zhí)行,其余活動都可在單位時間內同時執(zhí)行;整個路網中允許至多3項施工活動同時進行,即Qtmax=3.

模型中的其余參數取值如下:各項修理活動的費用取1～100間的均勻隨機數mca～U[1,100];考慮到同一類維修活動的周期會依據線路在路網中的重要程度有所不同,文中干線(l1、l2、l3、l4)上各項維修活動的周期取2～26之間的均勻隨機數La～U[2,26],非干線(l5、l6)上對應維修活動的周期略長,為La+3;各項維修活動距離最近一次執(zhí)行的時間取0～La之間的均勻隨機數Ga～U[0,La];各項施工活動最早可能開始時間取1～52之間的均勻隨機數ESp～U[1,52],最晚可能開始時間取ESp～(52-ESp)之間的均勻隨機數LSp～U[ESp,52-ESp],施工持續(xù)時間取1～4之間的均勻隨機數Dp～U[1,4],年度計劃中禁止進行施工的時間段為[1,12]∪[26,32];路網中干線每單位時間的股道占用費用為pcli=75,li∈{l1、l2、l3、l4},非干線每單位時間的股道占用費用為pclj=25,lj∈{l5,l6}.

5.2 模型求解結果

根據5.1節(jié)中的參數取值,利用啟發(fā)式算法求解模型,模型求解的硬件環(huán)境為:Intel(R)Core (TM)2 CUP,主頻1.83 GHz,內存2.00 GB, Windows Server 32位操作系統.求解耗時1分27秒,最優(yōu)年度線路養(yǎng)護維修計劃的費用目標函數值為25 670.7,模型求解結果以圖3的形式展示.圖中垂直方向為路網中每條線路需要安排的修理活動,水平方向為以“周”為單位的計劃時間,灰色實心方框代表活動將在對應的時間安排執(zhí)行.由仿真結果可以看出:各條線路的修理活動都普遍集中,其中,線路l1和l2在同一周內同時安排3項及以上修理活動的周次分別占總計劃時間(H=52)的17.3%和25.0%;這樣,線路中未安排維修計劃的周次得到最大程度的增加,如線路l5和l6中未安排維修的周次分別占總計劃時間(H=52)的65.4%和67.3%.上述編制結果使線路得到充分養(yǎng)護維修的同時,減少了由于養(yǎng)護維修造成的股道占用,增加了股道空閑時間,降低了修理的總成本.

圖3 區(qū)域路網年度線路養(yǎng)護維修計劃時間表Fig.3 Annual maintenance planning timetable for regional railway network

6 研究結論

合理安排線路設備養(yǎng)護維修既能夠保持線路設備完整和質量均衡、延長設備使用壽命,還能最大程度地減少運營支出,提高維修工作效率.因此,為制定最優(yōu)化的線路養(yǎng)護維修計劃,本文以區(qū)域路網下的多條鐵路線路為研究對象,以費用最小化為目標提出了基于整數規(guī)劃的養(yǎng)護維修計劃優(yōu)化模型,主要工作成果總結如下:

(1)模型目標函數考慮了三部分的費用:維修費用、股道占用費用和懲罰費用,通過在單位時間內集中安排維修活動和施工活動,有效減少股道占用時間,優(yōu)化了目標函數,同時,懲罰費用的設置使模型能夠適用于連續(xù)的計劃編制.

(2)模型考慮了路網中維修資源有限,結合現場實際情況,設置了避免多項施工活動集中進行的約束條件及禁止施工的時間范圍,證明合理有效.

(3)根據維修活動按周期執(zhí)行的特點設計了啟發(fā)式算法并求解模型,并通過仿真實驗生成了區(qū)域路網中各線路以“周”為時間單位的年度養(yǎng)護維修計劃.仿真結果表明,該模型計算效率較高,可操作性強,具有較大的實用價值.

本文模型未考慮列車運行計劃與線路養(yǎng)護維修計劃編制之間的相互影響,在下一步研究中將融入列車運行計劃中的相關約束,進一步完善模型.

[1] Higgins A.Scheduling of railway maintenance activities and crews[J].Journal of the Operational Research Society,1998,49:1026-1033.

[2] 許玉德,曾學貴.建立整數型軌道狀態(tài)最優(yōu)綜合維修計劃模型[J].鐵道學報,2003,25(6):85-88.[XU Y D,ZENG X G.Foundation of the optimized comprehensive integral track maintenance plan model [J].Journal of the China Railway Society,2003,25 (6):85-88.]

[3] 周宇,許玉德.基于遺傳算法的軌道狀態(tài)最優(yōu)綜合維修計劃模型改進[J].華東交通大學學報,2005, 22(1):15-20.[ZHOU Y,XU Y D.Designing of optimization track synthetical maintenance plan model based on genetic algorithms[J].Journal of East ChinaJiaotong University,2005,22(1):15-20.]

[4] Vale C,Ribeiro I,Cal?ada R.Integerprogramming to optimize tampinginrailwaytracksaspreventive maintenance[J].Journal of Transportation Engineering, 2012,137(1):123-131.

[5] Miwa M.Mathematicalprogramming model analysis for the optimal track maintenance schedule[R].Japan: Railway Technical Research Institute,2002,43(3): 131-136.

[6] 李雪,吳俊勇,楊媛,等.高速鐵路接觸網懸掛系統維修計劃的優(yōu)化研究[J].鐵道學報,2010,32(2): 24-29.[LI X,WU J Y,YANG Y,et al.Research on optimization of catenary system maintenance schedule for high-speed railways[J].Journal of the China Railway Society,2010,32(2):24-29.]

[7] 陳紹寬,彭宏勤,毛保華,等.基于費用最小的鐵路牽引變電所維修計劃優(yōu)化模型[J].鐵道學報, 2011,32(8):39-44.[CHEN S K,PENG H Q,MAO B H,et al.Optimization model of least-cost-based maintenance schedules for railway traction substations [J].Journal of the China Railway Society,2011,32 (8):39-44.]

[8] 陳紹寬,賈順平,杜鵬,等.基于可靠性最大的鐵路牽引變電所維修計劃優(yōu)化模型[J].交通運輸系統工程與信息,2011,11(3):43-49.[CHEN S K,JIA S P,DU P,et al.Highest reliability-based optimum maintenance scheduling model for traction substations in railways[J].Journal of Transportation Systems Engineering and Information Technology,2011,11 (3):43-49.]

[9] 陳民武,李群湛,解紹鋒.牽引供電系統維修計劃的優(yōu)化與仿真[J].華南理工大學學報(自然科學版), 2009,37(11):100-106.[CHEN M W,LI Q Z,XIE S F.Optimization and simulation of maintenance plan of traction power supply systems[J].Journal of South China UniversityofTechnology(NaturalScience Edition),2009,37(11):100-106.]

[10] 余澤西.基于RCM的鐵路基礎設施維修管理信息系統的設計[J].交通運輸系統工程與信息,2009,9 (2):161-164.[YU Z X.RCM based design for comprehensive maintenance management information system ofrailwayinfrastructure[J].Journalof Transportation Systems Engineering and Information Technology,2009,9(2):161-164.]

[11] Zhao J,Chan AHC,Burrow MPN.Reliabilityanalysis and maintenance decision for railway sleepers using track conditioninformation[J].Journalofthe Operational Research Society,2007,58:1047-1055.

[12] Zhao J,Chan AHC,Burrow MPN.Ageneticalgorithm-based approach for scheduling the renewal of railway track components[J].Proceedings of the Institution of Mechanical Engineers Part F-Journal of Rail and Rapid Transit,2009,223:533-541.

[13] Zhang T,Andrews J,Wang R.Optimal scheduling of track maintenance on a railway network[J].Quality and Reliability Engineering International,2012.

[14] Budai G,Huisman D,Dekker R.Schedulingpreventive railway maintenance activities[J].Journal of the OperationalResearchSociety,2006,57(9): 1035-1044.

[15] Coenraad Esveld.Model railway track(the second edition)[M].MRT-Productions:Zaltbommel,2001: 350-400.

[16] 中華人民共和國鐵道部.鐵路線路修理規(guī)則[S].北京:中國鐵道出版社,2010.[The Ministry of Railways of The People's Republic of China.Repair rules for railwaylines[S].Beijing:ChinaRailway Press,2010.]

Integral Optimization Model for Scheduling Railway Maintenance

GUO Ran,HAN Bao-ming,WANG Fu-tian
(School of Traffic and Transportation,Beijing Jiaotong University,Beijing 100044,China)

Scheduling railway maintenance should guarantee both sufficient maintenance and economic benefit.Therefore,taking regional railway network as research object,this paper develops an optimization model of railway maintenance plan based on integer programming.Considering the constraint of maintenance resources for lines in a regional railway network,the maintenance time and the condition of track possession are used as decision variables,and the minimum total cost of track possession,maintenance and penalty are used as target function in this model.The track possession time is reduced,and the optimal objective achieved finally with scheduling all the maintenance activities clustered.The simulated results based on the heuristic algorithm indicate that the proposed model is strong adaptability and can provide decision support for scheduling annual railway maintenance in a network.

railway transportation;maintenance plan;integer programming;optimization model; heuristic algorithm

U216.2Document code: A

U216.2

A

1009-6744(2013)04-0149-08

2013-01-29

2013-03-15錄用日期:2013-03-25

國家科技支撐計劃(2009BAG12A10).

郭然(1984-),男,山東濟寧人,博士生.

*通訊作者:bmhan@bjtu.edu.cn