2022年2022年公交查询系统的最佳乘车方案设计 .pdf

《2022年2022年公交查询系统的最佳乘车方案设计 .pdf》由会员分享，可在线阅读，更多相关《2022年2022年公交查询系统的最佳乘车方案设计 .pdf（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、公交查询系统的最佳乘车方案设计摘要本文研究的问题是针对已知的公交线路信息如何设计出最佳的乘车方案。首先，进行数据处理，用excel 建立起公交线路矩阵。然后，上网查阅了公交乘客乘车心理分析的资料，得出影响乘客出行的三个主要因素依次为为：换乘次数、出行时间、出行费用随后，建立了站点 线路序列模型。 利用公交乘客的出行过程抽象为站点线路的交替转换的思想，从而确定了出行者出行路线的一般数学表达式。针对问题一，仅考虑公汽的情况下，以换乘次数最少为第一目标、出行时间为第二目标、 乘车费用为第三目标， 建立起多目标最优化分层求解模型。并依靠站点线路序列模型确定的出行线路表达式，采用图论中计算方法并结合广度

2、搜索法经 matlab编程(见附录一 ) 得到了公交乘客的最少换乘次数， 所经过的站点，出行时间、出行费用 (见表 1)。针对问题二，在问题一的基础上考虑了地铁线路，处理的方法是将地铁线当成特殊的公交线， 将地铁站点当成公交站点并与给定的公交站连接。按照问题一的模型和算法得到乘客的最少换乘次数，出行时间、出行费用(见表 2)。针对问题三，在问题二的基础上考虑了所有站点之间的步行时间，由成人步行速度估算出该时间大小。 步行线路与公汽线路相同但每条均有上行和下行。将步行线路矩阵与公交线路矩阵整合后按照问题二的算法得到乘客的最少换乘次数，出行时间、出行费用(见 9.2)。最后，建立公交负载模型对前三

3、问的模型进行了改进。考虑到了实际中公交线路堵车的情况， 将堵车线路拆分为两段新的线路并相应改变公交线路矩阵。算法与前三问算法相同，但使得最佳路径的选择更加灵活且更符合实际情况。关键词：分层求解交替序列多目标最优化改进广度搜索法名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 38 页 - - - - - - - - - 1 问题重述1.1 问题背景我国人民翘首企盼的第29 届奥运会明年 8 月将在北京举行，届时有大量观众到现场观看奥运比赛， 其中大部分人将会乘坐公共交通工具

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

5、1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485 (4)、S0008S0073 (5)、S0148S0485 (6)、S0087S3676 问题二：同时考虑公汽与地铁线路，解决以上问题。问题三：假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。2 模型的假设及符号说明2.1 模型假设假设 1：假设乘客都是理性乘车且能顺利到达目的地假设 2：假设不考虑红绿灯造成的等待时间，不考虑堵车，车祸等因素假设 3：假设乘客能接受的最大换乘次数为2 次假设 4：假设乘客乘车过程中不能2 次经过同一站点。假设 5：假设公交与地铁换乘距离固定，

6、换乘步行时间为常数2.2 符号说明名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 38 页 - - - - - - - - - 符号说明SS公汽站点集，395700020001,SSSSLL 表示公汽线路集，520002001,LLLLDD 地铁站点集，390201,DDDDTT 表示地铁线路集，21,TTTvikikv 出行者选择第i条公交线路所经过的第k个站点 (Svik或Dvik) ikPikP 出行者选择第i条公交线路所乘坐的第k辆公交工具 (LPik或TPik)

7、 Ni换乘次数Si途经的车站数ti行程时间Qi所需费用3 问题分析本文研究的问题是设计一个公交线路选择的自助查询的计算机系统，并从实际情况出发考虑， 以满足查询者的各种不同需求。 设计该系统的核心是线路选择的模型与算法。针对问题一： 问题一要求只考虑公汽线路， 给出最佳路径。 通过查阅相关资料，知道对乘客影响最大的三个因素：换乘次数，行程时间，所需费用(重要性从大到小 )。据此，我们建立以换乘次数为第一目标，行程时间最为第二目标，所需费用为第三目标的多目标最优化模型。对于换乘次数， 联系被选择线路上的站点线路交替序列TRi个数可以表示出来； 站点总数则采用给同一线路上的站点排序的方法也可以求到

