最优公交线路的模型研究

1、2007高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置

2、报名号的话）： 所属学校（请填写完整的全名）： 北京化工大学 参赛队员 (打印并签名) ：1. 郑宇 2. 姜园博 3. 来斯惟 指导教师或指导教师组负责人 (打印并签名)： 郭秋敏 日期： 2007 年 09 月 24 日赛区评阅编号（由赛区组委会评阅前进行编号）：2007高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：最优公交线路的模型研究摘要本文以乘车的路线为研究对象，根据乘客的不同需求，存在总时间、总费用、

3、换乘次数三个目标函数。将求解目标函数最优值的问题转化为最短路径问题。在仅考虑公汽线路的时间最短模型中，首先由已知信息建立有向赋权图，以公交站点为顶点，所有直通公交线路为边。对于时间，每条边的权值为公交车的运行时间加上转车时间。然后可直接采用Dijkstra算法求出任意两公汽站点之间最优线路。该模型方法比较简单，准确性高，可操作性强。且对图中的权值做相应的改变，可以将其转化为总费用最少模型以及换乘次数最少模型。同时考虑公汽和地铁线路，存在公汽与地铁的换乘问题，基于该问题本文设计了另一种有向赋权图，以所有公汽站点和地铁站点为顶点，所有直接连通线路为边。以时间最短作为目标，边的权值设为两点间实际运动

4、的时间。并相应地提出一种修改的Dijkstra算法，在拼接两条邻边时，会加上换乘时间。根据这种算法可得到任意两公交站点之间的较优线路，该算法效率较高。但在求解中发现，该方法并不能总求得最优解，因为到某一站点的最短路不仅仅由其前面的一个站点的最短路决定。基于这个问题，本文采用双层Dijkstra算法，在该算法中，考虑一站点对其以后两站的最短路径的影响。双层Dijkstra算法复杂度较高，但运用该算法可以得到更优化的线路。统计结果表明，修改的Dijkstra算法求得的最优解中，有5.7%的解可以被双层Dijkstra算法的最优解更新。类似的，双层Dijkstra算法也可以求解总费用最少模型和换乘次

5、数最少模型。仅考虑公汽线路，6对站(1)S3359S1828 (2)S1557S0481 (3)S0971S0485 (4)S0008S0073 (5)S0148S0485 (6)S0087S3676的总时间最短的线路所对应时间分别为64、99、103、59、102、46（分钟）；总费用最少的线路所需费用分别为3、3、3、2、3、2（元）；总换乘次数最少的线路所需换乘次数分别为1、2、1、1、2、1（次）。同时考虑公汽和地铁线路，本文求得6对起始站终到站的总时间最短的线路所需时间分别为62、99、95、53.5、86.5、30（分钟）；总费用最少的线路所需费用分别为3、3、3、2、3、2（元）

6、；总换乘次数最少的线路所需换乘次数分别为1、2、1、1、2、0（次）。最后，本文对模型进行了评价和推广，使其能更好的应用于实际生产生活中。关键词双层Dijkstra算法，最短路径1. 问题分析1.1. 问题背景及分析奥运会即将来临了，届时有很多观众希望方便快捷的到达各个比赛场地，公交出行成为很多人的首选。北京市的公交线路已达800条以上，因此乘客面临多条线路的选择问题。本文的核心是提出一个解决公交线路选择问题的方案。根据对实际情况的考虑并结合北京公交网和北京地铁网提供的线路搜索需求，本文认为查询者的需求主要为总时间短、总费用低、换乘次数少。这三种需求对应的三个目标函数的最优解的求解与最短路径问

