乘公交看奥运大学生数学模型

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

2、）：重庆人学参赛队员（打印并签名）：1.2.3.指导教师或指导教师组负责人（打印并签名）：fi期： 年 月 fi赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）:赛区评阅记录（可供赛区评阅时使用）:评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）:全国评阅编号（由全国组委会评阅前进行编号）:本文建立了乘公交看奥运最佳线路的选择模型。在仅就满足公众对乘车耗时最少和花费最低的两种需求，对三个情形：仅考虑公汽 的单一线路，同时考虑公汽与地铁两种线路，兼顾步行公汽地铁 三种线路，分别建立了任意两站点之间线路选择问题的数学模型，依 托matlab软

3、件编程给出相应的的算法。并利用所建立的模型与算法, 求出给定的6对起始站一终到站之间的最佳路线，并做出了清晰的评 价说明。最后，本文还对模型作出了进一步分析、评价和推广。针对问题一中仅考虑乘坐公汽，我们在对问题分析的基础上，运用matlab软件编程并搜索，就乘客的耗时最少需求，建立了模型i （耗 时最少的线路选择模型），给出了相应的算法步骤及程序框图，并针 对六组得到如下结果：s3359s1828,换乘一次有两条线路，都 经过了 32个站点，所花费的时间均为101分钟；s1557s0481：至少需换乘两次，线路有两条，也经过32个站点，耗时101分钟;s0971s0485：换乘一次，通过41站

4、，耗时128分钟；s0008s0073：换乘一次，有14种不同线路，经过26站，耗时83分钟；s0148s0485：至少需换乘两次，线路有6条，且都经过32个站点，耗时101分钟；s0087ts3676：换乘一次，经过20站,耗时65分钟。同样，就乘客的费用最低需求，建立了模型ii （费用最低的线路选择 模型），给出了相应的算法步骤，得到结果详见正文第12页至第13 页。针对问题二，同时考虑公汽与地铁两种线路，我们建立了模型iii （分步规划模型），通过设计算法步骤,再运用matlab编程可求出以上完成，我们可求出以上六组点的结果，详见正文第15页至第18页。针对问题三，兼顾步行公汽地铁三种线

5、路，我们建立了模型iv （线路 综合评价模型），第三题是在前面问题的基础上，加入了步行这一较 为自主化的“交通工具”，使得原本的选择最优线路模型不再适用，于 是我们这里建立了一个线路综合评价模型，通过分类讨论的方式，提 供适合各种情况的线路选择方案,从而解决在三种交通工具并行时的 路线选择问题。本文最后还对这一自主查询系统进行了推广，将自主查询系统推广到 手机彩信或短信，给出了系统结构设计和网络拓扑结构图；同时，将 这一自主查询系统应用到旅游线路选择上，并绘制了旅游线路选择系统结构图。关键词：线路选择；换乘；分步规划;自主查询系统；matlab§1、问题的重述一、问题背景1、看奥运要

6、出行 2008年8月8日至8月24日，我国人民翘首企盼的第29届奥运会将在北京举行，届时将会有大量观众从不同地点到达比赛现场去观看 奥运盛况，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。2、乘公交需择线这些年来，随着科技进步、政府投资及市政部门对城市道路的不断完 善，我国城市的公交系统有了很大发展，作为我国首都北京市, 它的公交线路已多达800条以上，这使得广大市民的出行更加通畅、 便利。但是，同时也因线路的众多，为广大市民的出行带来一个新的 问题，乘车从一个地方到另一个地方，如果都在同一条公交线路上, 市民则不存在选择；如果需要换乘，特别是二次以上的换乘，市民则 面临

7、着多种选择，可分别从选最短线路、花最少时间、用最少换乘、 节省票价等各个方面进行决策，以实现出行任务的完成。3、做系统先建模针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自 主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模 型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。二、有关数据1、基本参数设定.-ail相邻公汽站平均行驶时间（包括停站时间）：3分钟;相邻地铁站平均行驶时间（包括停站时间）：2.5分钟;公汽换乘公汽平均耗时:5分钟（其中步行时间2分钟）;地铁换乘地铁平均耗时:4分钟（其中步行时间2分钟）;地铁换乘公汽平均耗时：7分钟（其中步行时间4分钟）

8、;公汽换乘地铁平均耗时：6分钟（其中步行时间4分钟）;公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分 段计价的票价为：020站：1元；2140站：2元；40站以上：3 元；地铁票价：3元（无论地铁线路间是否换乘）。注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。2、公交线路及相关信息（详见附件2中文本文档1、1.1、1.2及2、 21、2.2 ）o三、问题提出1、问题一：仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与 算法，求出以下6对起始站-终到站之间的最佳路线（要有清晰的评 价说明）。 s3359s1828；

