日益现代化的交通方式给人们出行带来很大便利，其中公交与地铁是大型城市中的主要交通工具。考虑到我国人口众多，城市交通拥堵问题日益严重，对公交地铁系统的研究已成为一个热门又困难的课题。公交地铁系统的研究主要包括网络构建、公交配流与最优路选择算法3个方面，而查询算法在其中起到核心作用，它为人们提供出行的路径选择，切身关系到整个公交地铁网络是否高效运作，是公交系统研究的核心问题之一。

目前虽然有一系列针对公交网络的最短路径搜索算法^{[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]}，主要包括基于图论的查询算法^{[1, 9]}，基于数据库的查询算法^{[2, 5]}和基于矩阵运算的查询算法^[11]。目前针对地铁主导下的公交网络的最短路径搜索算法却不多见。

考虑到地铁在大城市公交系统中日益占主导地位这一事实，在文献^[9]的基础上，将优选地铁出行作为基本出发点，对公交与地铁站点标号的同时，将地铁线路上站点间的权值成倍缩小，再依次按照换乘次数、乘车距离进行路径选择时就达到了优选地铁的目的，且一体化后的模型更加清晰、简便。

称一个数组是k维的，如果它的元素是由k个指标索引的，更确切地说，称S是一个形如 Id(i₁,i₂,…,i_k;n₁,n₂,…,n_k)的k维数组，如果它能表示成^{[10, 12]}：

S的大小，即S中元素的个数，记作|S|。且|S|=n1×n2×…×n_k。
记σ(1),σ(2),…,σ(k)是1,2,…,k的一个排列，若它能排成一个

文中需记录大量两站点i,j在L_k线路上所经过的站点数，它是三维数组，记公交地铁网络信息矩阵W=[w_i,j^k]_n×n×m，w_i,j^k表示i,j两站点在L_k线路上所经过的站点数，m表示有m条公交地铁线路，n表示有n个公交地铁站点。

公交地铁网络是由公交线路和地铁线路组成的网络^[13]，每条线路经过若干站点，每个站点有多条线路通过，记站点集合S={S₁,S₂,…,S_n}，其中S₁,S₂,…,S_n为站点；线路集合L={L₁,L₂,…,L_m}，其中L₁,L₂,…,L_m为线路。由站点集合S和线路集合L构成的二元组H={S,L}反映到图上，即为公交地铁网络图。

例如，某公交地铁网络由1条地铁线路、2条公交线路、2个地铁站点(地铁站点都为公交站点)和2个公交站点(不包含前述地铁站点)组成，他们分别为地铁线路L₀，公交线路L₁、L₂，地铁站点S₁、S₂，公交站点S₃、S₄，如图 1。

图 1 公交地铁网络 Fig. 1 Bus and subway network

图选项

公交地铁网络二分图是三元组G=(S,L,E)，其中S和L是2个不相交的顶点集，分别为顶部和底部的顶点集，并且E⊆S×L是一个边集，边连接顶部和底部的顶点。

具有2种属性的复杂网络可用二分图表示^{[14, 15]}.公交地铁网络的站点和线路2种属性决定了它可以反映到二分图上。将顶点集合S看作二分图的上顶点集，线路集合L看作二分图的下顶点集，公交线路L′经过站点S′，则在L′线路与S′站点之间有边相连。图 2是图 1的公交网络对应的网络二分图。

图 2 网络二分图 Fig. 2 Bipartite network graph

图选项

由图 2看出，S₁与S₂可直接到达，S₁与S₃需经过S₂转乘，S₁与S₄需经过S₂,S₃转乘到达。二分图比网络图更加直观地显示出换乘次数。

公交地铁网络图的映射图包括线路映射网络图和站点映射网络图，可以由二分图得到。

二分图G=(S,L,E)的上顶点映射图(即站点映射网络图)为G^S=(S,E^S)，边集E^S= {S_iS_j|N(S_i)∩N(S_j)≠∅}，其中N(S_i)为S_i在二分图中的邻接点集合。它的下顶点映射图(即线路映射网络图)为G^L=(L,E^L)，边集E^L={L_iL_j|N(L_i)∩N(L_j)≠∅}，其中N(L_i)为L_i在二分图中的邻接点集合。线路映射网络图能反映出线路之间的连通关系，两站点所在的线路在线路映射网络图中所连接的边数反映了乘客的换乘次数。站点映射网络图表示站点之间的连通关系，它能反映出乘客换乘次数的同时，也给出了换乘站点。

图 3为图 2的线路映射网络图，图 4为图 2的站点映射网络图。由图 3可以看出，L₁与L₀、L₂之间分别为一条边，即若出发站点在L₁站点上，目的地站点在L₀站点或L₂站点上，转乘1次公交或者地铁即可到达。若出发站点在L₀线路上，目的地站点在L₂线路上，则需在L₁线路上的某2个站点处转乘，乘坐3次公交或地铁即可到达目的地。由图 4可以看出，S₁与S₂有一条边相连，即两站点在一条线路上，可以直达。S₁与S₃之间有2条边，且经过S₂站点，则从S₁站点到达S₃站点必须在S₂站点转乘，即坐2次公交或地铁到达。S₁与S₄之间有3条边相连，从图可直接看出，由S₁站点出发，需在S₂和S₃站点转乘，以到达S₄站点。