8、， 由于只考虑了公汽之间的换乘， 则出行时间只与换乘次数和所历站数有关； 对于出行费用则在换乘次数的基础上，引入分段计价的加价函数也可求得。针对问题二：问题二在一得基础上考虑可以搭乘地铁，乘客的选择更加灵活。主要变化为：地铁票价稍高但是固定且在地铁航线之间换乘而不需另外支付交通费用，相邻站点之间的距离较公汽站点大，而运行时间却相对减少； 地铁与公汽之间进行换乘时， 由于地铁站点不可能与公汽站点都建在同一个地方，因此从地铁站到公汽站的步行时间相对较多， 而且位于与地铁换乘的公汽站点还可以通过名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -

9、- - 名师精心整理 - - - - - - - 第 3 页，共 38 页 - - - - - - - - - 本地铁站进行免费耗时换乘到下一个公汽站。我们可以把跨公交站的步行视为一种免费耗时的交通方式，据此分层求解。针对问题三： 考虑到出行者在步行时， 所经过的任意两站点之间的路径都应该是至少有一条公汽线路上的公交工具通过，由问题三的条件可知， 步行时所经过的两站点之间的步行时间是一个已知值。当换乘的两站之间站数不多时， 我们考虑步行，这要可以减少换乘次数，节约金钱。4 数据处理及分析4.1 数据处理4.1.1 数据统计我们运用 Excel 软件对给的“公汽线路信息”和“地铁线路信息”进行统

10、计得到如下数据：表 1 公汽线路站点数地铁线路分段计价单一票价上下行路径不同上下行路径相同环形路线公汽站点地铁站点直行线路环形线路283条237条409条89 条22条3957个39 个1 条1 条公交系统共有公汽线路520 条总站点3996个地铁线路共 2 条根据表一并结合本文参数设定中的票价信息，综合考虑，分析如下：在分段计价路线中，共有27条的公汽站点数不超过20，有 148 条的公汽站点数在 2140之间，公汽站点数超过40 的线路有 108条。因此，从单独的计算角度来考虑，可以将分段计价中站数不超过20 的线路归为单一票制1 元的线路，因此上述信息可修正为： 票价信息为单一票制1 元

11、的线路 264条；在分段计价的路线中，共有 256 条，其中有 148 条的公汽站点数在2140之间，公汽站点数超过 40 的线路有 108 条。4.1.2数据的储存与处理由于所给的数据格式不利于程序软件直接读取和操作，我们运用 Excel 将数据处理为规范格式，建立起公交线路矩阵A。(1) 把公汽线路信息以及地铁线路信息分别导入到Excel 表格中(2) 将公汽数据中的上下行相同、上下行不同、环行的线路分别找出并归类。(3) 将上下行相同的上行序列倒序后作为下行序列。则每条线路对应两个行向量。(4) 环行线路若有 n 个站点，则依次以每个站点为起点和终点建立起n 条首位相同的线路序列。(5)

12、 在第 k 条线路对应的所有序列前加上数字 k 作为标记列，其意义为第 k 条路线。(6) 运用 Excel 的查找替换功能将公汽站点编号“S”和地铁站点编号“ D”分别名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 38 页 - - - - - - - - - 用 0 和 111代替。目的是为了在汽车站和地铁站区别的条件下让matlab 可以识别和进行矩阵操作。(7) 将所有的序列整合到同一个excel 表中，建立交线路矩阵A， 每一行储存一条线路站点信息，没有信息的点

