资源描述：
《位势法在交通优化问题中的应用_周康》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第37卷第1期华中科技大学学报(自然科学版)Vol.37No.12009年1月J.HuazhongUniv.ofSci.&Tech.(NaturalScienceEdition)Jan.2009位势法在交通优化问题中的应用1,2111,2周康高婧覃磊同小军(1武汉工业学院数理科学系,湖北武汉430023;2华中科技大学控制科学与工程系,湖北武汉430074)摘要:研究了单源多汇交通优化问题及其重要性质,提出了单源多汇交通优化问题的位势法,该算法以关于费用的最短路程为初始势,以非零流的最小费用流为初始流;用标号法找可行的增广链,在标号过程中若某点不满足平衡要求则由到达该
2、点的可行的增广链增广最小费用流的流量;以弧割为工具,计算最小费用流的势的最大调整量,并修改最小费用流的势.算例证明了算法的正确性和复杂性及算法的有效性.关键词:交通优化问题;最小费用流;位势法;可行的增广链;弧割中图分类号:TP301.6文献标识码:A文章编号:1671-4512(2009)01-0056-05Applicationofpotentialalgorithmtotrafficoptimization1,2111,2ZhouKangGaoJingQinLeiTongXiaojun(1DepartmentofMathematicsandPhysics,Wuh
3、anPolytechnicUniversity,Wuhan430023,China;2DepartmentofControlScienceandEngineering,HuazhongUniversityofScienceandTechnology,Wuhan430074,China)Abstract:Singleorigin-manyterminustrafficoptimizationanditsimportancewerestudied.Potentialalgorithmforsingleorigin-manyterminustrafficoptimizati
4、onisproposed,inwhichinitializationpo-tentialistheshortestdistanceofcostandinitializationflowisanonzerominimumcostflow.Feasibleaugmentingchainwassearchedusinglabelingalgorithm.Intheprocessoflabeling,ifequilibriumconditionofavertexisnotsatisfied,flowvalueoftheminimumcostflowisaugmentedbyf
5、easibleaugmentingchaintothisvertex.Optimaladjustivevalueofminimumcostflowpotentialiscomputedusingarccut.Andminimumcostflowpotentialisamended.Correctnessandcomplexityofthealgo-rithmareobtainedandproved.Andanexampleexplainsfeasibilityofthepotentialalgorithm.Keywords:trafficoptimization;mi
6、nimumcostflow;potentialalgorithm;feasibleaugmentingchain;arccut在交通网络中生产企业或物流公司考虑的一来改善最小费用流的流量,或用DNA计算设计个主要优化问题是如何以最小的成本将一处(产算法,而对于实际生产中经常遇到的单源多汇的地)的企业产品或公司商品运往多处(销地),这就最小费用流问题及其算法讨论较少,因此,直接给是单源多汇最小费用流问题.该问题是一类十分出单源多汇的最小费用流问题的算法是有现实意重要而普遍的交通网络优化问题,在许多生产实义的.在提出的算法中,在初始位势的布局、初始际中都有极强的应用背景,
7、与物流管理供应链、通流的调整和位势的调整等方面均有所创新.信等研究领域有较密切的关系.对单源单汇的最小费用流问题及其应用,文献[1～10]报道了多种1单源多汇的交通优化问题算法,这些算法总体思路是在残量网络中求最短路或增广圈,或寻找满足互补松紧条件的增广链考虑有向单源多汇容量-费用网络D=(V,收稿日期:2008-03-04.作者简介:周康(1965-),男,副教授,E-mail:zhoukang65@tom.com.基金项目:国家自然科学基金资助项目(60574041);湖北省自然科学基金资助项目(2007ABA407);湖北省教育厅重点科研项目(
