基于理想点法的多目标最短路求解算法研究.pdf

《基于理想点法的多目标最短路求解算法研究.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第33卷第3期2016年3月公路交通科技JoumalofHighwayandTransportationResearchandDevelopmentV01．33No．3Mar．2016doi：10．3969／j．issn．1002—0268．2016．03．016基于理想点法的多目标最短路求解算法研究冯树民，吴海月，王弟鑫(哈尔滨工业大学交通科学与工程学院，黑龙江哈尔滨150090)摘要：为了简化多目标最短路算法并解决不同度量单位之间存在的换算问题，利用理想点法的优点，探索出一种多目标最短路问题的简便

2、算法。该算法首先确定理想点，计算各目标的^一最短路路径，这些路径组成一个存在可能解的集合，然后对所有的最短路目标值进行归一化处理，并确定所有路径归一化之后的目标值与理想点之间的加权欧几里得距离，从路径集合中寻找与理想点距离最近的路径，该路径即为多目标最短路问题的满意解。最后，给出了算法分析和算法流程，并通过一个虚拟运输网络对算法进行了验证。结果表明：这种算法能够解决多目标最短路问题中不同目标度量单位之间换算或相互矛盾的问题，并能够把复杂的非线性函数转换为简单的线性函数，是一种简单、有效的算法。关键词：

3、交通工程；多目标最短路；理想点法；七一最短路；加权欧几里得距离中图分类号：u495文献标识码：A文章编号：1002—0268(2叭6)03—0097—05StudyofMuIti-objectiVeShortestPathAIgorithmBasedonldeaIPointSolutionFENGShu-min，WUHai-yue，WANGDi—xin(Sch00lofTransponationScienceandEn百neering，HarbinInstituteofTechnology，Harbi

4、nHeilon自iang150090，China)AbstraCt：Inordertosimplifyt}lemulti—objectiVeshortestpathalgorithmands01VetheconVersionproblembetweendifferentmeasurementunits，weexploredasimplealgorithmofmulti-objectiVeshonestpathproblemtakingadVantageofidealpointmethod．Thealg

5、orithmdetenninestheidealpointsandcalculatestheconespondingobjectiVe尼一shortestpaths，thesepathsconstituteasetofpossiblesolutions．ThenaUtheta曙etvaluesoftheshortestpathsareno瑚alized，andtheweightedEuclideandistancebetweeneachnomalizedtargetValueandidealpoint

6、canbecalculated．Wecan6ndoutthenearestpathtotheidealpointf而mthesetofpaths．‘11latist}lesatisfactorysolutionofmulti—objectiVeshortestpathpmblem．Finally，wegavethealgorithmstepsandVerifiedthealgorithmthroughaVirtualtransportnetwork．Theresultshowsthatthisalgo

7、rithmcansolVetheconVersionandmutualcontradictionproblemsamongmeasuringunitsofdifkrenttargetsonthemulti—objectiveshonestpathpmblem，thealgorithmcanbeabletoconvertcomplexnonlinearfunctiontoasimple1inearfunction，itisasimpleandef亿ctivealgorithm．Keywords：traf

8、ficengineering；multi—objectiVeshonestpath；idealpointmethod；七一shonestpath；weightedF=¨P1ideandistance0引言现实生活中许多问题都属于多目标最优化问题，如工程设计、货物运输、经济规划、金融决策、资源分配等。由于各个目标之间通常存在一些冲突，不可能同时达到最优，因此多目标优化问题一般不存在最优解集，而是一个满意解集，也称为Pareto解集¨2’。多目标最短路问题属