13、用“0”填充。公交线路矩阵 A 11121312122232123.ddnnnndvvvvvvvvAvvvv建立交线路矩阵 A 后，我们可以把矩阵 A 导入 MATLAB 中，运用改进广度搜索算法求解最佳路径。5 模型的准备5.1 乘客心理调查北京公交车线路达800 条以上，每一个公交站点可能有多条线路贯穿，通往不同的起点或终点， 同样，一个目的地也可由多条线路到达，错综复杂的公交车路线犹如网状般将各站点联系起来，将城市的行人们带到其各自的目的地。我们通过互联网查阅相关资料发现，影响乘客公交线路的选择， 主要有以下几个因素：换乘次数，行程时间，所需费用，途经的总站数等。其中有 18.6%的乘客

14、出行时，首先考虑的是乘车费用，30.4%的乘客首先考虑的是行程时间， 42%的乘客首先考虑的是换乘次数。图 1：乘客出行调查图0.00%5.00%10.00%15.00%20.00%25.00%30.00%35.00%40.00%45.00%所需费用行程时间换乘次数其它名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 38 页 - - - - - - - - - 就乘客本身而言，公交乘客出行更多考虑的是出行的方便性和舒适性，下面就影响公交乘客出行的各因素进行具体分析，不妨将

15、以上影响因素作如下归纳解释：(1)换乘次数：出行者完成一次从出发点到终点出行过程中所换车的次数。(2)行程时间：出行者在一次乘公交出行过程中所用的总时间。(3)所需费用：出行者在完成一次由起点到达目的地过程中所花的车费。(4)途径的总站数：出行者完成一次出发点到终点过程中所经过的车站总数5.2 影响选择因素分析“换乘次数”和“行程时间”是影响出行者的两个独立的因素，经研究表明多数的公交乘客希望换乘次数最少， 况且公交公司对公交线路的设计也是尽量减少乘客的平均换乘次数； 而且公交乘客出行时还受到行李、地理位置等客观因素的影响，这样更不希望有较多的换乘。其次对于看奥运非常心切的出行者来讲，出行耗时

16、对他们也是比较关键的。 在此当给出供乘客选择的公交路线也应当尽可能的满足公交乘客的需求。当然，在此基础上我们还要考虑乘车费用。综上所述，可以以换乘次数最少为第一目标， 再选择易于量化的 “出行时间”和“所需费用”作为第二位的优化目标。由此，我们认为，乘客在选择路线时，可以根据自己的不同需求，对线路进行选择。5.3 最优乘车方案算法分析在站点上放置一个便于乘客查询到达目的地的理想乘车方案的计算机系统，必须让计算机收集到本站到其他任意一站的路径与换乘信息，因此单独设计这样的算法是相当困难的， 而且算法的精度要求也比较高。 对本文附件中的公交系统中所列的 3957 个公汽站点和 39 个地铁站点来说

17、，直接要得到所有任意两站点之间的最优公交路径的计算量是相当大的。当面对这样一个密集的交通网络来说，对路线的选择主要是将面临一个P类问题，根据P类问题的处理特点， 可以用某种主次改进的方法来求解。 由于每次改进中的计算量都是多项式界的，改进的次数也是多项式界的。 目前已找到具有这种特性的算法， 如椭球算法，卡马卡算法，但都相当复杂。因此要满足出行者的路线需求，则有必要对目标进行归类筛选，以降低不必要的选择、 计算与搜索。 不妨采用改进的广度优先搜索算法，基于改进次数为多项式界的算法理论， 本文选择从某次乘公交的起点和终点的两端进行同时搜索，在满足换乘次数最少的条件下寻找不同线路中的共同站点或不同

18、站点之间的相同线路，并计算其总路线的中的乘车时间和站点数。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 38 页 - - - - - - - - - 6 站点线路交替序列模型的建立6.1 模型的建立本文所要解决的根本问题是设计一个公交线路选择的自助查询的计算机系统，并从实际情况出发考虑， 以满足查询者的各种不同需求。设计该系统的核心是线路选择的模型与算法。我们建立交替序列模型寻找最优线路。6.1.1 模型的预处理出行者所选择出行的起始站为v0，终到站为 vd，从 v0到

