基于成对可替代子路径的交通分配改进算法.pdfVIP

第 １１卷　第５期 铁道科学与工程学报 Ｖｏｌｕｍｅ１１　Ｎｕｍｂｅｒ５ ２０１４年 １０月 ＪｏｕｒｎａｌｏｆＲａｉｌｗａｙＳｃｉｅｎｃｅａｎｄＥｎｇｉｎｅｅｒｉｎｇ Ｏｃｔｏｂｅｒ２０１４ ① 基于成对可替代子路径的交通分配改进算法 苏焕银，史峰，徐光明 （中南大学交通运输工程学院，湖南长沙４１００７５） 摘　要：以Ｂａｒ－Ｇｅｒａ设计的基于成对可替代子路径（ＰＡＳ）的交通分配算法（ＴＡＰＡＳ）为研究对象，注意到ＴＡＰＡＳ算法为了 追求最大熵用户均衡交通分配，存储了大量ＰＡＳ并从中选择ＰＡＳ集合进行流量转移。由于很多交通分配问题更加专注于 提高算法的收敛速度和其简易性，将算法的核心操作仅限于当前新构建的有效ＰＡＳ（不再存储ＰＡＳ集合），在新构建的ＰＡＳ 上转移流量以均衡子路径费用，在相关起点之间均衡路径流量比例。设计包括有效ＰＡＳ构建子算法、基于ＰＡＳ的流量转移 子算法和基于ＰＡＳ在相关起点之间均衡路径流量等比例分配子算法。通过数值试验算例分析，结果表明：相比原算法，仅 基于当前新构建ＰＡＳ上进行流量转移的交通分配改进算法的收敛效率不会降低，同时，改进后的算法结构更简单，编程工 作量更小，对部分案例来说更适于应用。 关键词：成对可替代子路径；交通分配算法；相关起点；比例均衡 中图分类号：Ｕ４９１　　　文献标志码：Ａ　　　文章编号：１６７２－７０２９（２０１４）０５－００５２－０６ Ｍｏｄｉｆｉｅｄｔｒａｆｆｉｃａｓｓｉｇｎｍｅｎｔｂｙｐａｉｒｅｄａｌｔｅｒｎａｔｉｖｅｓｅｇｍｅｎｔｓ ＳＵＨｕａｎｙｉｎ，ＳＨＩＦｅｎｇ，ＸＵＧｕａｎｇｍｉｎｇ （ＳｃｈｏｏｌｏｆＴｒａｆｆｉｃａｎｄＴｒａｎｓｐｏｒｔａｔｉｏｎＥｎｇｉｎｅｅｒｉｎｇ，ＣｅｎｔｒａｌＳｏｕｔｈＵｎｉｖｅｒｓｉｔｙ，Ｃｈａｎｇｓｈａ４１００７５，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｔｈｉｓｐａｐｅｒｓｔｕｄｉｅｓｔｒａｆｆｉｃａｓｓｉｇｎｍｅｎｔｂｙｐａｉｒｅｄａｌｔｅｒｎａｔｉｖｅｓｅｇｍｅｎｔｓ，ｗｈｉｃｈｗａｓｄｅｓｉｇｎｅｄｂｙＢａｒ－ Ｇｅｒａ．ＴＡＰＡＳｆｏｃｕｓｅｓｏｎａｃｑｕｉｒｉｎｇｔｈｅｅｎｔｒｏｐｙｕｓｅｒ－ｅｑｕｉｌｉｂｒｉｕｍｒｏｕｔｅｆｌｏｗｖｅｃｔｏｒ，ｗｈｉｃｈｎｅｅｄｓｔｏｓｔｏｒｅｖａｓｔ ＰＡＳｓａｎｄｔｈｅｎｓｅｌｅｃｔｓｏｍｅｔｏｓｈｉｆｔｆｌｏｗｓ．Ｓｉｎｃｅｍａｎｙｔｒａｆｆｉｃａｓｓｉｇｎｍｅｎｔａｌｇｏｒｉｔｈｍｓｃｏｎｃｅｎｔｒａｔｅｏｎｉｎｃｒｅａｓｉｎｇｔｈｅ ｒａｔｅｏｆｃｏｎｖｅｒｇｅｎｃｅａｎｄｓｉｍｐｌｉｆｉｃａｔｉｏｎ，ｔｈｉｓｐａｐｅｒｆｏｃｕｓｅｓｏｎｂｕｉｌｄｉｎｇａｎｅｗｅｆｆｅｃｔｉｖｅＰＡＳ，ｓｈｉｆｔｉｎｇｆｌｏｗｓｂｅｔｗｅｅｎ ｓｅｇｍｅｎｔｓｏｆａｎｅｆｆｅｃｔｉｖｅＰＡＳｉｎｏｒｄｅｒｔｏｂａｌａｎｃｅｔｈｅｃｏｓｔｓａｎｄｒｅｄｉｓｔｒｉｂｕｔｉｏｎｏｆＰＡＳｆｌｏｗｓｂｅｔｗｅｅｎｏｒｉｇｉｎｓａｃｃｏｒｄ ｉｎｇｔｏｔｈｅｃｏｎｄｉｔｉｏｎｏｆｐｒｏｐｏｒｔｉｏｎａｌｉｔｙ．ＴｈｅｍａｎａｇｅｍｅｎｔｏｆＰＡＳｓｅｔ，ｉｎｃｌｕｄｉｎｇｓｔｏｒａｇｅａｎｄｅｌｉｍｉｎａｔｉｏｎ，ａｒｅａｂａｎ ｄｏｎｅｄ．Ｔｈｒｅｅｓｕｂ－ａｌｇｏｒｉｔｈｍｓａｒｅｄｅｓｉｇｎｅｄ，ｉｎｃｌｕｄｉｎｇｂｕｉｌｄｉｎｇａｎｅｗｅｆｆｅｃｔｉｖｅＰＡＳ，ｓｈｉｆｔｉｎｇｆｌｏｗｓｂｅｔｗｅｅｎｓｅｇ ｍｅｎｔｓｏｆａｎｅｆｆｅｃｔｉｖｅＰＡＳａｎｄｒｅｄｉｓｔｒｉｂｕｔｉｏｎｏｆＰＡＳｆｌｏｗｓｂｅｔｗｅｅｎｏｒｉｇｉｎｓ．Ｎｕｍｅｒｉｃａｌｒｅｓｕｌｔｓｗｅｒｅｐｒｅｓｅｎｔｅｄｆｏｒａ ｔｅｓｔｎｅｔｗｏｒｋ．Ｔｈｅｒｅｓｕｌｔｓｓｈｏｗｔｈａｔ，ｆｏｒｓｏｍｅｃａｓｅ