图 3 线路映射网络图 Fig. 3 Line mapping network graph

图选项

图 4 站点映射网络图 Fig. 4 Site mapping network graph

图选项

首先对每条线路上的站点进行一体化标号，考虑到地铁的快捷性、准时性、舒适性等优点，优选地铁出行是大势所趋。这样，将地铁线路上两站点间乘车距离权值适当减小，这样就达到了优选地铁出行的目的。

若线路L_k上有k_n个站点，L_k:S_k1,S_k2,…,S_kn，站点S_kj在线路L_k上的标号为j，记为N_j^k=j，在二分网络图中边L_kS_kj的权值为该站点在线路L_k上的标号：N_j^k=j。

然后建立公交地铁线路映射网络和站点映射网络。在站点映射网络中，对边S_iS_j赋值，记为w_i,j^k，且w_i,j^k=|N_j^k－N_i^k|，它代表在L_k线路上S_i、S_j两站点之间的站点数。若S_i、S_j不在L_k线路上，令w_i,j^k=0。

1)给出任两站点S_i与S_j，构造直达检验向量α_ij=W▷e_i▷e_j，其中W=[w_i,j^k]_n×n×m，e_i表示第i个元素为1，其余全为0的n维单位向量，若α_ij=(w_i,j¹,w_i,j²,…,w_i,j^m)|^T≠0，则S_i站点与S_j站点可以直达，若v=arg{w_i,j^k}，则w_i,j^v为S_i与S_j站点之间的最小直达距离，最优路径为L_v。

2)若S_i站点与S_j站点不可直达，根据站点映射网络图，记与S_i站点邻接的站点集合S′_i={S_i1,S_i2,…,S_ik}与S_j站点邻接的站点集合S′_j={S_j1,S_j2,…,S_jl}，若S′_i∩S′_j≠∅，则表示S_i站点与S_j站点转乘一次可到达，记S′_i∩S′_j={S_r1,S_r2,…,S_rp}，则S_i与S_j可经p种方法到达，则d(S_i,S_j)=min{w_i,r^l+w_r,j^l′}，L_l∈L,L_l′∈L′，根据公交网络二分图，L与L′分别为连接S_i与S_r，S_r与S_j站点的线路，其对应的路线为最优出行路线。

3)若S′_i∩S′_j=∅，即一次转乘不可达，则检验S′_i与S′_j中有无可直达的两站点，若N(S_ip)∩N(S_jq)≠∅，S_ip∈S′_i，S_jq∈S′_j，则站点S_ip与站点S_jq之间有直达线路，d(S_i,S_j)=min{w_i,ip^l₁+w_ip,jq^l₂+w_jq,j^l₃}，L_l1∈L₁，L_l2∈L₂，L_l3∈L₃，其中L₁、L₂、L₃根据公交地铁网络二分图确定，且L₁、L₂、L₃分别为连接S_i与S_ip，S_ip与S_jq，S_jq与S_j站点的线路，其对应方案为最优出行方案。

调查表明，在一个成熟的公交地铁网络中，2次换乘可以实现绝大多数出发地与目的地之间的连接。

算法的复杂性用数据输入规模的函数度量。由站点集合S={S₁,S₂,…,S_n}和公交线路集合L={L₁,L₂,…,L_m}组成的地铁公交网络，存储数据W=[w_i,j^k]_n×n×m的规模为n²m。但因为W为稀疏三维数组，占用存储空间大大减小。在能够直达的情况下，算法的计算量主要为检验向量的计算上，运算量为O(n²m)。在不能直达情况下的转乘问题的计算量主要为寻找转乘站点和转乘线路的计算上。寻找转乘站点实质是在站点映射网络上寻找从S_i到S_j的中间站点，可以在站点映射网络上采用经典最短路算法，如Dijkstra算法，运算量为O(n²)。在映射网络图上的求S_i与S_j的最短路的最小优化问题，实质是多阶段决策问题，可以用经典动态规划或最短路算法来求解，计算量为O(m²)。总体上，该算法总的计算量为O(n²m)。

选取由4条公交线路L₁、L₂、L₃、L₄，1条地铁线路L₀及9个站点组成的公交网络，如图 5，地铁线路L₀经S₁、S₄、S₆站点，线路L₁经S₁、S₂、S₃站点，线路L₂经S₅、S₃、S₄、S₇站点，线路L₃经S₅、S₆、S₈站点，线路L₄经S₈、S₉站点。其中N₁⁰=1，N₄⁰=7，N₆⁰=10；N₁¹=2，N₂¹=5，N₃¹=11；N₅²=6，N₃²=9，N₄²=12，N₇²=16；N₅³=6，N₆³=9，N₈³=13；N₈⁴=4，N₉⁴=9。

