运费无差异的多品种流交通网络最小费用算法

《运费无差异的多品种流交通网络最小费用算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第４６卷第８期哈尔滨工业大学学报Ｖｏｌ?４６Ｎｏ?８２０１４年８月ＪＯＵＲＮＡＬＯＦＨＡＲＢＩＮＩＮＳＴＩＴＵＴＥＯＦＴＥＣＨＮＯＬＯＧＹＡｕｇ．２０１４运费无差异的多品种流交通网络最小费用算法寇玮华，崔皓莹（西南交通大学交通运输与物流学院，６１００３１成都）摘要：为了解决交通网络应用中多品种流问题，对运送费用无差异的多品种流交通网络进行分析，在借鉴连续最短路算法和Ｆｏｒｄ⁃Ｆｕｌｋｅｒｓｏｎ算法基础上，构造了复合参数和复合指标．基于设定的复合参数、复合指标以及相应的计算规则，构建了多品种流交通网络最小费用流分配算法，通过算例验证了算法

2、的可行性．运费无差异的多品种流交通网络最小费用算法为解决交通运输领域普遍存在的运送费用无差异的多品种流最小费用流问题提供了应用基础．关键词：多品种流；交通网络；最小费用流；复合参数和复合指标；连续最短路算法；Ｆｏｒｄ⁃Ｆｕｌｋｅｒｓｏｎ算法中图分类号：Ｕ１１３文献标志码：Ａ文章编号：０３６７－６２３４（２０１４）０８－０１２２－０７ＡｍｉｎｉｍｕｍｃｏｓｔａｌｇｏｒｉｔｈｍｆｏｒｍｕｌｔｉｃｏｍｍｏｄｉｔｙｆｌｏｗｔｒａｆｆｉｃｎｅｔｗｏｒｋｗｈｉｃｈｈａｓｓａｍｅｃｏｎｖｅｙｃｏｓｔＫＯＵＷｅｉｈｕａ，ＣＵＩＨａｏｙｉｎｇ（Ｓｃｈｏｏ

3、ｌｏｆＴｒａｎｓｐｏｒｔａｔｉｏｎａｎｄＬｏｇｉｓｔｉｃｓ，ＳｏｕｔｈｗｅｓｔＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，６１００３１Ｃｈｅｎｇｄｕ，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｔｏｓｏｌｖｅｔｈｅｍｕｌｔｉｃｏｍｍｏｄｉｔｙｆｌｏｗｐｒｏｂｌｅｍｉｎｔｒａｆｆｉｃｎｅｔｗｏｒｋ，ｔｈｉｓｐａｐｅｒａｎａｌｙｓｅｓｔｈｅｍｕｌｔｉｃｏｍｍｏｄｉｔｙｆｌｏｗｔｒａｆｆｉｃｎｅｔｗｏｒｋｗｉｔｈｓａｍｅｃｏｓｔ，ａｎｄｂｕｉｌｄｓｔｈｅｃｏｍｐｏｓｉｔｅｐａｒａｍｅｔｅｒｓａｎｄｃｏｍｐｏｓｉｔｅｉｎｄｉｃａｔｏｒｓｏｎａｃｃｏｕｎｔｏｆｔｈｅ

4、ｓｕｃｃｅｓｓｉｖｅｓｈｏｒｔｅｓｔｐａｔｈａｌｇｏｒｉｔｈｍａｎｄｔｈｅＦｏｒｄ⁃Ｆｕｌｋｅｒｓｏｎａｌｇｏｒｉｔｈｍ．Ｂａｓｅｄｏｎｔｈｅｃｏｒｒｅｓｐｏｎｄｉｎｇｃａｌｃｕｌａｔｉｏｎｒｕｌｅｓｏｆｃｏｍｐｏｓｉｔｅｐａｒａｍｅｔｅｒｓａｎｄｃｏｍｐｏｓｉｔｅｉｎｄｉｃａｔｏｒｓ，ｔｈｉｓｐａｐｅｒｂｕｉｌｄｓａｍｉｎｉｍｕｍｃｏｓｔｆｌｏｗａｌｇｏｒｉｔｈｍｆｏｒｍｕｌｔｉｃｏｍｍｏｄｉｔｙｆｌｏｗｔｒａｆｆｉｃｎｅｔｗｏｒｋａｎｄｔｈｅｆｅａｓｉｂｉｌｉｔｙｏｆｔｈｉｓａｌｇｏｒｉｔｈｍｉｓｖｅｒｉｆｉｅｄｂｙａｎｅｘａｍｐｌ

