多目标最短路径模型及算法  

Model and Algorithm for Shortest Path of Multiple Objectives

作　　者：郝光[1] 张殿业[2] 冯勋省[3] 

机构地区：[1]铁道部经济规划研究院,北京100038 [2]西南交通大学物流学院,四川成都610031 [3]西南交通大学交通运输学院,四川成都610031

出　　处：《西南交通大学学报》2007年第5期641-646,共6页Journal of Southwest Jiaotong University

基　　金：西南交通大学交通运输工程研究生创新实践基地资助项目

摘　　要：为获得满足决策者需要的多目标最短路径问题的有效路径,建立了多目标最短路径模型,并提出了综合k-最短路径算法和多目标格序决策方法的多项式算法.该算法根据决策者可以接受的各单目标的上限,用k-最短路径算法,分别确定各单目标的可行路径集及其交集.再用多目标格序决策方法,比较交集中的有效路径,最终获得决策者满意的路径.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.

关 键 词：多目标 有效路径 k-最短路径 格序决策 模型 算法 

分 类 号：U116.2[交通运输工程]