9、s1557s0481；s0971s0485； s0008s0073；s0148s0485；s0087s3676。2、问题二：同时考虑公汽与地铁线路，解决问题一中两个问题。3、问题三：假设又知道所有站点之间的步行时间，请你给出任意两 站点之间线路选择问题的数学模型。§2、问题的分析一.问题的总体分析与相关量的明确1、问题的总体分析乘公交看奥运公交线路选择问题涉及到数百条公汽线路与两条地铁 公交线路、数千个公汽站点与几十个地铁站点、三类不同乘车票价信 息、上行下行单行环形四种车行方向等多个因素，且出行查询者的通 常需求分别有选最短线路、花最少时间、用最少换乘以及用最低票价, 当然这些需求

10、在小城市道路比较单一时可能是相一致的，但对拥有众 多车辆及线路且道路如网的首都北京而言，这些需求则不尽然。故问 题这是一类多因素多数据计算机查询信息处理及多目标决策问题，核 心是算法。2、几个重要的量为了便于解决问题，下面我们先明确问题涉及到的几个重要相关量。 运用相关的统计方法，从竞赛b题所给的压缩文本文档中，我们不 难得到以下几个量的准确信息: 公交线路：520条公汽线路，编号：l001l520；两条地铁线路t1 与t2。公交站点：3957个公汽站点，编号：s0001s3957；39个地铁站点，编号：d01d39。公汽线路与站点:文本文档1.1具体地给出了 520条公汽线路编号, 票价信息

11、，车行线信息（详见2007年竞赛b题压缩文本文档l.l）o 地铁线路与站点：文本文档1.2具体地给出了北京地铁线路t1与t2,我们通过上网搜索1很易获取相关的地铁图片（图1）与北京地铁tl、t2线路图（图2）。结合文档12所给北京地铁线路t1与t2的信息，我们不难发现，地铁t1的23个站与地铁t2的16个站 相吻合，且图2中的复兴门为d12与建国门为d18是可以换乘的两 个站。二、对具体问题的分析1、对问题一的分析问题：仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的般数学模型与算法。并根据附录数据，利用所给出的模型与算法, 求出6对起始站t终到站之间的最佳路线，且要有清晰的评价说明。分析

12、：要寻找两站之间的最佳公交线路，就是要满足不同乘客乘坐 公交的一定要求，比如选最短线路、花最少时间、用最少换乘或花最 低票价等等。为了简化对问题的解决，我们不妨假定求最佳路线，仅 在乘车耗时最少、花费最低两种条件下确定最佳公交线路。对于在同一线路上的任意两个站点，若通过两个站点的线路仅一条（如图3左），显然这一条也就是最佳路线；若通过两个站点的线路 有两条及两条以上的线路，按基本参数设定知，最佳路线是中间站 点数最少的线路，如图3右图中蓝色的直线即最佳路线。图3两站间通过的线路仅一条与两站间通过的线路有两条线路图 对于不在任何一条公交线路上的两个站点，即没有直达的公交线路, 则要考虑换乘，若通

13、过起始站的所有线路和通过终到站的所有线路有 且仅有一个公共站点，如图4左可知，则相交站点的线路acb即为 最佳路线;若通过起始站的所有线路和通过终到站的所有线路多于 个公共站点，如图4右c站和d站均为换乘站点，显然同样换乘次 数时换乘线路所经过的站数较少的acb线要优于adb,从而acb线为最佳路线。同样换乘次数时多于两条换乘线的，则换乘线路所经 过站数最少的为最佳路线。图4两站间换乘一次线路仅有一条与换乘一次线路有两条线以上的 线路图如果对进行一次换乘不能完成出行任务的，我们要进行两次换行计划。类似上述的分析，我们可以得到两次的换乘情形下的最佳路线。显然这要比前两类情形复杂得多,但运用计算机

14、进行编程一般是可以 实现的。如果对进行两次换乘仍不能完成出行任务的，我们要进行三次或三次 以上的换乘。但考虑到换乘三次及三次以上研究的技术处理和实际操 作太复杂且实际意义不大，故在最初建模时可不予考虑，在对建模进 行改进时，可酌情考虑。当然，对于基于最低价格的最佳模型求解,除了要考虑以上的分析外, 我们还要考虑各类票价信息。首先我们要搜索出所有需要分段计价的 公汽线路，然后根据题目中的分段计价要求建立一个价格矩阵，再由 前述换乘法求出的结果进行价格计算，看是否满足价格最小的条件, 对不满足的利用排序求出最小价格，并得到相对应的线路信息。2、对问题二的分析问题：同时考虑公汽与地铁线路时，解决问题

