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

《多目标最短路径模型及算法》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第42卷第5期西南交通大学学报Vol.42No.52007年10月JOURNALOFSOUTHWESTJIAOTONGUNIVERSITYOct.2007文章编号:0258-2724(2007)05-0641-06多目标最短路径模型及算法1,232郝光,张殿业,冯勋省(1.铁道部经济规划研究院,北京100038;2.西南交通大学交通运输学院,四川成都610031;3.西南交通大学物流学院,四川成都610031)摘要:为获得满足决策者需要的多目标最短路径问题的有效路径,建立了多目标最短路径模型,并提出了综合k-最短路径算

2、法和多目标格序决策方法的多项式算法.该算法根据决策者可以接受的各单目标的上限,用k-最短路径算法,分别确定各单目标的可行路径集及其交集.再用多目标格序决策方法,比较交集中的有效路径,最终获得决策者满意的路径.关键词:多目标;有效路径;k-最短路径;格序决策;模型;算法中图分类号:U116.2文献标识码:AModelandAlgorithmforShortestPathofMultipleObjectives1,232HAOGuang,ZHANGDianye,FENGXunsheng(1.EconomicsandPlan

3、ningResearchInstituteoftheMinistryofRailwayofChina,Beijing100038,China;2.SchoolofTrafficandTransp.,SouthwestJiaotongUniversity,Chengdu610031,China;3.SchoolofLogistics,SouthwestJiaotongUniversity,Chengdu610031,China)Abstract:Toobtainacceptableshortestpaths,whichm

4、eetthedecision-makersrequirements,foramulti-objectiveshortestpathproblem,amodelandapolynomialalgorithmwerepresented.Thealgorithmisacombinationofak-shortestpathalgorithmandamulti-objectivelattice-orderdecision-makingmethod.Inthealgorithm,asetoffeasiblepathsforea

5、chobjectiveisdeterminedusingthek-shortestpathalgorithmaccordingtotheacceptableupperlimitfortheobjective,andtheintersectionofallthesetsisobtained.Thenefficientpathsintheintersectionarecomparedwitheachotherbythemethodofmulti-objectivelattice-orderdecision-making,a

6、ndthebestoneinthesetisfinallyselectedastheacceptablepath.Keywords:multi-objective;efficientpath;k-shortestpath;lattice-orderdecision-making;model;algorithm[1～6]经典的最短路径问题只涉及单目标优化,考虑最短的旅行时间或距离,已经得到了深入研究.但是,单一的目标函数往往很难准确描述现实生活中的问题.例如,在运输网络的路径选择中,需要同时考虑多个目标,如成本、时间、风

7、险和安全性等.在求解过程中有多个目标函数需要优化,这就拓展出多目标最短路径问题.各目标之间通常存在冲突,针对某个目标具有优势的解对于另一个目标来说可能并不是最优的,导致多目标最短路径问题一般不存在单一的最优解,而只有满意解,也称Pareto解,相应的问题难度也[7]大大增加了.Current等对于多目标最短路径问题的研究现状进行了分类和概括.主要的多目标最短路径求解方法有3类:收稿日期:2006-06-30基金项目:西南交通大学交通运输工程研究生创新实践基地资助项目作者简介:郝光(1972-),男,助理研究员,博士,研

8、究方向为交通运输规划与系统优化,电话:028-86466735,E-mail:haoguang128@163.com642西南交通大学学报第42卷[8](1)效用函数法根据决策者的先验偏好信息,确定相应的效用函数;[9](2)交互式方法在整个问题求解过程中均使用偏好信息;[10](3)产生式方法直接求完整的Pareto优化或近似优