第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)≠，４ 算 例 选取由 ４ 条公交线路 Ｌ１ 、Ｌ２ 、Ｌ３ 、Ｌ４ ，１ 条地铁线路 Ｌ０ 及 ９ 个站点组成的公交网络，如图 ５，地铁线路 Ｌ０ 经 Ｓ１ 、Ｓ４ 、Ｓ６ 站点，线路 Ｌ１ 经 Ｓ１ 、Ｓ２ 、Ｓ３ 站点，线路 Ｌ２ 经 Ｓ５ 、Ｓ３ 、Ｓ４ 、Ｓ７ 站点，线路 Ｌ３ 经 Ｓ５ 、Ｓ６ 、Ｓ８ 站点，线路 Ｌ４ 经 Ｓ８ 、Ｓ９ 站点。 其中 Ｎ ０ １ ＝ １，Ｎ ０ ４ ＝ ７，Ｎ ０ ６ ＝ １０；Ｎ １ １ ＝ ２，Ｎ １ ２ ＝ ５，Ｎ １ ３ ＝ １１；Ｎ ２ ５ ＝ ６，Ｎ ２ ３ ＝ ９，Ｎ ２ ４ ＝ １２，Ｎ ２ ７ ＝ １６； Ｎ ３ ５ ＝ ６，Ｎ ３ ６ ＝ ９，Ｎ ３ ８ ＝ １３；Ｎ ４ ８ ＝ ４，Ｎ ４ ９ ＝ ９。 图 ５ 公交地铁网络 Ｆｉｇ． ５ Ｂｕｓ ａｎｄ ｓｕｂｗａｙ ｎｅｔｗｏｒｋ ｇｒａｐｈ 如第 ３ 节中对标号的叙述，为达到优选地铁的目 的，不妨将地铁线路上站点的标号根据实际情况缩小 适当倍，这样可将整个公交网络系统一体化处理。 而 实际上的目的是使地铁线路上的乘车距离权值变小， 即需将标号之间的差值成比例缩小。 此例中 Ｎ ０ １ ＝ １， Ｎ ０ ４ ＝ ７，Ｎ ０ ６ ＝ １０，按照式ｗ ｋ ｉ，ｊ ＝ Ｎ ｋ ｊ － Ｎ ｋ ｉ ，得ｗ ０ １，４ ＝ ６， ｗ ０ １，６ ＝ ９，ｗ ０ ４，６ ＝ ３。 若将此权值３ 倍缩小可得出 ｗ ０ １，４ ＝ ２，ｗ ０ １，６ ＝ ３，ｗ ０ ４，６ ＝ １，其余公交线路上权值为 ｗ １ １，２ ＝ ３， ｗ １ １，３ ＝ ９，ｗ １ ２，３ ＝ ６；ｗ ２ ３，４ ＝ ３，ｗ ２ ３，５ ＝ ３，ｗ ２ ３，７ ＝ ７，ｗ ２ ４，５ ＝ ６， ｗ ２ ４，７ ＝ ４，ｗ ２ ５，７ ＝ １０；ｗ ３ ５，６ ＝ ３，ｗ ３ ５，８ ＝ ７，ｗ ３ ６，８ ＝ ４；ｗ ４ ８，９ ＝ ５ 。 其余 ｗ ｋ ｉ，ｊ 赋值为零。 图 ６ 网络二分图 Ｆｉｇ． ６ Ｂｉｐａｒｔｉｔｅ ｎｅｔｗｏｒｋ 图 ７ 线路映射网络图 Ｆｉｇ． ７ Ｌｉｎｅ ｍａｐｐｉｎｇ ｎｅｔｗｏｒｋ 图 ８ 站点映射网络图 Ｆｉｇ． ８ Ｓｉｔｅ ｍａｐｐｉｎｇ ｎｅｔｗｏｒｋ ｇｒａｐｈ 建立图 ５ 的公交地铁网络二分图，如图 ６。 图 ７ 为图 ６ 的线路映射网络图，图 ８ 为图 ６ 的站点映射 网络图。 １）考虑站点 Ｓ２ 到站点 Ｓ３ 的最短路问题，构造 直达检验向量 α２３ ＝ Ｗ▷ｅ２▷ｅ３ ，可得到 α２３ ＝ （ｗ ０ ２，３ ， ｗ １ ２，３ ，ｗ ２ ２，３ ，ｗ ３ ２，３ ，ｗ ４ ２，３ ） Ｔ ≠ ０，若 ｖ ＝ ａｒｇ ｍｉｎ ｋ ｗ ｋ ２，３ { } ＝ １， 即 ｗ １ ２，３ ＝ ６ 为最小直达距离， Ｌ１ 为所选乘车路线，途 径 ６ 站。 ２）考虑站点 Ｓ１ 到站点 Ｓ５ 的最短路问题， α１５ ＝ Ｗ▷ ｅ１▷ ｅ５ ＝ ０，即不可直达，根据站点网络映射图， 如图 ８，得到与 Ｓ１ 站点邻接的站点集合 Ｓ ′ １ ＝ ｛Ｓ２ ，Ｓ３ ， Ｓ４ ，Ｓ６ ｝ ，与 Ｓ５ 站点邻接的站点集合 Ｓ ′ ５ ＝ ｛Ｓ３ ，Ｓ４ ，Ｓ６ ， Ｓ７ ，Ｓ８ ｝ ，由于 Ｓ ′ １ ∩ Ｓ ′ ５ ≠ ∅ ，表示 Ｓ１ 站点与 Ｓ５ 站点 转乘 １ 次可到达。 又 Ｓ ′ １ ∩Ｓ ′ ５ ＝ ｛Ｓ３ ，Ｓ４ ，Ｓ６ ｝ ，则 Ｓ１ 站 点与 Ｓ５ 站点可经 ３ 种 １ 次转乘的方案到达， ｄ（Ｓ１ ， Ｓ５ ） ＝ ｍｉｎ ｗ １ １，３ ＋ ｗ ２ ３，５ ，ｗ ０ １，４ ＋ ｗ ２ ４，５ ，ｗ ０ １，６ ＋ ｗ ３ ６，５ { } ＝ ｍｉｎ{９ ＋ ３，２ ＋ ６，３ ＋ ３} ＝ ６，对应最优路径为从 Ｓ１ 站点乘坐地铁线路 Ｌ０ 到达 Ｓ６ 站点，转乘公交线路 Ｌ３ 到达 Ｓ５ 站点，途经 ６ 站。 可看出，从 Ｓ１ 站点到 Ｓ５ 站点与从 Ｓ２ 站点到 Ｓ３ 站点都是经过 ６ 站地，而网络图中明显看出 Ｓ１ ，Ｓ５ 站点的距离是远远大于 Ｓ２ ，Ｓ３ 站点的距离，这是减 少地铁站点标号的权值的结果。 结果显示出地铁的 优越性。 ３）考虑站点 Ｓ４ 到站点 Ｓ９ 的最短路问题， Ｓ４ 在线 路 Ｌ０ 与线路 Ｌ２ 上， Ｓ９ 在线路 Ｌ４ 上， α４９ ＝ Ｗ▷ ｅ４▷ ｅ９ ＝ ０，即不可直达， Ｓ ′ ４ ＝ ｛Ｓ１ ，Ｓ３ ， Ｓ５ ，Ｓ６ ，Ｓ７ ｝，Ｓ ′ ９ ＝ ｛Ｓ８ ｝ ， Ｓ ′ ４ ∩ Ｓ ′ ９ ＝ ∅ ，即 １ 次转乘不可达。 下面考虑 ２ 次转乘的情况，根据线路网络映射图， Ｌ０ 或 Ｌ２ 线路 与 Ｌ４ 线路之间有 Ｌ３ 连接，即从 Ｌ０ 线路或 Ｌ２ 线路需转 乘 Ｌ３ 到线路上，再转乘到 Ｌ４ 线路上。 根据网络二分图，可得： Ｎ（ Ｓ１ ） ＝ ｛ Ｌ１ ，Ｌ０ ｝ ， Ｎ（ Ｓ３ ） ＝ ｛ Ｌ１ ，Ｌ２ ｝ ， Ｎ（ Ｓ５ ） ＝ ｛ Ｌ２ ，Ｌ３ ｝ ， Ｎ（ Ｓ６ ） ＝ ｛ Ｌ０ ，Ｌ３ ｝ ， Ｎ（ Ｓ７ ） ＝ ｛ Ｌ２ ｝ ，而 Ｎ（ Ｓ８ ） ＝ ｛ Ｌ３ ，Ｌ４ ｝ ， 则 Ｎ（ Ｓ５ ） ∩ Ｎ（ Ｓ８ ） ≠ ∅， Ｎ（ Ｓ６ ） ∩ Ｎ（ Ｓ８ ） ≠ ∅， 第 ３ 期 徐勇，等：公交地铁一体化下的网络模型与最优路选择算法 ·４８５·