图 5 公交地铁网络 Fig. 5 Bus and subway network graph

图选项

如第3节中对标号的叙述，为达到优选地铁的目的，不妨将地铁线路上站点的标号根据实际情况缩小适当倍，这样可将整个公交网络系统一体化处理。而实际上的目的是使地铁线路上的乘车距离权值变小，即需将标号之间的差值成比例缩小。此例中N₁⁰=1，N₄⁰=7，N₆⁰=10，按照式w_i,j^k=|N_j^k－N_i^k|，得w_1,4⁰=6,w_1,6⁰=9,w_4,6⁰=3。若将此权值3倍缩小可得出w_1,4⁰=2,w_1,6⁰=3,w_4,6⁰=1，其余公交线路上权值为w_1,2¹=3,w_1,3¹=9,w_2,3¹=6;w_3,4²=3,w_3,5²=3,w_3,7²=7,w_4,5²=6,w_4,7²=4,w_5,7²=10;w_5,6³=3,w_5,8³=7,w_6,8³=4;w_8,9⁴=5。其余w_i,j^k赋值为零。

建立图 5的公交地铁网络二分图，如图 6。图 7为图 6的线路映射网络图，图 8为图 6的站点映射网络图。

图 6 网络二分图 Fig. 6 Bipartite network

图选项

图 7 线路映射网络图 Fig. 7 Line mapping network

图选项

图 8 站点映射网络图 Fig. 8 Site mapping network graph

图选项

1)考虑站点S₂到站点S₃的最短路问题，构造直达检验向量α₂₃=W▷e₂▷e₃,可得到α₂₃=(w_2,3⁰,w_2,3¹,w_2,3²,w_2,3³,w_2,3⁴)^T≠0，若v=arg{w_2,3^k}=1，即w_2,3¹=6为最小直达距离，L₁为所选乘车路线，途径6站。

2)考虑站点S₁到站点S₅的最短路问题，α₁₅=W▷e₁▷e₅=0，即不可直达，根据站点网络映射图，如图 8，得到与S₁站点邻接的站点集合S′₁={S₂,S₃,S₄,S₆}，与S₅站点邻接的站点集合S′₅={S₃,S₄,S₆,S₇,S₈}，由于S′₁∩S′₅≠∅，表示S₁站点与S₅站点转乘1次可到达。又S′₁∩S′₅={S₃,S₄,S₆}，则S₁站点与S₅站点可经3种1次转乘的方案到达，d(S₁,S₅)=min{w_1,3¹+w_3,5²,w_1,4⁰+w_4,5²,w_1,6⁰+w_6,5³}=min{9+3,2+6,3+3}=6，对应最优路径为从S₁站点乘坐地铁线路L₀到达S₆站点，转乘公交线路L₃到达S₅站点，途经6站。

可看出，从S₁站点到S₅站点与从S₂站点到S₃站点都是经过6站地，而网络图中明显看出S₁,S₅站点的距离是远远大于S₂,S₃站点的距离，这是减少地铁站点标号的权值的结果。结果显示出地铁的优越性。

3)考虑站点S₄到站点S₉的最短路问题，S₄在线路L₀与线路L₂上，S₉在线路L₄上，α₄₉=W▷e₄▷e₉=0，即不可直达，S′₄={S₁,S₃,S₅,S₆,S₇},S′₉={S₈}，S′₄∩S′₉=∅，即1次转乘不可达。下面考虑2次转乘的情况，根据线路网络映射图，L₀或L₂线路与L₄线路之间有L₃连接，即从L₀线路或L₂线路需转乘L₃到线路上，再转乘到L₄线路上。

根据网络二分图，可得：N(S₁)={L₁,L₀},N(S₃)={L₁,L₂},N(S₅)={L₂,L₃},N(S₆)={L₀,L₃},N(S₇)={L₂}，而N(S₈)={L₃,L₄}，则N(S₅)∩N(S₈)≠∅,N(S₆)∩N(S₈)≠∅，即S′₄中的S₅站点与S₆站点可与S₈站点直达，而且它们分别都在L₃线路上，则可求得

在文献^[10]的基础上，将公交地铁进行一体化标号，缩小地铁两站点间的路径距离以达到优选地铁的目的。据乘客出行心理，依次以换乘次数少、出行距离短为优化目标，利用高维数组运算，根据公交地铁网络图与二分图、线路映射网络图、站点映射网络图得到两站点间的最优路径的选择算法。

公交网络的寻径问题一直以来被认为是NP难问题，而日益发达的公交系统对最优路径选择算法的要求也越来越高。因此，改进和创新算法在整个公交系统中至关重要。本文尚未将地铁的时变性考虑在内，可对此进一步研究，使得人们无论何时出行都有一个对应此时间点的方案，使查询更加精确可靠。