第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。 线路之间的连通关系，两站点所在的线路在线路映于数据库的查询算法［２，５］ 和基于矩阵运算的查询算 法［１１］ 。 目前针对地铁主导下的公交网络的最短路 径搜索算法却不多见。 考虑到地铁在大城市公交系统中日益占主导地 位这一事实，在文献［９］的基础上，将优选地铁出行 作为基本出发点，对公交与地铁站点标号的同时，将 地铁线路上站点间的权值成倍缩小，再依次按照换 乘次数、乘车距离进行路径选择时就达到了优选地 铁的目的，且一体化后的模型更加清晰、简便。 １ 高维数组的表示 称一个数组是 ｋ 维的，如果它的元素是由 ｋ 个 指标 索 引 的， 更 确 切 地 说， 称 Ｓ 是 一 个 形 如 Ｉｄ ｉ １ ，ｉ ２ ，…，ｉ ｋ；ｎ１ ，ｎ２ ，…，ｎｋ ( ) 的 ｋ 维数组，如果它能 表示成［１０，１２］ ： Ｓ ＝ Ｓｉ１ ，ｉ２ ，…，ｉｋ ｜ ｉ １ ＝ １，２，…，ｎ１ ；…；ｉ ｋ ＝ １，２，…，ｎｋ { } Ｓ 的大小，即 Ｓ 中元素的个数，记作 ｜ Ｓ ｜ 。 且 ｜ Ｓ ｜ ＝ ｎ１ × ｎ２ × … × ｎｋ 。 记 σ(１) ，σ(２) ，…，σ(ｋ) 是 １，２，…，ｋ 的一个 排列，若它能排成一个 ｎσ (ｔ) × ｎσ (１ ) …ｎσ (ｔ－１ ) ｎσ (ｔ＋１ ) …ｎσ (ｋ ) 的矩阵，称它是按照 ｔ １，…，ｔ － １，ｔ ＋ １，…，ｋ é ë ê ê ù û ú ú 形式 排列的，即按照 ｔ ⁃行形式排列的。 文中需记录大量两站点 ｉ，ｊ 在 Ｌｋ 线路上所经过 的站点数，它是三维数组，记公交地铁网络信息矩阵 Ｗ ＝ ｗ ｋ ｉ，ｊ [ ] ｎ×ｎ×ｍ ， ｗ ｋ ｉ，ｊ 表示 ｉ，ｊ 两站点在 Ｌｋ 线路上所 经过的站点数， ｍ 表示有 ｍ 条公交地铁线路， ｎ 表 示有 ｎ 个公交地铁站点。 ２ 公交地铁网络优化模型 ２．１ 公交地铁网络图 公交地铁网络是由公交线路和地铁线路组成的 网络［１３］ ，每条线路经过若干站点，每个站点有多条 线路通过，记站点集合 Ｓ ＝ Ｓ１ ，Ｓ２ ，…，Ｓｎ { } ，其中 Ｓ１ ， Ｓ２ ，…，Ｓｎ 为站点；线路集合 Ｌ ＝ Ｌ１ ，Ｌ２ ，…，Ｌｍ { } ，其 中 Ｌ１ ，Ｌ２ ，…，Ｌｍ 为线路。 由站点集合 Ｓ 和线路集合 Ｌ 构成的二元组 Ｈ ＝ {Ｓ，Ｌ} 反映到图上，即为公交 地铁网络图。 例如，某公交地铁网络由 １ 条地铁线路、２ 条公 交线路、２ 个地铁站点（地铁站点都为公交站点）和 ２ 个公交站点（不包含前述地铁站点）组成，他们分 别为地铁线路 Ｌ０ ，公交线路 Ｌ１ 、Ｌ２ ，地铁站点 Ｓ１ 、Ｓ２ ， 公交站点 Ｓ３ 、Ｓ４ ，如图 １。 图 １ 公交地铁网络 Ｆｉｇ． １ Ｂｕｓ ａｎｄ ｓｕｂｗａｙ ｎｅｔｗｏｒｋ ２．２ 公交地铁网络的二分图模型 公交地铁网络二分图是三元组 Ｇ ＝ (Ｓ，Ｌ，Ｅ) ， 其中 Ｓ 和 Ｌ 是 ２ 个不相交的顶点集，分别为顶部和 底部的顶点集，并且 Ｅ ⊆ Ｓ × Ｌ 是一个边集，边连接 顶部和底部的顶点。 具有 ２ 种属性的复杂网络可用二分图表示［１４－１５］ ． 公交地铁网络的站点和线路 ２ 种属性决定了它可以 反映到二分图上。 将顶点集合 Ｓ 看作二分图的上顶 点集，线路集合 Ｌ 看作二分图的下顶点集，公交线路 Ｌ ′ 经过站点 Ｓ ′ ，则在 Ｌ ′ 线路与 Ｓ ′ 站点之间有边相连。 图 ２ 是图 １ 的公交网络对应的网络二分图。 图 ２ 网络二分图 Ｆｉｇ． ２ Ｂｉｐａｒｔｉｔｅ ｎｅｔｗｏｒｋ ｇｒａｐｈ 由图 ２ 看出， Ｓ１ 与 Ｓ２ 可直接到达， Ｓ１ 与 Ｓ３ 需经 过 Ｓ２ 转乘， Ｓ１ 与 Ｓ４ 需经过 Ｓ２ ，Ｓ３ 转乘到达。 二分图 比网络图更加直观地显示出换乘次数。 ２．３ 公交地铁网络图的映射图 公交地铁网络图的映射图包括线路映射网络图 和站点映射网络图，可以由二分图得到。 二分图 Ｇ ＝ (Ｓ，Ｌ，Ｅ) 的上顶点映射图（即站点 映 射 网 络 图 ） 为 Ｇ Ｓ ＝ Ｓ，Ｅ Ｓ ( ) ， 边 集 Ｅ Ｓ ＝ ＳｉＳｊ { ｜ Ｎ（Ｓｉ） ∩ Ｎ（Ｓｊ） ≠ ∅} ，其中 Ｎ（Ｓｉ） 为 Ｓｉ 在 二分图中的邻接点集合。 它的下顶点映射图（即线 路 映 射 网 络 图 ） 为 Ｇ Ｌ ＝ Ｌ，Ｅ Ｌ ( ) ， 边 集 Ｅ Ｌ ＝ ＬｉＬｊ { ｜ Ｎ（Ｌｉ） ∩ Ｎ（Ｌｊ） ≠ ∅} ，其中 Ｎ（Ｌｉ） 为 Ｌｉ 在 二分图中的邻接点集合。 线路映射网络图能反映出 线路之间的连通关系，两站点所在的线路在线路映 第 ３ 期 徐勇，等：公交地铁一体化下的网络模型与最优路选择算法 ·４８３·