7、题相似。现在如果把三个目标函数的最优解的求解转化为最短路径问题，就会遇到以下两个问题：（1）同时考虑公汽线路和地铁线路时，线路比较复杂，如何用已知的线路信息建立有向赋权图（2）建立有向赋权图之后，图论中传统的最短路径算法是否适用。如果不适用，是否可以对传统的最短路径算法做相应的改变，使其改变后可以求解已经建立的有向赋权图，或者是否可以提出新的算法用来求解已经建立的有向赋权图。基于这两个问题，考虑两种解决办法：（1）考虑简单的公交线路，即只考虑公汽线路。根据已知公汽线路的信息建立有向赋权图，使该有向赋权图的最短路径问题可以直接求解（2）同时考虑公汽线路和地铁线路。首先，根据已知公交线路的信息建立

8、有向赋权图，使得该有向赋权图包含实际情况中的任意一种情形。其次，对传统的最短路径算法做改变使它可以求解已经建立的有向赋权图。1.2. 题中数据的两个问题及修正除L290外，其余环行公交线路所标的首站和末站均相同。而环行线L290的首站为S1477，末站为S1479。根据L066可知S1477和S1479为相邻两站，故认为此线路的最后少标了一个S1477，实际仍为环行线。普通线路L406的起点站和终点站相同，均为S1871。L406的第二站为S1008，倒数第二站为S0941，由L034可知，S1008和S0941相邻，故认为数据没有问题。但是从实际情况看，这样的线路会被当作环线使用，而不会在S

9、1871让乘客强制下车。所以我们把L406改成环线。2. 模型假设2.1. 总时间=乘客到达最后一个公汽站的时刻乘客离开第一个公汽站的时刻；2.2. 假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)；2.3. 换乘交通工具所用时间分为等待时间和步行到站点时间两部分.(题目中给出了换乘中的步行时间)；2.4. 环线地铁和公汽的线路都是双向的3. 符号说明第k条公汽线路（站点相同运行方向不同的公汽线路用不同的k表示）第k条地铁线路（k=1, 2, 3, 4；站点相同运行方向不同的地铁线路用不同的k表示）第k条公汽线路上公汽站的个数第k条地铁线路上地铁站的个数标号为i的公汽

10、站标号为i的地铁站 和确定的边对应的权和确定的边对应的权和确定的边对应的权换乘系数4. 模型的建立与求解4.1. 仅考虑公汽线路的模型4.1.1. 建立有向赋权图1) 总时间为目标函数对于任意一条公汽线路，有个站，以这个站为顶点。对于这个顶点中的任意两个顶点和，以和为端点的线段为边，公汽的运行方向为边的方向。记，则和确定的边对应的权= 相邻公汽站平均行驶时间+公汽换乘公汽平均耗时。这样就建立了仅包含一条公汽线路的有向赋权图，对每一条公汽线路都按以上方法建立有向赋权图，就得到包含所有公汽线路的有向赋权图。由于在权值中加入了公汽的换乘时间，因此所有的边都具有可加性。此时，只要得到有向图中两顶点A

11、、B间的最短路径，就可以得到乘客从公汽站A到公汽站B的最短时间。2) 总费用为目标函数顶点和边的选取与1）相同，和确定的边对应的权为该公交线所需的车票费用，即：3) 换乘次数为目标函数顶点和边的选取与1）相同，和确定的边对应的权。4.1.2. 模型求解在已经建立的有向赋权图中，需要求出任意两顶点间的最短路径。Dijkstra算法可以解决有向赋权图的最短路径问题，该算法要求所有边的权值非负，4.1.1建立的有向赋权图显然满足该算法的要求。以Dijkstra算法为基础，编程求解4.1.1中有向赋权图的最短路径。1) 总时间最少的模型求解程序计算的得到的总时间比实际情况多了一次换乘时间，因此，最优线

12、路的总时间=程序计算的得到的总时间-5分钟。 起始站终到站最优线路的总时间（分钟）S3359S1828 时间： 64 花费：3 换乘：2S1557S0481 时间： 99 花费：4 换乘：3S0971S0485时间：103 花费：3 换乘：2S0008S0073时间： 59 花费：5 换乘：4S0148S0485时间：102 花费：4 换乘：3S0087S3676时间： 46 花费：3 换乘：22) 总费用最少的模型求解起始站终到站最优线路的总费用（元）S3359S1828 时间：145 花费：3 换乘：2S1557S0481 时间：115 花费：3 换乘：2S0971S0485时间：149

