基于k短路径算法的多目标最短路径算法

243/420118JournalofChangzhouInstituteofTechnologyVol．24No．3/4Aug．20112011-05-261986—。k730070k。k。Vague。kVagueO122．6A1671－0436201103/04－0025－03AlgorithmforShortestPathofMulti-objectivesBasedonkShortParthAlgorithmKANGTai-pingZHANGXiao-gangWANGZong-fengHEShang-luSchoolofMathematicsPhysicsandSoftwareEngineeringLanzhouJiaotongUniversityLanzhou730070AbstractToobtainamulti-objectiveshortestpathwhichmaymeetthedecision-maker'srequire-mentsthispaperpresentsthebasisofsyclicresearchkshortestpathandconstructsapolynomialalgorithmtointersectthenewset．Aftereveryroundofthekshortestpathsearchingthealgorithmpreducesamulti-objectiveshortestpathoralternativepathbytheintersection．Whenanumberofalternativepathsareavaila-blethemethodofprojectionofVaguesetanddistanceisused．Theoptionalschemesaresequencedaccord-ingtotheevaluationsizethusthebestoptimalsolutionmaybeobtained．Keywordsmulti-objectivekshortestpathVagueset01、、、、、。。。。Pareto2－3。、、。4k5k。12011G=NENE|N|=n|E|=m。Aqq=12…QqAqijq=12…QijqOD。1r*qq=12…QODqr*qq=12…QRqq=12…Q。∩Qq=1Rq≠Φr*∈∩Qq=1Rq。2k———p1p2…pkv1vkWp1≤Wp2≤…≤Wpkpv1vpp1…pkWp≥Wpkpkv1vk。21DijstraG=NEqq=12…QR1qq=12…Q。2∩Qq=1R1q≠Φ。3。3qq=12…QkRkq=Rkq∪Rk－1qk=23…q=12…Q∩Qq=1Rkq∩Qq=1Rkq≠Φ43。4∩Qq=1Rkq=1。∩Qq=1Rkq＞16Vague。31ST1。31233。ST。1ST1/km//%SA521200．20SB481000．38SC45840．15AB42300．40CB29700．60AF40600．50AE35500．45BE38900．10BD23300．80CD42300．20FE60750．70DE31500．35FT48300．45ET40800．50DT502000．40①k2。Dijstra1、2、3SBDT、SAFT、SCDR∩3q=1Rq=Φ。②qkRkq∩3q=1Rkq4R4qR41=SBDTSBETSAETSCDTR42=SAFTSCDETSAETSBDETR43=SCDTSCBETSBETSAET∩3q=1R4q=SAET。③16Vague。623/4k5R5qR51=SBDTSBETSAETSCDTSAFTR52=SAFTSCDETSAETSBDETSBETR53=SCDTSCBETSBETSAETSAFT2k/kmk/k/%k1S－B－D－T1215S－A－F－T2104S－C－D－T0．752S－B－E－T1269S－C－D－E－T2448S－C－B－E－T0．93S－A－E－T1273S－A－E－T2502S－B－E－T0．984S－C－D－T1376S－B－D－E－T2603S－A－E－T1．155S－A－F－T1402S－B－E－T2705S－A－F－T1．156S－B－D－E－T14213S－A－B－D－E－T3109S－C－D－E－T1．27S－C－B－D－T1474S－C－D－T31412S－A－B－E－T1．28S－C－B－E－T15211S－C－B－D－E－T3141S－B－D－T1．589S－C－D－E－T15812S－A－B－E－T32010O－F－L－D1．810O－F－L－D1678S－C－B－E－T32414S－A－F－E－T1．911S－C－B－D－E－T1681S－B－D－T3307S－C－B－D－T1．9512S－A－B－E－T17214S－A－F－E－T3356S－B－D－E－T2．0313S－A－B－D－E－T18810O－F－L－D38013S－A－B－D－E－T2．2514S－A－F－E－T1927S－C－B－D－T38411S－C－B－D－E－T2．4∩3q=1R5q=SAETSBETSAFTAii=123A1=SAETA2=SBETA3=SAFT3Cjj=123VagueA*=11VagueA1C135[]()35C235[]()35C3({25[])}25A2C145[]()45C215[]()15C3({15[])}15A3C115[]()15C21[](){1C3[(15])}15①DAiA*AiJAiA*AiZAiA*Ai。DA1A*=槡8215JA1A*=槡7215ZA1A*=815DA2A*=槡2215JA2A*=槡3215ZA2A*=615DA3A*=槡7215JA3A*=槡8215ZA3A*=715②ZA1A*＞ZA3A*＞ZA2A*A1＞A3＞A2A1k。A14。Vague5A2A3VagueA3A2。33723/4GPON。ONU。OLTONU。QoS。1．GPONDBAJ．2005170－74．2．GPOND．2007．3．GPONJ．2005658－59．4．GPONQoSJ．2006317－19．櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚櫚274k。kk。Vaguek。1．M．2000119－143．2MartinsEQVSantosJLE．TheLabelingAlgorithmfortheMultiobjectiveShortestPathProblemR．CISUCTechnicalRe-portTR99/005CoimbraPortugalUniversityofCoimbra1999．3GuerrieroFMusmannoR．LabelCorrectingMethodstoSolveMulticriteriaShortestPathProblemsJ．JournalofOptimizationTheoryandApplications20013589－613．4．J20075641－645．5．M．2005238－241．6．VagueJ．2009219－22．33