19、 vd的所有路径的集合也为 TR，其中第 i 条路径为 TRi，所乘坐的第k节公交工具为pik。进一步分析和考虑出行者乘公交的具体情况，一个出行者的出行可简单描述为如下路径图 2：出行者选乘公交路径规律分析示意图从图中内容也可以反应， 出行者出行乘公交的路径可看着是站点、车次、站点、车次的交替进行，直至到达终到站。为区别前后的车次或站点，使得前后排列的站点与车次都有一定的顺序，由于出行者不能在同一站点上出现两次，即vik各不相同，特别地令00vvi，dNivvi1；6.1.2 交替序列的表示分析可知，选择线路上的站点线路交替序列iTR 为：diiiiivvpvpvTR,22110其中站点线路交

20、替序列iTR表示从起始点0v 选择线路11iivp 到达，换乘2ip到达2iv ，, ，最终到达dv 的第i种路径。起始站0v 到达终到站dv 的公交线路选择集TR，即：diiiiiivvpvpvTRTRTR,|22110起始站中转站 1 乘第 1 节公交离开公交结束选乘初次车出发,中转站 2 中转站 3 选择路线乘第 2 节公交第 1 次换乘终到站乘第3 节公交第2 次换乘中转站 Ni乘第 Ni+1 节公交第 Ni次换乘名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 3

21、8 页 - - - - - - - - - 对于乘客而言，我们只要知道他的出行起始站v0和终到站 vd之后，便可以在路径集 TR 中找到他最需要的出行路线。 本模型对路线的选择范围确定了界限，这样也明确了寻求最优线路的讨论范围，即搜索的路径(公交线路pik)和节点 (公交站点 vik)都是相互关联的。7 问题一的解答7.1 多目标最优化分层求解模型的建立7.1.1 确定目标函数本文所要解决的根本问题最佳乘车路线的设计问题。建立以换乘次数Ni为第一目标，再选择易于量化的 “出行时间 ti”作为第二目标的多目标最优化模型。minminminiiiNtQ为了便于求解我们定义目标函数U 表示以 Ni为

