匈牙利方法在铁路列车乘务组分派问题中的应用

26320076()JournalofLanzhouJiaotongUniversity(NaturalSciences)Vol.26No.3Jun.2007:1001O4373(2007)03O0055O033(,730070):,,,..:;;:U292:A0,,,,,:,,,,,,.1:minZ=6ni=16nj=1cijxij(1)s.t6ni=1xij=1(j=1,2,,n)6nj=1xij=1(i=1,2,,n)xij=01(i,j=1,2,,n)xij=1,ij;0,ij.2,(),;,,(),.3(),minZ=6ni=16nj=1cijxijC,C,CC.C0(n0),n0,0xij,,,C,0.,ui,cij=cij-ui;vj3:2006O10O27:(1982O),,,.©1994-2009ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.()26,cij=cij-ui-vj.:CC;n0,CC.1),(Konig).[cij]()ui(),()vj(),[cij],cij=cij-ui-vj,[cij][cij].[3].2),,(Konig).C0,0,C0()C.,n,..4AB5,1,,(AB),(BA).,AA.,2h,A5,BRA(,A16,B16h,19B,615B).,B5,ARB,5,.1Fig.1Passengertrainschedule246810RA=[aij]=135792225681316192427131621234111419212710151722246810RB=[bij]=13579201712105223181611522119147423211611832520:RARB,,12A,Ba12=22h;B,Ab12=20h,12B.,RARB,cij=min{aij,bij},C(cijABijAB).246810c=[cij]=1357920B17B6A8A5B2B19A18B2A7A5B2B21A,B19B4A7B4B19A21A,B2A7A8B3B17A20B(C).:1:C.1)C:Ciui(),,C.2)C:Cjvj(),,C.C=2017685219182752211947419212783172065©1994-2009ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.=151213001716053019172521719045014172:C().n,xij=1,,(C).n,3..C=151213(0)(0)1716053(0)19172521719045(0)14173:C.(),,1);2);3).C=[cij],2.1(16h):1Tab.1Optimumdistribution1,103,25,47,49,6BBBBB/h52243:[1].[J].,2001,(6):18O20.[2],,.[M].:,2006.[3],,,.[M].:,1996.ApplicationofHungaryAlgorithminAssignmentProblemofTrainCrewLiWenhui(SchoolofTrafficandTransportationEngineering,LanzhouJiaotongUniversity,Lanzhou730070,China)Abstract:ThebasicthoughtandprincipleofHungarysmethodareelaborated,combiningthefactualcandi2tionoftherailroadtrainmovement.Accordingtotheessentialfeatureofthetraincrewassignment,themathematicalmodelisestablishedandthesolutionofHungarysmethodiscarriedout.Thismethodismoreconvenientthanthegenericsimplemethodandtablemanipulationmethod.Keywords:Hungarysmethod;trainmovement;assignmentproblem75©1994-2009ChinaAcademicJournalElectronicPublishingHouse.Allrightsreserved.