第10卷第3期 智能系统学报 Vol.10 No.3 2015年6月 CAAI Transactions on Intelligent Systems Jun.2015 D0:10.3969/j.issn.1673-4785.201404036 网s络出版地址：http://www.cnki.net/kcms/detail/23.1538.tp.20150526.1415.002.html 公交地铁一体化下的网络模型与最优路选择算法 徐勇，贾欣，王哲，王翠柳 (河北工业大学理学院，天津300401) 摘要：公交地铁网络出行线路优选问题是公交网络系统研究的核心问题之一。为此研究了公交地铁一体化条件 下的公交网络出行优化模型与算法。构造公交地铁网络的标号模型及映射网络模型，以适当倍数缩小地铁线路上 站点之间的权值，进而可将公交与地铁进行一体化处理，缩小后可使地铁线路具有明显的优势以达到优选地铁的目 的。运用映射网络图、二分图、半张量积等理论给出了公交地铁一体化网络的最优路选择算法。最后实证了该方法 在公交地铁网络线路优选的有效性。 关键词：公交：地铁：最优线路：半张量积：标号：映射网络：二分图 中图分类号：TP18;U491文献标志码：A文章编号：1673-4785(2015)03-0482-06 中文引用格式：徐勇，贾欣，王哲，等.公交地铁一体化下的网络模型与最优路选择算法[J].智能系统学报，2015,10(3)：482487. 英文引用格式：XU Yong,JIA Xin,WANG Zhe,etal.Transit network models and optimal path selection algorithm for the inte- grated bus and subway system[J].CAAI Transactions on Intelligent Systems,2015,10(3):482-487. Transit network models and optimal path selection algorithm for the integrated bus and subway system XU Yong,JIA Xin,WANG Zhe,WANG Cuiliu (School of Science,Hebei University of Technology,Tianjin 300401,China) Abstract:In this paper,the travel optimal model and algorithm of public transit network for the integrated bus and subway system are studied.First,a label model and mapped network model are constructed for the bus and subway network.The weight between two subway stations is appropriately reduced to deal with the bus and subway integra- tion problem.The subway has obvious advantages after reduction and subway becomes the preferred option.Next, the optimal path selection algorithm of the integration network of bus and subway is given using the mapping net- work graph,bipartite graph,and semi-tensor product theory.Finally,the effectiveness of the proposed method in optimized selection of the public transit network is illustrated by a numerical example. Keywords:public transit;subway;optimal path;semi-tensor product;label;mapping network graph;bipartite graph 日益现代化的交通方式给人们出行带来很大便 题。公交地铁系统的研究主要包括网络构建、公交 利，其中公交与地铁是大型城市中的主要交通工具。 配流与最优路选择算法3个方面，而查询算法在其 考虑到我国人口众多，城市交通拥堵问题日益严重， 中起到核心作用，它为人们提供出行的路径选择，切 对公交地铁系统的研究已成为一个热门又困难的课 身关系到整个公交地铁网络是否高效运作，是公交 系统研究的核心问题之一。 收稿日期：2014-04-18.网络出版日期：2015-05-26 基金项目：河北省自然科学基金资助项目(A2013202198):国家大学 目前虽然有一系列针对公交网络的最短路径搜 生创新创业训练计划项目(201310080030). 索算法[1-，主要包括基于图论的查询算法[1)，基 通信作者：徐勇.E-mail:xuyong(@hebut..cdu.cn.第 １０ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．３ ２０１５ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１５ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１４０４０３６ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５０５２６．１４１５．００２．ｈｔｍｌ 公交地铁一体化下的网络模型与最优路选择算法 徐勇，贾欣，王哲，王翠柳 （河北工业大学 理学院，天津 ３００４０１） 摘 要：公交地铁网络出行线路优选问题是公交网络系统研究的核心问题之一。 为此研究了公交地铁一体化条件 下的公交网络出行优化模型与算法。 构造公交地铁网络的标号模型及映射网络模型，以适当倍数缩小地铁线路上 站点之间的权值，进而可将公交与地铁进行一体化处理，缩小后可使地铁线路具有明显的优势以达到优选地铁的目 的。 运用映射网络图、二分图、半张量积等理论给出了公交地铁一体化网络的最优路选择算法。 最后实证了该方法 在公交地铁网络线路优选的有效性。 关键词：公交；地铁；最优线路；半张量积；标号；映射网络；二分图 中图分类号：ＴＰ１８； Ｕ４９１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０３⁃０４８２⁃０６ 中文引用格式：徐勇，贾欣，王哲，等． 公交地铁一体化下的网络模型与最优路选择算法［Ｊ］． 智能系统学报， ２０１５， １０（３）： ４８２⁃４８７． 英文引用格式：ＸＵ Ｙｏｎｇ， ＪＩＡ Ｘｉｎ， ＷＡＮＧ Ｚｈｅ， ｅｔ ａｌ． Ｔｒａｎｓｉｔ ｎｅｔｗｏｒｋ ｍｏｄｅｌｓ ａｎｄ ｏｐｔｉｍａｌ ｐａｔｈ ｓｅｌｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｉｎｔｅ⁃ ｇｒａｔｅｄ ｂｕｓ ａｎｄ ｓｕｂｗａｙ ｓｙｓｔｅｍ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（３）： ４８２⁃４８７． Ｔｒａｎｓｉｔ ｎｅｔｗｏｒｋ ｍｏｄｅｌｓ ａｎｄ ｏｐｔｉｍａｌ ｐａｔｈ ｓｅｌｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｉｎｔｅｇｒａｔｅｄ ｂｕｓ ａｎｄ ｓｕｂｗａｙ ｓｙｓｔｅｍ ＸＵ Ｙｏｎｇ， ＪＩＡ Ｘｉｎ， ＷＡＮＧ Ｚｈｅ， ＷＡＮＧ Ｃｕｉｌｉｕ （Ｓｃｈｏｏｌ ｏｆ Ｓｃｉｅｎｃｅ， Ｈｅｂｅｉ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｔｉａｎｊｉｎ ３００４０１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｔｈｅ ｔｒａｖｅｌ ｏｐｔｉｍａｌ ｍｏｄｅｌ ａｎｄ ａｌｇｏｒｉｔｈｍ ｏｆ ｐｕｂｌｉｃ ｔｒａｎｓｉｔ ｎｅｔｗｏｒｋ ｆｏｒ ｔｈｅ ｉｎｔｅｇｒａｔｅｄ ｂｕｓ ａｎｄ ｓｕｂｗａｙ ｓｙｓｔｅｍ ａｒｅ ｓｔｕｄｉｅｄ． Ｆｉｒｓｔ， ａ ｌａｂｅｌ ｍｏｄｅｌ ａｎｄ ｍａｐｐｅｄ ｎｅｔｗｏｒｋ ｍｏｄｅｌ ａｒｅ ｃｏｎｓｔｒｕｃｔｅｄ ｆｏｒ ｔｈｅ ｂｕｓ ａｎｄ ｓｕｂｗａｙ ｎｅｔｗｏｒｋ． Ｔｈｅ ｗｅｉｇｈｔ ｂｅｔｗｅｅｎ ｔｗｏ ｓｕｂｗａｙ ｓｔａｔｉｏｎｓ ｉｓ ａｐｐｒｏｐｒｉａｔｅｌｙ ｒｅｄｕｃｅｄ ｔｏ ｄｅａｌ ｗｉｔｈ ｔｈｅ ｂｕｓ ａｎｄ ｓｕｂｗａｙ ｉｎｔｅｇｒａ⁃ ｔｉｏｎ ｐｒｏｂｌｅｍ． Ｔｈｅ ｓｕｂｗａｙ ｈａｓ ｏｂｖｉｏｕｓ ａｄｖａｎｔａｇｅｓ ａｆｔｅｒ ｒｅｄｕｃｔｉｏｎ ａｎｄ ｓｕｂｗａｙ ｂｅｃｏｍｅｓ ｔｈｅ ｐｒｅｆｅｒｒｅｄ ｏｐｔｉｏｎ． Ｎｅｘｔ， ｔｈｅ ｏｐｔｉｍａｌ ｐａｔｈ ｓｅｌｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｏｆ ｔｈｅ ｉｎｔｅｇｒａｔｉｏｎ ｎｅｔｗｏｒｋ ｏｆ ｂｕｓ ａｎｄ ｓｕｂｗａｙ ｉｓ ｇｉｖｅｎ ｕｓｉｎｇ ｔｈｅ ｍａｐｐｉｎｇ ｎｅｔ⁃ ｗｏｒｋ ｇｒａｐｈ， ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ， ａｎｄ ｓｅｍｉ⁃ｔｅｎｓｏｒ ｐｒｏｄｕｃｔ ｔｈｅｏｒｙ． Ｆｉｎａｌｌｙ， ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ ｉｎ ｏｐｔｉｍｉｚｅｄ ｓｅｌｅｃｔｉｏｎ ｏｆ ｔｈｅ ｐｕｂｌｉｃ ｔｒａｎｓｉｔ ｎｅｔｗｏｒｋ ｉｓ ｉｌｌｕｓｔｒａｔｅｄ ｂｙ ａ ｎｕｍｅｒｉｃａｌ ｅｘａｍｐｌｅ． Ｋｅｙｗｏｒｄｓ：ｐｕｂｌｉｃ ｔｒａｎｓｉｔ； ｓｕｂｗａｙ； ｏｐｔｉｍａｌ ｐａｔｈ； ｓｅｍｉ⁃ｔｅｎｓｏｒ ｐｒｏｄｕｃｔ； ｌａｂｅｌ； ｍａｐｐｉｎｇ ｎｅｔｗｏｒｋ ｇｒａｐｈ； ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ 收稿日期：２０１４⁃０４⁃１８． 网络出版日期：２０１５⁃０５⁃２６． 基金项目：河北省自然科学基金资助项目（Ａ２０１３２０２１９８）；国家大学 生创新创业训练计划项目（２０１３１００８００３０）． 通信作者：徐勇． Ｅ⁃ｍａｉｌ： ｘｕｙｏｎｇ＠ ｈｅｂｕｔ．ｅｄｕ．ｃｎ． 日益现代化的交通方式给人们出行带来很大便 利，其中公交与地铁是大型城市中的主要交通工具。 考虑到我国人口众多，城市交通拥堵问题日益严重， 对公交地铁系统的研究已成为一个热门又困难的课 题。 公交地铁系统的研究主要包括网络构建、公交 配流与最优路选择算法 ３ 个方面，而查询算法在其 中起到核心作用，它为人们提供出行的路径选择，切 身关系到整个公交地铁网络是否高效运作，是公交 系统研究的核心问题之一。 目前虽然有一系列针对公交网络的最短路径搜 索算法［１－１１］ ，主要包括基于图论的查询算法［１，９］ ，基