22、第一目标， ti作为第二目标Qi作为第三目标：min(, ,)iiiiTRU N t Q7.1.2 确定约束条件1.目标函数 U 最小时，换乘次数和乘车时间也要求最小，因此U 与 Ni及 ti是正相关的。0,0 .iiUUtt2. 由于在优先选择权上，按相应条件，在目标函数),(iitNU中，iN 应优于it ，iiUUNt7.1.3 相关变量的确定求解 Ni 取最小值时，再进行其它变量的确定与计算，才能选择到相应的目标。即需要在可行域diiiiiivvpvpvTRTRTR,|22110中进行优先性的条件搜索。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - -

23、 - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 38 页 - - - - - - - - - I 换乘次数设iR 表示有序集diiiiivvpvpvTR,22110中的元素的个数，为便于区别，现标记iiiTRCardR，换乘次数可表示为121iiRNII 所通过的总站数设非环行线路ikp 上的两个站点1kiv和kiv在沿着公交工具行进方向上的站数按照正整数从小到大的排序分别为),(1kiikvpk和),(kiikvpk，其中仍然记00vvi；dNivvi1，于是由数据处理中的相关统计结果可知：),(max(),(),(),(min(1kiikkiikki

24、ikkiikvpkvpkvpkvpk当线路ikp 为环行线路时，设该环行路线上的总站数为ikK，1 iv 为ikp 上的任意一站，0iv ，2iv 分别为公交工具在沿着ikp 行进方向上的最后一站和前一站，于是可标记ikiikKvpk),(0；1),(1 iikvpk；2),(2iikvpk；, ；jvpkijik),(；,所以出行者乘坐ikp 线路的公交所经过的站点数目为：.),(),(),(),(),(111为环行线路为非环行线路；ikikkiikkiikikkiikkiikikkiikpKvpkvpkpvpkvpkvvp所以，出行者途经的总站数为共条行车路线上车站数的总和，即111),(

25、iNkkikiikivvpSIII 乘客所用时间设出行者选择第 i 条线路从起始站 v0到达终到站 vd所耗的平均总时间为ti，换乘一次所耗的平均时间为ot =5 分钟，相邻两站点之间乘车的平均时间为*ot=3分钟。则有00(1)iiitt NtSIV 乘车总费用公汽线路上的单一制票价为1 元， 分段计价的票价标准为出行者通过本线路020个站： 1 元；2140站：2 元；40 站以上： 3 元。公汽的单一票价为Qi0，出行者在所选择的出行线路中所应支付的车旅费为Qi，所乘同一公交线路上的名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - -

26、- - 名师精心整理 - - - - - - - 第 9 页，共 38 页 - - - - - - - - - 最高收费为1iQ ，分段计价时加价的最少站数为0L ，于是有：iNkikikiikikiiiQLvvppLNQQ1101*01),(min)() 1(，其中A 表示取不超过A的最大整数，参数：10iQ（元） ，31iQ（元） ，200L. .10)(*为分段记价线路线路为单一票制线路；线路ikikikpppL综上所述，对问题一建立多目标优化分层求解模型min(, ,)iiiiTRU N t Q0112211,1*001*0110|,;11;2.().(1)(,)() min1iiii

27、iiiidiiiiiNiiki kikkiiiNiki kikiiiikikTRTR TRvpvpvvRCard TRRNstSpvvtt NtSpvvQQNL pQL，7.2 模型的求解7.2.1 线路的抽象处理从 A 站到 B 站的行车路线时，首先考虑是否有经过A 站直接到达 B 站。如果存在不只一条的直达线路， 在考虑所走路线的远近， 选择距离最近的乘车方案；如果没有直达车，就会考虑换一次车的方案。即经过A 站的车与经过 B 站的车是否有公共站点 C。如果有，则可在公共站点 C 处转车到达站点 B。如果没有换一次车的方案，则又要考虑乘坐经过A 点的车到某一站 C 下车，经过 C 站点的车

28、与经过 B 站点的车是否有公共站点D，如果有，就到公共站点D 转车，两次转车可到达站点 B；如果没有，则需要转乘三次或三次以上才可到达目的地。在上述情况中如果存在不止一种的选择方案，则在考虑乘车距离， 选择路程最短的乘车方案。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 38 页 - - - - - - - - - 运用 matlab求解如下（具体程序见附录一）表 1 问题一的结果路径换乘次数时间(分)费用(元)总站数L436L167S3359S1784S18281

29、95333L084L189460S1557S1919S3186S0481297333L013L485S0971S2184S04171122442L159L474S0008S0400S0073177227L308L156L417S0148S0036S2210S0485297333L454L209S0087S3496S36761592217.3 结果分析我们以换乘次数为第一目标， 假设乘客可以接受的换乘次数不超过2 次，将问题简化。 只考虑乘公汽， 所求的 6 条路径没有直达的其中第1，3,4,6 条要换乘一次；第 2,5 条路径要换乘 2 次。8 问题二的解答8.1 多目标最优化分层求解模型的建

30、立8.1.1 确定目标函数问题二在问题一的基础上考虑可以搭乘地铁。乘客的选择更加灵活。 其主要变化的因素有： 1 地铁票价稍高但是固定且在地铁航线之间换乘而不需另外支付交通费用，相邻站点之间的距离较公汽站点大，而运行时间却相对减少x(d)换乘多次车的情况图 2 公交线路换乘方案示意图(a)直达的情况(b)换乘一次车的情况A B C B A (c)换乘两次车的的情况A B C D A B C D 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 38 页 - - - - -

31、 - - - - 2 地铁与公汽之间进行换乘时，由于地铁站点不可能与公汽站点都建在同一个地方，因此从地铁站到公汽站的步行时间相对较多，而且位于与地铁换乘的公汽站点还可以通过本地铁站进行免费换乘到下一个公汽站。min(, ,)iiiiTRU N t Q8.1.2 确定约束条件0,0 ,iiiiUUUUttNt8.1.3 变量的确定当并入地铁公汽的交通网络时， 增加地铁站与其周围的公汽站之间的步行线连接转换后，本问题可转化为问题一中的模型求解， 同样有出行者通过公汽换乘、地铁换乘、公汽与地铁之间的换乘后从起始站v0到达终到站 vd的可行路径集为：diiiiiivvpvpvTRTRTR,|22110

32、其中 pik的属性将被扩大，它将表示公汽、地铁、步行这三类交通路线中的某一类交通路线；而ikv 的含义与问题一中ikv 的含义相同，仍表示公交站点或地铁站点。I 换乘次数与途经总站数同样设路径iTR 的换乘次数为,iN途经总站数为iS ，同问题一对iN ，iS 仍然有：1111,1,(,)2iNiiiiiiki ki kikRRCard TRNSpvvII 出行者乘公交所用时间在地铁公汽的公交系统中， 出行者将会表现在公汽运行耗时，地铁运行耗时，地铁换乘公汽耗时，公汽换乘地铁耗时，公汽换乘公汽耗时，地铁换乘地铁耗时，公汽通过指定地地铁换乘公汽耗时。为简化变量， 考虑出行者的异站步行也纳入到公交

33、线的行列中， 则所消耗的时间可归结为： 交通工具运行耗时， 交通线路换乘耗时两类。设出行者从起始站0v 到达终到站dv 所用的总时间为it ，从公交站点1kiv乘kip 线路公交工具到达公交站点kiv所消耗的时间（包括相邻两站点间的停站时间）为：),(1ikkivvt，由kip 线路的公交工具换乘到1kip线路的公交工具所消耗的名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 38 页 - - - - - - - - - 时间为：),(1kikippt，由基本参数设定的信

34、息可得：111111),(),(),(iiNkNkkikiikkiikkiikipptvvtvvpt其中111113;2.5;(,)7;6;0.i kiki kiki kiki kiki kikvS vSvD vDt vvvD vSvS vD；其它.0;5;4),(111其它；LpLpTpTppptikkiikkiikkiIV 乘车总费用在问题二的讨论中， 乘车的总体花费会受到出行者换乘次数，乘坐分段计价车时通过的站数的影响， 而在本问题中， 有假设知道同一地铁站对应的任意两个公汽站可以通过地铁站换乘而不需要支付地铁费，同样根据问题一中， 对乘公交所支付费用的讨论思想，仍然令乘坐公汽的单一票价

35、为Qi0，出行者在所选择的出行线路中所应支付的车旅费为Qi，所乘同一公交线路上的最高收费（含地铁收费）为 Qil，分段计价时加价的最少站数为L0，于是有：iiNkikikiikikNkikikiiQLvvppLppNQQ1101*1101),(min)(,，）（其中A 表示取不超过 A 的最大整数；参数：01iQ（元） ，13iQ（元） ，020L.10)(*为分段记价的公交线路线路线路；为单一票制线路或地铁线路ikikikpppL其它0,3,1),(111TpTpLpLpppNikikiikikik综上所述，对问题二建立多目标最优化分层求解模型名师资料总结 - - -精品资料欢迎下载 - -

36、 - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 38 页 - - - - - - - - - min(, ,)iiiiTRU N t Q0112211,111,1,1111*0110|,;11;2.().()()();(,)(,)() miniiiiiiiiiidiiiiiNiiki kikkNNiiki kiki kiki kikkkNiki kikiiiki kikkTRTR TRvpvpvvRCard TRRNstSpvvtpvvt vvt p vpvvQQN ppLpL11010120;3;1.iNikiiQ

37、LQQ，8.2 模型的求解8.2.1 设计算法1 输入乘车的起始站点A及目的站点B；2 求经过站点 A 的所有线路集 S(I)和经过站点 B 的所有线路集 T(J)；3 判断 S(I)=T(J)如果有，则找到了从站点A到站点B的直达线路 S(I)即 T(J)，输出结果，结束运算，如果没有则进行下一步。4 求线路 S(I)上的站点 E(I,U)以及线路 T(J)上的站点 F(J,V)；5 判断是否存在相同站点， 即),(UIE=),(VJF，或者存在紧邻站点， 即满足wFEt),(；如果满足),(UIE=),(VJF，则线路)(IS，)(JT即为一次转车的线路，),(UIE即为转车站点且换车时不

38、用更换站点；如果满足),(),(UJFUIE但满足wFEt),(，则线路)(IS，)(JT即为一次专车线路，),(UIE即为转车站点但换车时要步行到紧邻站点),(VJF。如果没有，再执行下面步骤。6 求经过),(UIE的线路集)(KR，经过),(VJF的线路集)(OY；7 判断)(KR=)(OY吗？如果有， 则线路)(IS，)(KR，)(JT为两次换车的线路，换车站点为),(UIE和),(VJF，输出结果，结束运算；如果没有则执行下面步骤。8 求线路)(KR上的站点),(WKG和线路)(OY上的站点),(XOL；名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - -

39、- - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 38 页 - - - - - - - - - 9 判断是否存在相同站点，即),(WKG=),(XOL，或者存在相邻站点，即满足wLGt),(；如果满足),(WKG=),(XOL，则线路)(IS，)(KR，)(OY，)(JT即为三次转车的线路，),(UIE，),(WKG，),(VJF即为转车站点，且换车时不用更换站点；如果满足),(),(XOLWKG但满足wLGt),(， 则在站点),(WKG专车时要步行到紧邻站点),(XOL。算法流程图开始获取起点和终点( )( )S IT J( ,)(,)(,)E I

40、 UF J Vor d E Fw()()R KY O(,)(,)(, )G K WL O Xor d G Lw真假假假输出)(IS,)(JT, ),(UIE),(VJF输出)(IS,)(KR, )(JT),(UIE),(VJF输出)(IS,)(KR,)(OY, )(JT,),(UIE,),(WKG, ),(XOL,),(VJF选择换乘次数最少且花费时间最短的乘车方案最为最终结果真真真结束名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 38 页 - - - - - - -

41、 - - 运用 matlab 求解结果如下（具体程序见附录二）表 2 问题二的结果路径换乘次数时间(分)费用(元)L436L167S3359S1784S18281 953L084L189460S1557S1919S3186S04812973L013L485S0971S2184S041711224L159L474S0008S0400S00731772L308L156L417S0148S0036S2210S04852973T02S0087D27D36S3676034.538.3 结果分析对比问题一与问题二的求解结果可知，前面 5 条路线求解的最佳路径是一样的，原因在于在换乘次数和行程时间差不多的情

42、况下，地铁较贵为3 元。所以，这种情况下， 尽量不乘坐地铁。 比较第 6 条路径，我们发现乘坐地铁使得行程时间大大缩短， 并且由于地铁站和起始站在一起，乘坐地铁不用换乘。 故考虑地铁后，第 6 条路径大大优化。9 问题三的解答9.1 多目标最优化分层求解模型的建立9.1.1 确定目标函数考虑到出行者在步行时， 所经过的任意两站点之间的路径都应该是至少有一条公汽线路上的公交工具通过， 由问题三的条件可知， 步行时所经过的两站点之间的步行时间是一个已知值。 据实际情况， 假设步行者步行在相邻两公汽站所用时间平均是公汽经过这两站（包括停站时间）所用时间的k倍，则由基本参数设定可知，步行者通过这样两站

43、点所用的平均时间为k3分钟，于是将行人步行所名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 38 页 - - - - - - - - - 经过的线路也纳入到公交线路中，其特点是费时费力但选择灵活。min(, ,)iiiiTRU N t Q9.1.2 确定约束条件0 ,0 ,iiiiUUUUttNt9.1.3 确定变量设出行者以步行、乘公交、换乘等任意的出行方式从初始站V0到达终到站Vd的可行路径集为：diiiiiivvpvpvTRTRTR,|22110，其中，上式中的i

44、kp 、ikv 都与问题二中ikp 、ikv 的含义分别相同，I 换乘次数、途经总站数设该路径iTR 的换乘次数为,iN途经总站数为iS ，仍然有121iiRN111),(iNkkikiikivvpSII 出行者乘公交所用时间在步行地铁公汽的公交系统中，出行者将会出现公汽运行耗时， 地铁运行耗时，地铁换乘公汽耗时，公汽换乘地铁耗时，公汽换乘公汽耗时，地铁换乘地铁耗时， 公汽通过指定地地铁换乘公汽耗时，公交站点之间的步行耗时。 同样考虑出行者的异站步行纳入到公交线的行列中来简化变量，则所耗时间仍然可分为：交通工具运行耗时（包括步行耗时） ，交通线路换乘耗时两类。同样设出行者从起始站0v 到达终到

45、站dv 所用的总时间为it ， 从公交站点1kiv乘kip线路公交工具到达公交站点kiv所消耗的时间（包括相邻两站点间的停站时间）为：),(1ikkivvt，由kip 线路的公交工具换乘到1kip线路的公交工具所消耗的时间为：),(1kikippt，则由基本参数设定的信息可得：名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 38 页 - - - - - - - - - 111111),(),(),(iiNkNkkikiikkiikkiikipptvvtvvpt其中.0;

46、,3,6,7,5 .2,3),(1111111其它；TpLpSvSvkDvSvSvDvDvDvSvSvvvtikkiikkiikkiikkiikkiikkiikkik为公汽行进时是出行者步行时的平均倍率。.0;5;4),(111其它；LpLpTpTppptikkiikkiikkiIII 乘车总费用在问题三的讨论中， 乘车的总体花费会受到出行者换乘次数，乘坐分段计价车时通过的站数的影响， 而在本问题中， 有假设知道同一地铁站对应的任意两个公汽站可以通过地铁站换乘而不需要支付地铁费，步行的出行者在步行的公交站点线路上也不需要支付公交费用， 同样由问题一中对乘公交所支付的费用的讨论思想，同样令乘坐公

47、汽的单一票价为0iQ ，出行者在所选择的出行线路中所应支付的车旅费为iQ ，所乘同一公交线路上的最高收费（含地铁收费）为1iQ ，分段计价时加价的最少站数为0L ，于是有：iiNkikikiikikNkikikiiQLvvppLppNQQ1101*1101),(min)(,，）（其中 A 表示取不超过A的最大整数，在本题中200L；31iQ；10iQ.10)(*为分段记价的公交线路线路线路；为单一票制线路或地铁线路ikikikpppL其它0,3,1),(111TpTpLpLpppNikikiikikik综上所述，对问题三建立多目标最优化分层求解模型min(, ,)iiiiTRU N t Q名师

48、资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 38 页 - - - - - - - - - 0112211,111,1,1111*011|,;11;2.().()()();(,)(,)() miniiiiiiiiiidiiiiiNiiki kikkNNiiki kiki kiki kikkkNiki kikiiiki kikkTRTRTRvpvpvvRCardTRRNstSpvvtpvvt vvt pvpvvQQN ppLpL110010120;3;1.iNikiiQLQ

49、Q，9.2 模型的求解由于成年人的平均行走速度为1.5m/s ，相邻车站的距离大约为1000m ，我们假设相邻车站距离，人步行所要的时间约为11min 运用 matlab 求解如下（具体程序见附录三）33591828SS先在站点 S3359乘坐 436 路车到 S1784,然后步行到 S1828； 一共费时 104 分钟,总花费为： 3 元971485SS先在站点 S971乘坐 13 路车到 S2184,然后步行到 S485；一共费时 131 分钟, 总花费为： 4 元873676SS先在站点 S87乘坐 454 路车到 S3496,然后步行到 S3676 ；一共费时 68 分钟, 总花费为：

50、 2 元873SS先在站点 S8乘坐 159 路车到 S400,然后步行到 S73；一共费时 86 分钟, 总花费为：2 元9.3 结果分析名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 38 页 - - - - - - - - - 对比分析问题二和问题三的求解结果，考虑当两站间相隔站数不多时， 可以步行这一情况后，选择路径，换乘次数和费用减少，所消耗的时间增加。比如33591828SS，考虑这一情况后， 时间增加了 9min，不用换乘了。步行是一种耗时省钱，选择灵活的