13、花费：3 换乘：1S0008S0073时间： 83 花费：2 换乘：1S0148S0485时间：124 花费：3 换乘：2S0087S3676时间： 71 花费：2 换乘：13) 换乘次数最少的模型求解起始站终到站最优线路的换乘次数（次）S3359S1828 时间：137 花费：3 换乘：1S1557S0481 时间：178 花费：4 换乘：2S0971S0485时间：260 花费：5 换乘：1S0008S0073时间：116 花费：3 换乘：1S0148S0485时间：196 花费：4 换乘：2S0087S3676时间： 71 花费：2 换乘：14.2. 考虑公汽和地铁线路的时间最短模型4.

14、2.1. 建立有向赋权图对于公汽线路的建图同4.1。类似的，对于任意一条地铁线路，有个站，以这个站为顶点。对于这个顶点中的任意两个顶点和，定义以和为端点的线段是一条边，地铁的运行方向为边的方向。和确定的边对应的权=(上和之间的站点个数(包括和) -1)相邻地铁站平均行驶时间。对于任意一个地铁站，都存在1至5个可供换乘的公汽站（例如地铁站D01存在3个可供换乘的公汽站S0567，S0042，S0025）。建立以和为顶点的双向边，其权值，即步行时间4分钟。根据以上三步可以建立包含所有公汽线路和地铁线路的有向赋权图，但该赋权图还没有考虑换乘时间。下面考虑每一种换乘情况，共有8种换乘情况。0代表地铁站

15、，1代表公汽站，A表示乘地铁，B表示乘公汽，C表示步行。那么0 0 0 ，0 0 1，0 1 0，0 1 1，1 0 0，1 0 1，1 1 0，1 1 1分别表示： 地铁站地铁站地铁站地铁间换乘时间：4分钟地铁站地铁站公汽站无换乘时间地铁站公汽站地铁站无换乘时间地铁站公汽站公汽站等待公汽的时间：3分钟公汽站地铁站地铁站等待地铁的时间：2分钟公汽站地铁站公汽站无换乘时间公汽站公汽站地铁站无换乘时间公汽站公汽站公汽站公汽间换乘时间：4分钟将这8种情况下在换乘所需的时间定义为换成系数（p,q,r的取值为0或1），则, , , , , , , 令所有的公汽站构成的集合为S, 所有的地铁站构成的集合为

16、D, V=SD,用表示V中的顶点。令所有的构成的集合为，所有的构成的集合为，所有的构成的集合为，W=，E=W所对应的各边。这样就得到了有向赋权图G(V,E,W)。4.2.2. 运用修改的Dijkstra算法求解模型1) 修改的Dijkstra算法在4.2.1建立的有向赋权图中，每一个顶点有换乘系数，显然此时不可以直接运用Dijkstra算法求最短路径。基于Dijkstra算法的基本思想，本文提出一种修改的Dijkstra算法，用于求该有向赋权图中顶点到顶点的最短路径。Dijkstra算法的基本思想是：将点集V分成两部分，一部分是顶点具有p标号（永久性标号）的集合P, 另一部分是顶点具有t标号（

17、临时性标号）的集合T，并首先至 具有p标号，而其余顶点具有t标号，然后逐步将具有t标号的顶点置为p标号。当 具有p标号时，就找到了顶点到顶点 的最短路径。所谓顶点的p标号是指从到的最短路径的长度，顶点的p标号是指从到的最短路径的长度。顶点的标号用表示。Dijkstra算法描述如下：（1）初始化。设具有p标号，=0，P=, T=V-P, 且的t标号是：（2）求下一个顶点的p标号。设顶点的t标号是T中所有顶点t标号的最小值。将的t标号改为p标号，修改永久性标号集P和临时性标号集T，使，。（3）修改T中各顶点的t标号值。对任意的（4）重复步骤（2）和（3），直到获p标号。为了适应中间的换乘时间，将原

