奥运路径——数学建模

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

2、如果赛区设置报名号的话）： 所属学校（请填写完整的全名）： 参赛队员 (打印并签名) ：1. 2. 3. 指导教师或指导教师组负责人 (打印并签名)： 日期： 2010 年 9 月 6 日11 / 13文档可自由编辑打印赛区评阅编号（由赛区组委会评阅前进行编号）：论文题目摘要随着城市交通系统的日益发达，线路的选择问题也日益严重。本文通过对北京交通路线的分析，并从实际情况出发考虑，建立了满足查询者各种不同需求的最佳路线的查询模型，并用程序加以实现。问题一是在只考虑公汽路线时，考虑到查询者的各种不同需求建立了五个模型，分别为最短路径模型、最短时间路径模型、最少换乘路径模型、最省钱路径模型以及满意度

3、最高路径选择模型。其中，满意度最高的路径模型是通过层次分析法，给出路径长度，时间，钱数，换乘数这四个因素对应的权重，通过加权法计算各个可行路径的评价值，已给出最佳路径。问题二是在问题一的基础上，增加了地铁路线。修改了问题一的五个模型，实现更方便、准确的搜索。问题三在前两问的基础上考虑站点间的步行，修改问题二中的模型。使模型更符合现实。摘要中应特别注意的是：应以第三人称写作.摘要是完整的短文,具有独立性,可以单独使用.即使不看论文全文的内容,仍然可以理解论文的主要内容,作者的新观点和想法以及论文所要实现的目的,采取的方法,研究的结果与结论.(摘要中不能出现“我”、“我们”等表示第一人称的词语)关

4、键词：Dijkstra算法；层次分析法；加权法1 问题重述随着交通系统的快速发展，交通路线的选择问题已成为人们关注的焦点。例如第29届奥运会在北京举行期间，有大量观众到现场观看奥运比赛，其中大部分人都选择乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。要求针对市场需求，从实际情况出发考虑，满足查询者的各种不同需求，开发一个解决公交线路选择问题的自主查询计算机系统。根据已给数据解决一下三个问题。1.1 问题一仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的

5、一般数学模型与算法。并根据附录数据，利用你们的模型与算法，求出以下6对起始站终到站之间的最佳路线（要有清晰的评价说明）。 (1)、S3359S1828 (2)、S1557S0481 (3)、S0971S0485(4) 、S0008S0073 (5)、S0148S0485 (6)、S0087S36761.2 问题二要求同时考虑公汽与地铁线路，解决问题一所述的问题。1.3 问题三假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。2 问题分析2.1 查询需求分析分析查询者的需求可将问题分为以下五种情况建立模型，分别为最短路径模型、最短时间路径模型、最少换乘路径模型、最省

6、钱路径模型以及满意度最高路径选择模型，即用户可能要查询路径最短的，时间最短的，换乘最少的，最省钱的，以及综合四个因素而成的最满意的路径。因此三个问题都分为以上五种建立模型。3 模型假设(1) 假设站点之间的距离相等。(2) 假设不考虑交通堵塞和其他延误车辆速度的问题。(3) 假设相邻公汽站平均行驶时间为3分钟(包括停车时间)。(4) 假设相邻地铁站平均行驶时间为2.5分钟(包括停站时间)。(5) 假设公汽换乘公汽平均耗时为5分钟(其中步行时间2分钟)。(6) 假设地铁换乘地铁平均耗时为4分钟(其中步行时间2分钟)。(7) 假设地铁换乘公汽平均耗时为7分钟(其中步行时间4分钟)。(8) 假设公汽

7、换乘地铁平均耗时为6分钟(其中步行时间4分钟)。(9) 假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)。(10) 公汽票价分为两种，单一票价和分段计价两种，单一票价为1元，分段计价为020站：1元；2140站：2元；40站以上：3元。(11) 地铁票价为3元(无论地铁线路之间是否换乘)。4 符号说明：查询者要查询的起点。： 查询者要查询的终点。：路线所经过点的集合。： 第种交通路线乘坐公汽需要经过的所有站点个数。： 第种交通路线中乘坐线路的公汽需要经过的站数。： 第种路线需要乘坐地铁所要经过的站数。： 第种路线所需时间。：第种路线所需花费的钱数。： 第种路线中乘坐公

8、交中为单一票制1元的个数。：第种路线中乘坐地铁的次数。：第种路线需要公汽换乘公汽的次数。：第种路线需要地铁换乘地铁的次数。：第种路线需要地铁换乘公汽的次数。：第种路线需要公汽换乘地铁的次数。： 相邻公汽站平均行驶时间。： 相邻地铁站平均行驶时间。： 公汽换乘公汽平均耗时。： 地铁换乘地铁平均耗时。： 地铁换乘公汽平均耗时。： 公汽换乘地铁平均耗时。：站点到站点需要的步行时间。模型建立与求解4.1 问题一在只考虑公汽的情况下，根据用户的不同需求建立以下五种路径选择模型。由于换乘次数太多是很不合理的，最大的忍耐程度是有限的，假设最大的忍耐度为2，即最多换乘两次。可画出如下的示意图，其中=0，1，2

9、。图1. 换乘图如图1所示的换乘方式，为直达路径；，公交路线为有一条交点的路径，即需换乘一次的路径；、公交路线为有两个交点的路径，即需要换乘两次到达目的地的路径。直达路径的求法：对于线路，满足，(1)则为站点到站点的直达路径。换乘一次的路径求法：线路，满足，(2)则、为站点到站点的换乘一次的需要乘坐的路线。换乘两次的路径求法：线路，满足，(3)则、为站点到站点的换乘两次需要乘坐的路线。查找到以上三种可行路径，再用以下的方法查找出满足查询者的各种不同需求的最佳路线。4.1.1 最短路径模型由于假设各站之间的距离相等，因此最短路径也就是经站点最少的路径。首利用程序查出所有由起点到终点可行路线，并通

