21组乘公交看奥运1.

1、乘公交看奥运摘要本文解决的是如何在众多的路线中选择两个公交站点之间最优乘车路线的 问题，其面向对象主要为普通公众以及奥运期间来北京的游人。根据不同乘客的路线选择偏好建立了在换乘次数最多为两次的约束条件下的多目标优化模型。对于问题一：对于两站点之间的最优乘车路线，不同的乘客有不同要求，一 般按关心的程度依次为：换乘次数、行程时间、乘车费用，故建立了以上三个因 素为目标的多目标模型，然后结合 Matlab运用广度优先搜索法求解直达、转乘 一次、转乘两次情况下的线路，最后按要求分别选出转乘次数最少、 行程时间最 短、费用最少情况下的最优路线。运行结果如下表所示：出发站S3359 S1557S0971

2、 S0008 S0148 S0087终点站S1828 S0481；S0485 S0073S0485S3676：最少转乘次数（次）121121最短行程时间（min）73112 112170r 10658:最少费用（元）333232对于问题二：处理地铁线路时，将其视为公汽线路处理。地铁周围邻近的公 汽站即可作为两者的交汇点。因此该模型的公交换乘路线模型与模型一中的基本 相同。求解直达、转乘一次、转乘两次情况下的线路，最后按要求分别选出转乘 次数最少、行程时间最短、费用最少情况下的最优路线。运行结果如下表所示：出发站S3359 S15571 S0971 S0008 1 S0148S0087终点站S1

3、828 S0481S0485 S0073 S0485S3676最少转乘次数（次）121121最短行程时间（min）73112 :937065.540.5 :最少费用（元）333254对于问题三：步行换乘通常有以下的两种类型： 1两条公交线路相交，但 不存在相交的站点，行人需要下车后步行到邻近的站点进行换乘。 2、两条公交 线路不相交，但两行车路线上有相邻站点。如果步行的代价足够小，而且可以有 效减少换乘次数和乘车费用，行人选择下车步行到邻近站点进行换乘。运行结果 如下表所示：出发站S3359 S1557.S0971 S0008 S0148 S0087.终点站S1828 S0481S0485 S

4、0073 S0485S3676最少转乘次数（次）012010最短乘车时间（min）57110 1938965.522最少费用（元）235231关键词：广度优先搜索、最优路线、转乘次数相邻公汽站平均行驶时间相邻地铁站平均行驶时间（包括停站时间 ）： 3 分钟（包括停站时间 ）： 2.5 分钟公汽换乘公汽平均耗时地铁换乘地铁平均耗时地铁换乘公汽平均耗时汽换乘地铁平均耗时：一、问题重述1.1问题背景我国人民翘首企盼的第 29 届奥运会明年 8 月将在北京举行，届时有大量观 众到现场观看奥运比赛， 其中大部分人将会乘坐公共交通工具 （简称公交， 包括 公汽、地铁等）出行。这些年来，城市的公交系统有了很

5、大发展，北京市的公交 线路已达 800 条以上，使得公众的出行更加通畅、 便利，但同时也面临多条线路 的选择问题。 针对市场需求， 某公司准备研制开发一个解决公交线路选择问题的 自主查询计算机系统。1.2需解决的问题为了设计这样一个系统， 其核心是线路选择的模型与算法， 应该从实际情况 出发考虑，满足查询者的各种不同需求。请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与 算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站一终到站 之间的最佳路线（要有清晰的评价说明） 。（1）、S3354 S1828（2）、S1557S0481 （3）、S0

6、971S0485（4）、S000IS0073（5）、S0148 S0485 （6）、S0087S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问 题的数学模型。二、模型的假设与基本参数设定2.1 模型的假设 假设一：同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘 （ 无需 支付地铁费 ） ；假设二：人们乘公交车最多能忍受换乘两次车； 假设三：若出发站、换乘站以及终点站与换乘站之间仅隔一个站点选择步行 而不换乘；假设四：直线型的地铁线路可以对开。2.2基本参数设定5分钟（其中步行时间 2 分钟）4 分钟（其中步行时间