15、一的建模、算法和6 条最佳路线。分析：问题二是在问题一只有公共汽车单一交通工具的基础上，通 过引入地铁这一交通工具，使得转乘不仅仅是公汽转公汽，还包括公 汽转地铁，地铁转地铁，地铁转公汽，使得转乘问题复杂化。为了得 到用时最少的线路，我们可考虑建立了分步规划模型进行求解，将总 用时最少这一规划问题，分成在每次搭乘都用时最少的分布规划问 题。从而在综合考虑公汽与地铁的情况下确定了最佳线路。3、对问题三的分析问题：假设又知道所有站点之间的步行时间，请你给出任意两站点 之间线路选择问题的数学模型。分析：第三题是在前面两个问题的基础上，加入了步行这一较为自 主化的“交通工具”，使得原本的选择最优线路模

16、型不再使用，于是我 们这里建立了一个线路综合评价模型，通过分类讨论的方式，提供适 合各种情况的线路选择方案，从而解决在三种交通工具并行时的路线 选择问题。§3.模型的假设1、为便于研究问题，规定每条线路起点站的位标为1,从起点站至终点站的其余各站的位标依次为2、32、由于基本参数已设定，不再考虑发车频率和乘客到达时刻及等待时间;3、由于公交线路的交错复杂，不考虑公交线路的编排次序和公交站点的编排次序；4、交通状况良好，无交通阻塞及其它影响交通运营的异常情况发生;5、作为交通系统比较发达和完善的首都北京，联通任意两站间的线路最多换乘两次，换乘三次及三次以上研究太复杂且实际意义不大, 故

17、不予考虑。§4、名词解释与符号说明一、名词解释1、换乘:从一辆车下来转乘另一辆车的过程;2、位标：为建模而自行定义的变量，规定一条线路从始发站起各站的位标依次为1、 2、 3、二、符号说明1. :所有公汽线路数据处理后得到的;2. :经过起始站s1的所有线路站台矩阵;3. :经过终到站s2的所有线路站台矩阵;4.,:公汽的起始站点;5. :公汽的终到站点；6. :只考虑公汽情况下起始站与终到站的公共站点；7. :公共站点与起始站在同一线路上的公共站点的列标；& :公共站点与终到站在同一线路的公共站点的列标；9. :与公共站点在同一条线路上的起始站的列标；10. :与公共站点在

18、同一条线路上的终到站的列标；12.11:只考虑公汽情况下从起始站到公共站点的站点数量，即;:只考虑公汽情况下从公共站点与终到站的站点数量，即；12.:只考虑公汽情况下从起始站到终到站的总的站点数量，即；13:只考虑公汽情况下耗费时间最少情况下得到的最佳路线的中转14.站;:只考虑公汽情况下乘车费用最低情况下得到的最佳路线的中转15.站;:为使得以一个向量的形式输出，同时为了循环的方便而引进的变量，初值为1;16.:乘车所耗费的总时间，包括等待和转乘的时间;17.:所有分段计价线路数据组成的矩阵;18.:只考虑公汽情况下从起始站到中转站的票价;19.:只考虑公汽情况下从中转站到终到站的票价;20

19、.:耗时最少的最佳路线的乘车费用，计算得到价格并计算出最低价格;21:乘车费用最低的最佳路线的最低乘车费用;22.:根据分段计价标准的不同得到的的分段计价价格向量，由数字1,2,3组成；23dij：地铁相邻的公汽站台矩阵；24. p：矩阵dij与矩阵b的交；25. q：矩阵dij与矩阵c的交；26. :矩阵b与矩阵dij的公共元素；27:矩阵c与矩阵dij的公共元素；28.ti：乘坐交通工具时经历的时间； 2910：交通工具换乘用时平均耗时;30. ni：乘坐交通工具时经过的有效站台数;31. :任意两站点i、j之间的步行时间。§5.模型的建立与求解从所要解决的问题和对问题所做的假设

20、出发，我们对问题一分别建立 了模型i （耗时最少的线路选择模型）和模型ii （费用最低的线路选 择模型），我们对问题二建立了模型iu （分步规划模型），我们对问题 三建立了模型iv （线路综合评价模型）。一、问题一的分析与求解1、问题一的分析要寻找两站之间的最佳公交线路,就是要满足各类乘客乘坐公交的不同要求，为了简化对问题解决，我们大体上认为最佳路线即是乘车耗时最少、乘车费用最:少两种情况来对问题一进行求解。为了实现这一目标，我们对题目给出的大量数据进行了相应的处理，发现对问题中 列出的六组站点，都无法根据现有的公交线路直达，于是就要考虑公 交车的换乘问题。在考虑到技术处理和实际操作的可行性，

21、我们不妨 假设最多换乘两次就可以到达任意站点，否则，乘客可以根据车行方向随机地选择车路，然后到一定车站后再行查询，或通过步行到能够附近站点。对于基于乘车费用最少的模型求解，我们首先搜索出所有需要分段计价的公汽线路,然后根据题目中的分段计价要求建立一个价格矩阵，首先对由模型i求出的结果进行价格计算，看是否满足价格最小的条件，对不满足的利用排序求出最小价格，并得到相对应的线路信息。2、建模的思想建立数据库 为了确定公汽线路的最佳路线选择，首先把附录2中的文本文档“11 公汽线路信息txt”进行处理，并转换到excel软件中，形成以第一列 线路为公汽线路编号，第二列为价格信息，第三列为车行性质，第四

