第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
第 １０ 卷第 ３ 期 智 能 系 统 学 报 Ｖｏｌ．１０ №．３ ２０１５ 年 ６ 月 ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ Ｊｕｎ． ２０１５ ＤＯＩ：１０．３９６９ ／ ｊ．ｉｓｓｎ．１６７３⁃４７８５．２０１４０４０３６ 网络出版地址：ｈｔｔｐ： ／ ／ ｗｗｗ．ｃｎｋｉ．ｎｅｔ ／ ｋｃｍｓ／ ｄｅｔａｉｌ ／ ２３．１５３８．ｔｐ．２０１５０５２６．１４１５．００２．ｈｔｍｌ 公交地铁一体化下的网络模型与最优路选择算法 徐勇，贾欣，王哲，王翠柳 （河北工业大学 理学院，天津 ３００４０１） 摘 要：公交地铁网络出行线路优选问题是公交网络系统研究的核心问题之一。 为此研究了公交地铁一体化条件 下的公交网络出行优化模型与算法。 构造公交地铁网络的标号模型及映射网络模型，以适当倍数缩小地铁线路上 站点之间的权值，进而可将公交与地铁进行一体化处理，缩小后可使地铁线路具有明显的优势以达到优选地铁的目 的。 运用映射网络图、二分图、半张量积等理论给出了公交地铁一体化网络的最优路选择算法。 最后实证了该方法 在公交地铁网络线路优选的有效性。 关键词：公交；地铁；最优线路；半张量积；标号；映射网络；二分图 中图分类号：ＴＰ１８； Ｕ４９１ 文献标志码：Ａ 文章编号：１６７３⁃４７８５（２０１５）０３⁃０４８２⁃０６ 中文引用格式：徐勇，贾欣，王哲，等． 公交地铁一体化下的网络模型与最优路选择算法［Ｊ］． 智能系统学报， ２０１５， １０（３）： ４８２⁃４８７． 英文引用格式：ＸＵ Ｙｏｎｇ， ＪＩＡ Ｘｉｎ， ＷＡＮＧ Ｚｈｅ， ｅｔ ａｌ． Ｔｒａｎｓｉｔ ｎｅｔｗｏｒｋ ｍｏｄｅｌｓ ａｎｄ ｏｐｔｉｍａｌ ｐａｔｈ ｓｅｌｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｉｎｔｅ⁃ ｇｒａｔｅｄ ｂｕｓ ａｎｄ ｓｕｂｗａｙ ｓｙｓｔｅｍ［Ｊ］． ＣＡＡＩ Ｔｒａｎｓａｃｔｉｏｎｓ ｏｎ Ｉｎｔｅｌｌｉｇｅｎｔ Ｓｙｓｔｅｍｓ， ２０１５， １０（３）： ４８２⁃４８７． Ｔｒａｎｓｉｔ ｎｅｔｗｏｒｋ ｍｏｄｅｌｓ ａｎｄ ｏｐｔｉｍａｌ ｐａｔｈ ｓｅｌｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｔｈｅ ｉｎｔｅｇｒａｔｅｄ ｂｕｓ ａｎｄ ｓｕｂｗａｙ ｓｙｓｔｅｍ ＸＵ Ｙｏｎｇ， ＪＩＡ Ｘｉｎ， ＷＡＮＧ Ｚｈｅ， ＷＡＮＧ Ｃｕｉｌｉｕ （Ｓｃｈｏｏｌ ｏｆ Ｓｃｉｅｎｃｅ， Ｈｅｂｅｉ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｔｅｃｈｎｏｌｏｇｙ， Ｔｉａｎｊｉｎ ３００４０１， Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｔｈｉｓ ｐａｐｅｒ， ｔｈｅ ｔｒａｖｅｌ ｏｐｔｉｍａｌ ｍｏｄｅｌ ａｎｄ ａｌｇｏｒｉｔｈｍ ｏｆ ｐｕｂｌｉｃ ｔｒａｎｓｉｔ ｎｅｔｗｏｒｋ ｆｏｒ ｔｈｅ ｉｎｔｅｇｒａｔｅｄ ｂｕｓ ａｎｄ ｓｕｂｗａｙ ｓｙｓｔｅｍ ａｒｅ ｓｔｕｄｉｅｄ． Ｆｉｒｓｔ， ａ ｌａｂｅｌ ｍｏｄｅｌ ａｎｄ ｍａｐｐｅｄ ｎｅｔｗｏｒｋ ｍｏｄｅｌ ａｒｅ ｃｏｎｓｔｒｕｃｔｅｄ ｆｏｒ ｔｈｅ ｂｕｓ ａｎｄ ｓｕｂｗａｙ ｎｅｔｗｏｒｋ． Ｔｈｅ ｗｅｉｇｈｔ ｂｅｔｗｅｅｎ ｔｗｏ ｓｕｂｗａｙ ｓｔａｔｉｏｎｓ ｉｓ ａｐｐｒｏｐｒｉａｔｅｌｙ ｒｅｄｕｃｅｄ ｔｏ ｄｅａｌ ｗｉｔｈ ｔｈｅ ｂｕｓ ａｎｄ ｓｕｂｗａｙ ｉｎｔｅｇｒａ⁃ ｔｉｏｎ ｐｒｏｂｌｅｍ． Ｔｈｅ ｓｕｂｗａｙ ｈａｓ ｏｂｖｉｏｕｓ ａｄｖａｎｔａｇｅｓ ａｆｔｅｒ ｒｅｄｕｃｔｉｏｎ ａｎｄ ｓｕｂｗａｙ ｂｅｃｏｍｅｓ ｔｈｅ ｐｒｅｆｅｒｒｅｄ ｏｐｔｉｏｎ． Ｎｅｘｔ， ｔｈｅ ｏｐｔｉｍａｌ ｐａｔｈ ｓｅｌｅｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ ｏｆ ｔｈｅ ｉｎｔｅｇｒａｔｉｏｎ ｎｅｔｗｏｒｋ ｏｆ ｂｕｓ ａｎｄ ｓｕｂｗａｙ ｉｓ ｇｉｖｅｎ ｕｓｉｎｇ ｔｈｅ ｍａｐｐｉｎｇ ｎｅｔ⁃ ｗｏｒｋ ｇｒａｐｈ， ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ， ａｎｄ ｓｅｍｉ⁃ｔｅｎｓｏｒ ｐｒｏｄｕｃｔ ｔｈｅｏｒｙ． Ｆｉｎａｌｌｙ， ｔｈｅ ｅｆｆｅｃｔｉｖｅｎｅｓｓ ｏｆ ｔｈｅ ｐｒｏｐｏｓｅｄ ｍｅｔｈｏｄ ｉｎ ｏｐｔｉｍｉｚｅｄ ｓｅｌｅｃｔｉｏｎ ｏｆ ｔｈｅ ｐｕｂｌｉｃ ｔｒａｎｓｉｔ ｎｅｔｗｏｒｋ ｉｓ ｉｌｌｕｓｔｒａｔｅｄ ｂｙ ａ ｎｕｍｅｒｉｃａｌ ｅｘａｍｐｌｅ． Ｋｅｙｗｏｒｄｓ：ｐｕｂｌｉｃ ｔｒａｎｓｉｔ； ｓｕｂｗａｙ； ｏｐｔｉｍａｌ ｐａｔｈ； ｓｅｍｉ⁃ｔｅｎｓｏｒ ｐｒｏｄｕｃｔ； ｌａｂｅｌ； ｍａｐｐｉｎｇ ｎｅｔｗｏｒｋ ｇｒａｐｈ； ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ 收稿日期：２０１４⁃０４⁃１８． 网络出版日期：２０１５⁃０５⁃２６． 基金项目：河北省自然科学基金资助项目（Ａ２０１３２０２１９８）；国家大学 生创新创业训练计划项目（２０１３１００８００３０）． 通信作者：徐勇． Ｅ⁃ｍａｉｌ： ｘｕｙｏｎｇ＠ ｈｅｂｕｔ．ｅｄｕ．ｃｎ． 日益现代化的交通方式给人们出行带来很大便 利，其中公交与地铁是大型城市中的主要交通工具。 考虑到我国人口众多，城市交通拥堵问题日益严重， 对公交地铁系统的研究已成为一个热门又困难的课 题。 公交地铁系统的研究主要包括网络构建、公交 配流与最优路选择算法 ３ 个方面，而查询算法在其 中起到核心作用，它为人们提供出行的路径选择，切 身关系到整个公交地铁网络是否高效运作，是公交 系统研究的核心问题之一。 目前虽然有一系列针对公交网络的最短路径搜 索算法［１－１１］ ，主要包括基于图论的查询算法［１，９］ ，基
第3期 徐勇，等：公交地铁一体化下的网络模型与最优路选择算法 ·483 于数据库的查询算法[2，)]和基于矩阵运算的查询算 法[)。目前针对地铁主导下的公交网络的最短路 径搜索算法却不多见。 考虑到地铁在大城市公交系统中日益占主导地 S (地铁线路) 位这一事实，在文献[9]的基础上，将优选地铁出行 作为基本出发点，对公交与地铁站点标号的同时，将 地铁线路上站点间的权值成倍缩小，再依次按照换 S 乘次数、乘车距离进行路径选择时就达到了优选地 铁的目的，且一体化后的模型更加清晰、简便。 图1公交地铁网络 Fig.1 Bus and subway network 1高维数组的表示 称一个数组是k维的，如果它的元素是由k个 2.2公交地铁网络的二分图模型 指标索引的，更确切地说，称S是一个形如 公交地铁网络二分图是三元组G=(S,L,E), Id(i1,i2,…,4;n1,n2,…,nz)的k维数组，如果它能 其中S和L是2个不相交的顶点集，分别为顶部和 表示成0.2] 底部的顶点集，并且E二S×L是一个边集，边连接 顶部和底部的顶点。 S={S2.…41i=1,2,…,n1…4=1,2,…,n} S的大小，即S中元素的个数，记作1S1。 具有2种属性的复杂网络可用二分图表示[1415] 公交地铁网络的站点和线路2种属性决定了它可以 且ISl=n1×n2×…×nk。 反映到二分图上。将顶点集合S看作二分图的上顶 记σ(1)，σ(2)，…，σ(k)是1,2，…，k的一个 点集，线路集合L看作二分图的下顶点集，公交线路 排列，若它能排成一个 L经过站点S,则在L线路与S站点之间有边相连。 na)Xne(I)…nu-1)n。+1)…ng(t) 图2是图1的公交网络对应的网络二分图。 的矩阵，称它是按照 形式 1,…,t-1,t+1,…,k 排列的，即按照t-行形式排列的。 文中需记录大量两站点i,j在L线路上所经过 的站点数，它是三维数组，记公交地铁网络信息矩阵 W=[0】xxm,0表示i两站点在L4线路上所 经过的站点数，m表示有m条公交地铁线路，n表 图2网络二分图 示有n个公交地铁站点。 Fig.2 Bipartite network graph 2公交地铁网络优化模型 由图2看出，S,与S2可直接到达，S,与S,需经 2.1公交地铁网络图 过S2转乘，S,与S,需经过S2,S转乘到达。二分图 公交地铁网络是由公交线路和地铁线路组成的 比网络图更加直观地显示出换乘次数。 网络[)，每条线路经过若干站点，每个站点有多条 2.3公交地铁网络图的映射图 线路通过，记站点集合S={S1,S2,…,Sn},其中S, 公交地铁网络图的映射图包括线路映射网络图 S2,…,Sn为站点；线路集合L={L1,L2…,Lm},其 和站点映射网络图，可以由二分图得到。 中L,L2,…,Ln为线路。由站点集合S和线路集合 二分图G=(S,L,E)的上顶点映射图（即站点 L构成的二元组H={S,L}反映到图上，即为公交 映射网络图)为G=(S,E),边集E= 地铁网络图。 {S,SIN(S)∩N(S)≠}，其中N(S:)为S:在 例如，某公交地铁网络由1条地铁线路、2条公 二分图中的邻接点集合。它的下顶点映射图（即线 交线路、2个地铁站点（地铁站点都为公交站点）和 路映射网络图)为G=(L,E),边集E= 2个公交站点（不包含前述地铁站点）组成，他们分 {L,LIN(L)∩N(L)≠☑)，其中N(L)为L:在 别为地铁线路Lo,公交线路L,、L2,地铁站点S、S2, 二分图中的邻接点集合。线路映射网络图能反映出 公交站点S3、S4,如图1。 线路之间的连通关系，两站点所在的线路在线路映
于数据库的查询算法［２，５］ 和基于矩阵运算的查询算 法［１１］ 。 目前针对地铁主导下的公交网络的最短路 径搜索算法却不多见。 考虑到地铁在大城市公交系统中日益占主导地 位这一事实，在文献［９］的基础上，将优选地铁出行 作为基本出发点，对公交与地铁站点标号的同时，将 地铁线路上站点间的权值成倍缩小，再依次按照换 乘次数、乘车距离进行路径选择时就达到了优选地 铁的目的，且一体化后的模型更加清晰、简便。 １ 高维数组的表示 称一个数组是 ｋ 维的，如果它的元素是由 ｋ 个 指标 索 引 的， 更 确 切 地 说， 称 Ｓ 是 一 个 形 如 Ｉｄ ｉ １ ，ｉ ２ ，…，ｉ ｋ；ｎ１ ，ｎ２ ，…，ｎｋ ( ) 的 ｋ 维数组，如果它能 表示成［１０，１２］ ： Ｓ ＝ Ｓｉ１ ，ｉ２ ，…，ｉｋ ｜ ｉ １ ＝ １，２，…，ｎ１ ；…；ｉ ｋ ＝ １，２，…，ｎｋ { } Ｓ 的大小，即 Ｓ 中元素的个数，记作 ｜ Ｓ ｜ 。 且 ｜ Ｓ ｜ ＝ ｎ１ × ｎ２ × … × ｎｋ 。 记 σ(１) ，σ(２) ，…，σ(ｋ) 是 １，２，…，ｋ 的一个 排列，若它能排成一个 ｎσ (ｔ) × ｎσ (１ ) …ｎσ (ｔ－１ ) ｎσ (ｔ＋１ ) …ｎσ (ｋ ) 的矩阵，称它是按照 ｔ １，…，ｔ － １，ｔ ＋ １，…，ｋ é ë ê ê ù û ú ú 形式 排列的，即按照 ｔ ⁃行形式排列的。 文中需记录大量两站点 ｉ，ｊ 在 Ｌｋ 线路上所经过 的站点数，它是三维数组，记公交地铁网络信息矩阵 Ｗ ＝ ｗ ｋ ｉ，ｊ [ ] ｎ×ｎ×ｍ ， ｗ ｋ ｉ，ｊ 表示 ｉ，ｊ 两站点在 Ｌｋ 线路上所 经过的站点数， ｍ 表示有 ｍ 条公交地铁线路， ｎ 表 示有 ｎ 个公交地铁站点。 ２ 公交地铁网络优化模型 ２．１ 公交地铁网络图 公交地铁网络是由公交线路和地铁线路组成的 网络［１３］ ，每条线路经过若干站点，每个站点有多条 线路通过，记站点集合 Ｓ ＝ Ｓ１ ，Ｓ２ ，…，Ｓｎ { } ，其中 Ｓ１ ， Ｓ２ ，…，Ｓｎ 为站点；线路集合 Ｌ ＝ Ｌ１ ，Ｌ２ ，…，Ｌｍ { } ，其 中 Ｌ１ ，Ｌ２ ，…，Ｌｍ 为线路。 由站点集合 Ｓ 和线路集合 Ｌ 构成的二元组 Ｈ ＝ {Ｓ，Ｌ} 反映到图上，即为公交 地铁网络图。 例如，某公交地铁网络由 １ 条地铁线路、２ 条公 交线路、２ 个地铁站点（地铁站点都为公交站点）和 ２ 个公交站点（不包含前述地铁站点）组成，他们分 别为地铁线路 Ｌ０ ，公交线路 Ｌ１ 、Ｌ２ ，地铁站点 Ｓ１ 、Ｓ２ ， 公交站点 Ｓ３ 、Ｓ４ ，如图 １。 图 １ 公交地铁网络 Ｆｉｇ． １ Ｂｕｓ ａｎｄ ｓｕｂｗａｙ ｎｅｔｗｏｒｋ ２．２ 公交地铁网络的二分图模型 公交地铁网络二分图是三元组 Ｇ ＝ (Ｓ，Ｌ，Ｅ) ， 其中 Ｓ 和 Ｌ 是 ２ 个不相交的顶点集，分别为顶部和 底部的顶点集，并且 Ｅ ⊆ Ｓ × Ｌ 是一个边集，边连接 顶部和底部的顶点。 具有 ２ 种属性的复杂网络可用二分图表示［１４－１５］ ． 公交地铁网络的站点和线路 ２ 种属性决定了它可以 反映到二分图上。 将顶点集合 Ｓ 看作二分图的上顶 点集，线路集合 Ｌ 看作二分图的下顶点集，公交线路 Ｌ ′ 经过站点 Ｓ ′ ，则在 Ｌ ′ 线路与 Ｓ ′ 站点之间有边相连。 图 ２ 是图 １ 的公交网络对应的网络二分图。 图 ２ 网络二分图 Ｆｉｇ． ２ Ｂｉｐａｒｔｉｔｅ ｎｅｔｗｏｒｋ ｇｒａｐｈ 由图 ２ 看出， Ｓ１ 与 Ｓ２ 可直接到达， Ｓ１ 与 Ｓ３ 需经 过 Ｓ２ 转乘， Ｓ１ 与 Ｓ４ 需经过 Ｓ２ ，Ｓ３ 转乘到达。 二分图 比网络图更加直观地显示出换乘次数。 ２．３ 公交地铁网络图的映射图 公交地铁网络图的映射图包括线路映射网络图 和站点映射网络图，可以由二分图得到。 二分图 Ｇ ＝ (Ｓ，Ｌ，Ｅ) 的上顶点映射图（即站点 映 射 网 络 图 ） 为 Ｇ Ｓ ＝ Ｓ，Ｅ Ｓ ( ) ， 边 集 Ｅ Ｓ ＝ ＳｉＳｊ { ｜ Ｎ（Ｓｉ） ∩ Ｎ（Ｓｊ） ≠ ∅} ，其中 Ｎ（Ｓｉ） 为 Ｓｉ 在 二分图中的邻接点集合。 它的下顶点映射图（即线 路 映 射 网 络 图 ） 为 Ｇ Ｌ ＝ Ｌ，Ｅ Ｌ ( ) ， 边 集 Ｅ Ｌ ＝ ＬｉＬｊ { ｜ Ｎ（Ｌｉ） ∩ Ｎ（Ｌｊ） ≠ ∅} ，其中 Ｎ（Ｌｉ） 为 Ｌｉ 在 二分图中的邻接点集合。 线路映射网络图能反映出 线路之间的连通关系，两站点所在的线路在线路映 第 ３ 期 徐勇，等：公交地铁一体化下的网络模型与最优路选择算法 ·４８３·
·484 智能系统学报 第10卷 射网络图中所连接的边数反映了乘客的换乘次数。 络。在站点映射网络中，对边S,S,赋值，记为，且 站点映射网络图表示站点之间的连通关系，它能反 =W-N|,它代表在L线路上S:S,两站点之 映出乘客换乘次数的同时，也给出了换乘站点。 间的站点数。若S、S不在L4线路上，令w=0。 图3为图2的线路映射网络图，图4为图2的 3.2基于标号网络模型最优路选择的算法 站点映射网络图。由图3可以看出，L,与L。、L2之 1)给出任两站点S:与S,构造直达检验向量 间分别为一条边，即若出发站点在L,站点上，目的 g=WDe,De,其中W=[0 l nnxm,e:表示第i 地站点在L。站点或L2站点上，转乘1次公交或者地 个元素为1，其余全为0的n维单位向量，若a,= 铁即可到达。若出发站点在L。线路上，目的地站点 (o,0,…,0)T≠0，则S,站点与S,站点可以直 在L,线路上，则需在L,线路上的某2个站点处转 达，若u=arg min{o},则o,为S,与S站点之间 乘，乘坐3次公交或地铁即可到达目的地。由图4 可以看出，S,与S2有一条边相连，即两站点在一条 的最小直达距离，最优路径为L。 线路上，可以直达。S,与S,之间有2条边，且经过S, 2)若S站点与S,站点不可直达，根据站点映射 站点，则从S,站点到达S,站点必须在S2站点转乘， 网络图，记与S,站点邻接的站点集合S:={S1,S2, 即坐2次公交或地铁到达。S,与S4之间有3条边相 …,S4}与S站点邻接的站点集合S={S1,S2,…, 连，从图可直接看出，由S,站点出发，需在S2和S S},若S∩S≠☑，则表示S站点与S站点转乘一 站点转乘，以到达S4站点。 次可到达，记S:∩S={S1,S2,…,Sm},则S:与S 可经p种方法到达，则d(S,S)=min{w,+w}, L,∈L,L'∈L,根据公交网络二分图，L与L分别为 连接S与S,,S,与S,站点的线路，其对应的路线为 最优出行路线。 3)若S:∩S=☑，即一次转乘不可达，则检验S,与 中有无可直达的两站点，若N(S)∩N(Sn)≠，S。∈S 图3线路映射网络图 ,S∈S,则站点S与站点Sn之间有直达线路，d(S,S) Fig.3 Line mapping network graph =min{p+$南+喻}，L,∈L,L2∈L2,L∈L, 其中L,山2山根据公交地铁网络二分图确定，且L凸2山 分别为连接S,与Sp,S与S,S与S站点的线路，其对 应方案为最优出行方案。 调查表明，在一个成熟的公交地铁网络中，2次 换乘可以实现绝大多数出发地与目的地之间的连接。 3.3算法的复杂性分析 图4站点映射网络图 算法的复杂性用数据输入规模的函数度量。由 Fig.4 Site mapping network graph 站点集合S={S1,S2,…,Sn}和公交线路集合L= 3最优路选择算法 {L1,L2,…,Lm}组成的地铁公交网络，存储数据W= 首先对每条线路上的站点进行一体化标号，考 [w】xn×m的规模为n2m。但因为W为稀疏三维数 组，占用存储空间大大减小。在能够直达的情况下， 虑到地铁的快捷性、准时性、舒适性等优点，优选地 算法的计算量主要为检验向量的计算上，运算量为 铁出行是大势所趋。这样，将地铁线路上两站点间 O(n'm)。在不能直达情况下的转乘问题的计算量 乘车距离权值适当减小，这样就达到了优选地铁出 主要为寻找转乘站点和转乘线路的计算上。寻找转 行的目的。 乘站点实质是在站点映射网络上寻找从S:到S,的中 3.1标号公交地铁网络的模型 间站点，可以在站点映射网络上采用经典最短路算 若线路L4上有k。个站点，L4:S,S2,…,S。, 法，如Dijkstra算法，运算量为O(n2)。在映射网络 站点S在线路L4上的标号为j,记为N=j,在二分 图上的求S,与S:的最短路的最小优化问题，实质是 网络图中边LS,的权值为该站点在线路L:上的标 多阶段决策问题，可以用经典动态规划或最短路算法 号：N=jo 来求解，计算量为O(m)。总体上，该算法总的计算 然后建立公交地铁线路映射网络和站点映射网 量为0(n2m)
射网络图中所连接的边数反映了乘客的换乘次数。 站点映射网络图表示站点之间的连通关系，它能反 映出乘客换乘次数的同时，也给出了换乘站点。 图 ３ 为图 ２ 的线路映射网络图，图 ４ 为图 ２ 的 站点映射网络图。 由图 ３ 可以看出， Ｌ１ 与 Ｌ０ 、Ｌ２ 之 间分别为一条边，即若出发站点在 Ｌ１ 站点上，目的 地站点在 Ｌ０ 站点或 Ｌ２ 站点上，转乘 １ 次公交或者地 铁即可到达。 若出发站点在 Ｌ０ 线路上，目的地站点 在 Ｌ２ 线路上，则需在 Ｌ１ 线路上的某 ２ 个站点处转 乘，乘坐 ３ 次公交或地铁即可到达目的地。 由图 ４ 可以看出， Ｓ１ 与 Ｓ２ 有一条边相连，即两站点在一条 线路上，可以直达。 Ｓ１ 与 Ｓ３ 之间有 ２ 条边，且经过 Ｓ２ 站点，则从 Ｓ１ 站点到达 Ｓ３ 站点必须在 Ｓ２ 站点转乘， 即坐 ２ 次公交或地铁到达。 Ｓ１ 与 Ｓ４ 之间有 ３ 条边相 连，从图可直接看出，由 Ｓ１ 站点出发，需在 Ｓ２ 和 Ｓ３ 站点转乘，以到达 Ｓ４ 站点。 图 ３ 线路映射网络图 Ｆｉｇ． ３ Ｌｉｎｅ ｍａｐｐｉｎｇ ｎｅｔｗｏｒｋ ｇｒａｐｈ 图 ４ 站点映射网络图 Ｆｉｇ． ４ Ｓｉｔｅ ｍａｐｐｉｎｇ ｎｅｔｗｏｒｋ ｇｒａｐｈ ３ 最优路选择算法 首先对每条线路上的站点进行一体化标号，考 虑到地铁的快捷性、准时性、舒适性等优点，优选地 铁出行是大势所趋。 这样，将地铁线路上两站点间 乘车距离权值适当减小，这样就达到了优选地铁出 行的目的。 ３．１ 标号公交地铁网络的模型 若线路 Ｌｋ 上有 ｋｎ 个站点， Ｌｋ：Ｓｋ１ ，Ｓｋ２ ，…，Ｓｋｎ ， 站点 Ｓｋｊ 在线路 Ｌｋ 上的标号为 ｊ ，记为 Ｎ ｋ ｊ ＝ ｊ ，在二分 网络图中边 ＬｋＳｋｊ 的权值为该站点在线路 Ｌｋ 上的标 号： Ｎ ｋ ｊ ＝ ｊ 。 然后建立公交地铁线路映射网络和站点映射网 络。 在站点映射网络中，对边 ＳｉＳｊ 赋值，记为 ｗ ｋ ｉ，ｊ ，且 ｗ ｋ ｉ，ｊ ＝ Ｎ ｋ ｊ － Ｎ ｋ ｉ ，它代表在 Ｌｋ 线路上 Ｓｉ、Ｓｊ 两站点之 间的站点数。 若 Ｓｉ、Ｓｊ 不在 Ｌｋ 线路上，令 ｗ ｋ ｉ，ｊ ＝ ０。 ３．２ 基于标号网络模型最优路选择的算法 １）给出任两站点 Ｓｉ 与 Ｓｊ ，构造直达检验向量 αｉｊ ＝ Ｗ▷ ｅｉ▷ ｅｊ ，其中 Ｗ ＝ ｗ ｋ ｉ，ｊ [ ] ｎ×ｎ×ｍ ， ｅｉ 表示第 ｉ 个元素为 １，其余全为 ０ 的 ｎ 维单位向量，若 αｉｊ ＝ ｗ １ ｉ，ｊ，ｗ ２ ｉ，ｊ，…，ｗ ｍ ｉ，ｊ ( ) Ｔ ≠ ０， 则 Ｓｉ 站点与 Ｓｊ 站点可以直 达，若 ｖ ＝ ａｒｇ ｍｉｎ ｋ ｗ ｋ ｉ，ｊ { } ，则 ｗ ｖ ｉ，ｊ 为 Ｓｉ 与 Ｓｊ 站点之间 的最小直达距离，最优路径为 Ｌｖ 。 ２）若 Ｓｉ 站点与 Ｓｊ 站点不可直达，根据站点映射 网络图，记与 Ｓｉ 站点邻接的站点集合 Ｓ ′ ｉ ＝ ｛Ｓｉ１ ，Ｓｉ２ ， …，Ｓｉｋ｝ 与 Ｓｊ 站点邻接的站点集合 Ｓ ′ ｊ ＝ ｛Ｓｊ１ ，Ｓｊ２ ，…， Ｓｊｌ｝ ，若 Ｓ ′ ｉ ∩Ｓ ′ ｊ ≠∅ ，则表示 Ｓｉ 站点与 Ｓｊ 站点转乘一 次可到达，记 Ｓ ′ ｉ ∩ Ｓ ′ ｊ ＝ ｛Ｓｒ１ ， Ｓｒ２ ， …，Ｓｒｐ｝ ，则 Ｓｉ 与 Ｓｊ 可经 ｐ 种方法到达，则 ｄ（Ｓｉ，Ｓｊ） ＝ ｍｉｎ ｗ ｌ ｉ，ｒ ＋ ｗ ｌ ′ ｒ，ｊ { } ， Ｌｌ ∈Ｌ，Ｌｌ ′ ∈Ｌ ′ ，根据公交网络二分图， Ｌ 与 Ｌ ′ 分别为 连接 Ｓｉ 与 Ｓｒ ， Ｓｒ 与 Ｓｊ 站点的线路，其对应的路线为 最优出行路线。 ３）若Ｓ ′ ｉ ∩Ｓ ′ ｊ ＝ ∅，即一次转乘不可达，则检验Ｓ ′ ｉ 与Ｓ ′ ｊ 中有无可直达的两站点，若Ｎ（Ｓｉｐ）∩Ｎ（Ｓｊｑ）≠∅，Ｓｉｐ ∈Ｓ ′ ｉ ， Ｓｊｑ ∈Ｓ ′ ｊ ，则站点Ｓｉｐ 与站点Ｓｊｑ 之间有直达线路，ｄ（Ｓｉ，Ｓｊ） ＝ ｍｉｎ ｗ ｌ１ ｉ，ｉｐ ＋ ｗ ｌ２ ｉｐ，ｊｑ ＋ ｗ ｌ３ ｊｑ，ｊ { } ， Ｌｌ１ ∈Ｌ１， Ｌｌ２ ∈Ｌ２， Ｌｌ３ ∈Ｌ３， 其中Ｌ１、Ｌ２、Ｌ３ 根据公交地铁网络二分图确定，且 Ｌ１、Ｌ２、Ｌ３ 分别为连接Ｓｉ 与Ｓｉｐ ，Ｓｉｐ 与Ｓｊｑ ，Ｓｊｑ 与Ｓｊ 站点的线路，其对 应方案为最优出行方案。 调查表明，在一个成熟的公交地铁网络中，２ 次 换乘可以实现绝大多数出发地与目的地之间的连接。 ３．３ 算法的复杂性分析 算法的复杂性用数据输入规模的函数度量。 由 站点集合 Ｓ ＝ Ｓ１ ，Ｓ２ ，…，Ｓｎ { } 和公交线路集合 Ｌ ＝ Ｌ１ ，Ｌ２ ，…，Ｌｍ { } 组成的地铁公交网络，存储数据 Ｗ ＝ ｗ ｋ ｉ，ｊ [ ] ｎ×ｎ×ｍ 的规模为 ｎ ２ｍ 。 但因为 Ｗ 为稀疏三维数 组，占用存储空间大大减小。 在能够直达的情况下， 算法的计算量主要为检验向量的计算上，运算量为 Ｏ ｎ ２ ( ｍ) 。 在不能直达情况下的转乘问题的计算量 主要为寻找转乘站点和转乘线路的计算上。 寻找转 乘站点实质是在站点映射网络上寻找从 Ｓｉ 到 Ｓｊ 的中 间站点，可以在站点映射网络上采用经典最短路算 法，如 Ｄｉｊｋｓｔｒａ 算法，运算量为 Ｏ ｎ ２ ( ) 。 在映射网络 图上的求 Ｓｉ 与 Ｓｊ 的最短路的最小优化问题，实质是 多阶段决策问题，可以用经典动态规划或最短路算法 来求解，计算量为 Ｏ ｍ ２ ( ) 。 总体上，该算法总的计算 量为 Ｏ ｎ ２ ( ｍ) 。 ·４８４· 智 能 系 统 学 报 第 １０ 卷
第3期 徐勇，等：公交地铁一体化下的网络模型与最优路选择算法 ·485 算例 选取由4条公交线路L,、L2L,L4,1条地铁线路 L,及9个站点组成的公交网络，如图5，地铁线路L。 经S、S4、S6站点，线路L,经SS2、S,站点，线路L2经 S5、S3、S4、S,站点，线路L3经S5、S6、Sg站点，线路L4 经Sg、S,站点。其中W9=1,N4=7,g=10;N= 2,N3=5,N=11:W=6,N=9,W=12,W=16: 图8站点映射网络图 W3=6,N8=9,N8=13;Ng=4,Ng=9。 Fig.8 Site mapping network graph 建立图5的公交地铁网络二分图，如图6。图7 为图6的线路映射网络图，图8为图6的站点映射 网络图。 L。(地铁线路) 1)考虑站点S2到站点S,的最短路问题，构造 直达检验向量a23=WDe,De3,可得到a3=(o.3, S.Sx 0.a,0吃.3，o2.3,0.3)T≠0，若v=arg min{o吃.}=1， 图5公交地铁网络 即w;,=6为最小直达距离，L,为所选乘车路线，途 Fig.5 Bus and subway network graph 径6站。 2)考虑站点S,到站点S,的最短路问题，a15= 如第3节中对标号的叙述，为达到优选地铁的目 WDe1>e5=0,即不可直达，根据站点网络映射图， 的，不妨将地铁线路上站点的标号根据实际情况缩小 如图8，得到与S,站点邻接的站点集合S,={S2,S3, 适当倍，这样可将整个公交网络系统一体化处理。而 实际上的目的是使地铁线路上的乘车距离权值变小， S4,S6},与S5站点邻接的站点集合S={S3,S4,S6, 即需将标号之间的差值成比例缩小。此例中=1， S,Sg},由于S1∩S≠☑，表示S,站点与S站点 W9=7,g=10,按照式w=|W-N|,得4=6， 转乘1次可到达。又S1∩S={S,S4,S6},则S站 .6=9,w.6=3。若将此权值3倍缩小可得出0。= 点与S,站点可经3种1次转乘的方案到达，d(S, 2,w6=3,86=1,其余公交线路上权值为心2=3， S3）=min{w.3+w.5,w4+oi.5,0.6+w.s}= min{9+3,2+6,3+3}=6,对应最优路径为从S, wi.3=9,1023=6:1w4=3,w5=3,1u7=7,w5=6, 站点乘坐地铁线路L。到达S。站点，转乘公交线路 w,7=4,w5.7=10:w56=3,03.8=7,06.8=4;0g.9= L3到达S5站点，途经6站。 5。其余，赋值为零。 可看出，从S,站点到S站点与从S2站点到S S.S.S Ss S.S. 站点都是经过6站地，而网络图中明显看出S,S 站点的距离是远远大于S2,S,站点的距离，这是减 少地铁站点标号的权值的结果。结果显示出地铁的 优越性。 3)考虑站点S4到站点S,的最短路问题，S4在线 路Lo与线路L2上，S,在线路L4上，a9=WD eD 图6网络二分图 eg=0,即不可直达，S4={S1,S3,S5,S6,S},Sg= Fig.6 Bipartite network {Sg},S4∩S。=☑，即1次转乘不可达。下面考虑 2次转乘的情况，根据线路网络映射图，L。或L2线路 与L,线路之间有L3连接，即从L,线路或L2线路需转 乘L3到线路上，再转乘到L线路上。 根据网络二分图，可得：N(S,)={L1,Lo}, N(S3)={L1,L2},N(S5)={L2,L},N(S6)= 图7线路映射网络图 {Lo,L3},N(S,)={L2},而N(Sg)={L3,L4} Fig.7 Line mapping network 则N(S5)∩N(Sg)≠☑，N(S6)∩N(Ss)≠
４ 算 例 选取由 ４ 条公交线路 Ｌ１ 、Ｌ２ 、Ｌ３ 、Ｌ４ ，１ 条地铁线路 Ｌ０ 及 ９ 个站点组成的公交网络，如图 ５，地铁线路 Ｌ０ 经 Ｓ１ 、Ｓ４ 、Ｓ６ 站点，线路 Ｌ１ 经 Ｓ１ 、Ｓ２ 、Ｓ３ 站点，线路 Ｌ２ 经 Ｓ５ 、Ｓ３ 、Ｓ４ 、Ｓ７ 站点，线路 Ｌ３ 经 Ｓ５ 、Ｓ６ 、Ｓ８ 站点，线路 Ｌ４ 经 Ｓ８ 、Ｓ９ 站点。 其中 Ｎ ０ １ ＝ １，Ｎ ０ ４ ＝ ７，Ｎ ０ ６ ＝ １０；Ｎ １ １ ＝ ２，Ｎ １ ２ ＝ ５，Ｎ １ ３ ＝ １１；Ｎ ２ ５ ＝ ６，Ｎ ２ ３ ＝ ９，Ｎ ２ ４ ＝ １２，Ｎ ２ ７ ＝ １６； Ｎ ３ ５ ＝ ６，Ｎ ３ ６ ＝ ９，Ｎ ３ ８ ＝ １３；Ｎ ４ ８ ＝ ４，Ｎ ４ ９ ＝ ９。 图 ５ 公交地铁网络 Ｆｉｇ． ５ Ｂｕｓ ａｎｄ ｓｕｂｗａｙ ｎｅｔｗｏｒｋ ｇｒａｐｈ 如第 ３ 节中对标号的叙述，为达到优选地铁的目 的，不妨将地铁线路上站点的标号根据实际情况缩小 适当倍，这样可将整个公交网络系统一体化处理。 而 实际上的目的是使地铁线路上的乘车距离权值变小， 即需将标号之间的差值成比例缩小。 此例中 Ｎ ０ １ ＝ １， Ｎ ０ ４ ＝ ７，Ｎ ０ ６ ＝ １０，按照式ｗ ｋ ｉ，ｊ ＝ Ｎ ｋ ｊ － Ｎ ｋ ｉ ，得ｗ ０ １，４ ＝ ６， ｗ ０ １，６ ＝ ９，ｗ ０ ４，６ ＝ ３。 若将此权值３ 倍缩小可得出 ｗ ０ １，４ ＝ ２，ｗ ０ １，６ ＝ ３，ｗ ０ ４，６ ＝ １，其余公交线路上权值为 ｗ １ １，２ ＝ ３， ｗ １ １，３ ＝ ９，ｗ １ ２，３ ＝ ６；ｗ ２ ３，４ ＝ ３，ｗ ２ ３，５ ＝ ３，ｗ ２ ３，７ ＝ ７，ｗ ２ ４，５ ＝ ６， ｗ ２ ４，７ ＝ ４，ｗ ２ ５，７ ＝ １０；ｗ ３ ５，６ ＝ ３，ｗ ３ ５，８ ＝ ７，ｗ ３ ６，８ ＝ ４；ｗ ４ ８，９ ＝ ５ 。 其余 ｗ ｋ ｉ，ｊ 赋值为零。 图 ６ 网络二分图 Ｆｉｇ． ６ Ｂｉｐａｒｔｉｔｅ ｎｅｔｗｏｒｋ 图 ７ 线路映射网络图 Ｆｉｇ． ７ Ｌｉｎｅ ｍａｐｐｉｎｇ ｎｅｔｗｏｒｋ 图 ８ 站点映射网络图 Ｆｉｇ． ８ Ｓｉｔｅ ｍａｐｐｉｎｇ ｎｅｔｗｏｒｋ ｇｒａｐｈ 建立图 ５ 的公交地铁网络二分图，如图 ６。 图 ７ 为图 ６ 的线路映射网络图，图 ８ 为图 ６ 的站点映射 网络图。 １）考虑站点 Ｓ２ 到站点 Ｓ３ 的最短路问题，构造 直达检验向量 α２３ ＝ Ｗ▷ｅ２▷ｅ３ ，可得到 α２３ ＝ （ｗ ０ ２，３ ， ｗ １ ２，３ ，ｗ ２ ２，３ ，ｗ ３ ２，３ ，ｗ ４ ２，３ ） Ｔ ≠ ０，若 ｖ ＝ ａｒｇ ｍｉｎ ｋ ｗ ｋ ２，３ { } ＝ １， 即 ｗ １ ２，３ ＝ ６ 为最小直达距离， Ｌ１ 为所选乘车路线，途 径 ６ 站。 ２）考虑站点 Ｓ１ 到站点 Ｓ５ 的最短路问题， α１５ ＝ Ｗ▷ ｅ１▷ ｅ５ ＝ ０，即不可直达，根据站点网络映射图， 如图 ８，得到与 Ｓ１ 站点邻接的站点集合 Ｓ ′ １ ＝ ｛Ｓ２ ，Ｓ３ ， Ｓ４ ，Ｓ６ ｝ ，与 Ｓ５ 站点邻接的站点集合 Ｓ ′ ５ ＝ ｛Ｓ３ ，Ｓ４ ，Ｓ６ ， Ｓ７ ，Ｓ８ ｝ ，由于 Ｓ ′ １ ∩ Ｓ ′ ５ ≠ ∅ ，表示 Ｓ１ 站点与 Ｓ５ 站点 转乘 １ 次可到达。 又 Ｓ ′ １ ∩Ｓ ′ ５ ＝ ｛Ｓ３ ，Ｓ４ ，Ｓ６ ｝ ，则 Ｓ１ 站 点与 Ｓ５ 站点可经 ３ 种 １ 次转乘的方案到达， ｄ（Ｓ１ ， Ｓ５ ） ＝ ｍｉｎ ｗ １ １，３ ＋ ｗ ２ ３，５ ，ｗ ０ １，４ ＋ ｗ ２ ４，５ ，ｗ ０ １，６ ＋ ｗ ３ ６，５ { } ＝ ｍｉｎ{９ ＋ ３，２ ＋ ６，３ ＋ ３} ＝ ６，对应最优路径为从 Ｓ１ 站点乘坐地铁线路 Ｌ０ 到达 Ｓ６ 站点，转乘公交线路 Ｌ３ 到达 Ｓ５ 站点，途经 ６ 站。 可看出，从 Ｓ１ 站点到 Ｓ５ 站点与从 Ｓ２ 站点到 Ｓ３ 站点都是经过 ６ 站地，而网络图中明显看出 Ｓ１ ，Ｓ５ 站点的距离是远远大于 Ｓ２ ，Ｓ３ 站点的距离，这是减 少地铁站点标号的权值的结果。 结果显示出地铁的 优越性。 ３）考虑站点 Ｓ４ 到站点 Ｓ９ 的最短路问题， Ｓ４ 在线 路 Ｌ０ 与线路 Ｌ２ 上， Ｓ９ 在线路 Ｌ４ 上， α４９ ＝ Ｗ▷ ｅ４▷ ｅ９ ＝ ０，即不可直达， Ｓ ′ ４ ＝ ｛Ｓ１ ，Ｓ３ ， Ｓ５ ，Ｓ６ ，Ｓ７ ｝，Ｓ ′ ９ ＝ ｛Ｓ８ ｝ ， Ｓ ′ ４ ∩ Ｓ ′ ９ ＝ ∅ ，即 １ 次转乘不可达。 下面考虑 ２ 次转乘的情况，根据线路网络映射图， Ｌ０ 或 Ｌ２ 线路 与 Ｌ４ 线路之间有 Ｌ３ 连接，即从 Ｌ０ 线路或 Ｌ２ 线路需转 乘 Ｌ３ 到线路上，再转乘到 Ｌ４ 线路上。 根据网络二分图，可得： Ｎ（ Ｓ１ ） ＝ ｛ Ｌ１ ，Ｌ０ ｝ ， Ｎ（ Ｓ３ ） ＝ ｛ Ｌ１ ，Ｌ２ ｝ ， Ｎ（ Ｓ５ ） ＝ ｛ Ｌ２ ，Ｌ３ ｝ ， Ｎ（ Ｓ６ ） ＝ ｛ Ｌ０ ，Ｌ３ ｝ ， Ｎ（ Ｓ７ ） ＝ ｛ Ｌ２ ｝ ，而 Ｎ（ Ｓ８ ） ＝ ｛ Ｌ３ ，Ｌ４ ｝ ， 则 Ｎ（ Ｓ５ ） ∩ Ｎ（ Ｓ８ ） ≠ ∅， Ｎ（ Ｓ６ ） ∩ Ｎ（ Ｓ８ ） ≠ ∅， 第 ３ 期 徐勇，等：公交地铁一体化下的网络模型与最优路选择算法 ·４８５·
·486 智能系统学报 第10卷 即S4中的S,站点与S。站点可与S。站点直达，而 query system of transit network[J].Journal of Liaoning 且它们分别都在L,线路上，则可求得 Technical University:Social Science Edition,2008,10 d(S4,So)= (4):380-382. min{o.5+03.g+0g.g,o8.6+0.g+0g.g}= [5]伍雁鹏，彭小奇，杨恒伏.改进的基于关系数据库技术 的公交查询算法[J].中南大学学报：自然科学版， min{6+7+5,1+4+5}=10 2009,40(3):763-766. 对应最优路线为从S,站点乘坐地铁线路L。到达 WU Yanpeng,PENG Xiaoqi,YANG Hengfu.Improved al- S。站点，转乘公交线路L3到达S。站点，再转乘公 gorithm based on relational database technology for querying 交线路L,到达S。站点，途径10站。 transit network[].Journal of Central South University:Sci- 5结束语 ence and Technology,2009,40(3):763-766. [6]刘健，徐维祥，刘旭敏.公交出行最优路线查询系统设 在文献[10]的基础上，将公交地铁进行一体化 计[J].计算机应用，2009,29(S2):110-112. 标号，缩小地铁两站点间的路径距离以达到优选地 LIU Jian,XU Weixiang,LIU Xumin.Design of urban pub- 铁的目的。据乘客出行心理，依次以换乘次数少、出 lic transit optimal route inquiry system[J].Journal of Com- 行距离短为优化目标，利用高维数组运算，根据公交 puter Applications,2009,29(S2):110-112. [7]伍雁鹏，彭小奇，黄同成.基于路径集合运算的公交网 地铁网络图与二分图、线路映射网络图、站点映射网 络寻径算法研究[J].计算机科学，2009,36(6)：239 络图得到两站点间的最优路径的选择算法。 240,272. 公交网络的寻径问题一直以来被认为是NP难 WU Yanpeng,PENG Xiaoqi,HUANG Tongcheng.Re- 问题，而日益发达的公交系统对最优路径选择算法的 search on path set operation based algorithm for path search- 要求也越来越高。因此，改进和创新算法在整个公交 ing in public transit network[J].Computer Science,2009. 系统中至关重要。本文尚未将地铁的时变性考虑在 36(6):239-240,272. 内，可对此进一步研究，使得人们无论何时出行都有 [8]刘作虎，黄明和，邹小云，等.一种网络公交查询系统 一个对应此时间点的方案，使查询更加精确可靠。 的改进算法[J].计算机与信息技术，2009，(4)：29-31. [9]徐勇，李杰，张军芳，等.新型公交网络模型与最优线 参考文献： 路选择算法[J].系统工程理论与实践，2011,31(11)： 2234-2240. [1]闫小勇，尚艳亮.基于二部图模型的公交网络路径搜索 XU Yong,LI Jie,ZHANG Junfang,et al.New urban transit 算法[J].计算机工程与应用，2010,46(5)：246-248. network models and optimal path searching algorithm[J]. YAN Xiaoyong,SHANG Yanliang.Path-finding algorithm of Systems Engineering-Theory and Practice,2011,31 public transport networks based on bipartite graph model (11）：2234-2240. [J].Computer Engineering and Applications,2010,46 [10]刘旭浩，徐勇.基于半张量积理论的公交网络查询[J]. (5):246-248. 复杂系统与复杂性科学，2013,10(1)：38-44. [2]梁虹，袁小群，刘蕊.一种新的公交数据模型与公交查 LIU Xuhao,XU Yong.An inquiry method of transit net- 询系统实现[J].计算机工程与应用，2007,43(3)：234 work based on semi-tensor productJ.Complex Systems 238. and Complexity Science,2013,10(1):38-44. LIANG Hong,YUAN Xiaoqun,LIU Rui.Novel model and [11]张林峰，范炳全，吕智林.公交网络换乘矩阵的分析与 realization of public transport route inquiring system[J]. 算法[J].系统工程，2003,21(6)：92-96. Computer Engineering and Applications,2007,43(3): ZHANG Linfeng,FAN Bingquan,LO Zhilin.Transfer ma- 234-238. trix of public transit network and algorithm J.Systems [3]王海帅，冀振燕，王森.公交线路查询算法[J].计算机 Engineering,2003,21(6):92-96. 系统应用，2013,22(2)：88-91. [12]程代展，齐洪胜.矩阵的半张量积理论与应用[M].北 WANG Haishuai,JI Zhenyan,WANG Sen.Bus transport 京：科学出版社，2007. transfer algorithm[J].Computer Systems and Applications, [13]YAO Baozhen,HU Ping,LU Xiaohong,et al.Transit net- 2013,22(2):88-91. work design based on travel time reliability[J].Transpor- [4]王防肠，于丽娜，郑保华，等.“集合燃烧”算法在公交 tation Research,Part C:Emerging Technologies,2014, 网络查询中的应用[J].辽宁工程技术大学学报：社会 43(3):233-248. 科学版，2008,10(4)：380-382 [14]张译，靳香翔，张毅，等.基于二分图的城市公交网络 WANG Fangyang,YU Lina,ZHENG Baohua,et al."Ag- 拓扑性质研究[J].系统工程理论与实践，2007,27 gregate-combustion"arithmetic and its application in the (7):149-155
即 Ｓ ′ ４ 中的 Ｓ５ 站点与 Ｓ６ 站点可与 Ｓ８ 站点直达，而 且它们分别都在 Ｌ３ 线路上，则可求得 ｄ（ Ｓ４ ，Ｓ９ ） ＝ ｍｉｎ ｗ ２ ４，５ ＋ ｗ ３ ５，８ ＋ ｗ ４ ８，９ ，ｗ ０ ４，６ ＋ ｗ ３ ６，８ ＋ ｗ ４ ８，９ { } ＝ ｍｉｎ｛ ６ ＋ ７ ＋ ５，１ ＋ ４ ＋ ５｝ ＝ １０ 对应最优路线为从 Ｓ４ 站点乘坐地铁线路 Ｌ０ 到达 Ｓ６ 站点，转乘公交线路 Ｌ３ 到达 Ｓ８ 站点，再转乘公 交线路 Ｌ４ 到达 Ｓ９ 站点，途径 １０ 站。 ５ 结束语 在文献［１０］的基础上，将公交地铁进行一体化 标号，缩小地铁两站点间的路径距离以达到优选地 铁的目的。 据乘客出行心理，依次以换乘次数少、出 行距离短为优化目标，利用高维数组运算，根据公交 地铁网络图与二分图、线路映射网络图、站点映射网 络图得到两站点间的最优路径的选择算法。 公交网络的寻径问题一直以来被认为是 ＮＰ 难 问题，而日益发达的公交系统对最优路径选择算法的 要求也越来越高。 因此，改进和创新算法在整个公交 系统中至关重要。 本文尚未将地铁的时变性考虑在 内，可对此进一步研究，使得人们无论何时出行都有 一个对应此时间点的方案，使查询更加精确可靠。 参考文献： ［１］闫小勇， 尚艳亮． 基于二部图模型的公交网络路径搜索 算法［Ｊ］． 计算机工程与应用， ２０１０， ４６（５）： ２４６⁃２４８． ＹＡＮ Ｘｉａｏｙｏｎｇ， ＳＨＡＮＧ Ｙａｎｌｉａｎｇ． Ｐａｔｈ⁃ｆｉｎｄｉｎｇ ａｌｇｏｒｉｔｈｍ ｏｆ ｐｕｂｌｉｃ ｔｒａｎｓｐｏｒｔ ｎｅｔｗｏｒｋｓ ｂａｓｅｄ ｏｎ ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ ｍｏｄｅｌ ［Ｊ ］． Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， ２０１０， ４６ （５）： ２４６⁃２４８． ［２］梁虹， 袁小群， 刘蕊． 一种新的公交数据模型与公交查 询系统实现［Ｊ］． 计算机工程与应用， ２００７， ４３（３）： ２３４⁃ ２３８． ＬＩＡＮＧ Ｈｏｎｇ， ＹＵＡＮ Ｘｉａｏｑｕｎ， ＬＩＵ Ｒｕｉ． Ｎｏｖｅｌ ｍｏｄｅｌ ａｎｄ ｒｅａｌｉｚａｔｉｏｎ ｏｆ ｐｕｂｌｉｃ ｔｒａｎｓｐｏｒｔ ｒｏｕｔｅ ｉｎｑｕｉｒｉｎｇ ｓｙｓｔｅｍ ［ Ｊ］． Ｃｏｍｐｕｔｅｒ Ｅｎｇｉｎｅｅｒｉｎｇ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， ２００７， ４３ （ ３ ）： ２３４⁃２３８． ［３］王海帅， 冀振燕， 王森． 公交线路查询算法［ Ｊ］． 计算机 系统应用， ２０１３， ２２（２）： ８８⁃９１． ＷＡＮＧ Ｈａｉｓｈｕａｉ， ＪＩ Ｚｈｅｎｙａｎ， ＷＡＮＧ Ｓｅｎ． Ｂｕｓ ｔｒａｎｓｐｏｒｔ ｔｒａｎｓｆｅｒ ａｌｇｏｒｉｔｈｍ［ Ｊ］． Ｃｏｍｐｕｔｅｒ Ｓｙｓｔｅｍｓ ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ， ２０１３， ２２（２）： ８８⁃９１． ［４］王昉旸， 于丽娜， 郑保华， 等． “集合燃烧”算法在公交 网络查询中的应用［ Ｊ］． 辽宁工程技术大学学报： 社会 科学版， ２００８， １０（４）： ３８０⁃３８２． ＷＡＮＧ Ｆａｎｇｙａｎｇ， ＹＵ Ｌｉｎａ， ＺＨＥＮＧ Ｂａｏｈｕａ， ｅｔ ａｌ． “Ａｇ⁃ ｇｒｅｇａｔｅ⁃ｃｏｍｂｕｓｔｉｏｎ” ａｒｉｔｈｍｅｔｉｃ ａｎｄ ｉｔｓ ａｐｐｌｉｃａｔｉｏｎ ｉｎ ｔｈｅ ｑｕｅｒｙ ｓｙｓｔｅｍ ｏｆ ｔｒａｎｓｉｔ ｎｅｔｗｏｒｋ ［ Ｊ ］． Ｊｏｕｒｎａｌ ｏｆ Ｌｉａｏｎｉｎｇ Ｔｅｃｈｎｉｃａｌ Ｕｎｉｖｅｒｓｉｔｙ： Ｓｏｃｉａｌ Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ， ２００８， １０ （４）： ３８０⁃３８２． ［５］伍雁鹏， 彭小奇， 杨恒伏． 改进的基于关系数据库技术 的公交查询算法 ［ Ｊ］． 中南大学学报： 自然科学版， ２００９， ４０（３）： ７６３⁃７６６． ＷＵ Ｙａｎｐｅｎｇ， ＰＥＮＧ Ｘｉａｏｑｉ， ＹＡＮＧ Ｈｅｎｇｆｕ． Ｉｍｐｒｏｖｅｄ ａｌ⁃ ｇｏｒｉｔｈｍ ｂａｓｅｄ ｏｎ ｒｅｌａｔｉｏｎａｌ ｄａｔａｂａｓｅ ｔｅｃｈｎｏｌｏｇｙ ｆｏｒ ｑｕｅｒｙｉｎｇ ｔｒａｎｓｉｔ ｎｅｔｗｏｒｋ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｅｎｔｒａｌ Ｓｏｕｔｈ Ｕｎｉｖｅｒｓｉｔｙ： Ｓｃｉ⁃ ｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ， ２００９， ４０（３）： ７６３⁃７６６． ［６］刘健， 徐维祥， 刘旭敏． 公交出行最优路线查询系统设 计［Ｊ］． 计算机应用， ２００９， ２９（Ｓ２）： １１０⁃１１２． ＬＩＵ Ｊｉａｎ， ＸＵ Ｗｅｉｘｉａｎｇ， ＬＩＵ Ｘｕｍｉｎ． Ｄｅｓｉｇｎ ｏｆ ｕｒｂａｎ ｐｕｂ⁃ ｌｉｃ ｔｒａｎｓｉｔ ｏｐｔｉｍａｌ ｒｏｕｔｅ ｉｎｑｕｉｒｙ ｓｙｓｔｅｍ［Ｊ］． Ｊｏｕｒｎａｌ ｏｆ Ｃｏｍ⁃ ｐｕｔｅｒ Ａｐｐｌｉｃａｔｉｏｎｓ， ２００９， ２９（Ｓ２）： １１０⁃１１２． ［７］伍雁鹏， 彭小奇， 黄同成． 基于路径集合运算的公交网 络寻径算法研究［ Ｊ］． 计算机科学， ２００９， ３６（ ６）： ２３９⁃ ２４０， ２７２． ＷＵ Ｙａｎｐｅｎｇ， ＰＥＮＧ Ｘｉａｏｑｉ， ＨＵＡＮＧ Ｔｏｎｇｃｈｅｎｇ． Ｒｅ⁃ ｓｅａｒｃｈ ｏｎ ｐａｔｈ ｓｅｔ ｏｐｅｒａｔｉｏｎ ｂａｓｅｄ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｐａｔｈ ｓｅａｒｃｈ⁃ ｉｎｇ ｉｎ ｐｕｂｌｉｃ ｔｒａｎｓｉｔ ｎｅｔｗｏｒｋ［Ｊ］． Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ， ２００９， ３６（６）： ２３９⁃２４０， ２７２． ［８］刘作虎， 黄明和， 邹小云， 等． 一种网络公交查询系统 的改进算法［Ｊ］． 计算机与信息技术， ２００９， （４）： ２９⁃３１． ［９］徐勇， 李杰， 张军芳， 等． 新型公交网络模型与最优线 路选择算法［Ｊ］． 系统工程理论与实践， ２０１１， ３１（１１）： ２２３４⁃２２４０． ＸＵ Ｙｏｎｇ， ＬＩ Ｊｉｅ， ＺＨＡＮＧ Ｊｕｎｆａｎｇ， ｅｔ ａｌ． Ｎｅｗ ｕｒｂａｎ ｔｒａｎｓｉｔ ｎｅｔｗｏｒｋ ｍｏｄｅｌｓ ａｎｄ ｏｐｔｉｍａｌ ｐａｔｈ ｓｅａｒｃｈｉｎｇ ａｌｇｏｒｉｔｈｍ ［ Ｊ］． Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ—Ｔｈｅｏｒｙ ａｎｄ Ｐｒａｃｔｉｃｅ， ２０１１， ３１ （１１）： ２２３４⁃２２４０． ［１０］刘旭浩， 徐勇． 基于半张量积理论的公交网络查询［ Ｊ］． 复杂系统与复杂性科学， ２０１３， １０（１）： ３８⁃４４． ＬＩＵ Ｘｕｈａｏ， ＸＵ Ｙｏｎｇ． Ａｎ ｉｎｑｕｉｒｙ ｍｅｔｈｏｄ ｏｆ ｔｒａｎｓｉｔ ｎｅｔ⁃ ｗｏｒｋ ｂａｓｅｄ ｏｎ ｓｅｍｉ⁃ｔｅｎｓｏｒ ｐｒｏｄｕｃｔ［ Ｊ］． Ｃｏｍｐｌｅｘ Ｓｙｓｔｅｍｓ ａｎｄ Ｃｏｍｐｌｅｘｉｔｙ Ｓｃｉｅｎｃｅ， ２０１３， １０（１）： ３８⁃４４． ［１１］张林峰， 范炳全， 吕智林． 公交网络换乘矩阵的分析与 算法［Ｊ］． 系统工程， ２００３， ２１（６）： ９２⁃９６． ＺＨＡＮＧ Ｌｉｎｆｅｎｇ， ＦＡＮ Ｂｉｎｇｑｕａｎ， ＬÜ Ｚｈｉｌｉｎ． Ｔｒａｎｓｆｅｒ ｍａ⁃ ｔｒｉｘ ｏｆ ｐｕｂｌｉｃ ｔｒａｎｓｉｔ ｎｅｔｗｏｒｋ ａｎｄ ａｌｇｏｒｉｔｈｍ ［ Ｊ］． Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ， ２００３， ２１（６）： ９２⁃９６． ［１２］程代展， 齐洪胜． 矩阵的半张量积理论与应用［Ｍ］． 北 京： 科学出版社， ２００７． ［１３］ＹＡＯ Ｂａｏｚｈｅｎ， ＨＵ Ｐｉｎｇ， ＬＵ Ｘｉａｏｈｏｎｇ， ｅｔ ａｌ． Ｔｒａｎｓｉｔ ｎｅｔ⁃ ｗｏｒｋ ｄｅｓｉｇｎ ｂａｓｅｄ ｏｎ ｔｒａｖｅｌ ｔｉｍｅ ｒｅｌｉａｂｉｌｉｔｙ［ Ｊ］． Ｔｒａｎｓｐｏｒ⁃ ｔａｔｉｏｎ Ｒｅｓｅａｒｃｈ， Ｐａｒｔ Ｃ： Ｅｍｅｒｇｉｎｇ Ｔｅｃｈｎｏｌｏｇｉｅｓ， ２０１４， ４３（３）： ２３３⁃２４８． ［１４］张译， 靳雪翔， 张毅， 等． 基于二分图的城市公交网络 拓扑性质研究［ Ｊ］． 系统工程理论与实践， ２００７， ２７ （７）： １４９⁃１５５． ·４８６· 智 能 系 统 学 报 第 １０ 卷
第3期 徐勇，等：公交地铁一体化下的网络模型与最优路选择算法 .487. ZHANG Yi,JIN Xuexiang,ZHANG Yi,et al.Topological 贾欣，女，1991年生，主要研究方向 analysis of urban transit networks using bipartite graph 为图论与交通网络优化。 model [J].Systems Engineering-Theory Practice, 2007,27(7):149-155. [15]王炜，杨新苗，陈学武.城市公共交通系统规划方法与 管理技术[M].北京：科学出版社，2002 作者简介： 徐勇，男，1971年生，教授.博士，主 王哲，男，1990年生，主要研究方向 要研究方向为复杂网络建模与优化。 为图论与交通网络优化。 参与或主持省部级科研项目10余项， 发表学术论文30余篇，其中被EI检索 10余篇。 2016年IEEE计算智能世界大会 2016 IEEE World Congress on Computational Intelligence 25-29 July 2016,Vancouver,Canada The IEEE World Congress on Computational Intelligence (IEEE WCCI)is the largest technical event in the field of com- putational intelligence.The IEEE WCCI 2016 will host three conferences:The 2016 International Joint Conference on Neural Networks IJCNN 2016),the 2016 IEEE International Conference on Fuzzy Systems FUZZ-IEEE 2016),and the 2016 IEEE Congress on Evolutionary Computation (IEEE CEC 2016)under one roof.It encourages cross-fertilization of i- deas among the three big areas and provides a forum for intellectuals from all over the world to discuss and present their re- search findings on computational intelligence. IEEE WCCI 2016 will be held at the Vancouver Convention Centre,Vancouver,Canada.Vancouver is Canada's Pacific gem,offering a winning combination of world-class hotels,meeting venues,and restaurants in a setting of spectacular beauty.Few convention cities can offer such a wide range of cosmopolitan amenities in a downtown core that is safe,clean, pedestrian friendly,and stunning in its backdrop of mountains and ocean. IJCNN is the flagship conference of the International Neural Network Society and the IEEE Computational Intelligence So- ciety.It covers a wide range of topics in the field of neural networks,from biological neural network modeling to artificial neural computation. FUZZ-IEEE is the foremost conference in the field of fuzzy systems.It covers all topics in fuzzy systems,from theory to ap- plications. IEEE CEC is a major event in the field of evolutionary computation,and covers all topics in evolutionary computation from theory to applications. Papers for IEEE WCCI 2016 should be submitted electronically through the Congress website at www.wcci2016.org,and will be refereed by experts in the fields and ranked based on the criteria of originality,significance,quality and clarity. Find Us At: www.wcci2016.org weci2016@gmail.com
ＺＨＡＮＧ Ｙｉ， ＪＩＮ Ｘｕｅｘｉａｎｇ， ＺＨＡＮＧ Ｙｉ， ｅｔ ａｌ． Ｔｏｐｏｌｏｇｉｃａｌ ａｎａｌｙｓｉｓ ｏｆ ｕｒｂａｎ ｔｒａｎｓｉｔ ｎｅｔｗｏｒｋｓ ｕｓｉｎｇ ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ ｍｏｄｅｌ ［ Ｊ ］． Ｓｙｓｔｅｍｓ Ｅｎｇｉｎｅｅｒｉｎｇ—Ｔｈｅｏｒｙ ＆ Ｐｒａｃｔｉｃｅ， ２００７， ２７（７）： １４９⁃１５５． ［１５］王炜， 杨新苗， 陈学武． 城市公共交通系统规划方法与 管理技术［Ｍ］． 北京： 科学出版社， ２００２． 作者简介： 徐勇，男，１９７１ 年生，教授，博士，主 要研究方向为复杂网络建模与优化。 参与或主持省部级科研项目 １０ 余项， 发表学术论文 ３０ 余篇，其中被 ＥＩ 检索 １０ 余篇。 贾欣，女，１９９１ 年生，主要研究方向 为图论与交通网络优化。 王哲，男，１９９０ 年生，主要研究方向 为图论与交通网络优化。 ２０１６ 年 ＩＥＥＥ 计算智能世界大会 ２０１６ ＩＥＥＥ Ｗｏｒｌｄ Ｃｏｎｇｒｅｓｓ ｏｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ ２５－２９ Ｊｕｌｙ ２０１６， Ｖａｎｃｏｕｖｅｒ， Ｃａｎａｄａ Ｔｈｅ ＩＥＥＥ Ｗｏｒｌｄ Ｃｏｎｇｒｅｓｓ ｏｎ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ （ＩＥＥＥ ＷＣＣＩ） ｉｓ ｔｈｅ ｌａｒｇｅｓｔ ｔｅｃｈｎｉｃａｌ ｅｖｅｎｔ ｉｎ ｔｈｅ ｆｉｅｌｄ ｏｆ ｃｏｍ⁃ ｐｕｔａｔｉｏｎａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ． Ｔｈｅ ＩＥＥＥ ＷＣＣＩ ２０１６ ｗｉｌｌ ｈｏｓｔ ｔｈｒｅｅ ｃｏｎｆｅｒｅｎｃｅｓ： Ｔｈｅ ２０１６ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｉｎｔ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋｓ （ＩＪＣＮＮ ２０１６）， ｔｈｅ ２０１６ ＩＥＥＥ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｆｕｚｚｙ Ｓｙｓｔｅｍｓ （ＦＵＺＺ⁃ＩＥＥＥ ２０１６）， ａｎｄ ｔｈｅ ２０１６ ＩＥＥＥ Ｃｏｎｇｒｅｓｓ ｏｎ Ｅｖｏｌｕｔｉｏｎａｒｙ Ｃｏｍｐｕｔａｔｉｏｎ （ＩＥＥＥ ＣＥＣ ２０１６） ｕｎｄｅｒ ｏｎｅ ｒｏｏｆ． Ｉｔ ｅｎｃｏｕｒａｇｅｓ ｃｒｏｓｓ⁃ｆｅｒｔｉｌｉｚａｔｉｏｎ ｏｆ ｉ⁃ ｄｅａｓ ａｍｏｎｇ ｔｈｅ ｔｈｒｅｅ ｂｉｇ ａｒｅａｓ ａｎｄ ｐｒｏｖｉｄｅｓ ａ ｆｏｒｕｍ ｆｏｒ ｉｎｔｅｌｌｅｃｔｕａｌｓ ｆｒｏｍ ａｌｌ ｏｖｅｒ ｔｈｅ ｗｏｒｌｄ ｔｏ ｄｉｓｃｕｓｓ ａｎｄ ｐｒｅｓｅｎｔ ｔｈｅｉｒ ｒｅ⁃ ｓｅａｒｃｈ ｆｉｎｄｉｎｇｓ ｏｎ ｃｏｍｐｕｔａｔｉｏｎａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ． ＩＥＥＥ ＷＣＣＩ ２０１６ ｗｉｌｌ ｂｅ ｈｅｌｄ ａｔ ｔｈｅ Ｖａｎｃｏｕｖｅｒ Ｃｏｎｖｅｎｔｉｏｎ Ｃｅｎｔｒｅ， Ｖａｎｃｏｕｖｅｒ， Ｃａｎａｄａ． Ｖａｎｃｏｕｖｅｒ ｉｓ Ｃａｎａｄａ＇ｓ Ｐａｃｉｆｉｃ ｇｅｍ， ｏｆｆｅｒｉｎｇ ａ ｗｉｎｎｉｎｇ ｃｏｍｂｉｎａｔｉｏｎ ｏｆ ｗｏｒｌｄ⁃ｃｌａｓｓ ｈｏｔｅｌｓ， ｍｅｅｔｉｎｇ ｖｅｎｕｅｓ， ａｎｄ ｒｅｓｔａｕｒａｎｔｓ ｉｎ ａ ｓｅｔｔｉｎｇ ｏｆ ｓｐｅｃｔａｃｕｌａｒ ｂｅａｕｔｙ． Ｆｅｗ ｃｏｎｖｅｎｔｉｏｎ ｃｉｔｉｅｓ ｃａｎ ｏｆｆｅｒ ｓｕｃｈ ａ ｗｉｄｅ ｒａｎｇｅ ｏｆ ｃｏｓｍｏｐｏｌｉｔａｎ ａｍｅｎｉｔｉｅｓ ｉｎ ａ ｄｏｗｎｔｏｗｎ ｃｏｒｅ ｔｈａｔ ｉｓ ｓａｆｅ， ｃｌｅａｎ， ｐｅｄｅｓｔｒｉａｎ ｆｒｉｅｎｄｌｙ， ａｎｄ ｓｔｕｎｎｉｎｇ ｉｎ ｉｔｓ ｂａｃｋｄｒｏｐ ｏｆ ｍｏｕｎｔａｉｎｓ ａｎｄ ｏｃｅａｎ． ＩＪＣＮＮ ｉｓ ｔｈｅ ｆｌａｇｓｈｉｐ ｃｏｎｆｅｒｅｎｃｅ ｏｆ ｔｈｅ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｎｅｕｒａｌ Ｎｅｔｗｏｒｋ Ｓｏｃｉｅｔｙ ａｎｄ ｔｈｅ ＩＥＥＥ Ｃｏｍｐｕｔａｔｉｏｎａｌ Ｉｎｔｅｌｌｉｇｅｎｃｅ Ｓｏ⁃ ｃｉｅｔｙ． Ｉｔ ｃｏｖｅｒｓ ａ ｗｉｄｅ ｒａｎｇｅ ｏｆ ｔｏｐｉｃｓ ｉｎ ｔｈｅ ｆｉｅｌｄ ｏｆ ｎｅｕｒａｌ ｎｅｔｗｏｒｋｓ， ｆｒｏｍ ｂｉｏｌｏｇｉｃａｌ ｎｅｕｒａｌ ｎｅｔｗｏｒｋ ｍｏｄｅｌｉｎｇ ｔｏ ａｒｔｉｆｉｃｉａｌ ｎｅｕｒａｌ ｃｏｍｐｕｔａｔｉｏｎ． ＦＵＺＺ⁃ＩＥＥＥ ｉｓ ｔｈｅ ｆｏｒｅｍｏｓｔ ｃｏｎｆｅｒｅｎｃｅ ｉｎ ｔｈｅ ｆｉｅｌｄ ｏｆ ｆｕｚｚｙ ｓｙｓｔｅｍｓ． Ｉｔ ｃｏｖｅｒｓ ａｌｌ ｔｏｐｉｃｓ ｉｎ ｆｕｚｚｙ ｓｙｓｔｅｍｓ， ｆｒｏｍ ｔｈｅｏｒｙ ｔｏ ａｐ⁃ ｐｌｉｃａｔｉｏｎｓ． ＩＥＥＥ ＣＥＣ ｉｓ ａ ｍａｊｏｒ ｅｖｅｎｔ ｉｎ ｔｈｅ ｆｉｅｌｄ ｏｆ ｅｖｏｌｕｔｉｏｎａｒｙ ｃｏｍｐｕｔａｔｉｏｎ， ａｎｄ ｃｏｖｅｒｓ ａｌｌ ｔｏｐｉｃｓ ｉｎ ｅｖｏｌｕｔｉｏｎａｒｙ ｃｏｍｐｕｔａｔｉｏｎ ｆｒｏｍ ｔｈｅｏｒｙ ｔｏ ａｐｐｌｉｃａｔｉｏｎｓ． Ｐａｐｅｒｓ ｆｏｒ ＩＥＥＥ ＷＣＣＩ ２０１６ ｓｈｏｕｌｄ ｂｅ ｓｕｂｍｉｔｔｅｄ ｅｌｅｃｔｒｏｎｉｃａｌｌｙ ｔｈｒｏｕｇｈ ｔｈｅ Ｃｏｎｇｒｅｓｓ ｗｅｂｓｉｔｅ ａｔ ｗｗｗ．ｗｃｃｉ２０１６．ｏｒｇ， ａｎｄ ｗｉｌｌ ｂｅ ｒｅｆｅｒｅｅｄ ｂｙ ｅｘｐｅｒｔｓ ｉｎ ｔｈｅ ｆｉｅｌｄｓ ａｎｄ ｒａｎｋｅｄ ｂａｓｅｄ ｏｎ ｔｈｅ ｃｒｉｔｅｒｉａ ｏｆ ｏｒｉｇｉｎａｌｉｔｙ， ｓｉｇｎｉｆｉｃａｎｃｅ， ｑｕａｌｉｔｙ ａｎｄ ｃｌａｒｉｔｙ． Ｆｉｎｄ Ｕｓ Ａｔ： ｗｗｗ．ｗｃｃｉ２０１６．ｏｒｇ ｗｃｃｉ２０１６＠ ｇｍａｉｌ．ｃｏｍ 第 ３ 期 徐勇，等：公交地铁一体化下的网络模型与最优路选择算法 ·４８７·