7、2 分钟）7 分钟（其中步行时间 4 分钟）6分钟（其中步行时间 4 分钟）公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元地铁票价： 3 元（无论地铁线路间是否换乘）三、符号说明n汽车线路的总数，为1040条Li公交线路的编号S乘客乘坐第Li条线路经过的公交站点数S乘客乘坐地铁时经过的地铁站的个数Ui第Li条公交路线的票价Tk第k条线路的行程时间N1公汽换乘公汽的次数N2地铁换乘地铁的次数N3地铁换乘公汽的次数N4公汽换乘地铁的次数a总的公汽站点数目，为3957个b总的地铁站点数目，为39个t AB起点站A与终点站B

8、之间的步行时间为tAB（A=1,2,3996;B=1,2,3996）四、数据处理4.1数据说明（1）该公交系统共有公汽线路520条。其中票价信息为分段计价的线路一共 有283条，单一票制1元的线路237条；上下行路径不同的线路409条, 上下行路径相同的线路89条，环行线路22条。（2）该公交系统共有公汽站点3957个。（3） 该公交系统共有地铁线路2条。其中直行线路1条，环行线路1条。（4）该公交系统共有地铁站点39个4.2对于原始数据中异常数据的处理（1）当一条线路中相邻站点名相同时，去掉其中任意 1个点。(2)在 L406 线路中未标明是否为环行线，将其当作环线处理。(3)由于 L290

9、 标明是环线，但首尾站点分别为 1477 与 1479 不重合，故将 站点 1479 当做 1477 处理。4.3对于线路标号的处理(1)将各公交站点的编号由字符型去掉 S换为数值型编号如S1404站点， 换为数值型后为 1404。( 2)对于各公交路线的编号， 首先去掉字符 L 将编号转换为数值型； 然后将 所有原公交路线的编号加 4000，得到新的公交路线编号；上行路线的标号为新 的公汽线路编号， 下行路线的标号为上行标号的数值与 520 之和，如第 8 条公交 线路上行路线的编号为 4008，下行路线的编号就为 4528。这样就可以方便的将 所有的公汽、 站点编号在保证数值不重复的情况下

10、存入到同一张 excel 表中，便 于数据的提取与查找。4.4公汽路线的存储公汽路线分三种情况：下行线不是上行线的原路返回下行线是上行线的 原路返回环线 。针对第种情况， 分离的两条标号不同的公汽路线的公汽站点是前后倒置的， 以 L001 为例，具体存储过程如下：L001: S0619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819-S3524-S0820-S3914-S0128-S0710经过处理后为： L001:S0619-S1914-S0388-S0348-S0392-S0429-S0436-S3885-S3612-S0819-

11、S3524-S0820-S3914-S0128-S0710L521: S0710-S0128-S3914-S0820-S3524-S0819-S3612-S3885-S0436-S0429-S0392-S0348-S0388-S1914-S0619针对第种情况，分离的两条标号不同的公汽路线的公汽站点分别为原上行 线与下行线站点路线，以 L002 为例，具体存储过程如下：L002上行：S3748-S2160-S1223-S1404-S2377-S1477-S2017-S2019-S1321-S1381-S1383-S 1691-S3766-S1729-S2654-S3231-S3917-S230

12、3-S1327-S3068-S2833-S1733-S 2113-S2636-S0012-S1968-S0004下行： S0004-S1968-S0012-S2636-S2113-S2112-S2833-S0618-S1327-S2303-S3917-S 3231-S2654-S1729-S3766-S1691-S1383-S1381-S1321-S2019-S2017-S1477-S 1404-S1223-S2160-S3748经过处理后为：L002： S3748-S2160-S1223-S1404-S2377-S1477-S2017-S2019-S1321-S1381-S1383- S16

13、91-S3766-S1729-S2654-S3231-S3917-S2303-S1327-S3068-S2833-S1733- S2113-S2636-S0012-S1968-S0004L522： S0004-S1968-S0012-S2636-S2113-S2112-S2833-S0618-S1327-S2303-S3917- S3231-S2654-S1729-S3766-S1691-S1383-S1381-S1321-S2019-S2017-S1477- S1404-S1223-S2160-S3748针对第种情况，分离的两条标号不同的公汽路线等效为两条顺、逆时针的 环形路线，例 如 环

14、形 路 线 S1-S2-S3-S4 存 为 路 线 S1-S2-S3-S4-S1-S2-S3-S4 和S1-S4-S3-S2-S1-S4-S3-S2两条公汽线路，以L089为例，具体存储过程如下：L089 : S3295-S0704-S0705-S1337-S1831-S1749-S0314-S1734-S0532-S0325-S0317 -S0327-S1341-S2285-S1333-S1334-S3265-S3295经过处理后上、下行线路的编号如下：L089 : S3295-S0704-S0705-S1337-S1831-S1749-S0314-S1734-S0532-S0325-S03

