Model and Algorithm for Shortest Path of Multiple Objectives
-
摘要: 为获得满足决策者需要的多目标最短路径问题的有效路径,建立了多目标最短路径模型,并提出了综合k-最短路径算法和多目标格序决策方法的多项式算法.该算法根据决策者可以接受的各单目标的上限,用k-最短路径算法,分别确定各单目标的可行路径集及其交集.再用多目标格序决策方法,比较交集中的有效路径,最终获得决策者满意的路径.Abstract: To obtain acceptable shortest paths,which meet the decision-maker’s requirements,for a multi-objective shortest path problem,a model and a polynomial algorithm were presented.The algorithm is a combination of a k-shortest path algorithm and a multi-objective lattice-order decision-making method.In the algorithm,a set of feasible paths for each objective is determined using the k-shortest path algorithm according to the acceptable upper limit for the objective,and the intersection of all the sets is obtained.Then efficient paths in the intersection are compared with each other by the method of multi-objective lattice-order decision-making,and the best one in the set is finally selected as the acceptable path.
-
Key words:
- multi-objective /
- efficient path /
- k-shortest path /
- lattice-order decision-making /
- model /
- algorithm
-
DIJKSTRA E W.A note on two problems in connection with graphs[J].Numer.Math.,1959,1:269-271.[2] CAI X,KLOKS T,WONG C K.Time varying shortest path problems algorithm for problems with constraints[J].Networks,1997,29:141-149.[3] IRINA LOACHIM S G.A dynamic programming algorithm for the shortest path problem with time windows and linear node costs[J].Networks,1998,31:193-204.[4] BURTON D,Toint L.On an instance of the inverse shortest pairs problem[J].Mathematical Programming,1992,53:45-61.[5] YU G,YANG J.On the robust shortest path problem[J].Computer Ops.Res.,1998,25:457-468.[6] PELEGRIM B,FERNQNDEZ P.On the sum-max bi-criterion path problem[J].Computer Ops.Res.,1998,25:1 043-1 054.[7] CURRENT J,MARSH M.Multiobjective transportation network design and routing problems:taxonomy and annotation[J].European Journal of Operational Research,1993,65:1-15.[8] BRUMBAUGH S J,SHIER D.An empirical investigation of some bicriterion shortest path algorithms[J].European Journal of Operational Research,1989,43:216-224.[9] GRANATA J,GUERRIERO F.The interactive analysis of the multicriteria shortest path problem by the reference point method[J].European Journal of Operational Research,2003,151:103-118.[10] MARTINS E Q V.On a multicriteria shortest path problem[J].European Journal of Operational Research,1984,16:236-245.[11] AZVEDO J,MARTINS E Q V.An algorithm for the muhiobjective shortest path problem on acyclic networks[J].Investigacao Operational,1991,11:52-69[12] MARTINS E Q V,SANTOS J L E.The labeling algorithm for the multiobjective shortest path problem[R].CISUC Technical Report TR99/005,Coimbra,Portugal:University of Coimbra,1999.[13] GUERRIERO F,MUSMANNO R.Label correcting methods to solve multicriteria shortest path problems[J].Journal of Optimization Theory and Applications,2001,111 (3):589-613.[14] SKRIVER A J V,ERSEN KA.A label correcting approach for solving bicriterion shortest-path problems[J].Computers and Ops.Res.,2000,27:507-524.[15] CHEN Y L.An algorithm for finding the k quickest path in a network[J].Computer Ops.Res.,1992,20(1):59-65.[16] EPPSTEIN D.Finding the k shortest paths[J].SIAM Journal on Computing,1999,28 (2):652-673.[17] YEN J Y.Finding the k shortest loopless paths in a network[J].Management Science,1971,17 (11):712-716.[18] 郝光,牟奇峰,张殿业,等.基于格序偏好的模糊多目标决策方法[J].西南交通大学学报,2006,41(4):517-521.HAO Guang,MOU Qifeng,ZHANG Dianye,et al.Approach of fuzzy multiple objective decision making based on latticeorder preference[J].Journal of Southwest Jiaotong University,2006,41 (4):517-521.
点击查看大图
计量
- 文章访问数: 1893
- HTML全文浏览量: 87
- PDF下载量: 1052
- 被引次数: 0