The traindriverrecoveryproblem—Asetpartitioningbasedmodelandsolution method

The needtorecoveratraindriverscheduleoccursduringmajordisruptionsinthedailyrailwayoperations. Based ondatafromtheDanishpassengerrailwayoperatorDSBS-togA/S,asolutionmethodtothetrain driver recoveryproblem(TDRP)isdeveloped.TheTDRPisformulatedasasetpartitioningproblem.We define adisruptionneighbourhoodbyidentifyingasmallsetofdriversandtraintasksdirectlyaffectedby the disruption.Basedonthedisruptionneighbourhood,theTDRPmodelisformedandsolved.IftheTDRP solution providesafeasiblerecoveryforthedriverswithinthedisruptionneighbourhood,weconsider that theproblemissolved.However,ifafeasiblesolutionisnotfound,thedisruptionneighbourhoodis expanded byaddingfurtherdriversorincreasingtherecoverytimeperiod.FractionalsolutionstotheLP relaxation oftheTDRPareresolvedwithaconstraintbranchingstrategyusingthedepth-firstsearchof the Branch&Boundtree.TheLPrelaxationoftheTDRPpossessesstrongintegerproperties.Wepresent test scenariosgeneratedfromthehistoricalreal-lifeoperationsdataofDSBS-togA/S.Thenumerical results showthatallbutonetestedinstancesproduceintegersolutionstotheLPrelaxationoftheTDRP and solutionsarefoundwithinafewseconds.