A Two-phase Approach for Real-world Train Unit Scheduling

《A Two-phase Approach for Real-world Train Unit Scheduling》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、ATwo-phaseApproachforReal-worldTrainUnitSchedulingZhiyuanLin·RaymondS.K.KwanAbstractAtwo-phaseapproachforthetrainunitschedulingproblemisproposed.Thefirstphaseassignsandsequencestraintripstotrainunitstemporarilyignoringsomeinfrastructuredetailsattrainstations.Thesolutionsof

2、thefirstphasewouldbenear-operable.Thesecondphasefocusesonsatisfyingtheremainingconstraintswithrespecttodetailedstationlayouts.Real-worldscenariossuchascompatibilityamongtractiontypesandtimeallowancesforcoupling/decouplingactivitiesareconsidered,sothatthesolutionswouldbeful

3、lyoperable.Thefirstphaseismodeledasalargescaleintegermulti-commoditynetworkflow(MCNF)problem.Abranch-and-priceintegerlinearprogrammingapproachisproposed.Preliminaryex-perimentshaveshownthattheapproachwouldnotyieldsolutionsinreasonabletimeforprobleminstancesexceedingabout100

4、0traintrips.Thetraincompanycollaboratinginthisresearchoper-atesover2400traintripsonatypicalweekday.Hence,aheuristichasbeendesignedforcompactingtheprobleminstancetoamuchsmallersizebeforetheILPsolverisapplied.Theprocessisitera-tivewithevolvingcompactionbasedontheresultsfrom

5、thepreviousiterationtherebyconvergingtonearoptimalresults.Thesecondphaseismodeledasamultidimensionalmatchingproblemwithamixedintegerlinearprogramming(MILP)formulation.Keywordstrainunitscheduling·railwayshunting·large-scaleintegerlinearprogramming·columngeneration1Introduc

6、tionAtrainmultipleunit,ortrainunitforshort,isasetoftraincarriageswithitsownbuilt-inengine(s),i.e.itisnotpulledbyaseparatelocomotive,andbeingabletomoveinbothdirectionsonitsown.Atrainunitcanalsobecoupledwithotherunitsofthesameorsimilartypestoincreasethepassengercarryingcapa

7、cityortoredistributetheunitsacrosstherailnetwork.Trainunitschedulingreferstotheplanningofhowtimetabledtraintrips(orsimplytrains)inoneoperationaldayaresequencedtobeoperatedbyeachtrainunitinthecompany’sfleet.Usuallyperformedafterthetimetablehasbeenfixed,andfollowedbyasubseque

8、ntcrewschedulingstage,trainunitschedulingisalsocalledtrainunitdiagrammingwhereaunitdiagramisasta