
高教杯数学建模竞赛——公交查询系统【数学建模】.doc
6页高教杯数学建模竞赛——公交查询系统【数学建模】 公交查询系统核心算法的讨论 摘要 问题一,我们采用C++?编程S3359→S1828在S3359站乘436路(下行)在S1784转167路车(下行)到终点S1828 S1557→S0481行车线路:在S1557站乘0084路(下行)在S1919转189路车(下行)在S3186转460路下行车到终点S0481 S0971→S0485行车线路:在S0971乘013路(下行)在S2184转417路车(下行)到终点S0485 S0008→S0073行车线路:在S0008乘坐355路(下行)在S2303转345路车(上行)到达终点S0073 S0148--S0485行车线路:在S0148乘坐308路在S0036转156路车在S2210转417路车到达终点S0485 S0087→S3676行车线路:在S0087乘坐454路(上行)在S3496转209路车(下行) 到达终点S3676 问题二,考虑到地铁站时,我们采取一种方式:例如T1号线,我们把这条地铁线经过的所有的公汽站点依次罗列,这样就构成了一条较长的公汽行车线路,当然,原来在同一个地铁站的公汽站点被处理成了相邻的公汽站点,我们可以对程序输出这样的可行路线进行观察,进一步处理,将那条较长的公汽线路再转换成地铁路线,这样,就可以求出实际的行车路线。
其中,在问题二中,考虑地铁站之后,新线路的耗时可能会减少,例如S0008→S0073 行车线路:150路(下行)转(3874――D30)T2路车再转(D25――0525)S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485 (4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676 2、同时考虑公汽与地铁线路,解决以上问题 3、假设又知道所有站点之间的步行时间,请你给出任意两站点之间线路选择问题的数学模型 2 问题分析 2.1 问题分析时应该考虑的各种因素 公交查询系统的应该根据乘客的要求来设计对于大多数乘客来说,选择路线时最先考虑的是转乘的次数要少,其次是所选的路线的行车耗时,再者是路线的费用;但是也不排除有的乘客的考虑因素的侧重点不同 2.2 转乘次数、行车耗时、费用之间的关系 一般来说,转乘的次数决定了行车耗时和费用但是在有地铁的情况下,增加一次或者两次转车,可能会缩短行车耗时,但这毫无疑问增加了费用所以,转乘次数、行车耗时、费用对选择路线的重要性依次递减,但当路线中出现地铁的时候(即问题二所考虑的情况)应该考虑运行的费用。
2.3原始数据处理 一般的公路查询系统的数据的格式都采用数的形式存储,里面包括线号以及站号等信息,本文的数据处理非常简单,只是把把数据以数组的形式存起来,每条线路(L001―L520)包括上行线及下行线,共1040行,每行中储存的是路线上依照行驶到达顺序的站点号码,这样可以根据行号确定改改行站点号是那一条公交线路,实上行的还是下行的当处理地铁时,把两条地铁线加在公交路线的后面,代号由D1,D2改为L521,L522,在数组中添加四行来增加两条地铁的上下行路线 2.3对于算法的选择 一点需要说明的是求最短路径一般使用Dijkstra算法,该算法可求出任一源点到其它所有网络结点的最短路径但是,我们的目的是求得任意一个点到另外任意一个点的最优路径,用这一经典算法算出的结果太繁杂,太浪费时间;所以,我们将起点和终点两头考虑,利用广度优先算法,这样行车线路查找范围就大大缩小了,当然,对于这种算法,站点和行车线路之间要灵活考虑,力求算法最简、最优 3 模型建立及求解 3.1 问题一 设: 1、考虑到实用性,3次以上的换乘不会被查询者接受; 2、假设该地区的公交运行状况良好,很少出现堵车现象; 3、假设当两个转乘站之间的距离小于等于两站时,可以选择步行; 明: A ―― 起始站点; B ―― 终点站; Ti ―― 转乘站点; 模型建立与算法分析 在题目所给的520条公汽线和2条地铁线中,考虑一对的车站间的最优路径,从不同的衡量角度有不同的结果,若从换乘次数考虑,则首先,最容易想到的是直达,如(图1) 图1 我们用C++编程来解决查找行车路线问题,然后再根据不同的衡量标准来确定最优解,下面再介绍另一种情况:换乘1次,如(图2),T1,T2为中转站: 图2 对于以上两种情况,我们编写了程序1.cpp。
对题目要求的6对车站进行了求解,求得了所有经过直达或转乘1次的行车路线,并依据不同的衡量角度对结果进行了求取最优路径 下面介绍一下程序1.cpp算法: 首先导入题目所给数据,一共520路行车路线,每条路线包括上下行,构成共1040条单向路线,在程序中,我们用1040×100的二维数组获取所有的站点信息,其中数字100是用来存放每条线路所包含的站点,接下来的算法是对这一个二维数组进行处理: 零次、一次换乘 零次换乘即在起点A和终点B之间有公交车直接往返,用户无需经过换乘就可以直达目的站点(如下图) 一次换乘即在起点A和终点B之间没有公交车直接往返,用户需要在途经的某个站点下车,然后转乘另一线路公交车才能到达目的站点 首先获取起点A和终点B; 求出所有经过起点A和终点B的线的集合R(A)和R(B),在集合R(A)中,将任意一条路线上点A以后的点求出,构成一个点的集合point(A),在集合R(B)中,将任意条路线上点A以后的点求出,构成一个点的集合point(B),图3中的小叉圆表示 图3 设定一个循环,比较集合point(A)和point(B)中的每一个站点,如果有相同的站点T,则由路线连通A,B,此时再比较相同的站点T,如果T属于同一行,则存在至大路线,如果不同那就是要转一次车; 如果仍然查找不到换乘方案,可以考虑两次换乘。
我们接下来讨论两次换乘的情况如(图4): 两次换乘: 两次换乘就是当经过一次换乘不能到达目的地时,例如题目所给数据的第2组(S1557-S0481)和第5组(S0148-S0485),利用两次换乘可以扩大选择线路的范围,增大存在可行路线的概率,2.cpp对二次换乘的算法进行了描述 获取起点A和终点B; 求出所有经过起点的线的集合R(A),在集合R(A)中,将每条路线上点A以后的点求出,构成一个点的大集合point(A),图4中的小叉圆表示 以集合point(A)中的每一个点为源起点,从上图中的T1到B作一次换乘计算,如果T2点存在,即可以求出T2点 这样A- T1- T2- B就构成了一条经过两次转乘的行车路线如果还没有找到,则进行三次转乘,但是两次转乘的路径覆盖已经很广,三路转乘只是为了得出更短的路径,当然,这是以转乘次数为代价的 三次转乘 经过三次转乘之后,我们没有必要再考虑四次转乘,因为其路线的覆盖已经近100%,况且四次转乘的路线一般不会被乘客采纳3.cpp对三次换乘的算法进行了描述,以下是四次转乘的示意图(图5)和算法: 图5 获取起点A和终点B; 求出所有经过起点的线的集合R(A),在集合R(A)中,将每条路线上点aa以后的点求出,构成一个点的集合point(A),图4中的小叉圆表示; 求出所有经过起点的线的集合R(T),在集合R(T)中,将每条路线上点bb以前的点求出,构成一个点的集合point(B),图4中的小叉圆表示; 设定一个双循环,使得point(A)任意一点T1与point(B)中的任意一点T3点都能组合一次; 对T1与T3的每一对组合进行一次换乘计算,这样,构成的A―T1―T2―T3―B 线路就是所要求得三次转乘线路;如果连经过三次转乘都没有可行路线,则说明该地区公交线分布存在缺陷。
多次换乘 通过以上的三次以内的换乘求解规律,我们不难得出多次换乘的求解方法,多次换乘方案的计算,实际上是一次换乘计算的递归执行而超过三次换乘的方案,一般是用户不能接受的,本文不再详细求解 根据以上的基于换乘次数的行车路线,我们可以求得耗时最短的行车路线,也可以求出花费最少的行车路线,一般情况下,换乘次数少,花费少;从起点到终点经过的站点少,耗时就少 分析求解 在仅考虑公汽线路的情况下为了满足广大市民的不同乘车要求分类对行车线路进行筛选首先我们分析出一条线路所包含的信息有:转车次数,车次,行车站数,行车耗时,花费钱数 利用我们编写的程序可以在已知始发站与终点站的情况下,查找出所有的可能乘车路线,路线分为四类:直达车,转乘一次,转乘两次,转乘三次(我们遍例了所有的车站之间的行车路线最高三次就能完成)并已经过车站数目为首要因素对所有可能的线路进行排队并取前五位候选这样就列出了一些乘车线路作为被选路线 我们再对人们出行乘坐公交选择路线考虑的不同因素进行分析我们发现人们有时想以最快的乘车方式到达目的,以节省时间;有时想花较少的钱到达目的地,浪费点时间无所谓;有时想减少换乘车辆的次数,少走些路;更为复杂的时候,北京交通繁忙繁华地段经常堵车,有的人更愿意乘坐地铁这种交通工具,因为它非常守时。
为了综合考虑各个因素我们试图对不同选择因素的权重进行分析,但我们考虑到实际情况下,人们乘坐公交选择路线时往往是考虑比较单一的因素也就是说我们再给不同因素付权重的时候只要根据不同的需求将某一因素负值为一即可即当希望尽快到达目的时可以仅考虑时间进行挑选,当希望少花钱时就以花钱多少作为标准进行挑选 当然在输出乘车线路时我们间输出多条路线被选,以便个人综合考虑各种因素的影响 下面是利用我们的模型与算法,以下6对起始站→终到站之间的最佳路线要以及全面的评价说明 (1)、S3359→S1828 (2)、S1557→S0481 (3)、S0971→S0485 (4)、S0008→S0073 (5)、S0148→S0485 (6)、S0087→S3676 以上六组数据在不考虑有地铁的情况下没有可以直达的车辆存在,(1)、(3)(4)、(6)组最少转乘一次公车才能到达目的地,(2)、(5)组最少转乘两次才能到达目的地 注:程序计算的可供选择路线见“问题一附录” : 第一组S3359→S1828 1、换乘次数最少: 在S3359站乘436路(下行)在S1784转167路车(下行)到终点S1828 途经车站数 32 花费 3 元 耗时 101 分钟(可步行,走一站节约一元) 2、耗时最少: 在S3359站乘015路(下行)在S2903转485路车(下行)在S1784转167路车下行到终点S1828 途经车站数18 花费 3 元 耗时64 分钟(可步行, 走两站节约两元) 3、花费最少 在S3359站乘436路(下行)在S1784转167路车(下行)到终点S1828 途经车站数 32 花费 3 元 耗时 101 分钟(可步行,走一站节约一元) 第二组S1557→S0481 换乘次数最少: 行车线路:在S1557站乘0084路(下行)在S1919转189路车(下行)在S3186转460路下行车到终点S0481 途经车站数32 花费 3 元 耗时 106 分钟(可步行三站节约一元) 耗时最少: 行车线路:在S1557站乘084路(下行)在S1919转189路车(下行)在S3186转091路下行车在S0902转239路下行车到终点S0481 途经车站数28 花费 4 元 耗时99 分钟 花费最少: 行车线路:在S1557站乘363路(下行)在S1919转189路车(下行)在S3186转460路下行车到终点S0481 途经车站数32 花费 3 元 耗时106 分钟(可步行三站节约一元) 第三组S0971→S0485 换乘次数最少: 。
