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

高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从a/b/c/d中选择一项填写）： b 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 重 庆 大 学 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 年 月 日赛区评阅编号（由赛区组委会评阅前进行编号）：高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：摘 要本文建立了乘公交看奥运最佳线路的选择模型。在仅就满足公众对乘车耗时最少和花费最低的两种需求，对三个情形：仅考虑公汽的单一线路，同时考虑公汽与地铁两种线路，兼顾步行公汽地铁三种线路，分别建立了任意两站点之间线路选择问题的数学模型，依托matlab软件编程给出相应的的算法。并利用所建立的模型与算法，求出给定的6对起始站终到站之间的最佳路线，并做出了清晰的评价说明。最后，本文还对模型作出了进一步分析、评价和推广。针对问题一中仅考虑乘坐公汽，我们在对问题分析的基础上，运用matlab软件编程并搜索，就乘客的耗时最少需求，建立了模型（耗时最少的线路选择模型），给出了相应的算法步骤及程序框图，并针对六组得到如下结果：s3359s1828，换乘一次有两条线路，都经过了32个站点，所花费的时间均为101分钟；s1557s0481：至少需换乘两次，线路有两条，也经过32个站点，耗时101分钟；s0971s0485：换乘一次，通过41站，耗时128分钟；s0008s0073：换乘一次，有14种不同线路，经过26站，耗时83分钟；s0148s0485：至少需换乘两次，线路有6条，且都经过32个站点，耗时101分钟；s0087s3676：换乘一次，经过20站，耗时65分钟。同样，就乘客的费用最低需求，建立了模型（费用最低的线路选择模型），给出了相应的算法步骤，得到结果详见正文第12页至第13页。针对问题二，同时考虑公汽与地铁两种线路，我们建立了模型（分步规划模型），通过设计算法步骤，再运用matlab编程可求出以上完成，我们可求出以上六组点的结果，详见正文第15页至第18页。针对问题三，兼顾步行公汽地铁三种线路，我们建立了模型（线路综合评价模型），第三题是在前面问题的基础上，加入了步行这一较为自主化的“交通工具”，使得原本的选择最优线路模型不再适用，于是我们这里建立了一个线路综合评价模型，通过分类讨论的方式，提供适合各种情况的线路选择方案，从而解决在三种交通工具并行时的路线选择问题。本文最后还对这一自主查询系统进行了推广，将自主查询系统推广到手机彩信或短信，给出了系统结构设计和网络拓扑结构图；同时，将这一自主查询系统应用到旅游线路选择上，并绘制了旅游线路选择系统结构图。关键词：线路选择；换乘；分步规划；自主查询系统；matlab1、问题的重述一、问题背景1、看奥运要出行2008年8月8日至8月24日，我国人民翘首企盼的第29届奥运会将在北京举行，届时将会有大量观众从不同地点到达比赛现场去观看奥运盛况，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。2、乘公交需择线这些年来，随着科技进步、政府投资及市政部门对城市道路的不断完善，我国城市的公交系统有了很大发展，作为我国首都北京市，它的公交线路已多达800条以上，这使得广大市民的出行更加通畅、便利。但是，同时也因线路的众多，为广大市民的出行带来一个新的问题，乘车从一个地方到另一个地方，如果都在同一条公交线路上，市民则不存在选择；如果需要换乘，特别是二次以上的换乘，市民则面临着多种选择，可分别从选最短线路、花最少时间、用最少换乘、节省票价等各个方面进行决策，以实现出行任务的完成。3、做系统先建模针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。二、有关数据1、基本参数设定相邻公汽站平均行驶时间(包括停站时间)：3分钟；相邻地铁站平均行驶时间(包括停站时间)：2.5分钟；公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)；地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)；地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)；公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)；公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元；地铁票价：3元（无论地铁线路间是否换乘）。注：以上参数均为简化问题而作的假设，未必与实际数据完全吻合。2、公交线路及相关信息（详见附件2中文本文档1、1.1、1.2及2、2.1、2.2）。三、问题提出1、问题一：仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。s3359s1828；s1557s0481；s0971s0485；s0008s0073；s0148s0485；s0087s3676。2、问题二：同时考虑公汽与地铁线路，解决问题一中两个问题。3、问题三：假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。2、问题的分析一、问题的总体分析与相关量的明确1、问题的总体分析乘公交看奥运公交线路选择问题涉及到数百条公汽线路与两条地铁公交线路、数千个公汽站点与几十个地铁站点、三类不同乘车票价信息、上行下行单行环形四种车行方向等多个因素，且出行查询者的通常需求分别有选最短线路、花最少时间、用最少换乘以及用最低票价，当然这些需求在小城市道路比较单一时可能是相一致的，但对拥有众多车辆及线路且道路如网的首都北京而言，这些需求则不尽然。故问题这是一类多因素多数据计算机查询信息处理及多目标决策问题，核心是算法。2、几个重要的量为了便于解决问题，下面我们先明确问题涉及到的几个重要相关量。运用相关的统计方法，从竞赛b题所给的压缩文本文档中，我们不难得到以下几个量的准确信息：公交线路：520条公汽线路，编号：l001l520；两条地铁线路t1与t2。公交站点：3957个公汽站点，编号：s0001s3957；39个地铁站点，编号：d01d39。公汽线路与站点：文本文档1.1具体地给出了520条公汽线路编号，票价信息，车行线信息（详见2007年竞赛b题压缩文本文档1.1）。地铁线路与站点：文本文档1.2具体地给出了北京地铁线路t1与t2，我们通过上网搜索1很易获取相关的地铁图片（图1）与北京地铁t1、t2线路图（图2）。结合文档1.2所给北京地铁线路t1与t2的信息，我们不难发现，地铁t1的23个站与地铁t2的16个站相吻合，且图2中的复兴门为d12与建国门为d18是可以换乘的两个站。 图1 地铁图片 图2 北京地铁t1、t2线路图二、对具体问题的分析1、对问题一的分析问题：仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用所给出的模型与算法，求出6对起始站终到站之间的最佳路线，且要有清晰的评价说明。分析：要寻找两站之间的最佳公交线路，就是要满足不同乘客乘坐公交的一定要求，比如选最短线路、花最少时间、用最少换乘或花最低票价等等。为了简化对问题的解决，我们不妨假定求最佳路线，仅在乘车耗时最少、花费最低两种条件下确定最佳公交线路。对于在同一线路上的任意两个站点，若通过两个站点的线路仅一条（如图3左），显然这一条也就是最佳路线；若通过两个站点的线路有两条及两条以上的线路，按基本参数设定知，最佳路线是中间站点数最少的线路，如图3右图中蓝色的直线即最佳路线。图3 两站间通过的线路仅一条与两站间通过的线路有两条线路图对于不在任何一条公交线路上的两个站点，即没有直达的公交线路，则要考虑换乘，若通过起始站的所有线路和通过终到站的所有线路有且仅有一个公共站点，如图4左可知，则相交站点的线路acb即为最佳路线；若通过起始站的所有线路和通过终到站的所有线路多于一个公共站点，如图4右c站和d站均为换乘站点，显然同样换乘次数时换乘线路所经过的站数较少的acb线要优于adb，从而acb线为最佳路线。同样换乘次数时多于两条换乘线的，则换乘线路所经过站数最少的为最佳路线。 图4 两站间换乘一次线路仅有一条与换乘一次线路有两条线以上的线路图如果对进行一次换乘不能完成出行任务的，我们要进行两次换行计划。类似上述的分析，我们可以得到两次的换乘情形下的最佳路线。显然这要比前两类情形复杂得多，但运用计算机进行编程一般是可以实现的。如果对进行两次换乘仍不能完成出行任务的，我们要进行三次或三次以上的换乘。但考虑到换乘三次及三次以上研究的技术处理和实际操作太复杂且实际意义不大，故在最初建模时可不予考虑，在对建模进行改进时，可酌情考虑。当然，对于基于最低价格的最佳模型求解，除了要考虑以上的分析外，我们还要考虑各类票价信息。首先我们要搜索出所有需要分段计价的公汽线路，然后根据题目中的分段计价要求建立一个价格矩阵，再由前述换乘法求出的结果进行价格计算，看是否满足价格最小的条件，对不满足的利用排序求出最小价格，并得到相对应的线路信息。2、对问题二的分析问题：同时考虑公汽与地铁线路时，解决问题一的建模、算法和6条最佳路线。分析：问题二是在问题一只有公共汽车单一交通工具的基础上，通过引入地铁这一交通工具，使得转乘不仅仅是公汽转公汽，还包括公汽转地铁，地铁转地铁，地铁转公汽，使得转乘问题复杂化。为了得到用时最少的线路，我们可考虑建立了分步规划模型进行求解，将总用时最少这一规划问题，分成在每次搭乘都用时最少的分布规划问题。从而在综合考虑公汽与地铁的情况下确定了最佳线路。3、对问题三的分析问题：假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。分析：第三题是在前面两个问题的基础上，加入了步行这一较为自主化的“交通工具”，使得原本的选择最优线路模型不再使用，于是我们这里建立了一个线路综合评价模型，通过分类讨论的方式，提供适合各种情况的线路选择方案，从而解决在三种交通工具并行时的路线选择问题。3、模型的假设1、为便于研究问题，规定每条线路起点站的位标为1，从起点站至终点站的其余各站的位标依次为2、3、。2、由于基本参数已设定，不再考虑发车频率和乘客到达时刻及等待时间；3、由于公交线路的交错复杂，不考虑公交线路的编排次序和公交站点的编排次序；4、交通状况良好，无交通阻塞及其它影响交通运营的异常情况发生； 5、作为交通系统比较发达和完善的首都北京，联通任意两站间的线路最多换乘两次，换乘三次及三次以上研究太复杂且实际意义不大，故不予考虑。4、名词解释与符号说明一、名词解释1、换乘：从一辆车下来转乘另一辆车的过程；2、位标：为建模而自行定义的变量，规定一条线路从始发站起各站的位标依次为1、2、3、。二、符号说明1. ：所有公汽线路数据处理后得到的；2. ：经过起始站s1的所有线路站台矩阵；3. ：经过终到站s2的所有线路站台矩阵；4. ， ：公汽的起始站点；5. ：公汽的终到站点；6. ：只考虑公汽情况下起始站与终到站的公共站点；7. ：公共站点与起始站在同一线路上的公共站点的列标；8. ：公共站点与终到站在同一线路的公共站点的列标；9. ：与公共站点在同一条线路上的起始站的列标；10. ：与公共站点在同一条线路上的终到站的列标；11. ：只考虑公汽情况下从起始站到公共站点的站点数量，即 ；12. ：只考虑公汽情况下从公共站点与终到站的站点数量，即 ；12. ：只考虑公汽情况下从起始站到终到站的总的站点数量，即 ；13. ：只考虑公汽情况下耗费时间最少情况下得到的最佳路线的中转站；14. ：只考虑公汽情况下乘车费用最低情况下得到的最佳路线的中转站；15. ：为使得 以一个向量的形式输出，同时为了循环的方便而引进的变量，初值为1；16. ：乘车所耗费的总时间，包括等待和转乘的时间；17. ：所有分段计价线路数据组成的矩阵；18. ：只考虑公汽情况下从起始站到中转站的票价；19. ：只考虑公汽情况下从中转站到终到站的票价；20. ：耗时最少的最佳路线的乘车费用，计算得到价格并计算出最低价格；21. ：乘车费用最低的最佳路线的最低乘车费用；22. ：根据分段计价标准的不同得到的 的分段计价价格向量,由数字1,2,3组成；23.ij：地铁相邻的公汽站台矩阵；24.p：矩阵ij与矩阵b的交；25.：矩阵ij与矩阵c的交；26. ：矩阵b与矩阵ij的公共元素；27. ：矩阵c与矩阵ij的公共元素；28.ti：乘坐交通工具时经历的时间；29.t0：交通工具换乘用时平均耗时；30.ni：乘坐交通工具时经过的有效站台数；31. ：任意两站点i、j之间的步行时间。5、模型的建立与求解从所要解决的问题和对问题所做的假设出发，我们对问题一分别建立了模型（耗时最少的线路选择模型）和模型（费用最低的线路选择模型），我们对问题二建立了模型（分步规划模型），我们对问题三建立了模型（线路综合评价模型）。一、问题一的分析与求解1、问题一的分析要寻找两站之间的最佳公交线路，就是要满足各类乘客乘坐公交的不同要求，为了简化对问题解决，我们大体上认为最佳路线即是乘车耗时最少、乘车费用最少两种情况来对问题一进行求解。为了实现这一目标，我们对题目给出的大量数据进行了相应的处理，发现对问题中列出的六组站点，都无法根据现有的公交线路直达，于是就要考虑公交车的换乘问题。在考虑到技术处理和实际操作的可行性，我们不妨假设最多换乘两次就可以到达任意站点，否则，乘客可以根据车行方向随机地选择车路，然后到一定车站后再行查询，或通过步行到能够附近站点。对于基于乘车费用最少的模型求解，我们首先搜索出所有需要分段计价的公汽线路，然后根据题目中的分段计价要求建立一个价格矩阵，首先对由模型求出的结果进行价格计算，看是否满足价格最小的条件，对不满足的利用排序求出最小价格，并得到相对应的线路信息。2、建模的思想建立数据库为了确定公汽线路的最佳路线选择，首先把附录2中的文本文档“1.1 公汽线路信息.txt”进行处理，并转换到excel软件中，形成以第一列线路为公汽线路编号，第二列为价格信息，第三列为车行性质，第四列为各线路上所有车站点的大型数据库（详见附录3），以此为基础，下面进一步研究。搜索起始站和终到站所经过的线路通过对数据库的搜索，查询起始站和终到站是否有相同的车经过，如果有且仅有一条，即为最佳乘车线路；如果有且多于一条，则只要计算从起始站到终到站的总站数，通过比较可以得到战数最少的公交线路，推荐给乘客。我们可用vb语言编程建立计算机循环查询系统。运用此系统产生的对话框进行查询起始站和终到站是否有相同的车经过，我们只要输入起始站的站名（比如s0001），然后再输入终到站的站名（比如s0158），则在打开的excel文件前的对话框里产生一串语句，比如有，则在回答“直达”，且紧跟“直达”的后面给出了起始站到终到站的站数，结束；如果没有，则回答“不能直达”，下面再转入下一步研究。寻找一次换乘的线路分别从数据库中搜索通过起始站的所有线路和通过终到站的所有线路，并将线路放到一起进行比较，如果存在公共的交点，则说明进行一次换乘即可完成出行计划。如果一次换乘的线路为一条，则是最佳乘车线路；如果一次换乘的线路多于一条，再通过计算通过的站点数进行比较，从而可找出站点数最小的最佳乘车线路。如果不存在公共的交点，则要进行两次或两次以上的换乘。寻找两次换乘的线路对上一步完成对数据库搜索后，若通过起始站的线路和通过终到站的线路不存在公共的站点，则对通过起始站线路的所有站点和对通过终到站线路的所有站点再进行第步的搜索，若存在存在公共的线路，则说明进行二次换乘即可完成出行计划。否则，我们考虑作为交通系统比较发达和完善的首都北京，联通任意两站间的线路最多换乘两次，换乘三次及三次以上研究太复杂且意义不大，故不予考虑。3、模型 耗时最少的线路选择模型模型的准备在寻找最佳线路之前，我们要给公汽线路信息给出的大量数据进行处理，即对上下行站点完全相同的数据补出它的下行数据；同时为处理简便起见，对环行线路我们以相同的线路写出它的下行路线，并对所有空白数据均补“0”。经过处理，得到一个1040行86列的的大矩阵a104086。下面我们以站点s3359s1828为例来说明公汽站点的最佳路线选择问题，其具体处理步骤如下：查找通过起始站与终到站的线路数利用数据库，我们运用软件 1 编程，可查找出通过起始站s3359和通过终到站s1828的线路数和具体线路数。a. 通过起始站s3359的线路有26条（包括上、下行）：l015(上下行)、l123(上下行)、l132(上下行) 、l291(上下行)、l324(上下行)、l352(上下行)、l366(上下行)、l378(上下行)、l436(上下行)、l469(上下行)、l473(上下行)、l474(上下行)、l484(上下行)。b. 通过终到站s1828的线路有10条（包括上、下行）： l041(上下行)、l167(上下行)、l182(上下行)、l217(上下行)、l238(上下行)因此，可以得到一个以通过s3359的线路为行、每行所有站点为列的 的矩阵 ，同理得到一个以通过s1828的线路为行、每行所有站点为列的 的矩阵 。确定公共点的位标为方便建模及其算法，下面定义一个新的名词。定义：规定一条公交线路从始发站起到终点站止各站的编号为位标，位标的大小依次为1、2、3、n。通过分析，我们了解到题目给出我们要求计算的起始站与终到站之间没有直达的情况，于是我们要考虑换乘车的问题。首先从换乘一次车的情况入手，我们利用 的查找命令求出起始站s3359与终到站s1828所有线路上的公共站点组成了集合 ，以及这些公共站点与起始站s3359在同一线路的位标 、这些公共站点与终到站s1828在同一线路的位标 。求换乘一次的总站点数通过索引，我们可以求出与对应公共站点在同一条线路上的起始站的位标 和这个公共站点在同一条线路上的终到站的位标 ，再利用公共站点与起始站在同一线路中列标的差额以及公共站点与终到站在同一线路中列标的差值就可以得到从起始站到公共站点的站点数量 和公共站点与终到站的站点数量 ，即 ， 。考虑到公汽的行驶顺序一定、无法反向行驶等实际意义，我们只对 的数据进行计算，然后把得到的 相加就可以得到总的站点数量 ，即 。确定目标函数由于题目中给出了相邻公汽站平均行驶时间相等（均为3分钟）的设定，所以要达到耗时最少，我们规定使得所经过的站点最少即可，于是我们利用上述步骤求得不同路线经过的最少站点数量就可以得到耗时最少情况下的最佳线路，即可得到对应的最佳线路的中转站 。此时得到的花费时间为 ，其中包括了公汽换乘公汽平均耗时5分钟。模型的建立通过上述分析，我们得到如下的耗时最少的线路选择模型: 目标函数 约束条件 算法步骤设起始站为 ，终到站为 ，具体的算法可按以下五个步骤来实现：搜索求出 与 站点的数据在矩阵 中的位置,并构造成矩阵 ；在 的情况下利用 查找矩阵 的公共元素 ； 搜索出 中第 行的数据等于 以及 中第 行的数据等于 的数据所在列 ，只考虑 和 的情况；在循环外层引进变量 ,并赋初值 ，计算从起始站 到终到站 所经过的所有站点数 ， ,其中 ，并得到与其对应的 的值,将 的数据以向量的形式显示出来；求出 的最小值，并输出对应最小 值所在的线路以及中转站。程序框图（如图5所示，程序见附录）图5 算法流程图模型的结果对问题一的第二小问，根据附录数据，利用上面的模型与算法，求出6对起始站终到站之间的耗时最少的线路选择及耗时如下：s3359s1828的最佳路线：首先在l436路车下行路线从s3359站开始乘车，途经s2026s1132s2266s2263s3917s2303s2301s3233s0618s0616s2112s2110s2153s2814s2813s3501s3515s3500s0756s0492s0903s1768s0955s0480s2703s2800s2192s2191s1829s3649s1784，然后在s1784站点换乘l217路车下行路线，下站即为s1828站；或者在s1784站点转乘l167路下行路线，下站也是s1828站。因此，得到 =31， ， 两种换乘方式都经过了32个站点。所花费的时间为 分钟。s1557s0481的最佳路线：线路1：首先在l363路车下行路线从s1557站开始乘车，途经s3158s2628s3408s2044s1985s2563s2682s2735s0029s0055s0051s1919，然后在s1919站点换乘l189路车下行路线，途经s1919s2840s1402s3186，之后在s3186站点换乘l460路车下行路线，途经s3186s3544s2116s2119s1788s1789s1770s2322s0992s2184s2954s3117s2424s1174s0902s903s2101s0481。此种转乘方式经过了s1919、s3186站点的共两次换乘，共经过了32站，所花费的时间为 分钟；线路2：首先在l084路车下行路线从s1557站开始乘车，途经s3158s2628s3408s2044s1985s2563s2682s0028s0029s0055s0051s1919，然后在s1919站点换乘l189路车下行路线，途经s1919s2840s1402s3186，之后在s3186站点换乘l460路车下行路线，途经s3186s3544s2116s2119s1788s1789s1770s2322s0992s2184s2954s3117s2424s1174s0902s903s2101s0481。此种转乘方式经过了s1919、s3186站点的共两次换乘，共经过了32站，所花费的时间为 分钟。s0971s0485的最佳路线：首先在l013路车下行路线从s0971站开始乘车，途经s3832s3341s2237s3565s3333s1180s3494s1523s1520s1988s1743s1742s1181s1879s3405s2517s3117s2954s0531s2184，然后在s2184站点换乘l417路车下行路线，途中经过以下站点:s2184s0992s2322s1770s1789s2119s2116s3544s3186s3409s2717s1402s2840s0643s2079s1920s2480s2482s2210s3332s3351s0485此种换乘方式经过了41站。所花费的时间为 分钟。s0008s0073的最佳路线：首先在l463路车下行路线从s0008站开始乘车，途经s0008s1383s1688s3459s2532s3474s0369s1776s2855s0338s2849s2782s0935s2084s2083，然后在s2083站点换乘l057路车上行路线，途中经过以下站点：s2083s1538s3547s0609s0483s0604s2650s3470s2619s2340s3162s2181s0073此种换乘方式共经过了26站。所花费的时间为 分钟。（本问有14种不同的换乘最佳方案，其他13种换乘方案详见附录）s0148s0485的最佳路线：首先在l308路车上行路线从s0148站开始乘车，途经s0462s0361s1797s2221s0302s2222s2737s1716s0128s2268s1308s1391s2272s0036然后在s0036站点换乘s路车上行路线，途经s0036s3233s0618s0617s0721s2057s2361s0608s0399s2535s2534s0239s0497s2090s2082s2210，之后在s2210站点换乘l417路车下行路线，途经s2210s3332s3351s0485。此种转乘方式经过了s0036、s2210站点的共两次换乘，共经过了33站，所花费的时间为 分钟。（本问有3种不同的换乘最佳方案，其他2种换乘方案详见附录1-2）s0087s3676的最佳路线：首先在l454路车上行线路从s0087站开始乘车，途经s0857s0630s1427s1426s0541s0978s3389s1919s0641s2840s3496，然后在s3496站点换乘l209路车下行路线，途中经过以下站点：s3496s1883s1159s2699s2922s3010s0583s1987s0082s3676此种换乘方式共经过了20站。所花费的时间为 分钟。4、模型 费用最低的线路选择模型模型的准备我们仍以从起始站s3359到终到站s1828的线路为例进行说明。首先对题目给出的分段计价的信息进行数据处理，通过搜索找到所有的分段线路，然后根据分段计价对乘坐站数不同而制定的具体计价要求（020站：1元；2140站：2元；40站以上：3元）建立一个价格向量，又由于共有86列的数据，于是我们得到一个前20列为1，21到40列为2，41到86列为3的向量 则 即为在分段计价情况下从起始站到中转站的公汽票价， 为分段计价情况下从中转站到终到站的票价（ 、 为整数，且 ）。在模型方法的基础上，得到通过在中转站的转乘所计算出来的从起始站s3359到终到站s1828所经过的站点总数 ，然后判断得到的各个方案所经过的路线是分段计价还是单一票制。因此，对从起始站到中转站的票价 和从中转站到终到站的票价 要进行分段讨论：在模型结果的基础上，为了达到在所用时间最少的同时乘车费用尽可能少的要求和便于大量数据进行比较处理以及在多种消耗时间最少的最佳线路中进行筛选，我们在模型计算出的最佳线路的基础上计算出一个费用 并与实际乘车的最低费用 进行比较，看其是否相等。如果 ，说明我们第一问中的最佳线路不仅满足了所消耗时间最少的目标，而且还使得其所花费的乘车成本最低，这样可以达到一举两得的效果；如果 ，说明我们在所消耗时间条件下的乘车费用不一定最低，于是我们再通过排序得到最小结果以及其所对应的行进线路和中转站。模型的建立由以上分析，我们可以得到目标函数： 由于我们在求解时考虑了耗时最少情况下能否同时达到乘车费用最少，因此我们目标函数的求解需要分两步进行求解。首先，我们要对模型做出的耗时最少的最佳线路计算其费用，如果与通过排序得到的最低费用相同，就可以同时达到耗时最少、费用最低的双目标，如果大于最低费用，我们就要利用下面的约束条件来计算出最低费用情况下的具体线路及中转站 ，可以得出约束条件。结合目标函数 有模型目标函数： 约束条件为： 算法步骤设起始站为 ，终到站为 ，具体的算法实现如下：对矩阵 搜索得到分段计价线路矩阵 ，并构造分段价格向量 ；搜索求出 与 站点的数据在矩阵 中的位置,并构造成矩阵 ；在 的情况下查找矩阵 的公共元素，即 ； 搜索出 中第 行的数据等于 以及 中第 行的数据等于 的数据所在列 ，只考虑 和 的情况；在模型计算出的 的最小值的基础上，计算得到价格 并计算出最低价格 ； 若 ，则得到最佳线路结果；若 ，输出最低费用情况下的线路及中转站点。模型结果利用 编程实现可得到结果（程序详见附录）：s3359s1828的最佳路线：首先在l436路车下行路线从s3359站开始乘车，途经s2026s1132s2266s2263s3917s2303s2301s3233s0618s0616s2112s2110s2153s2814s2813s3501s3515s3500s0756s0492s0903s1768s0955s0480s2703s2800s2192s2191s1829s3649s1784，然后在s1784站点换乘l217路车下行路线，下站即为s1828站；或者在s1784站点转乘l167路下行路线，下站也是s1828站。因此，得到 =31， ， 两种换乘方式都经过了32个站点。乘车费用均为3元，与实际的最低费用相等。s1557s0481的最佳路线：s0971s0485的最佳路线：首先在l013路车下行路线从s0971站开始乘车，途经s3832s3341s2237s3565s3333s1180s3494s1523s1520s1988s1743s1742s1181s1879s3405s2517s3117s2954s0531s2184，然后在s2184站点换乘l417路车下行路线，途中经过以下站点:s2184s0992s2322s1770s1789s2119s2116s3544s3186s3409s2717s1402s2840s0643s2079s1920s2480s2482s2210s3332s3351s0485此种换乘方式经过了41站。乘车费用均为3元，与实际的最低费用相等。s0008s0073的最佳路线：首先在l463路车下行路线从s0008站开始乘车，途经s0008s1383s1688s3459s2532s3474s0369s1776s2855s0338s2849s2782s0935s2084s2083，然后在s2083站点换乘l057路车上行路线，途中经过以下站点：s2083s1538s3547s0609s0483s0604s2650s3470s2619s2340s3162s2181s0073此种换乘方式共经过了26站。乘车费用均为2元，与实际的最低费用相等。（本问有14种不同的换乘最佳方案，其他13种换乘方案详见附录1-1）s0148s0485的最佳路线：首先在l308路车上行路线从s0148站开始乘车，途经s0462s0361s1797s2221s0302s2222s2737s1716s0128s2268s1308s1391s2272s0036然后在s0036站点换乘s路车上行路线，途经s0036s3233s0618s0617s0721s2057s2361s0608s0399s2535s2534s0239s0497s2090s2082s2210，之后在s2210站点换乘l417路车下行路线，途经s2210s3332s3351s0485。此种转乘方式经过了s0036、s2210站点的共两次换乘，共经过了33站，所花费的时间为 分钟。（本问有3种不同的换乘最佳方案，其他2种换乘方案详见附录1-2）s0087s3676的最佳路线：首先在l454路车上行线路从s0087站开始乘车，途经s0857s0630s1427s1426s0541s0978s3389s1919s0641s2840s3496，然后在s3496站点换乘l209路车下行路线，途中经过以下站点：s3496s1883s1159s2699s2922s3010s0583s1987s0082s3676此种换乘方式共经过了20站。乘车费用均为2元，与实际的最低费用相等。最少的乘车路线。二、问题二的分析与求解1、模型 分步线性规划模型模型的准备我们在模型中只以公共汽车为交通工具的基础上，引进地铁这一快捷方便的搭乘工具，重新建立一套新的公交和地铁最佳线路选择问题的自主查询系统，使得这一系统能够自主的提供一个公交和地铁交替使用的用时最少的线路，从而为赶时间的乘客提供更加人性化的建议。这里共给出t1、t2两条地铁线路和地铁站台相邻的若干个公汽站，且两条线路可以相互换乘，换乘只能在d12和d18两个站点。因此我们认为两个地铁是相通的，可以任意换乘，且可以在从一个地铁站到达其他任意一个地铁站。这里我们将t1、t2两条地铁线路看成一条地铁。建立地铁站台相邻公汽矩阵 ：t1，t2地铁站台相邻公汽矩阵分别为 ， ：由于我们将t1、t2两条地铁线路视为一条地铁线路，因此可以得到所有地铁站台相邻公汽矩阵 ：模型的算法在所有地铁站台相邻公汽矩阵 中搜索，是否有所要的起始站 与终到站 ，如果有则可以通过地铁从起始站 直达终到站 ；当在中没有搜索到起始站 与终到站 时，这说明地铁只能作为整个线路中的中间搭乘工具，前后都必须通过搭乘公共汽车来连通起始站，如图6图6 公汽、地铁换乘示意图这里就涉及到在该在哪一站搭乘地铁和在哪一站下地铁这一问题。为解决这一问题，我们将矩阵 中所有元素进行迭代搜索，这一步骤分成两步完成：先搜索经过起始站 的所有线路矩阵b与矩阵 的公共元素 ，其中 ；再搜索经过终到站 的所有线路矩阵c与矩阵 的公共元素 ，其中 。这里我们依据时间t最小为目标，选取所有线路中的最短路线。这里t是由四部分组成，分别为乘坐公共汽车l1的时间t1、乘坐地铁t的时间t2、乘坐公共汽车l2的时间t3、交通工具换乘用时t0，其中交通工具换乘用时t0包括：换乘地铁平均耗时t01=4分钟(其中步行时间2分钟)；地铁换乘公汽平均耗时t02=7分钟(其中步行时间4分钟)；公汽换乘地铁平均耗时t03=6分钟(其中步行时间4分钟)；因此总用时t为：其中t1、t2、t3是由经过的站数决定的，设l1、l2、t经过的站点数依次为：n1、n2、n3，则：由于中我们是分两步来进行的，因此要分两步求最优线路，即两段都是最短线路时得到最优线路。在中存在t1、t2两条地铁线路的转乘问题，这就涉及如何计算n2的问题。由于地铁转乘只能在d12、d18里两个站台，需要对于不同的上下地铁的站台进行分类讨论，计算出有效站台数n2。我们通过if语句将各种可能会出现的情况，分别进行了讨论，这样就能保证得到的是有效站台数n2，即符合地铁行驶和转乘实际。模型建立：根据上述算法可建立规划问题，目标函数为： ，根据的叙述建立分步线性规划模型，并通过matlab编程实现：约束条件： 约束条件： 模型的结果s3359s1828：从起始站s3359乘坐l015上行，途经s3359s2266s3917s2303s1327s3068；在s3068下车，从d08转乘地铁t1上行，途经d08d09d10d11d12d13d14d15d16d17d18；从d18下地铁t1，转乘t2，途经d18-d33-d34-d35-d36-d37-d38；从d38下地铁t2，从s3262转乘l041上行，途经s3262-s1772-s0259-s0258-s1781-s1790-s0458-s1792-s1783-s1671-s1828；即到达终到站s1828。用时94分钟，与模型用时101分钟相比，节省时间7分钟，但比模型多花去3元钱。 s1557s0481：线路1：从起始站s1557乘坐l363下行，途经s1557-s3158-s2628-s3408-s2044 -s1985- s2563-s2682-s2735-s0029-s0055-s0051-s1919；在s1919下车，从d20转乘地铁t1下行，途经d20d19d18；从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-s0055-s0051-s1919；在s1919下车，从d20转乘地铁t1下行，途经d20d19d18；从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。线路1和线路2用时均为117分钟，与模型用时分钟相比，节省时间分钟，但多花去2元钱；与模型s0971s0485线路1：从起始站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转乘l469下行，途经s0464-s0964-s3189-s2810-s2385-s0485；即到达终到站s0485。线路2：从起始站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，从s0466转乘l051上行，途经s0466-s3189-s2810-s2385-s0071-s0485；即到达终到站s0485。线路3：从起始站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转乘l104上行，途经s0464-s0964-s3189-s2810-s2385-s0485；即到达终到站s0485。线路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；在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转乘l450下行，途经s0466-s3189-s2810-s2385-s0071-s0