·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)。射网络图中所连接的边数反映了乘客的换乘次数。 站点映射网络图表示站点之间的连通关系，它能反 映出乘客换乘次数的同时，也给出了换乘站点。 图 ３ 为图 ２ 的线路映射网络图，图 ４ 为图 ２ 的 站点映射网络图。 由图 ３ 可以看出， Ｌ１ 与 Ｌ０ 、Ｌ２ 之 间分别为一条边，即若出发站点在 Ｌ１ 站点上，目的 地站点在 Ｌ０ 站点或 Ｌ２ 站点上，转乘 １ 次公交或者地 铁即可到达。 若出发站点在 Ｌ０ 线路上，目的地站点 在 Ｌ２ 线路上，则需在 Ｌ１ 线路上的某 ２ 个站点处转 乘，乘坐 ３ 次公交或地铁即可到达目的地。 由图 ４ 可以看出， Ｓ１ 与 Ｓ２ 有一条边相连，即两站点在一条 线路上，可以直达。 Ｓ１ 与 Ｓ３ 之间有 ２ 条边，且经过 Ｓ２ 站点，则从 Ｓ１ 站点到达 Ｓ３ 站点必须在 Ｓ２ 站点转乘， 即坐 ２ 次公交或地铁到达。 Ｓ１ 与 Ｓ４ 之间有 ３ 条边相 连，从图可直接看出，由 Ｓ１ 站点出发，需在 Ｓ２ 和 Ｓ３ 站点转乘，以到达 Ｓ４ 站点。 图 ３ 线路映射网络图 Ｆｉｇ． ３ Ｌｉｎｅ ｍａｐｐｉｎｇ ｎｅｔｗｏｒｋ ｇｒａｐｈ 图 ４ 站点映射网络图 Ｆｉｇ． ４ Ｓｉｔｅ ｍａｐｐｉｎｇ ｎｅｔｗｏｒｋ ｇｒａｐｈ ３ 最优路选择算法 首先对每条线路上的站点进行一体化标号，考 虑到地铁的快捷性、准时性、舒适性等优点，优选地 铁出行是大势所趋。 这样，将地铁线路上两站点间 乘车距离权值适当减小，这样就达到了优选地铁出 行的目的。 ３．１ 标号公交地铁网络的模型 若线路 Ｌｋ 上有 ｋｎ 个站点， Ｌｋ：Ｓｋ１ ，Ｓｋ２ ，…，Ｓｋｎ ， 站点 Ｓｋｊ 在线路 Ｌｋ 上的标号为 ｊ ，记为 Ｎ ｋ ｊ ＝ ｊ ，在二分 网络图中边 ＬｋＳｋｊ 的权值为该站点在线路 Ｌｋ 上的标 号： Ｎ ｋ ｊ ＝ ｊ 。 然后建立公交地铁线路映射网络和站点映射网 络。 在站点映射网络中，对边 ＳｉＳｊ 赋值，记为 ｗ ｋ ｉ，ｊ ，且 ｗ ｋ ｉ，ｊ ＝ Ｎ ｋ ｊ － Ｎ ｋ ｉ ，它代表在 Ｌｋ 线路上 Ｓｉ、Ｓｊ 两站点之 间的站点数。 若 Ｓｉ、Ｓｊ 不在 Ｌｋ 线路上，令 ｗ ｋ ｉ，ｊ ＝ ０。 ３．２ 基于标号网络模型最优路选择的算法 １）给出任两站点 Ｓｉ 与 Ｓｊ ，构造直达检验向量 αｉｊ ＝ Ｗ▷ ｅｉ▷ ｅｊ ，其中 Ｗ ＝ ｗ ｋ ｉ，ｊ [ ] ｎ×ｎ×ｍ ， ｅｉ 表示第 ｉ 个元素为 １，其余全为 ０ 的 ｎ 维单位向量，若 αｉｊ ＝ ｗ １ ｉ，ｊ，ｗ ２ ｉ，ｊ，…，ｗ ｍ ｉ，ｊ ( ) Ｔ ≠ ０， 则 Ｓｉ 站点与 Ｓｊ 站点可以直 达，若 ｖ ＝ ａｒｇ ｍｉｎ ｋ ｗ ｋ ｉ，ｊ { } ，则 ｗ ｖ ｉ，ｊ 为 Ｓｉ 与 Ｓｊ 站点之间 的最小直达距离，最优路径为 Ｌｖ 。 ２）若 Ｓｉ 站点与 Ｓｊ 站点不可直达，根据站点映射 网络图，记与 Ｓｉ 站点邻接的站点集合 Ｓ ′ ｉ ＝ ｛Ｓｉ１ ，Ｓｉ２ ， …，Ｓｉｋ｝ 与 Ｓｊ 站点邻接的站点集合 Ｓ ′ ｊ ＝ ｛Ｓｊ１ ，Ｓｊ２ ，…， Ｓｊｌ｝ ，若 Ｓ ′ ｉ ∩Ｓ ′ ｊ ≠∅ ，则表示 Ｓｉ 站点与 Ｓｊ 站点转乘一 次可到达，记 Ｓ ′ ｉ ∩ Ｓ ′ ｊ ＝ ｛Ｓｒ１ ， Ｓｒ２ ， …，Ｓｒｐ｝ ，则 Ｓｉ 与 Ｓｊ 可经 ｐ 种方法到达，则 ｄ（Ｓｉ，Ｓｊ） ＝ ｍｉｎ ｗ ｌ ｉ，ｒ ＋ ｗ ｌ ′ ｒ，ｊ { } ， Ｌｌ ∈Ｌ，Ｌｌ ′ ∈Ｌ ′ ，根据公交网络二分图， Ｌ 与 Ｌ ′ 分别为 连接 Ｓｉ 与 Ｓｒ ， Ｓｒ 与 Ｓｊ 站点的线路，其对应的路线为 最优出行路线。 ３）若Ｓ ′ ｉ ∩Ｓ ′ ｊ ＝ ∅，即一次转乘不可达，则检验Ｓ ′ ｉ 与Ｓ ′ ｊ 中有无可直达的两站点，若Ｎ（Ｓｉｐ）∩Ｎ（Ｓｊｑ）≠∅，Ｓｉｐ ∈Ｓ ′ ｉ ， Ｓｊｑ ∈Ｓ ′ ｊ ，则站点Ｓｉｐ 与站点Ｓｊｑ 之间有直达线路，ｄ（Ｓｉ，Ｓｊ） ＝ ｍｉｎ ｗ ｌ１ ｉ，ｉｐ ＋ ｗ ｌ２ ｉｐ，ｊｑ ＋ ｗ ｌ３ ｊｑ，ｊ { } ， Ｌｌ１ ∈Ｌ１， Ｌｌ２ ∈Ｌ２， Ｌｌ３ ∈Ｌ３， 其中Ｌ１、Ｌ２、Ｌ３ 根据公交地铁网络二分图确定，且 Ｌ１、Ｌ２、Ｌ３ 分别为连接Ｓｉ 与Ｓｉｐ ，Ｓｉｐ 与Ｓｊｑ ，Ｓｊｑ 与Ｓｊ 站点的线路，其对 应方案为最优出行方案。 调查表明，在一个成熟的公交地铁网络中，２ 次 换乘可以实现绝大多数出发地与目的地之间的连接。 ３．３ 算法的复杂性分析 算法的复杂性用数据输入规模的函数度量。 由 站点集合 Ｓ ＝ Ｓ１ ，Ｓ２ ，…，Ｓｎ { } 和公交线路集合 Ｌ ＝ Ｌ１ ，Ｌ２ ，…，Ｌｍ { } 组成的地铁公交网络，存储数据 Ｗ ＝ ｗ ｋ ｉ，ｊ [ ] ｎ×ｎ×ｍ 的规模为 ｎ ２ｍ 。 但因为 Ｗ 为稀疏三维数 组，占用存储空间大大减小。 在能够直达的情况下， 算法的计算量主要为检验向量的计算上，运算量为 Ｏ ｎ ２ ( ｍ) 。 在不能直达情况下的转乘问题的计算量 主要为寻找转乘站点和转乘线路的计算上。 寻找转 乘站点实质是在站点映射网络上寻找从 Ｓｉ 到 Ｓｊ 的中 间站点，可以在站点映射网络上采用经典最短路算 法，如 Ｄｉｊｋｓｔｒａ 算法，运算量为 Ｏ ｎ ２ ( ) 。 在映射网络 图上的求 Ｓｉ 与 Ｓｊ 的最短路的最小优化问题，实质是 多阶段决策问题，可以用经典动态规划或最短路算法 来求解，计算量为 Ｏ ｍ ２ ( ) 。 总体上，该算法总的计算 量为 Ｏ ｎ ２ ( ｍ) 。 ·４８４· 智 能 系 统 学 报 第 １０ 卷