18、Dijkstra算法的第（3）步改为：对任意的，其中，换乘系数的取值为4.2.1中8种换乘情况之一。为到的最短路径（实际上只是原Dijkstra算法中的最短路径，修改后并非最短）上，的上一级顶点。2) 模型求解以1)中修改的Dijkstra算法为基础编程，求4.2.1中建立的有向赋权图中任意两顶点的最短路径。计算结果如下（具体路线间附录）：起始站终到站最优线路的总时间（分钟）S3359S1828 时间:62 花费:7 换乘:4S1557S0481 时间:99 花费:4 换乘:3S0971S0485时间:95 花费:6 换乘:3S0008S0073时间:53.5 花费:5 换乘:3S0148S0

19、485时间:86.5 花费:6 换乘:3S0087S3676时间:30 花费:3 换乘:04.2.3. 运用双层Dijkstra算法求解模型图12.51247.5443上文4.2.2中的修改的Dijkstra算法虽然具有和原始Dijkstra算法相同的时空复杂度，计算效率很高，但并不是总能算得最短路径。如图1所示的公交线路图（此图仅作示例，并非从实际数据中获得），1、2、4号顶点为地铁站，3号顶点为公汽站，12线上另有2个地铁站，故12线所需时间为7.5分钟，2为地铁换乘点，24线的时间为2.5分钟。3号公交站同时连接1号和2号地铁站（如数据中S0540同时连接了D17和D31），两条边的权值

20、均为4分钟。下面我们用修改的Dijkstra算法来计算这个问题。第一步：L(1)=0第二步：由1号顶点出发更新其它顶点，L(3)=4，L(2)=7.5第三步：由3号顶点出发更新其它顶点，L(2)=min7.5, L(3)+4+=7.5第四步：由2号顶点出发更新其它顶点，L(4)=L(2)+2.5+=14。因为2号顶点由1号顶点扩展而来，所以是。实际上，如果走1324的路线距离反而更短。L=4+4+2.5=12.5这种修改的Dijkstra算法不能总能算得最短路径的原因在于我们加了这一项，其中的p为q的前一个顶点。这就说明顶点p可以影响之后的两层顶点，而Dijkstra算法每次只扫描并修改了一层

21、顶点。从这一原因出发，我们考虑把算法设计为“双层Dijkstra算法”。在双层Dijkstra算法中，每次扫描顶点均尝试更新直接相邻的顶点和与直接相邻的顶点相邻的顶点。即将原Dijkstra算法的第（3）步改为：对任意的，i, j, k互不相等，用双层Dijkstra算法计算得到六条线路的最少时间与4.2.2中修改的Dijkstra算法相同，但在之后的模型评价中可以看出双层Dijkstra算法还是很有优势的。4.3. 考虑公汽和地铁线路的费用最少模型以及换乘次数最少模型1) 建立有向赋权图该模型的有向赋权图类似4.2.1的有向赋权图，顶点和边的设置与4.2.1完全相同，权值的设置、换乘系数的设

22、置与4.2.1不同。对于公汽线路的有向赋权图，和确定的边对应的权为该公交线所需的车票费用，即：对于任意一条地铁线路，和确定的边对应的权，地铁票价。对于任意一个地铁站，都存在1至5个可供换乘的公汽站，建立以和为顶点的双向边，其权值=0。因为没有乘坐交通工具。换乘系数的设置：, , , , , , , 。因为 地铁站地铁站地铁站（A表示乘地铁）多收了一次地铁票价。2) 运用双层Dijkstra算法求解模型用双层Dijkstra算法计算得到六条线路的最少费用，结果如下（具体路线间附录）：起始站终到站最优线路的总费用（元）S3359S1828 时间:137 花费:3 换乘:1S1557S0481 时间