22、 列为各线路上所有车站点的大型数据库（详见附录3）,以此为基础,f面进一步研究。搜索起始站和终到站所经过的线路 通过对数据库的搜索，查询起始站和终到站是否有相同的车经过，如 果有且仅有一条，即为最佳乘车线路；如果有且多于一条，则只要计 算从起始站到终到站的总站数，通过比较可以得到战数最少的公交线 路，推荐给乘客。我们可用vb语言编程建立计算机循环查询系统。运用此系统产生的对话框进行查询起始站和终到站是否有相同的车 经述 我们只要输入起始站的站名（比如s0001）,然后再输入终到 站的站名（比如s0158）,则在打开的excel文件前的对话框里产生一 串语句，比如有，则在回答“直达3且紧跟“直达

23、，啲后面给出了起始 站到终到站的站数，结束；如果没有，则回答“不能直达”，下面再转 入下一步研究。寻找一次换乘的线路 分别从数据库中搜索通过起始站的所有线路和通过终到站的所有线 路，并将线路放到一起进行比较，如果存在公共的交点，则说明进行一次换乘即可完成出行计划。如果一次换乘的线路为一条，则是最佳 乘车线路；如果一次换乘的线路多于一条，再通过计算通过的站点数 进行比较，从而可找出站点数最小的最佳乘车线路。如果不存在公共 的交点，则要进行两次或两次以上的换乘。寻找两次换乘的线路对上一步完成对数据库搜索后，若通过起始站的线路和通过终到站的线路不存在公共的站点，则对通过起始站线路的所有站点和对通过终

24、 到站线路的所有站点再进行第步的搜索，若存在存在公共的线路, 则说明进行二次换乘即可完成出行计划。否则，我们考虑作为交通系 统比较发达和完善的首都北京，联通任意两站间的线路最多换乘两 次，换乘三次及三次以上研究太复杂且意义不大，故不予考虑。3、模型i耗时最少的线路选择模型模型的准备 在寻找最佳线路之前，我们要给公汽线路信息给出的大量数据进行处 理，即对上下行站点完全相同的数据补出它的下行数据；同时为处理 简便起见，对环行线路我们以相同的线路写出它的下行路线，并对所 有空白数据均补“0”。经过处理，得到一个1040行86列的的大矩阵a1040x86o下面我们以站点s3359s1828为例来说明公

25、汽站点的最佳路线选择问题，其具体处理步骤如下： 查找通过起始站与终到站的线路数利用数据库，我们运用软件|1编程，可查找出通过起始站s3359和通过终到站s1828的线路数和具体线路数。a. 通过起始站s3359的线路有26条（包括上、下行）：l015（上下行）、l123（上下行）、l132（上下行）.l291（上下行）、l324（上 下行）、l352（上下行）、l366（上下行）、l378（上下行）、l436（上下行）、 l469（±下行）、l473（上下行）、l474（上下行）、l484（上下行）。b. 通过终到站s1828的线路有10条（包括上、下行人l041（上下行）、l167

26、（上下行）、l182（上下行）、l217（上下行）、l238（上下行） 因此，可以得到一个以通过s3359的线路为行、每行所有站点为列的 的矩阵，同理得到一个以通过s1828的线路为行、每行所有站点为 列的的矩阵。 确定公共点的位标 为方便建模及其算法，下面定义一个新的名词。定义：规定一条公交线路从始发站起到终点站止各站的编号为位标,位标的大小依次为1、2、3、 no通过分析，我们了解到题目给出我们要求计算的起始站与终到站之间 没有直达的情况，于是我们要考虑换乘车的问题。首先从换乘一次车 的情况入手，我们利用的查找命令求出起始站s3359与终到站s1828 所有线路上的公共站点组成了集合，以及

27、这些公共站点与起始站s3359在同一线路的位标、这些公共站点与终到站s1828在同一线路的位标。 求换乘一次的总站点数 通过索引，我们可以求出与对应公共站点在同一条线路上的起始站的 位标 和这个公共站点在同一条线路上的终到站的位标，再利用公共 站点与起始站在同一线路中列标的差额以及公共站点与终到站在同 一线路中列标的差值就可以得到从起始站到公共站点的站点数量和 公共站点与终到站的站点数量，即，。考虑到公汽的行驶顺序一定、无法反向行驶等实际意义，我们只对的 数据进行计算，然后把得到的相加就可以得到总的站点数量，即。 确定目标函数 由于题目中给出了相邻公汽站平均行驶时间相等（均为3分钟）的设 定，

