毕业论文-乘公交-看奥运模型论文.doc

乘公交_看奥运模型高教社杯全国大学生数学建模竞赛承 诺 书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规则的行为，我们将受到严肃处理。我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 重 庆 大 学 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 年 月 日赛区评阅编号（由赛区组委会评阅前进行编号）：高教社杯全国大学生数学建模竞赛编 号 专 用 页赛区评阅编号（由赛区组委会评阅前进行编号）：赛区评阅记录（可供赛区评阅时使用）：评阅人评分备注全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：乘公交，看奥运模型摘要本文要解决的是合理选择公交车去看奥运会的问题，现在给出了每一条路线的具体信息，但是人们出行不会到所有的路线去查询，因此要快速、高效地从众多可行路线中选出最优路线，为了选出最佳路线我们建立了多目标规划模型。对于问题一：在仅考虑乘坐公汽的情况下，出行的过程中我们要考虑的是换乘次数、行程时间、行程费用，我们建立了以换乘次数最少、行程时间最少、行程费用最低为目标的多目标规划模型。利用层次求解法，以换乘次数最少为第一目标，在换乘次数最少的情况下对应的费用低或耗时少的最优路线。通过模型的算法建立公交查询系统，得到给出的各线路的目标值：目标123456转乘次数121111行程时间（分钟）1011061288312865行程费用（元）333232对于问题二：在考虑公汽和地铁换乘的情况下，同样要获得出行的最佳路线。所以建立的模型同样是多目标规划模型。在对公交查询系统建立的时候多加两条地铁线路和站点转乘。同样以换乘次数最少为第一目标，考虑不同的需求者对时间和费用的要求。得到给出起始站和终点站的各目标值：目标123456转乘次数无地铁121111有地铁333331行程时间（分钟）无地铁1011061288312865有地铁107.510391.51288839.5行程费用（元）无地铁333232有地铁635353对于问题三：综合考虑乘车与步行的线路选择情况，这种路线的选取更加符合实际情况灵活性更大，步行一定数量的站点可以减少换乘的次数对我们的第一目标是很好的满足。所以要选取最佳路线我们同样建立了多目标规划模型。最后通过改进各种不同的约束条件，使得问题与实际更加贴近。我们的查询系统也得到完善，具有一定的实用性。【关键词】 公交查询系统 最优路线 多目标规划 层次求解法1. 问题重述1.1 问题的背景我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。1.2 问题的相关信息为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。1.基本参数设定相邻公汽站平均行驶时间(包括停站时间)： 3分钟相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）1.3 需解决的问题问题一：仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S3676问题二：同时考虑公汽与地铁线路，解决以上问题。问题三：假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。2. 模型的假设与符号说明2.1,模型假设假设1： 只要有公交车来，就可以上车，不考虑满载而无法搭载。假设2： 公交车准时到达，不会出现晚点。假设3： 公交系统不会出现交通故障，运行畅通。假设4： 乘客所经过的站点不能有相同站点经过两次。假设5： 相邻站点的公交行驶时间相同。假设6： 环行路线为双向路线。2.2符号说明表示出行者选择第条公交线路所经过的第个站点，或表示公汽站点集，表示出行者选择第条公交线路乘坐的第辆公交线，或表示公汽线路集，表示地铁站点集，表示地铁线路集，表示第i条交通路线需要的时间表示第i条交通路线的换乘次数表示第i条交通路线的经过站点数表示第i条交通路线需要的费用表示站点数3. 问题分析本题主要在三种不同情况下，研究任意两站点之间的线路选择问题。联系实际，公众乘坐公交车主要考虑的因素包括转乘次数、行程时间、乘车费用等因素。为满足一般公众的乘车需求，主要按照公众对不同乘车信息的重视程度，确定出最佳的乘车路线。针对问题一：要求仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型。以选择换乘次数、乘车所用时间、乘车的费用为目标可得到相应的目标函数，而具体的约束条件则需要另外求得。对于换乘次数，联系被选择线路上的站点线路交替序列的元素个数可以表示出来；站点总数则采用给同一线路上的站点排序的方法也可以求到，由于只考虑了公汽之间的换乘，则出行时间只与换乘次数和所历站数有关；对于出行费用则在换乘次数的基础上，引入分段计价的加价函数也可求得。针对问题二：考虑地铁与公汽并行时的公交系统时，出行者的乘车路线选择将变得更加丰富，其主要变化的因素有：地铁票价稍高但是固定且在地铁航线之间换乘而不需另外支付交通费用，相邻站点之间的距离较公汽站点大，而运行时间却相对减少；地铁与公汽之间进行换乘时，由于地铁站点不可能与公汽站点都建在同一个地方，因此从地铁站到公汽站的步行时间相对较多，而且位于与地铁换乘的公汽站点还可以通过本地铁站进行免费耗时换乘到下一个公汽站。将跨公交站的步行也同样看成是一条步行公交线路，不过该条公交线路具有免费耗时的特点。同问题一中的解决方案可建立相应的数学模型。针对问题三：考虑到出行者在步行时，所经过的任意两站点之间的路径都应该是至少有一条公汽线路上的公交工具通过，由问题三的条件可知，步行时所经过的两站点之间的步行时间是一个已知值。据实际情况，假设步行者步行在相邻两公汽站所用时间平均是公汽经过这两站（包括停站时间）所用时间的倍，则由基本参数设定可知，步行者通过这样两站点所用的平均时间为分钟，于是将行人步行所经过的线路也纳入到公交线路中，其特点是费时费力但选择灵活，路途捷近。4. 模型准备4.1数据处理由EXCEL软件统计题目中的【附录1】和【附录2】中的公交线路系统数据，可以得到如下信息：（1） 该公交系统共有公汽线路520条。其中票价信息为分段计价的线路283条，单一票制1元的线路237条；上下行路径不同的线路409条，上下行路径相同的线路89条，环行线路22条。（2） 该公交系统共有公汽站点3957个。（3） 该公交系统共有地铁线路2条。其中直行线路1条，环行线路1条；（4） 该公交系统共有地铁站点39个；（5） 一条线路中的站点最多不超过86个。对于上述统计的直观信息，结合票价信息和分段计价线路进行综合考虑，可得：在分段计价路线中，共有27条的公汽站点数不超过20，有148条的公汽站点数在2140之间，公汽站点数超过40的线路有108条。因此，从单独的计算角度来考虑，可以将分段计价中站数不超过20的线路归为单一票制1元的线路，因此上述信息（1）可修正为：票价信息为单一票制1元的线路264条；在分段计价的路线中，共有256条，其中有148条的公汽站点数在2140之间，公汽站点数超过40的线路有108条。线路图的简化：（1）上、下行线路原路返回（2）上、下行线路不是原路返回（3）环路（双向）由公交线路得到两个算法矩阵：（1）站点的线路矩阵由经过每一个站点的公汽号排成的矩阵A*B，公汽数目不足的用0填充。（2）线路的站点矩阵由每一路公交按行驶的方向，经过的站点组成的矩阵C*D，站点不足的用0填充。4.2 乘车路线乘客在出行时，乘车的方式可以简化为如下的线路图：起始站中转站1乘第1辆公交离开公交结束选乘初次车出发中转站2中转站3选择路线乘第2辆公交第1次换乘终到站乘第3辆公交第2次换乘中转站Ni乘第Ni+1辆公交第Ni次换乘由附件中的统计信息可以知道，任意一个公交站点都不是孤立的，即连接任意两公交站点之间的公交路径都是存在的。这样的路径可能只有一条，也可能有多条，设出行者所选择出行的起始站为，终到站为，从到的所有路径的集合为，其中第条路径为。出行者出行乘公交的路径可看着是站点S、车次L、站点S、车次L的交替进行，直至到达终到站。为区别前后的车次或站点，使得前后排列的站点与车次都有一定的顺序，设出行者选择第条路径时，所乘坐的第辆公交工具为，第个换乘站点（中转站）记为，出行者在同一站点上不能出现两次，即各不相同，特别地令，；于是可以得到从到的所有路径集中的第条路径为：因此将所有路径集在一起，可得：由此而来，对任何一个出行者来说，只要知道他的出行起始站和终到站之后，便可以在路径集中找到他最需要的出行路线。4.3 行程通过的总站数设非环行线路上的两个站点和在沿着公交工具行进方向上的站数按照正整数从小到大的排序分别为和，其中仍然记；，于是由附件中的相关统计结果可知：当线路为环行线路时，设该环行路线上的总站数为，为上的任意一站，分别为公交工具在沿着行进方向上的最后一站和前一站，于是可标记；所以出行者乘坐线路的公交所经过的站点数目为：所以，出行者途经的总站数为共条行车路线上车站数的总和，即5 问题一的解答针对问题一是在对公汽的行驶路线上选取最佳路线。5.1 模型的建立5.1.1模型分析该问题是解决的是任意公交站点之间的路线选取，要满足的需求者有不同。换乘次数、耗时、行程费用是乘客主要的考虑因素，其中路线满足换乘少、耗时少、行程费用低的是最优的路线。因此我们得到以下的目标函数：目标一：换乘次数设表示有序集中的元素的个数，为便于区别，现标记，得到的换乘次数为：目标二：行程耗时由模型准备中分析的行程总站数和以及需要换乘的次数，可以得到每一条路线所需的时间。第条线路从起始站到达终到站所耗的平均总时间为，换乘一次所耗的平均时间为=5分钟，相邻两站点之间乘车的平均时间为=3分钟。则有目标三：行程费用设公汽的单一票价为，出行者在所选择的出行线路中所应支付的车旅费为，所乘同一公交线路上的最高收费为，分段计价时加价的最少站数为，由模型的准备中得到了线路的站点数，于是有：其中，表示取不超过X的最大整数，参数：（元），（元），。5.1.2综上所述得到优化模型5.2 模型的求解 5.2.1模型的算法根据看奥运的实际出发，人们在坐车的时候会考虑的是减少转乘次数为第一目标，再来选取转乘次数少的情况下的费用和行程耗时少的路线为出行路线。所以得到算法的基本思想为，分别从起点A、终点B出发，通过比较公交网络上各车站的可换乘车站，搜索A到B换乘次数最少的可能路径，然后比较各路线所用的时间和费用来确定最佳选择的路径。公交的换乘示意图：(d)换乘多次车的情况 公交线路换乘方案示意图(a)直达的情况(b)换乘一次车的情况ABCBA(c)换乘两次车的的情况ABCDABCD路线搜索的具体算法步骤为：第一歩：输入乘车始点站和终点站，在数据库的站点线路矩阵中查询是否有相同路线的公汽，（1）有相同路线公汽，则查询站点间有直达线路，输出所有可直达车辆信息，结束程序； （2）没有相同路线公汽，则查询站点间需要转乘，进入第二步 。第二步；将始点和终点输入公汽站点矩阵，查询是否有相同的站点，（1）有相同站点，则查询站点可以通过一次转乘达到，输出所有一次转乘的车次和中转站的信息，结束程序； （2）没有相同站点，则查询站点间需要转乘两次，进入第三步 。第三步：找最后一个中转站，在终点站所在线路中沿车驶向的反向找一个站点当做终点站称为伪终点站，根据伪终点站和始点站输入到公汽站点矩阵，查询是否有相同的站点，（1）有相同站点，则查询站点可以通过两次转乘达到，输出所有两次转乘的车次和中转站的信息，结束程序； （2）没有相同站点，则查询站点间需要转乘三次，进入第四步 。第四步：找第一个中转站，在始点站所在线路中沿车驶向找一个站点当做始点站称为伪始点站，根据伪始点站和伪终点站输入到公汽站点矩阵，查询是否有相同的站点，（1）有相同站点，则查询站点可以通过三次转乘达到，输出所有三次转乘的车次和中转站的信息，结束程序； （2）没有相同站点，则查询站点间需要多次转乘。 第五步：多次转乘的就是重复第三步和第四步直到找出可行路线。由以上的搜索方法得到公交查询系统的流程，具体流程图如下：公交的站点矩阵站点的线路矩阵输入起始点查询站直达输出相同站点直达线路输出换乘站点与路线无相同站点相同线路有有输出无换乘一次到达寻找终点所在路线之前站点为终点无公交的站点矩阵换乘多次到达换乘站点与路线有无5.2.2具体查询根据以上的算法和流程图，利用MATLAB程序设计（具体程序见附录）得到了路线的查询系统。输入要查询的路线始点站和终点站就可以得到具体的车次、中转站和行程经过站点总数和行程时间。待查询的路线：(1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4)、S0008S0073 (5)、S0148S0485 (6)、S0087S3676通过查询系统我们比较选取了几条好的出行路线：具体乘车方案始末站点转乘次数行程时间（分）行程费用（元）乘车路线11013210631128318321128316525.3 评价说明在我们建立的查询系统中，可以得到换乘次数不是最少的情况的各出行路线，但是由于这样考虑的更加全面，换乘的次数多了耗时是少情况比较复杂，所以具体的路线没有给出。但是通过所得的系统可以满足各类的需求，可以避免少数极端的出行者的要求不能被满足。所以我们表达出的仅仅是符合多数实际情况的出行路线。 6. 问题二的解答针对问题二是在问题一的情况下加入了地铁的换乘的最佳路线选取6.1 模型的建立6.1.1模型分析该问题是仅在问题一上多加了两条地铁线路，在公汽站与地铁站的换乘上有时间的消耗没有换乘次数增加。所以路线满足换乘少、耗时少、行程费用低的是最优的路线。在地铁站与公汽站的换乘因此我们得到以下的目标函数：目标一：换乘次数设表示有序集中的元素的个数，即 ，得到的换乘次数为：目标二：行程耗时从公交站点乘线路公交工具到达公交站点所消耗的时间（包括相邻两站点间的停站时间）为：，由线路的公交工具换乘到线路的公交工具所消耗的时间为： ，由基本参数设定的信息可得：其中目标三：行程费用在问题二的讨论中，乘车的总体花费会受到出行者换乘次数，乘坐分段计价车时通过的站数的影响，而在本问题中，有假设知道同一地铁站对应的任意两个公汽站可以通过地铁站换乘而不需要支付地铁费，同样根据问题一中，对乘公交所支付费用的讨论思想，所以的到行程费用为： 其中，表示取不超过X的最大整数，参数：（元），（元），。6.1.2综上所述得到优化模型6.2 模型的求解根据问题一的算法，在该问题上优先考虑换乘次数，在换乘次数最少的情况下在来考虑行程时间和费用。在有路线通过地铁的时候仅仅先考虑换乘次数少，再来比较其他的路线就与问题一的路线差别不大。所以我们分开来讨论，换乘次数最少没有地铁的路线与有地铁的换乘路线。根据MATLAB程序设计得到公交查询系统，输入任意的始点站和终点站可以得到各条路线的换乘次数、路经站数。所以由经过的具体路径可以得到具体每一条路径需要的时间。(1)不考虑地铁（与问题一相同）换乘次数最少的情况始末站点转乘次数行程时间（分）行程费用（元）乘车路线1101321063112831832112831652（2）考虑地铁乘坐地铁后转乘次数最少的情况始末站点转乘次数行程时间（分）行程费用（元）乘车路线3107.5631033391.55312833885139.53由上面两个表比较可以得到不同的乘坐方式得到不同的最佳路线，根据乘客的乘坐偏好，选取恰当的乘车方式。7. 问题三的解答针对问题三在问题二给定了站点间的步行时间，所以除了公汽地铁外还可以步行，由此选择最佳的出行路线。7.1 模型的建立该问题是对路线的选择更加符合实际情况的考虑，出行中会遇到乘车还是步行，步行可以减少换乘次数增加了行程时间。所以路线满足换乘少、耗时少、行程费用低的是最优的路线。在步行与乘车的路线选择中我们得到以下的目标函数：目标一：换乘次数目标二：行程耗时 从公交站点到达公交站点所消耗的时间为：，其中站点之间的步行时间为时间给定了假设为t。由线路的公交工具换乘到线路的公交工具所消耗的时间为：，所以可以得到：其中，目标三：行程费用根据问题二中，乘车的总体花费会受到出行者换乘次数，乘坐分段计价车时通过的站数的影响。而在本问题中，由于同一地铁站对应的任意两个公汽站可以通过地铁站换乘而不需要支付地铁费，所以的到行程费用为： 其中，表示取不超过X的最大整数，参数：（元），（元），。7.2综上所述得到的模型8. 模型的评价、改进及推广8.1模型评价优点：（1） 该模型的考虑了不同交通方式的混合路线选取最佳路线的方法，根据实际需求选择路线具有一定的实用性。（2） 对于在多加考虑了地铁后，若坐地铁换乘次数就明显增加，对换乘次数分开讨论更加有利于乘客的需求。缺点：（1）由于题目给出的参数做了简化，未必与实际数据吻合不利于模型推广。（2）模型中给出的仅是多目标的一种求法的结果，不能更好的符合实际所要考虑的因素。8.2模型改进 该模型中在求解的过程中都是在为奥运期间乘车考虑的，即看奥运的会考虑的是换乘次数最少的情况。但是可以考虑非奥运期间的乘客的想法就会发生变化，他们主要考虑的或许是时间和费用了。因此可以将该模型进行更多方面的拓展，可以用到更多的乘车选择问题上。8.3模型推广模型讨论的是乘车的路线选取，同样我们也可以用于旅游景点的路线安排，就好比景点是站点等同处理。参考文献1 宋来忠，王志明,数学建模与实验,北京：科学出版社,2005。2 韩中庚，数学建模方法及其应用，北京，高等教育出版社，2007。3 杨学桢，数学建模方法，河北大学出版社，1999。附录程序：问题一：function way,n0,l0,n,ch,ti,co = cost( b1,c2,d,m1,s,n1,c,l1,start,end1,up,n,ch,ti,co,t,way,n0,l0) t1=0; if(t=0) f=0; ti=inf; co=inf; else f=l0(t); end n0(n,t+1)=0; n4=n0; t2=t; way1=way; n01=n; l01=l0; ch1=ch; for i=1:m1(start) for j=1:m1(end1) if(b1(start,i)=b1(end1,j) & b1(start,i)=f) if(c2(start,i)=c2(end1,j) if(sum(n0(n,1:t+1)=0) n3=sum(n0(n,1:t+1)-1; else n3=sum(n0(n,1:t+1); end if(d(start,i)d(end1,j) n0(n,t+1)=n0(n,t+1)+d(end1,j)-d(start,i); n5=n0(n,1:t+1); if(3*sum(n5)+5*t=ti) l0(n,t+1)=b1(start,i); c01=0; for k=1:t+1 if(c(l0(n,k)=1) c01=c01+1; elseif(n0(n,k)=40) c01=c01+ceil(n0(n,k)/20); else c01=c01+3; end end if(3*sum(n5)+5*tti | c01co) if(t=0) else ti=3*sum(n5)+5*t; co=c01; way=0; n0=0; l0=0; ch=0; way(1,1:n3+t)=way1(n01,1:n3+t); n0(1,1:t+1)=n5(1:t+1); l0(1,1:t2)=l01(n01,1:t2); ch(1,1:t2)=ch1(n01,1:t2); n=1; end end t=t+1; l0(n,t)=b1(start,i); ch(n,t)=s(c2(start,i),d(end1,j),b1(start,i); way(n,n3+t:sum(n5)+t)=s(c2(start,i),d(start,i):d(end1,j),b1(start,i); t1=1; n5=0; end elseif(l1(2*b1(start,i)-1)=2 & c2(start,i)=1) n0(n,t+1)=n0(n,t+1)+n1(c2(start,i),b1(start,i)-d(start,i)-1; n6=n0(n,1:t+1); n0(n,t+1)=n0(n,t+1)+d(end1,j); n5=n0(n,1:t+1); if(3*sum(n5)+5*t=ti) l0(n,t+1)=b1(start,i); c01=0; for k=1:t+1 if(c(l0(n,k)=1) c01=c01+1; elseif(n0(n,k)=40) c01=c01+ceil(n0(n,k)/20); else c01=c01+3; end end if(3*sum(n5)+5*tti | c01co ) if(t=0) else ti=3*sum(n5)+5*t; co=c01; way=0; n0=0; l0=0; ch=0; way(1,1:n3+t)=way1(n01,1:n3+t); n0(1,1:t+1)=n5(1:t+1); l0(1,1:t2)=l01(n01,1:t2); ch(1,1:t2)=ch1(n01,1:t2); n=1; end end t=t+1; l0(n,t)=b1(start,i); way(n,n3+t:sum(n6)+t)=s(c2(start,i),d(start,i):n1(c2(start,i),b1(start,i)-1,b1(start,i); n3=sum(n6); n0(n,t)=n0(n,t)+d(end1,j)-1; ch(n,t)=s(c2(start,i),d(end1,j),b1(start,i); way(n,n3+t:sum(n5)+t)=s(c2(start,i),1:d(end1,j),b1(start,i); t1=1; n5=0; end end end end if(t1=1) n=n+1; n0(n,1:t2+1)=n4(n01,1:t2+1); t=t2; way(n,1:sum(n0(n,1:t2+1)+t)=way1(n01,1:sum(n0(n,1:t2+1)+t); l0(n,1:t)=l0(n-1,1:t); ch(n,1:t)=ch(n-1,1:t); t1=0; end end end if(t=up) t=t+1; end if(t=up | t1=1) else for