23、:160 花费:3 换乘:2S0971S0485时间:149 花费:3 换乘:1S0008S0073时间:83 花费:2 换乘:1S0148S0485时间:121 花费:3 换乘:2S0087S3676时间:71 花费:2 换乘:14.4. 考虑公汽和地铁线路的换乘次数最少模型1) 建立有向赋权图公汽线路的有向赋权图同4.1.1的3)。对于任意一条地铁线路，有个站，以这个站为顶点。对于这个顶点中的任意两个顶点和，定义以和为端点的线段是一条边，地铁的运行方向为边的方向。和确定的边对应的权=1。对于任意一个地铁站，都存在1至5个可供换乘的公汽站，建立以和为顶点的双向边，其权值=0。因为没有乘坐交通

24、工具。2) 运用Dijkstra算法求解模型用Dijkstra算法计算得到六条线路的最少换乘次数，结果如下（具体路线见附录）：起始站终到站最优线路的总费用（元）S3359S1828 时间:132 花费:3 换乘:1S1557S0481 时间:166 花费:3 换乘:2S0971S0485时间:260 花费:5 换乘:1S0008S0073时间:116 花费:3 换乘:1S0148S0485时间:196 花费:4 换乘:2S0087S3676时间:30 花费:3 换乘:04.5. 已知行走时间的最佳路线考虑了步行时间，换乘次数、票价这两个目标将失去意义，因为查询者会选择走完全程，以获得换乘次数为

25、0，且没有票价的“最优路线”。因此我们只需要分析时间这一目标。在4.2的基础上，我们可以得到任两点间乘坐公交的最短路线。建立图G1，顶点为所有公交站点，边权值为各顶点间通过公交线到达的最短时间。我们已知了任两点间的步行时间，故可用最短路径算法直接求得任意两点间的最少步行时间。建立图G2，顶点为所有公交站点，边权值为各顶点间通过步行到达的最短时间。因为G1和G2的所有边已是各自的最短路径，所以G1或是G2中任意两条属于同一个图的边的拼接只会让路径更长。我们只需考虑轮换拼接G1和G2中的边。G1边接G2边：公交车之后步行，两条边可以直接拼接。G2边接G1边：步行之后乘坐公交车，可能需要在此处加入公

26、汽或地铁的等待时间。具体要看这条公交边中最开头的两站。我们发现这里和之前4.2.3中建立双层Dijkstra算法时遇到的情形是一样的，在拼接两条边时需要加上换乘系数，每个顶点会对之后两层顶点产生影响。与4.2.3不同的是，要拼接的边不在同一张图中。我们假设第一条边来自G1，对于奇数号顶点，采用以下两个公式代替4.2.3中的公式对于偶数号顶点，把上述公式的W1和W2互换即可。然后再假设第一条边来自G2，用完全对应的方法计算，最后取两者的最小值即可。5. 模型评价及改进5.1. 模型评价1）本文根据乘客的不同需求，提出三个目标函数（总时间最短、总费用最少、换乘次数最少），并求出三个目标函数在仅考虑

27、公汽线路时的最优解，以及目标函数在同时考虑公汽线路和地铁线路时的最优解。因此本文所建的模型可以满足乘客的不同需求。但是，本文并没有提出一个综合考虑乘客3种需求的模型。2）在模型4.1中，采用Dijkstra算法求出任意两公汽站点之间最优线路。该模型方法比较简单，准确性高，可操作性强。但该算法只能解决公交线路比较简单的情况，具有它的局限性。 3）双层Dijkstra算法与修改的Dijkstra算法的比较为了说明双层Dijkstra算法较修改的Dijkstra算法的优点，枚举了3996个站点（其中3957个公汽站点和39个地铁站点）的两两组合，一共= 7982010种查询。对于每一个查询，分别用两

