10203-数学建模-B20004029中南大学庞胜张剑锋汤文达
- 格式：doc
- 大小：429.50 KB
- 文档页数：23
承诺书我们仔细阅读了中国大学生数学建模竞赛的竞赛规则.我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。
我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参考文献中明确列出。
我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。
如有违反竞赛规则的行为，我们将受到严肃处理。
我们参赛选择的题号是（从A/B/C/D中选择一项填写）： B我们的参赛报名号为（如果赛区设置报名号的话）：20004029所属学校（请填写完整的全名）：中南大学参赛队员(打印并签名) ：1. 庞胜2. 张剑锋3. 汤文达指导教师或指导教师组负责人(打印并签名)：朱世华日期： 2007 年 09 月 24 日赛区评阅编号（由赛区组委会评阅前进行编号）：编号专用页赛区评阅编号（由赛区组委会评阅前进行编号）：全国统一编号（由赛区组委会送交全国前编号）：全国评阅编号（由全国组委会评阅前进行编号）：基于矩阵分析的最优公交路径选择模型摘要本文为了解决公交出行的策略选择问题。
提出了矩阵分析模型，以公交线路为节点，以公交线路是否连通为条件，建立了0-1矩阵（邻接矩阵）。
该矩阵与图论当中的无向图相对应，对于有公共站点的公交线路，对应的节点邻边赋权值1，否则赋权值0。
并通过该邻接矩阵采用Dijkstra算法得出任意两点之间的最短路,以此为基础从理论上给出了换乘次数的指标及其定理，见数据验证了北京公交网络至多3次转车可实现两站点之间的出行问题。
根据得出的北京公交线路间的最短路得出的最小换乘矩阵，可迅速得出任意两条公交线路间的最小换乘次数。
对于任意两个站点之间的选线问题，我们首先统计了经过两个站点的所有公交路线，然后从已知的北京公交线路间的最小换乘矩阵中得出这两个站点间所有公交线路的最少换乘子矩阵，并找出这两个站点间的最小换乘次数，由此将节点搜索范围局限在换乘次数最小的线路上，比普通的穷举搜索法，降低了搜索的范围。
以S0971——》S0485为例，最少经过一次转车即可到达。
如果不进行矩阵分析，要进行3082次搜索，进行矩阵分析之后，搜索的路线降低为20条，即只需进行202次搜索，计算量减小了200倍，若进行两次转车的搜索，计算量会减小2002倍，若进行三次搜索，计算量就会减小2003倍，从而用这种算法大大降低了程序的计算量，大大提高了搜索速度,得出了题目中六组站点每组站点的最少转车次数分别为1-2-1-1-2-1。
根据换乘次数的不同，我们在基于广度优先搜索的基础上给出了换乘次数为0，换乘次数为1，换乘次数为2的三种搜索方法。
对于换乘次数为0的站点，即站点间有直达车，只需搜索从起始站点发出并与终点站相交的公交路径。
对于换乘次数为1的两个站点，我们以经过起始点和终止点的公交线路为搜索对象，找出相交的两条公交路线，即为两个站点之间换乘一次的出行路线。
随着转车次数的增加，搜索的范围也越来越大，为减少搜索量，同时简化搜索方式，于最少需换乘两次的站点，我们将经过起始点的公交路上的点作为新的起始点，搜索新的起始点到终点换乘一次的公交路线，从而即可得到从起始点到终点需换乘2次的公交路线。
由此我们得出了题中所给的六组车站基于最小换乘次数情况下的出行路径，并计算出了该出行路径的消耗的时间和路费。
详见附录结果1。
地铁站的加入不仅增加了新的出行方式，同时地铁站也将上述不连通的一些公交车站联结到了一起。
我们仍旧采用邻接矩阵分析模型，根据新的线路的联通关系得出了一个新的邻接矩阵和新的最少换乘次数矩阵。
由于地铁将其周围的公交车站联结在了一起，为此我们在经过地铁的线路中引入了一个与地铁站同名大的虚拟的站点，并将其安置在相邻的公交站旁。
将其转化为问题一，得出了换乘次数最少的出行路线。
详见附录结果2。
针对问题三，根据人们的心理偏爱，人们只会在站点间距离很短的情况选择步行。
在找出了两条公交路线路间步行距离最短的站点后，这两个站点为原本两条不相交的行车路线提供了一种步行换乘的方式。
比较乘车换乘和步行换乘两种路线用时的长短，若步行比较省时，可用步行的方式来代替换乘即可。
关键词：矩阵分析广度优先搜索换乘替代换乘指标一、问题重述我国人民翘首企盼的第29届奥运会明年8月将在北京举行，届时有大量观众到现场观看奥运比赛，其中大部分人将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。
这些年来，城市的公交系统有了很大发展，北京市的公交线路已达800条以上，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。
针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。
为了设计这样一个系统，其核心是线路选择的模型与算法，应该从实际情况出发考虑，满足查询者的各种不同需求。
需要解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。
并根据附录数据，利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。
(1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485(4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S36762、同时考虑公汽与地铁线路，解决以上问题。
3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。
题目的附录1给出了票价和时间的基本参数设定。
二、模型假设与符号说明1．问题假设（1）乘客总会选择转乘次数最少，出行时间最短，而且消费最低的路线。
（2）各路公交的形式路况一样，也就是说，忽略因路况不同而引起乘客选择的变化。
（3）各路公交车都能正常行驶。
2．符号说明A ——城市交通系统所对应的邻接矩阵B ——最少换乘次数矩阵D ——最小换乘子矩阵1l ，2l ——给定的两条公交车线路ij a ——城市交通系统所对应的邻接矩阵中第i 条线路与第j 条线路的关联关系ij b ——最少换乘次数矩阵中第i 条线路到第j 条线路需转乘的次数pq d ——由过A 站点的第p 个公交线路转到过B 站点的第q 个公交线路所需的转车次数。
三、问题背景及初步分析3.1 问题的社会背景本文研究的是北京市公交系统资助查询问题。
北京市成功申办2008年奥运会，举国同庆。
随着奥运会开幕的时间越来越近，各个方面的问题接踵而来。
交通问题是世界上大中型城市的一个普遍的问题。
为了满足广大人民的出行要求，优化公交资源的配置，进行公交线路查询系统的研究有着比较重大的意义。
3.2 问题的研究背景目前应用较广泛的公路网络最短路径算法有Dijkstra 算法、Floyd 算法和Moore Pape 算法。
无论是距离最短，时间最快还是费用最低，他们的核心算法都是最短路径算法。
经典的最短路径算法——Dijkstra 算法是目前多数系统解决最短路径问题的理论基础。
该算法基于图论中的网络图模型，用标号的算法不仅求出从起点到终点的最短路径，然后所得到的实际上是从起点到它的各个节点的最短路径，所以在求解时，其算法的时间复杂度为2()O N 。
由此可以看出，在实际模型的节点数N 较大情况下，算法的计算时间成幂次增长，一般的计算机甚至无法运行，很难满足实际的运算需要。
在讨论最优路线的问题上，人们一般都注重解决任意两点间的最短路径问题。
但是，对最短路径来讲，只要两个顶点之间有边存在，它就可以进行搜索，而不去考虑该路径的换车代价，这就可能造成搜索得到的最短路径需要换多次车。
因此，这样的最短路径虽与司机来说，有着较为重要的意义，但是对于旅客来说却不一定是最佳选择。
对旅客而言，在半路上换车是个相当敏感的问题，因为换车的次数越多，意味着花费的时间和金钱越多。
这也是Dijkstra 算法不能实现该运算的原因[1]。
3.3 乘客心理的分析杨新苗等1999年在南京市的8个主要的公交站点进行了公交出行心理问讯调查，调查表明公交乘客选择出行路线时主要考虑的因素有3个：首先是换乘最少，其次才是时间最少、路程最短[2]，如图：图1 公交乘客出行心理分析图[2]乘客都有要求便利的心理特征，因此，一般来说，在可以直达的情况下，乘客不会转车，转一次可以到达，乘客就不会转两次。
因此，可设转乘次数最少为乘客挑选路线的首要标准，在此基础上，挑选时间最短和花费最少的方案。
四、 基本矩阵分析模型的建立与算法分析（问题一求解）4.1 背景知识邻接矩阵是图论中的重要理论, 邻接矩阵和图之间有着一一对应的关系, 即从邻接矩阵可以画出唯一的图, 反之, 根据图可以写出唯一的邻接矩阵. 具体的讲, 对于有n 个要素的系统()1,2,3,,p p p pn ， 定义邻接矩阵A 如下：[]ij A a =， 式中,10ij a ⎧=⎨⎩ 当线段从p I 向着p j 时, ij a 值为1， 否则为0。
利用图论方法研究问题日益广泛，首先将研究的对象抽象成一个图。
图的顶点表示事物, 图的边表示事物之间的联系, 然后根据图的性质和有关的理论进行研究。
受此启发，在解决本文所提出的问题时，可以首先通过图论知识建立邻接矩阵，然后对邻接矩阵进行一系列的分析，最终得出结论。
4.2 模型建立4.2.1 邻接矩阵假定某城市共有n 条公交线路，若不靠虑方向（即上行下行问题），可以把n 条公交线路抽象为n 个顶点，任意两条公交线路之间的联系取决两者之间有无交点(共同的停靠站点)，相应地该两条线路之间的矩阵元素值为1 或者0，这样就把城市公交线路系统可以抽象为n*n 邻接矩阵。
可以借用邻接矩阵的特性和算法，来解决公交线路换乘问题。
不失一般性，我们假定某城市有1路、2 路、3 路、4 路这四条公交线路, 记为L1、L2、L3、L4，如图所示：图2则组成的邻接矩阵为1010010110100101A⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦由此，可以方便的看出四条公交线路的连接关系。
当1ija=时，表示第i条线路和第j条线路之间相互连通，即从第i条线路到第j条线路经一次转车即可到达。
当0ija=时，表示第i条线路和第j条线路之间相互不连通，即从第i条线路到第j条线路经一次转车不能到达。
4.2.2 最少换乘次数矩阵的提出及分析为了进一步的研究，可以提出最少换乘次数矩阵的概念，即有最少换乘次数矩阵[]ijB b=，其中ijb表示从第i条线路到第j条线路需转乘的次数，0iib=，1,2,ijb=，根据上例，可以写出0211201111021120B ⎡⎤⎢⎥⎢⎥=⎢⎥⎢⎥⎣⎦由此矩阵可以看出，L1经两次转车可以与L2线路连通，L1线路经一次转车即可与L3线路连通。