28、所以要达到耗时最少，我们规定使得所经过的站点最少即可，于 是我们利用上述步骤求得不同路线经过的最少站点数量就可以得到 耗时最少情况下的最佳线路，即可得到对应的最佳线路的中转站。此时得到的花费时间为，其中包括了公汽换乘公汽平均耗时5分钟。模型的建立 通过上述分析，我们得到如下的耗时最少的线路选择模型: 目标函数 约束条件 算法步骤 设起始站为，终到站为，具体的算法可按以下五个步骤来实现: 搜索求出与站点的数据在矩阵中的位置，并构造成矩阵; 在的情况下利用查找矩阵的公共元素; 搜索出中第 行的数据等于以及中第 行的数据等于的数据所 在列，只考虑和的情况； 在循环外层引进变量，并赋初值，计算从起始站

29、到终到站所经 过的所有站点数，其中，并得到与其对应的的值，将的数据以向 量的形式显示出来; 求出的最小值，并输出对应最小值所在的线路以及中转站。程序框图（如图5所示，程序见附录） 图5算法流程图 模型的结果 对问题一的第二小问，根据附录数据，利用上面的模型与算法，求出6对起始站-终到站之间的耗时最少的线路选择及耗时如下:s3359s1828的最佳路线：首先在l436路车下行路线从s3359s2026ts1132ts2266ts2263ts3917s2303ts2301ts3233ts0 618ts0616ts2112ts2110s2153ts2814ts2813ts3501ts351 5-&g

30、t;s3500ts0756->s0492s0903->s1768ts0955->s0480ts2703s2800s2192ts2191s1829s3649s1784,然后在 s1784 站 点换乘l217路车下行路线，下站即为s1828站；或者在s1784站点 转乘l167路下行路线，下站也是s1828站。因此，得到=31, 两种换乘方式都经过了 32个站点。所花费的时间为分钟。s1557s0481的最佳路线：线路1：首先在l363路车下行路线从s1557站开始乘车，途经s3158ts2628s3408ts2044s1985ts2563ts2682ts2735ts0029ts

31、0055ts0051ts1919,然后在s1919站点换乘l189路车下行路线，途经s1919s2840->s1402->s3186,之后在s3186站点换乘l460 路 车 下 行 路 线， 途 经s3186fs3544->s2116->s2119ts1788->s1789ts1770fs2322ts0992ts2184ts2954ts3117ts2424ts1174ts0902ts903ts2101s0481。此种转乘方式经过了 s1919. s3186站点的共两次换乘,共经过了 32站，所花费的时间为分钟;线路2：首先在l084路车下行路线从s1557站开始

32、乘车，途经s3158fs2628->s3408fs2044->s1985fs2563->s2682->s0028->s0029ts0055s0051s1919,然后在s1919站点换乘l189路车下行 路线，途经s1919s2840ts1402ts3186,之后在s3186站点换乘l460 路 车 下 行 路 线， 途 经s3186ts3544ts2116ts2119ts1788ts1789s1770ts2322ts0992->s2184s2954->s3117->s2424s1174s0902->s903s2101 s0481。此种转乘方

33、式经过了 s1919、s3186站点的共两次换乘，共经过了 32站，所花费的时间为分钟。s0971s0485的最佳路线：首先在l013路车下行路线从s0971站 开 始 乘 车，途 经s3832ts3341->s2237ts3565->s3333ts1180s3494->s1523->s1 520ts1988ts1743ts1742ts1181ts1879ts3405ts2517s3117s2954ts0531ts2184,然后在s2184站点换乘l417路车下行路线， 途 中 经 过 以 下 站ts3186ts3409ts2717ts1402ts2840ts0643s

34、2079ts1920ts2480s2482ts221 0s3332ts3351 s0485此种换乘方式经过了 41站。所花费的时间为分钟。s0008s0073的最佳路线：首先在l463路车下行路线从s0008站 开 始 乘 车，途 经s0008ts1383ts1688ts3459s2532ts3474ts0369ts1776ts2855ts0338ts2849ts2782ts0935ts2084ts2083,然后在 s2083站点换乘l057路车上行路线，途中经过以下站点：s2083ts1538ts3547ts0609ts0483ts0604ts2650ts3470ts2 619s2340ts

35、3162ts2181ts0073此种换乘方式共经过了 26站。所花费的时间为分钟。（本问有14种不同的换乘最佳方案，其他13种换乘方案详见附录） s0148s0485的最佳路线: 首先在l308路车上行路线从s0148站开始乘车，途经s0462ts0361s1797ts2221ts0302ts2222ts2737ts1716ts0128->s2268s1308->s1391f s2272s0036 然后在 s0036 站点换乘ts 路 车 上 行 路 线， 途 经s0036ts3233->s0618ts0617->s0721ts2057->s2361->s0

36、608->s0399ts2535ts2534ts0239ts0497ts2090ts2082s2210 ,之后 在s2210站点换乘l417路车下行路线，途经 s2210s3332->s3351f s0485。此种转乘方式经过了 s0036、s2210站点的共两次换乘，共经过了 33站，所花费的时间为分钟。（本问有3种不同的换乘最佳方案，其他2种换乘方案详见附录1-2） s0087s3676的最佳路线：首先在l454路车上行线路从s0087乘 车，途 经s0857ts0630ts1427ts1426ts0541ts0978ts3389ts1919ts0641s2840ts3496,

37、然后在s3496站点换乘l209路车下行路线，途中经过以下站点：s3496ts1883ts1159ts2699ts2922ts3010ts0583ts1987ts0082->s3676此种换乘方式共经过了 20站。所花费的时间为分钟。4、模型ii费用最低的线路选择模型模型的准备 我们仍以从起始站s3359到终到站s1828的线路为例进行说明。 首先对题目给出的分段计价的信息进行数据处理，通过搜索找到所 有的分段线路，然后根据分段计价对乘坐站数不同而制定的具体计价 要求（020站：1元；2140站：2元；40站以上：3元）建立一 个价格向量，又由于共有86列的数据，于是我们得到一个前20列

38、为1, 21到40列为2, 41到86列为3的向量则即为在分段计价情况下从起始站到中转站的公汽票价，为分段计 价情况下从中转站到终到站的票价（、为整数，且）。 在模型i方法的基础上，得到通过在中转站的转乘所计算出来的从 起始站s3359到终到站s1828所经过的站点总数,然后判断得到的各个方案所经过的路线是分段计价还是单一票制。因此，对从起始站到中转站的票价和从中转站到终到站的票价要进行分段讨论： 在模型i结果的基础上，为了达到在所用时间最少的同时乘车费用 尽可能少的要求和便于大量数据进行比较处理以及在多种消耗时间 最少的最佳线路中进行筛选，我们在模型i计算出的最佳线路的基础 上计算出一个费用

39、并与实际乘车的最低费用 进行比较，看其是否相 等。如果，说明我们第一问中的最佳线路不仅满足了所消耗时间最 少的目标，而且还使得其所花费的乘车成本最低，这样可以达到一举 两得的效果；如果，说明我们在所消耗时间条件下的乘车费用不一 定最低，于是我们再通过排序得到最小结果以及其所对应的行进线路 和中转站。模型的建立由以上分析，我们可以得到目标函数：由于我们在求解时考虑了耗时最少情况下能否同时达到乘车费用最 少，因此我们目标函数的求解需要分两步进行求解。首先，我们要对 模型i做出的耗时最少的最佳线路计算其费用，如果与通过排序得到 的最低费用相同，就可以同时达到耗时最少、费用最低的双目标，如 果大于最低

40、费用，我们就要利用下面的约束条件来计算出最低费用情 况下的具体线路及中转站，可以得出约束条件。结合目标函数有模目标函数：约束条件为:算法步骤 设起始站为，终到站为，具体的算法实现如下: 对矩阵搜索得到分段计价线路矩阵，并构造分段价格向量; 搜索求出与站点的数据在矩阵中的位置，并构造成矩阵; 在的情况下查找矩阵的公共元素，即; 搜索出中第 行的数据等于以及中第 行的数据等于的数据所 在列，只考虑和的情况; 在模型i计算出的的最小值的基础上,计算得到价格并计算出最 若，则得到最佳线路结果；若，输出最低费用情况下的线路及中 转站点。模型结果利用编程实现可得到结果（程序详见附录）: s3359s182

41、8的最佳路线：首先在l436路车下行路线从s3359站 开 始 乘 车，途 经s2026ts1132ts2266ts2263ts3917s2303ts2301ts3233ts0 618ts0616ts2112ts2110ts2153ts2814ts2813ts3501t s3515ts3500ts0756ts0492ts0903ts1768ts0955ts0480ts2703s2800ts2192ts2191ts1829ts3649ts1784,然后在 si784 站点换乘l217路车下行路线，下站即为s1828站；或者在s1784站点转乘l167路下行路线，下站也是s1828站。因此，得到=

42、31,两种换乘方式都经过了 32个站点。乘车费用均为3元，与实际的最低费用相等。 s1557s0481的最佳路线： s0971s0485的最佳路线：首先在l013路车下行路线从s0971站 开 始 乘 车，途 经s3832ts3341s2237ts3565ts3333ts1180ts3494ts1523ts1 520ts1988ts1743ts1742ts1181ts1879s3405ts2517ts311 7ts2954s0531ts2184,然后在s2184站点换乘l417路车下行路线， 途 中 经 过 以 下 站点 ：s2184ts0992ts2322ts1770ts1789ts2119

43、ts2116ts3544ts3186ts3409ts2717ts1402s2840ts0643ts2079ts1920ts2480ts2482ts2210ts3332s3351ts0485此种换乘方式经过了 41站。乘车费用均为3元，与实际的最低费用相等。s0008s0073的最佳路线：首先在l463路车下行路线从s0008站 开 始 乘 车，途 经s0008ts1383s1688ts3459s2532ts3474ts0369ts1776ts2855ts0338ts2849ts2782ts0935ts2084ts2083,然后在 s2083站点换乘l057路车上行路线，途中经过以下站点：s20

44、83ts1538ts3547ts0609ts0483ts0604ts2650ts3470ts2 619s2340ts3162ts2181ts0073用相等。（本问有14种不同的换乘最佳方案，其他13种换乘方案详见附录1-1）s0148s0485的最佳路线：首先在l308路车上行路线从s0148站开始乘车，途经s0462ts0361s1797ts2221ts0302ts2222ts2737ts1716ts0128->s2268s1308->s1391->s2272->s0036 然后在 s0036 站点换乘-s 路 车 上 行 路 线， 途 经s0036fs3233-&g

45、t;s0618fs0617->s0721fs2057->s2361->s0608->s0 399s2535fs2534ts0239ts0497ts2090s2082s2210,之后在s2210站点换乘l417路车下行路线，途经s2210ts3332->s3351ts0485。此种转乘方式经过了 s0036、s2210站点的共两次换乘，共经过了 33站，所花费的时间为 分钟。（本问有3种不同的换乘最佳方案，其他2种换乘方案详见附录1-2） s0087s3676的最佳路线：首先在l454路车上行线路从s0087s0857ts0630ts1427ts1426s0541t

46、s0978ts3389ts1919ts0641s2840ts3496,然后在s3496站点换乘l209路车下行路线， 途 中 经 过 以 下 站 点：s3496ts1883ts1159ts2699ts2922ts3010ts0583ts1987ts0082s3676用相等。最少的乘车路线。二、问题二的分析与求解1、模型iii分步线性规划模型模型的准备我们在模型i中只以公共汽车为交通工具的基础上，引进地铁这一快 捷方便的搭乘工具,重新建立一套新的公交和地铁最佳线路选择问题 的自主查询系统，使得这一系统能够自主的提供一个公交和地铁交替 使用的用时最少的线路，从而为赶时间的乘客提供更加人性化的建 议

47、。这里共给出tl、t2两条地铁线路和地铁站台相邻的若干个公汽站, 且两条线路可以相互换乘，换乘只能在d12和d18两个站点。因此 我们认为两个地铁是相通的，可以任意换乘，且可以在从一个地铁站 到达其他任意一个地铁站。这里我们将tl. t2两条地铁线路看成一 条地铁。建立地铁站台相邻公汽矩阵:tl, t2地铁站台相邻公汽矩阵分别为,:由于我们将tl、t2两条地铁线路视为一条地铁线路，因此可以得到 所有地铁站台相邻公汽矩阵: 模型的算法 在所有地铁站台相邻公汽矩阵中搜索，是否有所要的起始站与终 到站，如果有则可以通过地铁从起始站直达终到站; 当在中没有搜索到起始站与终到站时，这说明地铁只能作为整

48、个线路中的中间搭乘工具,前后都必须通过搭乘公共汽车来连通起始 站，如图6图6公汽、地铁换乘示意图 这里就涉及到在该在哪一站搭乘地铁和在哪一站下地铁这一问题。为 解决这一问题，我们将矩阵中所有元素进行迭代搜索，这一步骤分 成两步完成：先搜索经过起始站的所有线路矩阵b与矩阵的公共 元素，其中；再搜索经过终到站的所有线路矩阵c与矩阵的公 共元素，其中。 这里我们依据时间t最小为目标，选取所有线路中的最短路线。这 里t是由四部分组成，分别为乘坐公共汽车l1的时间tl、乘坐地铁t的时间12、乘坐公共汽车l2的时间t3、交通工具换乘用时to,其中交通工具换乘用时to包括：换乘地铁平均耗时t01=4分钟（其

49、中步 行时间2分钟）；地铁换乘公汽平均耗时t02=7分钟（其中步行时间4.tiii分钟）；公汽换乘地铁平均耗时t03=6分钟（其中步行时间4分钟）；因 此总用时t为: 其中tl、t2、t3是由经过的站数决定的，设li. l2> t经过的站点数依次为：nl、n2、n3,贝!j：由于中我们是分两步来进行的，因此要分两步求最优线路，即两段都是最短线路时得到最优线路。 在中存在tl、t2两条地铁线路的转乘问题，这就涉及如何计算n2的问题。由于地铁转乘只能在d12、d18里两个站台，需要对于不同的上下地铁的站台进行分类讨论，计算出有效站台数h2。我们 通过if语句将各种可能会出现的情况，分别进行了

50、讨论，这样就能保证得到的是有效站台数n2,即符合地铁行驶和转乘实际。模型建立：根据上述算法可建立规划问题,目标函数为:,根据的叙述建立分步线性规划模型，并通过matlab编程实现: 约束条件: 约束条件：模型的结果 s3359s1828：从起始站 s3359 乘坐 l015 上行，途经s3359ts2266->s3917ts2303->s1327ts3068；在 s3068 下车，从d08 转 乘 地 铁 t1 上 行， 途 经d08td09td10td11td12td13td14td15d16td17td18；从 d18 下地铁 t1,转乘 t2,途经 d18-d33-d34-d

51、35-d36-d37-d38；从 d38下地铁t2 ,从s3262转乘l041上行，途经s3262-s1772-s0259-s0258-s1781-s1790-s0458-s1792-s1783-s1671-s 1828；即到达终到站s1828o用时94分钟，与模型i用时101分餅相比，节省时间7分钟，但比模型ii多花去3元钱。 s1557s0481：线路1 ：从起始站s1557乘坐l363下行，途经-s1985-s1557-s3158-s2628-s3408-s2044s2563-s2682-s2735-s0029-s0055-s0051-s1919；在 s1919 下车，从d20转乘地铁t

52、1下行，途经d20->d19->018；从d18下地铁t1,转乘 t2,途经 d18-d33-d34-d35-d36-d37-d38-d39-d24；从 d24下地铁 t2 ,从 s0537 转乘 l516 上行，途经s0537-s2651-s3013-s1808-s1173-s0910-s3517-s0453-s2424-s1174-s0902 -s0903-s2101-s0481；即到达终到站 s0481。线路2 :从起始站s1557乘坐l084下行，途经s1557-s3158-s2628-s3408-s2044-s1985-s2563-s2682-s0028-s0029-s0

53、055-s0051-s1919；在 s1919 下车，从 d20 转 乘地铁t1下行，途经d20->d19d18；从d18下地铁t1,转乘t2,途经 di8-d33-d34-d35-d36-d37-d38-d39-d24；从 d24 下地铁t2 , 从 s0537 转乘 l516 上行， 途经s0537-s2651-s3013-s1808-s1173-s0910-s3517-s0453-s2424 -s1174-s0902 -s0903-s2101-s0481；即到达终到站 s0481。线路1和线路2用时均为117分钟，与模型i用时分钟相比，节省时间分钟，但多花去2元钱；与模型ii s0

54、971s0485线路1： 从起始站 s0971 乘坐 l094 上行，途经s0971-s3571-s1609-s0345-s1419-s2389 -s0567；在 s0567 下车，从d01 转乘地铁 t1 上行，途经 doi -d02-d03-d04-d05-d06 -d07-d08-d09-d10-d11-d12-d13-d14-d15-d16-d17-d18-d19-d20- d21；从d21下地铁t1,从s0464转乘l469下行，途经 s0464-s0964-s3189-s2810-s2385-s0485；即到达终到站 s0485。线路2：从起始站 s0971 乘坐 l094 上行途

55、经s0971-s3571-s1609-s0345-s1419-s2389-s0567；在 s0567 下车，从d01 转乘地铁 t1 上行，途经 d01-d02-d03-d04-d05-d06-d07-d08- d09-d10-d11-d12-d13-d14-d15-d16-d17-d18-d19-d20-d21 ； 从d21下地铁 t1 ,从s0466转乘 l051上行，途经 s0466-s3189-s2810-s2385-s0071-s0485；即到达终到站 s0485。线路3：从起始站 s0971 乘坐 l094 上行，途经 s0971-s3571-s1609-s0345- s1419-

56、s2389 -s0567；在s0567下车，从d01转乘地铁t1上行，途 经 d01-d02-d03-d04-d05-d06-d07 d08-d09-d10-d11-d12-d13-d14-d15-d16-d17-d18-d19-d20-d21；从 d21 下地铁 t1,从 s0464 转乘 l104 上行，途经 s0464-s0964-s3189-s2810-s2385-s0485； 即到达终到站s0485o线路4：从起始站s0971乘坐l094上行，途经s0971-s3571-s1609- s0345-s1419 -s2389-s0567；在 s0567 下车，从 d01 转乘地铁 t1 上 行，途经d01-d02-d03-d04-d05-d06-d07-d08-d09-d10-d11-d12-d13-d14-d15-d16-d17-d18-d19 d20-d21；从d21下地铁t1,从s0464转乘l395下行，途经s0464-s0964-s3189-s2810-s2385-s0485；即到达终到站 s0485。线路5：从起始站s0971乘坐l094上行，途经s0971-s3571-s1609-s0345-s1419 -s2389-s0567；在