28、种算法计算，并加以比较，发现双层Dijkstra算法在其中的458681条查询更优，其余的计算结果相同。两种算法最多会相差3.5分钟。如S1914S3060，用修改的Dijkstra算法算得最少时间为42分钟，用双层Dijkstra算得最少时间为38.5分钟。具体路线见附录。把所有相差的时间平均分散到所有查询中，每条线路多用4.5秒。修改的Dijkstra算法效率较高，但不是总能获得时间最少的解。从分析中看，该算法在94.3%情况下适用。在其不适用的5.7%中，最大误差也仅为3.5分钟，这已是一种十分实用的近似算法。双层Dijkstra算法能获得最短路径，但效率相对降低，大约比修改的Dijks

29、tra算法慢40倍。从实际应用来看，该公司可以将所有路径计算好，待查询者查询时，直接查表即可。4）双层Dijkstra算法可以得到非常好的结果，但是本文无法给出严格的证明。5.2. 模型改进1）单一目标函数能找到使其目标函数达到很好，但并不一定实用的路线。可考虑多个目标函数加权作为权值以获得更实用的路线。参考文献1(美)科曼(Cormen, T.H.)等著；潘金贵等译，算法导论，北京：机械工业出版社，2006。附录附1：只考虑公汽的最佳路线详细换乘表（公交线路后的括号内的两个数据分别为车票花费和时间）最少时间S3359S1828S1557S0481时间：64 花费：3 换乘：2S3359S29

30、03 乘 L474(1, 8), L436(1, 8), L366(1, 8), L352(1, 8), L132(1, 8), L123(1, 8), L015(1, 8)S2903S1784 乘 L485(1, 53), L485(1, 53)S1784S1828 乘 L217(1, 8), L167(1, 8)时间：99 花费：4 换乘：3S1557S1919 乘 L363(1, 41), L084(1, 41)S1919S3186 乘 L189(1, 14)S3186S0902 乘 L317(1, 35), L091(1, 35)S0902S0481 乘 L516(1, 14), L4

31、60(1, 14), L447(1, 14), L312(1, 14), L254(1, 14)S0971S0485S0008S0073时间：103 花费：3 换乘：2S0971S2517 乘 L013(1, 53)S2517S2159 乘 L290(1, 44), L290(1, 44)S2159S0485 乘 L469(1, 11)时间：59 花费：5 换乘：4S0008S1691 乘 L198(1, 11)S1691S2085 乘 L476(1, 20)S2085S0609 乘 L406(1, 8), L406(1, 8), L017(1, 8), L017(1, 8)S0609S052

32、5 乘 L328(1, 14)S0525S0073 乘 L103(1, 11)S01480485S00873676时间：102 花费：4 换乘：3S0148S3604 乘 L308(1, 50)S3604S2361 乘 L354(1, 11), L123(1, 11), L081(1, 11)S2361S2210 乘 L156(1, 32)S2210S0485 乘 L417(1, 14)时间：46 花费：3 换乘：2S0087S0088 乘 L454(1, 8), L206(1, 8), L021(1, 8)S0088S0427 乘 L381(1, 35), L231(1, 35), L231

33、(1, 35)S0427S3676 乘 L462(1, 8), L097(1, 8)最少换乘次数最小花费S3359 S1828时间：137 花费：3 换乘：1S3359S0304 乘 L469(2, 92)S0304S1828 乘 L217(1, 50)时间：145 花费：3 换乘：2S3359S0772 乘 L469(1, 47)S0772S0096 乘 L204(1, 65)S0096S1828 乘 L167(1, 38)S1557 S0481时间：178 花费：4 换乘：2S1557S0051 乘 L363(1, 38), L084(1, 38)S0051S0273 乘 L384(1,

34、65)S0273S0481 乘 L460(2, 80)时间：115 花费：3 换乘：2S1557S1919 乘 L363(1, 41), L084(1, 41)S1919S0902 乘 L417(1, 65)S0902S0481 乘 L516(1, 14), L460(1, 14), L447(1, 14),L312(1, 14), L254(1, 14)S0971 S0485时间：260 花费：5 换乘：1S0971S0354 乘 L119(2, 80)S0354S0485 乘 L377(3, 185)时间：149 花费：3 换乘：1S0971S0872 乘 L119(1, 56)S0872

