一种求解双目标最短路的方法

:1001-4098(2005)07-0113-05魏　航1,蒲　云2,李　军1(1.,　610031;2.,　610031)　:在运输过程中,有时往往需要考虑两个目标。由于在实际的求解过程中,往往很难获得两个目标同时最小的绝对最短路径。通常,只要找到满足决策者需要的有效路径就可以了。提出了一种利用k-最短路算法来获得双目标最短路的有效路径的算法,并对算法的复杂性进行了分析。最后给出了一个应用算例。:最短路;双目标;有效路径;k-最短路:U116.2　　　:A1　引言(SP),,2050Dijkstra[1],2060Floyd,2070～80。2090,、、,,。,[2-7]。,,、。,,、、、,,。Current[8]。,,。,,。,NP,。,,J.Current,C.Revelle,J.Cohon[9]J.Coutinaho-Rodrigues,J.Climcao,J.Current[10],。,,,,Hansen[11],ClimacoMartins[12]。k-,,,。,,。2　问题描述及模型,,:G=(N,E),E,N,|N|=n,|E|=m.,z1(i,j)z2(i,j)i(O),i(O)j(D)12,z1(i,j)z2(i,j)。OD。,:yij=1,　ij0,　,(BOSP):237(139)　　　　　　　系　统　工　程Vol.23,No.720057　　　　　　　　　　　　　SystemsEngineeringJul.,2005　:2005-04-16:(70471039);(20030613016):(1976-),,,,:,;(1962-),,,,:,;(1967-),,,,:,。min　Z1=∑(i,j)yijz1(i,j)　　　　　　　　　(1)min　Z2=∑(i,j)yijz2(i,j)(2)s.t.　∑jyij-∑jyji=1,-1,0,i=Oi=D　i∈N(3)　　　∑jyij≤1,　i∈N(4)　　　yij∈{0,1},　(i,j)∈E(5)3　方法分析。1　h1h2OD。Z1(h1)≤Z1(h2),Z2(h1)≤Z2(h2),,Pareto,h1h2.2　hOD,Z(h)ODh,Z(h)=(Z1(h),Z2(h))。ODh′h,h′∈K,KBOSP,hBOSP。3　h*1ODZ1,Z1(h*1)h*1Z1,h*2ODZ2,Z2(h*2)h*2Z2,(Z1(h*1),Z2(h*2))BOSP。h*1=h*2,h*=h*1=h*2,h*BOSP。1　h*1∈i*1,h*2∈i*2,,i*1ODZ1,i*2ODZ2。,(Z1(h*1),minZ2(h*1))(minZ1(h*2),Z2(h*2)),h*1、h*2BOSP。　(Z1(h*1),Z2(h*1)),h*1BOSP。,hZ1(h*1)≥Z1(h)minZ2(h*1)≥Z2(h),。,h*1ODZ1,Z1(h*1)≥Z1(h),h∈i*1,Z1(h*1)=Z1(h)。minZ2(h*1)Z2(h),。,h*2。,h*,。,Hasen[11],ClimacoMartins[12],,,;,,,()。,,。,,。Dijstra,Z*1Z*2.12,12upZ*1upZ*2.k-[13]1upZ*1K12upZ*2K2,K*.K*,,12。,1,AZ1,BZ2。,K*EFGH。,Z1Z2。1　,K*C.,:(1)|C|=0;(2)|C|=1;(3)|C|1。(1),,12,,;(2),C,,12,,;(3),1,,,12,,。2　CBOSP。　hCBOSP,hi∈K,Z1(hi)≤Z1(h),Z2(hi)≤Z2(h),,KBOSP。Z1(h)≤upZ*1,Z2(h)114　　　　　　　　　　　　　　　　　　　　　2005≤upZ*2,Z1(hi)≤upZ*1,Z2(hi)≤upZ*2,。,hi∈C,hC。。4　算法,,:1:DijstraG=(N,E)12h*1h*22:h*1=h*2,,33:Z*1Z*2h*1h*212,12upZ*1upZ*24:k-1upZ*1K15:k-2upZ*2K26:K1K2K*7:K*C8:(1)|C|=0,9;(2)|C|=1,,;9;(3)|C|1,,;99:12upZ*1upZ*2,43　O(n3+n2)。　,DijstraZ1Z2O(n2)。,k-Z1Z2K1K2O(n3)。,,。,O(n3)。,,O(n3+n2)。5　算例,。2OD,121。OD,。2　1　12(O,1)(O,2)(O,3)(1,3)(2,3)(2,4)(3,5)(1,6)(5,4)(5,6)(4,D)(5,D)(6,D)130506020151810505582552609580355545206054025505　　,Dijstra,12,70125。,12,C,2。2,12,。upZ*1=80upZ*2=125,|C|=0,。,12,upZ*1=85upZ*2=130,|C|=2,,12。upZ*1=85upZ*2=150,|C|=3,,1,2,3。upZ*1=90upZ*2=160,|C|=4,,1,2,34。,12,。,1157　　　　　　　　　　　　,:。2　121212(80,125)--(85,130)1:O,3,5,4,D(83,130)2:O,1,6,D(85,125)(85,150)1:O,3,5,4,D(83,130)2:O,1,6,D(85,125)3:O,1,3,5,4,D(73,145)(90,160)1:O,3,5,4,D(83,130)2:O,1,6,D(85,125)3:O,1,3,5,4,D(73,145)4:O,1,3,5,6,D(70,160)(90,160)1:O,3,5,4,D(83,130)2:O,1,6,D(85,125)3:O,1,3,5,4,D(73,145)4:O,1,3,5,6,D(70,160)6　结束语,。k-。,,k-,,。,,,,。:[1]　DijkstraEW.Anoteontwoproblemsinconnectionwithgraphs[J].NumerMath,1959,1:269～271.[2]　CaiX,KloksT,WongCK.Timevaryingshortestpathproblemsalgorithmforproblemswithconstraints[J].Networks,1998,31193～204.[3]　IrinaLoachimSG.Adynamicprogrammingalgorithmfortheshortestpathproblemwithtimewindowsandlinearnodecode[J].Networks,1998,31193～204.[4]　MirchandaniP.AsimpleO(n2)algorithmfortheall-pairsshortestpathproblemonanintervalgraphnetworks[Z].1996,27215～217.[5]　BurtonD,Ph.TointL.Onaninstanceoftheinverseshortestpairsproblem[J].MathematicalProgramming,1992,5345～61.[6]　YuG,YangJ.Ontherobustshortestpathproblem[J].Computer&Ops.Res.,1998,25457～468.[7]　PelegrimB,FernqndezP.Onthesum-maxbi-criterionpathproblem[J].Computer&Ops.Res.,1998,251043～1054.[8]　CurrentJ,MarshM.Multiobjectivetransportationnetworkdesignandroutingproblems:taxonomyandannotation[J].EuropeanJournalofOperationalResearch,1993,65:1～15.[9]　CurrentJ,RevelleC,CohonJ.Aninteractiveapproachtoindentifythebestcompromisesolutionfortwoobjectiveshortestpathproblems[J].Computer&Ops.Res.,1990,17(2):187～198.116　　　　　　　　　　　　　　　　　　　　　2005[10]　Coutinaho-RodriguesJ,ClimcaoJ,CurrentJ.Aninteractivebi-objectiveshortestpathapproach:searchforunsupportednondominatedsolutions[J].Computer&Ops.Res.,1999,26:789～798.[11]　Hansen.Bicriterionpathproblems[A].FandelG,GalT.Multiplecriteriadecisionmakingtheoryandapplication[C].1979:109～127.[12]　Climaco,Martins.Abicriterionshortestpathalgorithm[J].EuropeanJournalofOperationalResearch,1982,11:399～404.[13]　ChenYL.Analgorithmforfindingthekquikestpathinanetwork[J].Computer&Ops.Res.,1992,20(1):59～65.AnApproachtoBiobjectiveShortestPathWEIHang1,PUYun2,LIJun1(1.SchoolofEconomicsandManagement,SouthwestJiaotongUniversity,Chengdu610031,China;2.GraduateSchool,SouthwestJiaotongUniversity,Chengdu,610031,China)Abstract:Ingeneral,twoobjectiveshouldbeconsideredinthetransportation.Itishardlytogetthepathwithminizationoftwoobjectives.Tothedecision-maker,itisagoodchoicetogetthenondominatedsolution.Thepaperdevelopedaalgorithmforthetwoobjectivesshortestpathbyusingthek-shortestpathalgorithm.Thecomputationalcomplexityofthealgorithmwasdiscussed.Atlast,acasewasstudied.Keywords:ShortestPath;Biobjective;NondominatedPath;k-shortestPath1177　　　　　　　　　　　　,: