乘公交_看奥运
对于直达路线，如果出发点与终点站之间相隔站点数小等于２则步行，否则乘车。对于需要转乘的路线的最优路线模型讨论如下：
1）以时间最短的路线作为最优路线的模型：路线总时间等于乘车时间加上步行时间，再加上转乘时间。
MinTk?3??(1?FSk,)m?(MSmmk,m?1)?2.5??(1?FD)?(MD?1)kk,nnn?5??FSk,m?(MSk,m?1)?5??FDk,n?(MDk,n?1)
?5?(N1FSk,m)?4?(N2k??FDk,n)?7?N3?N4kk??k?6mn （6.9式）
??(3?2FS(MSk,m?1)??(2.5?2.5FDk,n)?(MDk,n?1)k,m)?mn?5?(N1FSk,m)?4?(N2k??FDk,n)?7?N3?N4kk??k?6mn其中，第k路线为同时考虑公汽与地铁的转乘路线中的一种或几种。
2）以转乘次数最少的路线作为最优路线的模型：每步行一次就少换乘一次车。 M （6.20式） inN1?FS?N2?FD?N3?N4??kk,mkk,nkmn此模型等效为以上转乘路线按直达、转乘一次、两次、三次（包括公交与地铁间的转乘）的优先次序来考虑。
3）以费用最少的路线作为最优路线的模型：
M 3 N 4 （6.21式） inC??(1FS?)C?L??kk,mk,mm其中，CLk,m仍满足（6.4式）。
七 模型的优缺点及改进
7.1模型的评价 7.1.1 模型优点
1、模型是由简单到复杂一步步建立的，使得更贴近实际。 2、本文的模型简单，其算法直观，容易编程实现。
3、本文模型比较注重数据的处理和存储方式，大大提高了查询效率。
4、本文模型注重效率的提高，通过大量的特征信息的提取，并结合有效的算法，使其完全可以满足实时系统的要求。
7.1.2 模型缺点
在建模与编程过程中，使用的数据只是现实数据的一种近似，因而得出的结果可能与现实情况有一定的差距。
7.2 模型的改进
以上模型主要是从公交线路出发，寻找公交线路的交叉站作为换乘站点，进而找出经过任意两个站点的可能乘车路线。我们也可以从公交站点的角度出发，用图论的方法建立有向赋权图（如图7.1所示），此向赋权图是针对问题三建立
16
乘公交_看奥运
的图论模型，问题一、问题二只是此模型的简化。图7.1中Li表示公汽线路标号，该线路是公汽线路Li的上行线或下行线，S1、ggg、Sj?1、Sj、Sj?1ggg、Sn是公汽线路Li上的站点标号；Tk表示地铁线路标号，该地铁线路是双向行驶的，
D1、gggDg、Dg?1、ggg、Dm是地铁线路Tj上的站点标号；公汽Li与地铁Tk可
以在公汽站Sj和地铁站Dg间换乘。如果图7.1中的地铁线路替换成公汽线路，为了表示公汽间换乘所需的时间或者费用，应将同一个换乘站点用两个站点来表示。
图7.1 公交线路的有向赋权图
根据不同的目标,给不同的站点间的边赋上不同的权值。然后利用图论的相关算法,找出相应的最短路径。
1）当以时间最短为目标时，给每条边赋上时间的权值。给同一线路上任意两个站点间的边赋值时，其权值等于站点间的公交线路段数与平均时间的乘积。当某段线路的两段点间间隔站点数小等于3时，选择步行，该线路的权值等于步行时间。不同公汽和地铁间进行换乘时需要赋给不同的权值，以表示换乘时间。
例如（如图7.1）：
S,S??(j??1)3当j>4时，S1到 Sj的边权值?；， 1jS,S5；从Sj?1到 Sj不需要的转车，但根据假设应选择步行，其边权值?， j?1j??从Sj?1到 Dj要么乘公交，然后转车，要么步行，根据步行的假设条件，Sj?1
S,D??5到 Dj 的站点间隔数小于2，因此选择步行，其边权值?；， j?1g 17
乘公交_看奥运
D,D???D,D??(g?1)?2.5当g>4时，D1与Dg之间的边权值?；， 1gg1Sj到Dg的边权值?S,D6； jg??Dg到Sj的边权值?D,S7； gj??当j>4、g>4时，S1到D1的路径长度为：
； (S,D)??S,S???S,D????D,D?(j?1)?3?6?(g?1)?2.5111jjgg1当j?4、g>4时，则从S1到Dg选择步行，再乘地铁到D1，其路径长度为；
； (S,D)??S,D???D,D??(j?1)?5?(g?1)?2.5111gg1找出任意两点间可行路线的路径长度后，再搜索出其中的最短路径的的可行
路线作为时间的最优路线。
2）当以费用最省为目标时，则给每条边赋上费用的权值。 公汽站点间的边权按（6.4式）赋值。
当公汽线路Li按单一票价计费，对于Li上任意两个公汽站点Sj和S°j间，
??0；若°若°，则选择步行?S,S，则?S,S??1； j?j?1?4j?j?1?4°°jjjj°??0；若3当公汽线路Li按分段计价，若°，则?S, S,D)??D,D??3若j?4，g?4，则从S1到Sj选择步行，(； 11g1S,D)?(S,S)D??,D??3?3?6若j?4，g?4，则(； 111jg1同样可以找出任意两点间可行路线的路径长度，然后再搜索出最短路径作为 费用的最优路线。 以上从公交站点出发，将公交站点作为网络图中顶点，得出公交的拓扑结构，进而寻求不同目标下的最短路径，为我们提供了另外一种思路。但是从以上图形的结构，我们已经看得出其复杂程度是不可预知的，尤其随着数据的增多，图的复杂度随之上升。如果不寻求一个好的算法，而用常规的Dijkstra算法，将有可 18 乘公交_看奥运 能在可以忍受的时间范围内得不出有效结果。 经过参考相关资料，我们发现用蚂蚁算法可能比较有效。该算法利用了蚂蚁寻食出行路径选择的行为特点，通过线路激素强度的更新机制，实现了以换乘次数最少和公交出行站点最少的公交出行路径选择优化目标。 八 参考文献 [1] 344000 温小文 臧德彦，城市公交信息查询系统设计初探，江西测绘，第65期，2006 [2] 龚劬 图论与网络最优化算法 重庆大学出版社，2000 [3] 1671-4512(2003)Sl-0313 张帅 彭玉青 赵镇 李志强，蚂蚁算法在公交查询最短路径求法中的应用，华中科技大学学报（自然科学报），第31卷，2003 九 附件 转乘0次的情况 起始站点 S0087 线路 L21 站点 S0087 站点 D27 线路 T2 站点 D36 站点 S3676 线路 L97 站点 S3676 耗时/min 车费/元 转乘次数 33 3 0 转乘1次的情况 起始站点:S0008转乘站点:S0073 起始站点 S0008 S0008 路线 129 129 站点 S0400 S0854 站点 S2633 S0856 路线 474 474 目标站点 S0073 S0073 耗时/min 80 83 车费/元 2 2 转乘次数 1 1 起始站点:S0087转乘站点:S3676 起始站点 S0087 路线 454 站点 S0541 站点 S0540 路线 462 目标站点 S3676 耗时/min 44 车费/元 2 转乘次数 1 转乘2次的情况 起始站点：S0008 目标站点：S0073 起始站点 线路 S0008 S0008 S0008 S0008 S0008 站点 站点 线路 站点 D30 D30 D30 D15 T2 T2 T2 T1 D25 D25 D25 D12 站点 线路 站点 耗时/min 55 55 55 65.5 67 车费/元 5 5 5 5 3 转乘次数 2 2 2 2 2 L150 S3874 L159 S3874 L259 S3874 L200 S2534 S0525 L103 S0073 S0525 L103 S0073 S0525 L103 S0073 S0609 L57 S0073 L159 S0400 S2633 L474 S0527 S0525 L103 S0073 起始站点：S0087 目标站点：S3676 起始站点 线路 S0087 S0087 L21 L28 站点 S0087 S0608 站点 线路 站点 D27 D12 T2 T2 D36 D36 站点 S3676 S3676 线路 L97 L97 站点 S3676 S3676 耗时/min 33 33.5 车费/元 3 5 转乘次数 0 2 19 乘公交_看奥运 S0087 S0087 S0087 S0087 S0087 L28 L28 L28 L28 L28 S0608 S0608 S0608 S0608 S0608 D12 D12 D12 D12 D12 T2 T2 T2 T2 T2 D36 D36 D36 D36 D36 S3676 L209 S3676 S3676 L209 S3676 S3676 L462 S3676 S3676 L462 S3676 S3676 L506 S3676 33.5 33.5 33.5 33.5 33.5 5 5 5 5 5 2 2 2 2 2 起始站点：S0148 目标站点：S0485 起始站点 线路 S0148 S0148 S0148 S0148 S0148 S0148 S0148 S0148 S0148 S0148 S0148 L24 L24 L24 L24 L24 L24 L24 L24 L24 L24 站点 S1487 S1487 S1487 S1487 S1487 S1487 S1487 S1487 S1487 S1487 站点 线路 站点 D2 D2 D2 D2 D2 D2 D2 D2 D2 D2 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 D21 D21 D21 D21 D21 D21 D21 D21 D21 D21 站点 S0466 线路 L51 站点 S0485 耗时/min 87.5 87.5 87.5 87.5 87.5 87.5 87.5 87.5 87.5 87.5 130 车费/元 5 5 5 5 5 5 5 5 5 5 3 转乘次数 2 2 2 2 2 2 2 2 2 2 2 S0464 L104 S0485 S0464 L395 S0485 S0466 L450 S0485 S0464 L469 S0485 S0466 L51 S0485 S0464 L104 S0485 S0464 L395 S0485 S0466 L450 S0485 S0464 L469 S0485 L308 S0302 S0303 L481 S2027 S2027 L469 S0485 起始站点：S0971 目标站点：S0485 起始站点 线路 S0971 S0971 S0971 S0971 S0971 S0971 S0971 S0971 S0971 S0971 S0971 S0971 S0971 S0971 S0971 S0971 S0971 S0971 S0971 S0971 L94 站点 S0567 站点 线路 站点 D1 D1 D1 D1 D1 D1 D1 D1 D1 D1 D1 D1 D1 D1 D1 D1 D1 D1 D1 D1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 T1 D21 D21 D21 D21 D21 D21 D21 D21 D21 D21 D21 D21 D21 D21 D21 D21 D21 D21 D21 D21 站点 S0466 S0466 线路 L51 L51 站点 S0485 S0485 耗时/min 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 96 车费/元 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 转乘次数 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 L119 S0567 L94 S0567 S0464 L104 S0485 S0464 L104 S0485 S0464 L395 S0485 S0464 L395 S0485 S0466 L450 S0485 S0466 L450 S0485 S0464 L469 S0485 S0464 L469 S0485 S0466 L51 S0485 L119 S0567 L94 S0567 L119 S0567 L94 S0567 L119 S0567 L94 S0567 L119 S0567 L94 L94 L94 L94 L94 S0567 S0567 S0567 S0567 S0567 S0464 L104 S0485 S0464 L395 S0485 S0466 L450 S0485 S0464 L469 S0485 S0466 L51 S0485 L119 S0567 L119 S0567 L119 S0567 L119 S0567 L119 S0567 S0464 L104 S0485 S0464 L395 S0485 S0466 L450 S0485 S0464 L469 S0485 起始站点：S1557 目标站点：S0481 起始站点 线路 站点 站点 线路 站点 站点 线路 站点 耗时/min 车费/元 转乘次数 20