15、17 -S0327-S1341-S2285-S1333-S1334-S3265-S3295-S3295-S0704-S0705-S13 37-S1831-S1749-S0314-S1734-S0532-S0325-S0317-S0327-S1341-S2285-S 1333-S1334-S3265-S3295L609: S3295-S3265-S1334-S1333-S2285-S1341-S0327-S0317-S0325-S0532-S1734 -S0314-S1749-S1831-S1337-S0705-S0704-S3295-S3265-S1334-S1333-S22 85-S1341

16、-S0327-S0317-S0325-S0532-S1734-S0314-S1749-S1831-S1337-S 0705-S0704所有公汽线路处理完毕后，得到1040条公交路线4.5不同票价的公汽路线的处理公汽票价分为单一票价与分段计价两种，将单一票价路线查找出来另行存储，得到474条单一票价为1元的公交路线。4.6存储经过每个站点的公交路线通过第二步的处理，找出经过每个公汽站点的所有公汽路线并进行数据存储， 例如经过S3359的所有公汽路线的集合为： L015、L123、L132、L291、L324、L352、L366、L378、L436、L469、L473、 L474、 L484、 L

17、535、 L643、 L652、 L811、 L844、 L872、 L886、 L898、 L956、 L989、 L993、 L994、 L1004经过S1828的所有公汽路线的集合为：L041、 L167、 L182、 L217、 L238、 L561、 L687、 L702、 L737、 L758 4.7换乘时的等待时间(1) 公汽的等待时间为3分钟;(2) 地铁的等待时间为2分钟。五、问题分析本文解决的是如何在众多的路线中选择两个公交站点之间最优乘车路线的 问题，其面向对象主要为普通公众以及奥运期间来北京的游人。根据不同乘客的路线选择偏好建立了在换乘次数最多为两次的约束条件下的多目标

18、优化模型。首先要明确评价两个公交站点之间线路好坏的因素， 一般来说公众乘坐公交时最关 心的就是从出发点到终点站的换乘次数、总行程时间以及乘车费用这三个因素， 然后分别以三个因素为目标建立了多目标模型。由于这三个目标的量纲不同，且对于不同的乘客出行时要求不同(部分人要求最快到达目的地、 部分乘客要求换 乘的次数最少而有的人希望花费最少)，故根据三种不同的要求做为最优线路的 目标模型进行求解。根据相关资料 对乘客的出行心理进行了调查研究，其结果 表明“换乘次数”是大部分乘客在选择出行方案时的首要考虑因素，且为了计算方便，将公众乘车时最多允许的转乘次数规定为两次。对于问题一：仅考虑公汽线路的情况。分

19、别根据三个目标：换乘次数最少、 从起点到终点的总行程时间最短以及乘车费用最少为最优目标的模型进行求解。 由于限制了两个站点之间的转乘次数不超过两次， 故而任意两个站点之间到达的 方式只有三种：直达、转乘一次、转乘两次。对于问题二：将公汽与地铁同时考虑，找出可行路线，然后寻找最优路线。 对于地铁线路，也可以将其作为公汽线路，本质上没有什么区别，只是乘车费用、 时间，换乘时间存在区别。因此可以将地铁站等效为公交站， 地铁和公交的转乘 站即可作为两者的交汇点。因此该模型的公交换乘路线模型与模型一中的基本相 同。然后计算直达、转乘一次、转乘两次情况下的线路，根据不同乘客的要求从 中选出最短行程时间或最

20、少费用情况下的最优路线。对于问题三：加入了步行的因素，使得公众出行可以选择的路线大大增加。 步行换乘通常有以下的两种类型：1、两条公交线路相交，但不存在相交的站点， 行人需要下车后步行到邻近的站点进行换乘。2、两条公交线路不相交，但两行车路线上有相邻站点，行人选择下车步行到邻近站点进行换乘。如果步行的代价 足够小，而且可以有效减少换乘次数和乘车费用。六、问题一的解答针对问题一建立了模型一6.1模型一的建立该模型针对问题一，仅考虑公汽线路时，先找出经过任意两个公汽站点 A、B 之间最多转乘两次公汽的路线，然后再根据不同查询者的需求搜寻出最优路线。 找出了任意两个公汽站点间的可行路线，就可以对这些

