高速铁路客运网络列车开行方案优化模型

186201012ChineseJournalofManagementScienceVol.18,No.6December,2010:1003-207(2010)06-0051-08高速铁路客运网络列车开行方案优化模型蓝伯雄,吴李知(清华大学经济管理学院,北京100084):,,,,:;;;:U2924:A:2010-06-08;:2010-11-30:-(2008X010):(1950-),(),,,,:1,,,,,(),,,,(),,,,,,,,2020,,,,,Bussieck(1997)[1],Claessens(1998,2004,2004,2006)[2-5],,,53Chang(2000)[6](,),Borndorfe(2004)[7],,Bussieck(2004)[8]Schobel(2005)[9],,DantzigWolfeBorndorfe(2008)[10],,,;,;,(2000)[11],O-D,,,(2006)[12],,(2007)[13],,,:(1)OD;(2),;(3)-232,,,,,,,,OD,OD,OD,,ODOD,,,,,:,:(1);(2);(3),,:(1);(2),;(3),,(4),,:(1),;(2),,,,,,,,,,,,3,,!52!2010,31()(),:I-,;II;III,:,;,III;,,,,(),,:,,,32(1)s:(station),s∀S,Se:(edge),,e∀E={(i,j)|i,j∀S}k:,k∀K,Kl:(leg),,l=(i,j),i,j∀Sp:O-D,p=(o,d),o,d∀S(2)Ap:mp#np,pOD()-,O-D();mppOD,np,1OD1-4OD,231OD,14(x14),3(x13,x343),2(x12,x242),234,6(mp=4,np=6),A:x12x13x14x23x24x341234111-111-1-11-1-1-1Dp:pODp:pODk:kpODBp:AppODAp,ApBp,bpkpODk,Bp=[bpk],np#|p|Qk:kODkqkpkpOD,pODk,Qk=[qkp],mk#|k|,mkkG:gekke,G=[gek],m#|K|,me:e,=(1,∃,m)!k:k,mk,kmkfk:k∀sp:∀tr:,∀trp=(0,∃,0,∀tr,∃,∀tr)np,mp-1,!53!6:Pk:k,mk(3):xpij:pOD(ij)xp=(xp12,xp13,∃),pOD()spp:pOD,ykp:kpOD()ykkOD,yppOD,xpijykpzk:k()33,,:(1):(---)max%kPkQkyk-%kfkzk-∀sp%pspp-%p∀trpxp(1)(2):xp=%k∀pbpkykpp(2)Apxp+#pspp=#pDpp(3)%p∀kqkpykp&!kzkk(4)%kgekzk&ee(5)zk=zk∋k,k∋k(6)xpij,spp,ykp(0,zk∀Z+k,p(7),#p=(1,0,∃,0,-1)mp(2)xy;(3),,;(4);(5)(6)(7),xpijypk,ABQ01,,xpijypk:(1),(2)-,,(3)z,,,(4),,(5)ABQODOD,,,34xp=Bpyp,:max%kPkQkyk-%kfkzk-∀sp%pspp-%p∀sppBpyp:max%p%k(Pkqkp-∀trpbpk)ykp-%kfkzk-%p∀spspp(8)st%k∀pApbpkykp+#pspp=#pDpp(9)%pqkpykp-!kzk&0k(10)%kgekzk&ee(11)zk=zk∋k,k∋k(12)spp,ykp(0,zk∀Z+k,p(13)441OD,,,:(1),stts,,!54!20101(2),I,21IIIIIII400~700II100~30050~150III50~15020~500,10~20(3),,I,(60,80,100),IIIIII32()()()()600300001000386003000010003570020000800253IIIIII6012,20%20,333%28,467%8012,15%28,35%40,50%10012,12%36,36%52,52%(4)50150,40(5)50;20(6)OD(7)Intel-Core(TM)3GHz321G;MicrosoftWindowsXP,ILOGOPLDevelopmentStudio50ILOGCplex101(8)1%30,()42,10,S=(60,80,100),SO-DPK4,,6080100,645,,,30,,,5(!)();;,,,,;,;,;,,;,,678,,,4(10)OD()160314336316388913691171002612036%2805525364287260400413654721304049%31008575383452411602095121691493098%!55!6:5(10)16014826467047913%743%792%28017139786924908%736%681%3100174534132595896%701%636%660(10)S569413025397883997%604583159142103117958%598711454455556806%780(10)S64167157518132777998%8050115199617142314951%5711514436170621776%8100(10)S73227188184170839995%10050172256246183607919%5113518811499009764%,,;,;,,,,,,,,,,,,,,,ykp,,,,,5,,,,,,u∀{1,∃,U},k-uku,u!fk,u!!k:ykup:k-upOD(),ykuk-uOD,yppODzku:k-u():max%p%k%u(Pkqkp-∀trpbpk)ykup-%k%uufkzku-%p∀spspp(14)s.t.%k∀p%uApbpkykup+#pspp=#pDpp(15)%pqkpykup-u!kzku&0k,u(16)%k%ugekzku&ee(17)zku=zku∋k-u∋k-u(18)spp,ykup(0,zku∀Z+k,u,p(19)460105,(U=2),9,,20%;!56!201010%;,33%96%960/026864720929%731%804%234/37072741896%937%732%126269882907%749%847%238/36475226878%964%677%225863638902%751%793%226/35268337862%959%735%326863761902%722%828%222/35672011869%931%785%425472245909%764%782%234/34481860880%950%645%26266849910%743%811%230/35774035877%948%715%6,,,,,-,,OD,,,,,,:(1),;(2),(3),,:[1]Bussieck,M.R.,Kreuzer,P,Zimmermann,U.T..Optimallinesforrailwaysystems[J]EuropeanJournalofOperationalResearch,1997,96(1):54-63[2]Claessens,M.T.,VanDijk,N.M.,Zwaneveld,P.J..Costoptimalallocationofrailpassengerlines[J].EuropeanJournalofOperationalResearch,1998,110(3):474-489[3]Goossens,J.W..Modelsandalgorithmsforrailwaylineplanningproblems[D]MaastrichtUniversity:Maastricht,2004.[4]Goossens,J.W.,VanHoesel,S.,Kroon,L.G..Abranchandcutapproachforsolvingrailwayline-planningproblems[J]TransportationScience,2004,38:379-393[5]Goossens,J.W.,VanHoesel,S.,Kroon,L.G..Onsolvingmulti-typelineplanningproblems[J]EuropeanJournalofOperationalResearch,2006,168(2):403-424[6]Chang,Y.H.,Yeh,C.H.,Shen,C.C..Multiobjectivemodelforpassengertrainservicesplanning:Applicationtotaiwan)shigh-speedrailline[J]TransportationResearchPartB,2000,34:91-106[7]Borndorfer,R.,Grotschel,M.,Pfetsch,M.E.Apath-basedmodelforlineplanninginpublictransport[R]TechnicalReport,ZIPBerlin,2004:05-18.[8]Bussieck,M.R.,Lindner,T.,Lubbecke,M.E.Afastalgorithmfornearcostoptimallineplans[J]MathematicalMethodsofOperationsResearch,2004,59:205-220[9]Schbel,A.,Scholl,S.Lineplanningwithminimaltravellingtime[R]UniversityofGottingen,Germany,2005[10]Borndorfer,R.,Grotschel,M.,Pfetsch,M.E.Modelsforlineplanninginpublictransport[J]LectureNotesinEconomicsandMathematicalSystems,2008,600(4):363-378[11],[J],2000,22(5):1-5[12][D],2006[13].[D],2007.!57!6:OptimizationModelforLinePlanninginRailPassengerTransportNetworkLANBoxiong,WULizhi(SchoolofEconomicsandManagement,TsinghuaUniversity,Beijing100084,China)Abstract:Thelineplanningproblemisoneofthefundamentalelementsinstrategicplanningofpublicrailtransport.Itconsistsinfindinglinesandcorrespondingfrequenciesintransportnetworksuchthatagiventraveldemandcanbesatisfied.Sofar,mostofthemodelsintheliteratureaimtominimizethecostsortomaximizethenumberofdirecttravelers.Inthispaperwepresentanewapproachmaximizingtheoperator)sprofit,whileensuringthenatureofitspublicservic