高教杯数学建模竞赛公交线路的自主查询系统 数学建模

高教杯数学建模竞赛——公交线路的自主查询系统【数学建模】公交线路的自主查询系统摘要本文首先对数据进行处理和分析，根据图论中加权有向图的理论建立了公交站的最小站距矩阵，表示站到站的最小站数。利用该矩阵进行全搜索解决了一个由公共汽车和地铁组成的公交系统的最佳线路选择问题。我们以考不考虑“利用地铁站公汽换乘公汽”为区别，将问题（1）分为两部分。首先不考虑利用地铁站公汽换乘公汽，我们通过对规划目标的讨论、公汽线路信息的研究、各站之间最小站程的确定和可行线路的搜索以及最佳线路的选择，逐步建立起用于选择最佳线路的全搜索模型，用此模型对题中六组数据进行了求解并进行了清晰、详尽的检验和评价。接下来利用地铁站公汽换乘公汽，我们构造了一个虚拟公交线路的方法，将同一地铁站周围的公交车串联起来，通过全搜索解决了该问题，并同样对六组数据进行了求解和分析。问题（2）中，我们再次运用改进后的全搜索模型，结合公汽-地铁网的特点，建立公交站的最小地铁站距矩阵，方便了模型的求解。对六组数据进行求解后，结合上文所有结果对各种因素进行了整体评价。问题（3）中，我们从实际出发，定性分析了步行的作用和对最佳线路选择的影响，并构造了该问题的模型和算法。我们的模型效率较高，能够满足查询者的各种不同需求，有很强的实用性。对六组数据在不同条件和要求下的求解结果见表1至表7，我们认为最佳线路的判别标准为：综合考虑换乘次数、时间、车费，根据个人的不同需求得出最佳线路。关键词：公交线路、最小站距矩阵、虚拟线路1问题的重述第29届奥运会明年8月将在北京举行，届时到现场观看奥运比赛的大部分观众将会乘坐公共交通工具（简称公交，包括公汽、地铁等）出行。这些年来，城市的公交系统有了很大发展，公交线路繁多，使得公众的出行更加通畅、便利，但同时也面临多条线路的选择问题。针对市场需求，某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。设计这样一个系统需要注意：一．线路选择的模型与算法必须利于程序的实现；二．应该从实际情况出发考虑，满足查询者的各种不同需求。请你们解决如下问题：1、仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录（公交线路及相关信息数据），利用你们的模型与算法，求出以下6对起始站→终到站之间的最佳路线（要有清晰的评价说明）。(1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485(4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S36762、同时考虑公汽与地铁线路，解决以上问题。3、假设又知道所有站点之间的步行时间，请你给出任意两站点之间线路选择问题的数学模型。为简化问题而设的基本参数：相邻公汽站平均行驶时间(包括停站时间)：3分钟相邻地铁站平均行驶时间(包括停站时间)：2.5分钟公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元地铁票价：3元（无论地铁线路间是否换乘）2符号说明编号为的公汽站点编号为的公汽线路编号为的地铁站点编号为的地铁线路从起始站到终到站所需的时间（单位：分钟）从起始站到终到站所需的费用（单位：元）最小公汽站距矩阵最小公汽站距对应的线路编号矩阵最小地铁站距矩阵最小地铁站距对应的线路编号矩阵从起始站到终到站的一条可行线路可行线路相关信息矩阵公汽线路信息数组公汽站点信息数组地铁站换乘公汽信息矩阵其余一些不常用的变量在文章中用到时会在后面注明。3问题的初步分析3.1问题的假设选择公交线路是日常生活中经常遇到的问题，每个人对此都有一些感性的认识，比如宁可绕点圈子也不愿反复换乘车（因为等车的时间总比坐车的时间感觉漫长）等等。基于此，我们的模型联系实际做了一些假设和近似，这与题目“从实际情况出发”的要求也是一致的：（1）公汽线路间的换乘只能是在同一公汽站或是在对应的地铁站；（2）从起点步行至通过地铁站相连的车站和从某站（通过地铁站与终点相连）步行至终点所花费的时间不计入总乘车时间。（3）在公汽线路的环线上乘车经过起始站/终到站不另外收费，且环线上有顺时针和逆时针两种走法；（4）多数人们至多只能接受转两次车，所以我们假设不管耗时或花费多少，优先选择转两次以内的车能够到达的线路（当然如果无论如何两次之内到达不了的话只能转两次以上）。事实上，如果换乘次数不限的话将有无数条可行线路；3.2问题的层次通过分析，得到三个问题之间的层次关系为：3.3需求分析要开发此公交线路选择的自主查询计算机系统至少需要满足以下要求：第一，模型的算法要利于程序的实现和在现实中的推广应用。即用户输入起始站和终到站两个参数后要在尽量短的时间内得到最佳的公交线路走法。第二，要满足查询者的各种不同需求。所谓“不同需求”一是乘公交的时间要尽量少，二是车费要尽量少，三是转车次数要尽量少；因此我们认为，算法简单易行是本文建立模型的最重要标准。3.4研究方向与算法选择一．如果将此公交系统看成一个赋权图(其权为各站点之间所用时间或车费，其方向为线路类型所决定的行驶方向)，这就是一个求最短路问题，但又不是一般的最短路问题，因为各边的权有时间和费用两种，而在各站点又有换乘时间等不定因素的影响。即使分别赋两种权，运用Dijkstra标号法求最短路对换乘费用的处理仍难以操作，需要加以改进。二．由于某段的线路选择会直接影响下一段线路的选择以及全局最优线路的结果，这就启发我们从全局的角度去建立模型：首先求出任意两站之间的最短距离，结合时间和费用的计算方法给所有邻接线路赋权；然后按照换乘的次数（即图的通路上的边数减1）分别求出换乘次数一定的最佳线路；最后比较所有线路得到全局最佳线路。事实上，模型的核心算法是换乘次数一定时对所有可行线路的搜索，这种搜索通过对各站点的搜索，得到所有可行线路并比较出最佳线路。三．附录中的数据量很大，尤其是公汽线路（线路有520个，站点有3957个），且乘车方式多元、换乘情况复杂。画图并从图中找规律的尝试是行不通的，这就需要将各个站点和各条线路的数据矩阵化，通过有序而全面的搜索，用编程的方法实现，因此，关键是在编程的过程中大胆假设、分清主次、简化算法。4数据处理数据的处理是和我们的模型与算法密切相关的，即有什么样的模型算法就对应着特定形式的数据处理。根据上面对问题的分析，在解决该问题的过程中，我们要找的最佳路线，是通过搜索出所有可能线路对应的目标值、然后比较目标值得到的。而搜索的对象就是跟优化目标密切相关的数字矩阵。我们可以通过以下的方法进行数据处理：把“1.1公汽线路信息.txt”、“2.1地铁T1线换乘公汽信息.txt”和“2.2地铁T2线换乘公汽信息.txt”三个文本文件导入到5相关理论应用构造，表示第个站点，为车站的总数。如果到有直达线路，则从到画有向弧，就对应于从到的一条有向线路；又定义为所对应的站距，这样就将公交线路网抽象为一个赋权有向图。求从到的一条最佳线路，就转化为中的最短路问题。6模型的建立题目的要求是给出任意两站点之间的最佳线路。所谓最佳线路不外乎是指某个指标（时间或费用）最小的线路，对此指标的探讨和计算就是我们建立模型的目的。通过问题的分析，给出此规划模型的一般形式：其中为某可行线路，而为此线路所需的时间，为此线路所需的费用。和是对次线路的某些限制。现在，要运用全搜索等方法对其进行求解。7问题（1）公汽站点间的线路选择在该问中，题目要求根据附录数据，仅考虑公汽路线，给出任意两站之间路线选择的数学模型和算法。而在附录数据中，关于公汽路线的有两种数据，一种是仅有公汽的数据，另一种是关于公汽和地铁的数据。现在的问题就是用还是不用后一种数据，我们不妨这样处理：把两种情况都算一下，等结果出来后，在分析用还是不用。7.1不考虑地铁站换乘的全搜索模型目标的讨论由于公众乘坐公交的原因有二：比步行或骑自行车省时、比坐出租车省钱，那么在选择公交线路时省时和省钱两个方面都必须考虑。提出双目标规划问题：其中，和表示可行线路所要满足的某些条件。根据公众的乘车要求和习惯不同，我们分以下三种情况讨论：一．选择不同的线路只有几元钱的花费差别，对于不太计较几元钱得失的乘客来说，节省时间是最重要的，需要将作为规划目标；二．有些人乘公交的选择主要源于出租车的高昂价格，因此乘公交的价格稍高的话就会使其难以接受，对这部分人来说，宁可多花点时间，最小才是重要的；三．由于公众的心理作用，有些人很在意转车的次数，即使只是多转一站，因此，必须将换乘次数也考虑在规划目标之内。需要指出的是，以上规划目标的选择是考虑一般情况的结果，并非必须如此。当然以上三种选择基本上可以满足公众的需求。线路信息的研究公汽线路的类型是有差别的：一．按票价信息分为：单一票制和分段计价，反映在信息表每条线路的第二行；两种线路有不同的收费方法。二．按线路的循环模式分为：单线（分为上下行不一致的Ⅰ型和上下行一致的Ⅱ型两种）和环线（设为Ⅲ型），反映在信息表每条线路的第三、四行；两种线路有不同的计站方法；为此，我们把公汽线路信息表做成如下的结构数组――“公汽线路信息数组”：一．第条公汽线路的信息占用数组中的第到行，（）；二．对第条公汽线路：（1）第行为线路编号，以字符开头；（2）第行为票价信息，以字符“单”（代表单一票制）或“分”（代表分段计价）开头；（3）第、行的内容对不同循环模式的线路有所区别：对于Ⅰ型线路，第行表示上行线路，以字符“上”开头，第行表示下行线路；对于Ⅱ型线路，第行表示全程线路，以字符“”开头，第行是空字符；对于Ⅲ型线路，第行表示全程线路，以字符“环”开头，第行是空字符。截取中的一段以说明其结构：注：主要用于对线路编号、票价信息和线路循环模式等公汽线路的整体特征进行区别和标识。此外，为方便对每条公汽线路中具体的站点进行提取和计算，还需要建立一个能反映站点情况的“站点信息数组”，为的矩阵，每一行的内容和相同，只不过将其中每一行中的站点字符串转换为以站点的编号为值的数字，且每个数字占据一个元素位置，其余字符串舍去，空格用0补齐。同样，截取中的一段以说明