35、S0485 乘 L417(2, 98)S0008 S0073时间：116 花费：3 换乘：1S0008S0181 乘 L259(1, 44)S0181S0073 乘 L058(2, 77)时间：83 花费：2 换乘：1S0008S0291 乘 L159(1, 59)S0291S0073 乘 L058(1, 29)S0148 S0485时间：196 花费：4 换乘：2S0148S0302 乘 L308(1, 20)S0302S0029 乘 L348(2, 119)S0029S0485 乘 L051(1, 62)时间：124 花费：3 换乘：2S0148S3604 乘 L308(1, 50)S36

36、04S0248 乘 L021(1, 20)S0248S0485 乘 L469(1, 59)S0087 S3676时间：71 花费：2 换乘：1S0087S1893 乘 L454(1, 41)S1893S3676 乘 L209(1, 35)时间：71 花费：2 换乘：1S0087S1893 乘 L454(1, 41)S1893S3676 乘 L209(1, 35)附2：考虑公汽和地铁的最佳路线详细换乘表（公交线路后的括号内的两个数据分别为车票花费和时间）最少时间S3359S1828S1557S0481时间：62 花费：7 换乘：4S3359S2903 乘 L474(1, 3), L436(1,

37、3), L366(1, 3), L352(1, 3), L132(1, 3), L123(1, 3), L015(1, 3)公汽换乘公汽(0, 5)S2903S0609 乘 L201(1, 12)S0609D12 步行(0, 4)等待地铁(0, 2)D12D37 乘 T2(3, 15)D37S1961 步行(0, 4)等待公汽(0, 3)S1961S1671 乘 L428(1, 6)公汽换乘公汽(0, 5)S1671S1828 乘 L041(1, 3)时间：99 花费：4 换乘：3S1557S1919 乘 L363(1, 36), L084(1, 36)公汽换乘公汽(0, 5)S1919S31

38、86 乘 L189(1, 9)公汽换乘公汽(0, 5)S3186S0902 乘 L317(1, 30), L091(1, 30)公汽换乘公汽(0, 5)S0902S0481 乘 L516(1, 9), L460(1, 9), L447(1, 9), L312(1, 9), L254(1, 9)S0971S0485S0008S0073时间：95 花费：6 换乘：3S0971S0567 乘 L119(1, 18), L094(1, 18)S0567D01 步行(0, 4)等待地铁(0, 2)D01D15 乘 T1(3, 35)D15S2534 步行(0, 4)等待公汽(0, 3)S2534S221

39、0 乘 L156(1, 15)公汽换乘公汽(0, 5)S2210S0485 乘 L417(1, 9)时间：53.5 花费：5 换乘：3S0008S2534 乘 L200(1, 18)S2534D15 步行(0, 4)等待地铁(0, 2)D15D12 乘 T1(3, 7.5)地铁换乘地铁(0, 4)D12D25 乘 T2(0, 5)D25S0525 步行(0, 4)等待公汽(0, 3)S0525S0073 乘 L103(1, 6)S0148S0485S0087S3676时间：86.5 花费：6 换乘：3S0148S1487 乘 L024(1, 12)S1487D02 步行(0, 4)等待地铁(0

40、, 2)D02D15 乘 T1(3, 32.5)D15S2534 步行(0, 4)等待公汽(0, 3)S2534S2210 乘 L156(1, 15)公汽换乘公汽(0, 5)S2210S0485 乘 L417(1, 9)时间：30 花费：3 换乘：0S0087D27 步行(0, 4)等待地铁(0, 2)D27D36 乘 T2(3, 20)D36S3676 步行(0, 4)最少换乘最少花费S3359 S1828时间：132 花费：3 换乘：1S3359S0304 乘 L469(2, 87)公汽换乘公汽(0, 5)S0304S1828 乘 L217(1, 45)时间：137 花费：3 换乘：1S3359S0304 乘 L469(2, 87)公汽换乘公汽(0, 5)S0304S1828 乘 L217(1, 45)S