21、路线按不同需求进行选择 并找出最优路线。6.1.1以换乘次数最短为目标函数：即相当于考虑直达、换乘1次、换乘2次的 情况。Min n T6.1.2以时间最短的路线作为最优路线的模型：可行路线的总行程时间为乘公交 时间与公交换乘时间之和。nMin TK =5(n -1) 3、q i #6.1.3、以花费最少为目标函数Min 5(1 -Uj )bi 4其中乘公交车的费用函数:1第Lj条线路为单一票价路线 ui =0第Lj条线路为分段计价路线40 Si =0;10 c s 兰 20; b221 兰 Si 兰 403s 兰41综上所述得问题一的模型如下所示:nMin TK =5(n -1) 3、si

22、i AMin n -1nMin U (1 ubi吕h第Li条线路为单一票价路线s.t. Ui = 0第Li条线路为分段计价路线0 Si = 0;1 0 c Si 兰 20; b = 2 21兰q兰403 s 416.2算法描述：针对本问题的目标函数，通过使用广度优化算法搜索出任意两点之间的可行 路线。设A、B两点分别为起点站与终点站，C、D分别为转乘站点。1）首先考虑直达的情况（如下图1所示）设LA为途径A站的所有路线的集合，LB为途径B站的所有路线的集合。 如果LA LB = 一，说明A到B站可以不用转车就能到达。取路线Line=LALB， 只要计算经过Line中的路线到达B站的所有情况，从

23、中选出最少时间或最少费 用的路线即可。若LA LB= ,即转入步骤2。2）需要经过一次转车时（如图 2所示）LA LB二、，设BusA为所有与 LA有公共站点的路线的集合，若同时满 LA LB ,说明A站到B站只需经 过一次转车就可到达。取 Line仁LA, LB，依次遍历Linel中各种情况，从中选 出最少时间或最少费用的路线即可。3）若LAi LB= ,则A到B需转车2次或2次以上（如图3所示），设LA2 为所有与LAi有公共站点的路线的集合，也即LA2为所有在A站转车两次能够搭 乘的公交路线。同步骤2），计算Line2=LA2 LB的所有情况，若Line2=_ ,类 似的计算LAi和Li

24、nei（i为转车次数），依此类推。如果存在多种选择，则以时 间和费用为第二目标进行排除，选出最优路线。算法流程图如下所示:6.3模型的求解 通过以不同目标为最优线路模型，利用 Matlab （计算程序见附录一）求解得，六个出发点与终点站在不同目标下的最优路线模型如下表所 示：当起点站、终点站分别为 S3354S1828时在不同的目标函数下对应的最优 路线如下表所示起点站终点站 目标换乘次数时间（分）费用（元）最少换乘次数1P1043L436L167S3359下行线S1784下行线S1828最短到达时间2733L352L201L041S3359下行线S2903上行线S458上行线S1828最小费

25、用11043S3359S182853359 下行线S1784 下行线S1784当起点站、终点站分别为 S1557- S0481时在不同的目标函数下对应的最优 路线如下表所示起点站终点站 目标换乘次数时间（分）费用（元）最少换乘次数：2：1123S15576S1919 L417 S2424上邑 S0481下行线上行线上行线最短到达时间21123S1557 L363 S1919 L417 S2424-5 S0481下行线上行线上行线最小费用21123S1557S0481S1557 L363 S1919 L417 S2424 L254 S0481下行线上行线上行线当起点站、终点站分别为 S0971-

26、S0485时在不同的目标函数下对应的最 优路线如下表所示起点站终点站 目标换乘次数时间（分）费用（元）S0971S0485最少换乘次数1P1373S0971 下行线 S1789 下行线 S0485下行线下行线最短到达时间21213L013L132L417S0971下行线S2324下行线S2480下行线S0485最小费用1373L013L417S0971下行线S1789下行线S0485当起点站、终点站分别为 SOOOIS0073时在不同的目标函数下对应的最优 路线如下表所示起点站终点站 目标换乘次数时间（分）费用（元）最少换乘次数1：862S0008S3614 -05 S0073下行线下行线最短

27、到达时间2703L159L447L118S0008下行线S630上行线S651下行线S0073最小费用1862S0008S0073S0008 下行S S3614 下行S S0073当起点站、终点站分别为 S014IS0485时在不同的目标函数下对应的最优路线如下表所示起点站终点站 目标换乘次数时间（分）费用（元）最少换乘次数2P1063L308L156L417S0148上行线S0036上行线S2210下行线S0485最短到达时间21063L308L156L417QAdQood norS0148 /4 S0036 /4 S2210/ 亠 S0485上行线上行线下行线最小费用21063S0148S

28、0485S0148 上行0线 S0036 上行线 S2210 下行1 线 S0485上行线上行线下行线当起点站、终点站分别为 S0087-S3676时在不同的目标函数下对应的最优 路线如下表所示起点站终点站 目标换乘次数时间（分）费用（元）最少换乘次数1：682S0087 礫 S3496 下Ih3676最短到达时间2583S0087,/21 S0088 231 S0427z462 S3676下行线环形下行线最小费用1682S0087S3676L454L209S0087-S3496-S3676上行线下行线七、问题二的解答针对问题二建立了模型二7.1模型二的建立本模型针对问题二，将公汽与地铁同时考

29、虑，找出可行路线，然后寻找最优 路线。对于地铁线路，也可以将其作为公交线路，本质上没有什么区别，只不过 乘车费用、时间，换乘时间不一样。因此地铁站可等效为公交站，地铁和公交的 转乘站即可作为两者的交汇点。因此该模型的公交换乘路线模型与模型一中的基 本相同。现建立模型二下的最优路线模型。7.1.1以时间最短的路线作为最优路线的模型：可行路线的总时间为乘公交（公 汽和地铁）时间与公汽与地铁换乘、公汽间、地铁间换乘时间之和。N i公汽换乘公汽的次数N 2地铁换乘地铁的次数N 3地铁换乘公汽的次数N 4公汽换乘地铁的次数故从出发点到终点乘做不同公交线路的次数为 N+ N3+1 ；乘坐不同地 铁线路的次

30、数为N2 +N4+1N1 N3 1N 2 fl4 1MinTk =5N1 4N2 7N3 6N43 $2.5 Sjimj17.1.2以转乘次数最少的路线为最优路线模型：Min N1 N2 N3 N47.1.3以费用最少的路线为最优路线模型：费用为搭乘公汽与地铁的票价之和，公汽的票价有单一票价与分段计价两 种，地铁的票价衡为3元。又因为地铁换地铁不用转乘费，故只有在公汽换乘地 铁时需要买票。Ni N3 -1Min 、 Ui (Ui)b 3N4N4表示公交换乘地铁的次数,i 4N1+ N3+1表示从出发点到终点乘做不同公交线路的总数。乘公交车的费用函数：h第Li条线路为单一票价路线 ui = 0第

31、Li条线路为分段计价路线0 Si =0;1 0 s 兰 20;b = 2 21兰$兰403 sU41-综上所述，问题二的模型为N1 N2 1N2：fN4 1MinTk =5N4N2 7N3 6N43 S 2.5 Sjyj d：Min N1 N 2 N3 N4弘叫1Min ui(1 -ujb 3N4i =1丄,1第Li条线路为单一票价路线S.t.Ui = “0第Li条线路为分段计价路线0 Si =0;1 0 417.2模型二的算法描述7.2.1数据的储存对于T1地铁线路：T1为直线型，因为直线型地铁可以对开（假设四），故 同公汽线路一样将其编号为上、下行两条路线；对于 T2地铁线路：T2为环形，

32、 将其编号为一条路线。由于每个地铁站点周围都对应有若干个公交站点，故将同 一个地铁站对应的公交站点再标一个同样的号码用来表示这几个公交站点均在 同一个地铁站附近。722计算过程针对本问题的目标函数，通过使用广度优化算法搜索出任意两点之间的可行 路线。1） 首先考虑直达的情况设LA为途径A站的所有路线（包括地铁与公交）的集合， LB为途径B站 的所有路线（包括地铁与公交）的集合。如果 L LB = ._ ,说明A到B站可以 不用转车就能到达。取路线 Line=LALB，只要计算经过Line中的路线到达B 站的所有情况，从中选出最少时间或最少费用的路线即可。若 LA LB=._ ,即 转入步骤2。

33、2） 需要经过一次转车时，LA LB=._ ,设LA为所有与LA有公共站点的 路线的集合，若同时满足LA LB-_ ,说明A站到B站只需经过一次转车就 可到达。取Line仁L A, LB，依次遍历Linel中各种情况，从中选出最少时间或 最少费用的路线即可。3） 若L A, LB= ,则A到B需转车2次或2次以上，设L A?为所有与L A, 有公共站点的路线的集合，也即 LA2为所有在A站转车两次能够搭乘的公交路 线。同步骤2）,计算Line2= L A? LB的所有情况，由于公众出行时最多转车两 次（假设二），所以不用考虑转乘次数大于两次的情况。7.3问题二的结果通过以不同目标为最优线路模型

34、，利用Matlab （计算程序见附录二）求解得，六个出发点与终点站在不同目标下的最优路线模型如下表所示：当起点站、终点站分别为 S3354S1828时在不同的目标函数下对应的最优 路线如下表所示起点站终点站 目标换乘次数时间（分）费用（元）最少换乘次数1P1043S3359 下行线S1784 下行线S1828最短到达时间2733L352L201L041S335J/一S2903 /S458 r /一下行线上行线上行线S1828最小费用11043S3359S1828L436L167S3359下行线S1784下行线S1784当起点站、终点站分别为 S1557- S0481时在不同的目标函数下对应的最

35、优 路线如下表所示起点站终点站 目标换乘次数时间（分）费用（元）最少换乘次数2：1123S1557 下行线S1919上行线S2424上行线S0481最短到达时间21123S1557 下行线 S1919 L4线 S2424 上2线 S0481下行线上行线上行线最小费用21123S1557S0481S1557 下行线 S1919 L41 线 S2424 上2线 S0481下行线上行线上行线当起点站、终点站分别为 S0971-S0485时在不同的目标函数下对应的最 优路线如下表所示起点站终点站 目标换乘次数时间（分）费用（元）最少换乘次数1P1373S0971下行线S1789下行1 线S0485下行

36、线下行线最短到达时间21213S0971 下行1 线 S2324 下-行线 S2480 下行线 S0485下行线下行线下行线最小费用11373S0971S0485S0971 下行3 S1789 下行1线 S0485下行线下行线当起点站、终点站分别为 S000IS0073时在不同的目标函数下对应的最优 路线如下表所示起点站终点站 目标换乘次数时间（分）费用（元）最少换乘次数1；862L159L058S0008下行线S3614下行线S0073最短到达时间2703S0008S0073S0008 59 S630 L447 S265L11 S0073下行线上行线下行线最小费用1862L159L058S0

37、008下行线S3614下行线S0073当起点站、终点站分别为 S014IS0485时在不同的目标函数下对应的最优路线如下表所示起点站终点站 目标换乘次数时间（分）费用（元）最少换乘次数2P1063S0148上行S0036 上行线 S2210下行S0485上行线上行线下行线最短到达时间21063S0148 上行线 S0036 上行线 S2210 下行线 S0485上行线上行线下行线最小费用21063S0148S0485S0148 上行卜 S0036 上行线 S2210下行线 S0485上行线上行线下行线当起点站、终点站分别为 S0087-S3676时在不同的目标函数下对应的最优 路线如下表所示起

38、点站终点站 目标换乘次数时间（分）费用（元）最少换乘次数1：682L454L209S0087,S3496,S3676上行线下行线最短到达时间2583S0087S0088 L2|1 S0427 占芽 S3676下行线环形下行线最小费用1682S0087S3676S0087 丄竺丄 S3496 丄p0 S3676上行线下行线八、问题三的解答对于问题三建立了模型三8.1模型的建立问题三加入了步行的因素，使得可以选择乘坐的路线大大增加。步行换乘通常有两种类型：一种是两条公交线路相交，但不存在相交的站点，行人需要下车后步行到邻近的站点进行换乘；另一种情况是两条公交线路不相交，但两行车 路线上有相邻站点，

39、行人选择下车步行到邻近站点进行换乘。如果步行的代价足 够小，就可以选择步行而且可以有效减少换乘次数与乘车费用。出发站、换乘站以及终点站与换乘站之间仅隔一个站点时选择步行而不选择换乘。设起点站A 与终点站 B 之间的步行时间为tAB（A=1,2,，3996;B=1,2,3996）卄 1则第A个站点到第B个站点选择步行右a二0第A个站点到第B个站点不选择步行3996 3996则从A、B两站点之间总的步行次数C = a a a ,步行的总时间为A- B=439963996TAB = tABaA吕B （其中1,2,3957为公汽站点，3958,3959，,3996之间共39个点为地 铁站点；若A、B表

40、示相同的站点则两点之间的步行时间为零。）8.1.1以总行程时间最短路线作为最优路线模型：总的行程时间包括三个方面：乘车时间、步行时间与换乘时间。3957 3957C为A、B两站之间总的步行次数，故公交线之间的换乘次数为叫二：/ a，AT B=!乘坐不同公交线路的次数为N1 N31-C,由于相邻的地铁站之间不能步行故地铁与地铁之间的转乘次数为 N2N1 N3 1-CN2 迅4 13957 3957Tk -3 Si 25 Sj +TAB+ 5（2 二二 a） 4N2 7N3 6N4iWjA毘 B =18.1.2以行程中花费的费用最少路线作为最优路线模型：费用包括两个方面：乘公汽的车费与乘地铁的花费

41、（公汽票价分为单一 票制与分段计价两种形式，地铁票价恒为3元）N1 N2 1-CMin 、（Ui （1 -ujb） 3N4i m公汽的费用函数如下1第Li条线路为单一票价路线Ui厂0第Li条线路为分段计价路线0 Si = 0;1 0 c Si 兰 20;b =i2 21兰s兰403 Sj K418.1.3以换乘次数最少的路线作为最优线路模型：3957 3957Min（Ni 2 N3 N4 - a 、 a）8.1.4以步行时间最短的路线作为最优线路模型（因为本问中加入了步行因素, 故还要考虑部分公众出行乘车时希望步行时间最短）3996 3996Min ；二 tABaA4 B 4综上所述问题三的模

42、型为N1 N3 1 -CN2 N4 13957 3957Min Tk -3 Si 2.5 Sj +TAB+ 5（弘 一、a） 4N2 7N3 6N4ijAA经 BT3957 3957Min（N12 N3 N4 二二 a）Az1 B z!39963996Min 二二 tABaAz1 B m1第Li条线路为单一票价路线ui = 0第Li条线路为分段计价路线0 Si =0;1 0 c s 兰 20;b 2 21兰s兰403 Sj 工418.2算法描述：相比于问题二，本问只引入了步行时间，算法过程与问题二中的一致8.3模型的求解通过以不同目标为最优线路模型，利用Matlab （计算程序见附录二）求解

43、得，六个出发点与终点站在不同目标下的最优路线模型如下表所示：当起点站、终点站为S335XS1828时在不同的目标函数下对应的最优路线： 以转乘次数为目标函数，最优路线为S3359L436 S1784步行一站 然后到终点站S1828 直达以行程时间最短为目标函数，最优路线为从起点站步行两站到S2903再经L201线路到S1671站点再步行一站到终点 站S1784最短行程时间为57分钟以最少费用为目标函数，最优路线与以行程时间最短为目标函数的最优路线 相同最少费用为2元。当起点站、终点站为S1557S0481时在不同的目标函数下对应的最优路线： 以转乘次数为目标函数，最优路线为从S1557出发经L

44、363线路到S1919站再转乘L417到S3919站最后步行两 站到终点站S0481。转乘次数为一次。以行程时间最短为目标函数和以最少费用为目标函数的最优线路同以转乘 最少为目标函数的最优路线，最短行程时间为110分钟，最少费用为3元。当起点站、终点站为S0971-S0485时在不同的目标函数下对应的最优路线： 以转乘次数为目标函数，最优路线为从S0971出发经L094线路到S0567站再转乘D01到D21，步行到S0464站 最后乘L0469路公交到终点站S0485转乘次数为两次。以行程时间最短为目标函数和以最少费用为目标函数的最优线路同以转乘 最少为目标函数的最优路线，最短行程时间为93分

45、钟，最少费用为5元。当起点站、终点站为SOOOMS0073时在不同的目标函数下对应的最优路线： 以转乘次数为目标函数，最优路线为从S0008步行两站到S1383站再乘L282路公交到终点站S0073,直达 以行程时间最短为目标函数，最优线路为：从S0008站出发乘L159路到S3614站下车再换乘L058路到终点站S0073 下车，最短行程时间为89分钟；以最小费用为目标函数的最优路线与以行程时间最短为目标函数的最优线 路相同，最少乘车费用为2元当起点站、终点站为S140MS0485时在不同的目标函数下对应的最优路线： 以转乘次数为目标函数，最优路线为从S1408站出发乘L308路到S036站再换乘L156路S3332站最后步行两站 到S0485站，最少换乘次数为一次。以最短行程时间为目标函数，最优路线为从S1408出发乘L0