5、ｅ．Ｔｈｉｓａｌｇｏｒｉｔｈｍｐｒｏｖｉｄｅｓｔｈｅｂａｓｉｓｔｏｓｏｌｖｅｔｈｅｐｒｏｂｌｅｍｏｆｍｕｌｔｉｃｏｍｍｏｄｉｔｙｆｌｏｗｍｉｎｉｍｕｍｃｏｓｔｆｌｏｗｗｉｔｈｓａｍｅｃｏｓｔｗｈｉｃｈｉｓｑｕｉｔｅｗｉｄｅｓｐｒｅａｄｉｎｔｈｅｆｉｅｌｄｏｆｔｒａｎｓｐｏｒｔａｔｉｏｎ．Ｋｅｙｗｏｒｄｓ：ｔｈｅｍｕｌｔｉｃｏｍｍｏｄｉｔｙｆｌｏｗ；ｔｒａｆｆｉｃｎｅｔｗｏｒｋ；ｍｉｎｉｍｕｍ⁃ｃｏｓｔｆｌｏｗ；ｃｏｍｐｏｓｉｔｅｐａｒａｍｅｔｅｒｓａｎｄｃｏｍｐｏｓｉｔｅｉｎｄｉｃａｔｏｒｓ；ｓｕｃｃｅｓｓｉｖｅｓｈｏｒｔｅｓｔｐａｔｈ

6、ａｌｇｏｒｉｔｈｍ；Ｆｏｒｄ⁃Ｆｕｌｋｅｒｓｏｎａｌｇｏｒｉｔｈｍ最小费用流问题是网络与流的核心问题之解决多品种流的最小费用流分配问题．针对交通一，最基本的算法是Ｆｏｒｄ⁃Ｆｕｌｋｅｒｓｏｎ算法，其他的运输领域出现的多品种流交通网络，有必要对其算法还有网络单纯形算法（ｇｒａｐｈｓｉｍｐｌｅｘ最小费用流分配问题作进一步研究，并在其他算ａｌｇｏｒｉｔｈｍ）、松弛算法（ｒｅｌａｘａｔｉｏｎａｌｇｏｒｉｔｈｍ）、消圈法的基础上，构造可行的最小费用流分配算法．算法（ｃｙｃｌｅ⁃ｃａｎｃｅｌｉｎｇａｌｇｏｒｉｔｈｍ）、瑕疵算法（ｏｕｔ⁃ｏｆ⁃本文主

7、要对运送费用无差异的多品种流交通［１－８］ｋｉｌｔｅｒａｌｇｏｒｉｔｈｍ）等等，这些算法都可以解决单网络相关问题进行分析，再基于连续最短路算法一品种流的最小费用流分配问题．在实际的交通（ｓｕｃｃｅｓｓｉｖｅｓｈｏｒｔｅｓｔｐａｔｈａｌｇｏｒｉｔｈｍ）和Ｆｏｒｄ⁃网络应用中，普遍出现了多品种流问题，所以有了Ｆｕｌｋｅｒｓｏｎ算法的思路，构造相应的多品种流交通流变换、流分解、组合应用、多品种流及预流推进网络的最小费用流算法．［９－１３］等新的理论和方法，但这些算法都没有彻底１运送费用无差异的多品种流交通网络分析收稿日期：２０１３－０５－１４

8、．１?１运送费用无差异的多品种流的交通网络引例基金项目：国家自然科学基金资助项目（７１２７１１７６）．作者简介：寇玮华（１９６７—），男，副教授．为了解运送费用无差异的多品种流交通网络通信作者：崔皓莹，４９