10、过记录每条路径所经过的站点数。因此只需求满足的路线。4.1.2 最短时间路径模型最短时间路径，即查找由起点到终点的耗时最少的路径。首利用程序查出所有由起点到终点可行路线，由于路径所耗时间包括乘车时间以及换乘所用时间，因此需记录每条路径所经过的站点数以及该路径所需换乘次数。因此只需求满足的路线，其中。 (4)4.1.3 最少换乘路径模型查找最少换乘路径，首先利用程序查出所有由起点到终点可行路线，并记录每条路径所需换乘次数，因此只需求满足的路线。4.1.4 最省钱路径模型由于公汽的收费分为两种，一种是通价票1元，另一种是分段计价的票价为：020站：1元；2140站：2元；40站以上：3元，所以要分

11、别记录该路径上乘坐这两种车的次数。查找最省钱路径，首先利用程序查出所有由起点到终点换乘在2次以下的可行路线，每条路径所需换乘次数，以及其中是通价1元的车辆次数和非通价1元的路线需要经过的站数。 (5)因此，查找最省钱路径只需找满足式(5)的路径。4.1.5 满意度最高路径选择模型综合以上四个因素，利用层次分析法可建立满意度最高路径。图2. 层次模型图建立路径满意程度的判断矩阵。 (6)矩阵通过归一化处理, (7)对式(4)中各行元素取平均可得到。 (8)矩阵的特征向量式(5)的规一化处理后得到 ， (9)。 (10)带入式(10)对矩阵的一致性检验，通过一致性检验，认为判断矩阵的一致性是可以接

12、受的，因此得出表1权重表。准则层权重0.2710.3420.284 0.103 表1. 最终的权重表因此根据表1权重的大小，可以列出下式。 (11)首先对数据无量纲化处理，再根据式(11)求出各个路线的评价值，值最小的即为满意度最高的路径。4.2 问题二将地铁线路考虑到模型中，根据假设(9)可以将地铁路线转化为公汽路线。4.2.1 最短路径模型由于假设各站之间的距离相等，因此最短路径也就是经站点最少的路径。首利用程序查出所有由起点到终点可行路线，并通过记录每条路径所经过的站点数。因此只需求满足的路线。4.2.2 最短时间路径模型添加地铁路线后，由于地铁的站点间的乘车时间、换乘时间与公汽不同，因

13、此要单独计算。最短时间路径，即查找由起点到终点的耗时最少的路径。首利用程序查出所有由起点到终点可行路线，并记录每条路径所经过的站点数以及该路径所需换乘次数、。因此只需求满足的路线，其中。 (12)4.2.3 最少换乘路径模型查找最少换乘路径，首先利用程序查出所有由起点到终点可行路线，并记录每条路径上四种换乘方式对应的次数、 ，有。(13)满足式(13)的路径即为换乘最少即可到到目的地的路径。4.2.4 最省钱路径模型查找最省钱路径，首先利用程序查出所有由起点到终点可行路线，每条路径所需换乘次数，以及其中是通价1元的车辆次数，第种交通路线中乘坐线路的公汽需要经过的站数，第种交通路线中乘坐地铁的次

14、数。 (14)因此，查找最省钱路径只需找满足式(14)的路径。4.2.5 满意度最高路径选择模型根据表1权重的大小，可以列出下式。 (15)首先对数据无量纲化处理，再根据式(15)求出各个路线的评价值，值最小的即为满意度最高的路径。4.3 问题三由于考虑到站点之间都可用步行的方式到达，而步行是要消耗时间而不需要费用的，因此最省钱的模型没有意义，改成只剩下四个模型。花费的费用依然是。 (16)4.3.1 最短路径模型由于假设各站之间的距离相等，因此最短路径也就是经站点最少的路径。首利用程序查出所有由起点到终点可行路线，并通过记录每条路径所经过的站点数。因此只需求满足的路线。4.3.2 最短时间路

15、径模型最短时间路径，即查找由起点到终点的耗时最少的路径。首利用程序查出所有由起点到终点可行路线，并通过记录每条路径所经过的站点数以及该路径所需换乘次数。因此只需求满足的路线，其中。 (17)4.3.3 最少换乘路径模型查找最少换乘路径，首先利用程序查出所有由起点到终点可行路线，并记录每条路径上四种换乘方式对应的次数、 ，有。(18)满足式(18)的路径即为换乘最少即可到到目的地的路径。4.3.4 最省钱路径模型由于考虑到站点之间都可用步行的方式到达，而步行是要消耗时间而不需要费用。考虑到走的站数越多费用越少，但步行的站点过多是不合理的，因此限制步行的站数不能多于4站。查找最省钱路径，首先利用程序查出所有由起点到终点可行路线，每条路径所需换乘次数，以及其中是通价1元的车辆次数，第种交通路线中乘坐线路的公汽需要经过的站数，第种交通路线中乘坐地铁的次数。 (19)因此，查找最省钱路径只需找满足式(14)的路径。4.3.5 满意度最高路径选择模型根据表1权重的大小，可以列出下式。 (20)首先对数据无量纲化处理，再根据式(20)求出各个路线的评价值，值最小的即为满意度最高的路径。5 模型实现6 模型评价与分析6.1鼠标左键单击该段落，输入替换之。内容为小