乘公交看奥运_第1页
乘公交看奥运_第2页
乘公交看奥运_第3页
乘公交看奥运_第4页
乘公交看奥运_第5页
已阅读5页,还剩22页未读, 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

1、公交查询系统最佳乘车方案研究与设计摘要本文主要利用改进的邻接算法解决多需求下公交线路的选择问题。本题建立模型求解后主要实现如下功能:用户发出请求,系统优先为用户提供直达的公交线路,若无直达线路,分别为用户提供转乘次数最少、耗时最短、费用最低三种线路作为备选线路,同时,在相同换乘次数内,按照乘车时间由少到多为用户提供多条相对较优的乘车路线,并给出相应的乘车费用作为参考,由用户自主选择满足其需求的乘车路线。问题一,依题意在数据处理阶段将不同公交汽线路抽象化,建立站点间直达线路信息存储结构元胞,基于直达线路数据库构造站点间以直达线路数目为元素的邻接矩阵,在邻接矩阵构成的数据结构之上,考虑公汽线路不同

2、票价、线路等条件,采用改进的邻接算法分别以转乘次数最少、耗时最短、费用最低为目标进行全局最佳路线的求解。问题二,在问题一的基础上考虑公汽与地铁混排,将地铁站点与周围的公汽站点集抽象为同一新站点,把以上公汽线路站点映射为新站点,建立新的直达数据库,结合地铁费用、地铁与公汽间的换乘时间以及两者站间行驶时间等条件,将地铁与公汽结合的问题转化为问题一,采用改进的邻接算法得到不同目标下的多种优化方案。问题三,根据问题一与问题二基于换乘次数最少逐步分析目标选定最佳路线的模型,在知道所有站点之间的步行时间的基础上,建立以步行代替短距离减少换乘次数和以步行邻边化减少出行用时的优化数学模型,采用广度优先算法,改

3、进公交线路的路线选择方案。本文中公交出行以达到用时短、费用低、换乘少等目标而涉及的公交线路安排问题可以归结为不同权值含义下的最短路问题,作为运筹学与图论中的经典优化问题,本文所建立的数学模型与求解方法具有较强的现实意义。关键字: 直达数据库 邻接算法 步行邻边化 广度优先算法一、问题重述第29届奥运会明年8月将在北京举行,作为城市枢纽的公共交通承担着非常重的运输任务。近年来,北京市的公交系统有很大的发展,公交线路的条数和公交车数量在迅速增多,给人民生活带来便利的同时,也面临多条线路得选择问题,有时出行往往还需要转乘多辆公交车才能到达目的地。如何在短时间、换乘次数最少、成本最低的情况到达目的地,

4、是人们所关注的问题。因此,我们通过建立线路选择的模型与算法,设计一套自主查询计算机系统,查询到出行时所需的最佳公交路线及换乘方法,给人们出行节约更多的时间和金钱。要求:1. 仅考虑公汽线路,建立任意两公汽站点之间线路选择问题的数学模型与算法。并求出以下6对起始站终到站之间的最佳路线。(1)S3359S1828 (2)S1557S0481 (3)S0971S0485(4)S0008S0073 (5)S0148S0485 (6)S0087S36762. 同时考虑公汽与地铁线路,解决1中问题。3. 如果所有站点间的步行时间已知,建立任意两站点间路线选择问题的数学模型。二、问题分析2.1 受限条件分析

5、2.1.1 约束条件繁琐度高1公交线路中的票价问题分为单一票制和分段计价两种不同情况;2耗时问题分为站点耗时和换乘耗时两类;3最短路径已非传统意义上距离的最短化,需要综合考虑所经站点数、步行距离和换乘次数等多方面因素。上述各种因素所形成的约束使本问题并非常见图论问题,难以直接应用图论知识解决。 数据(信息)量大所研究的北京市公交系统,共有公汽线路520条,站点3957站,单条线路对应站点约5060个;地铁线路2条,站点39站。线路与站点间的对应关系复杂,考虑换乘情况,运用现有的Dijkstra、Floyd等图论算法,处理该数量级数据量,时空复杂度高,时效性低,不能满意解决本问题。2.2 乘客选

6、择线路分析乘客需求的多样化乘客在进行公交路线选择时,考虑的因素多种多样,有的乘客会侧重考虑出行费用;有的乘客会侧重考虑出行耗时;有的乘客(如老年人、残疾人等)会侧重考虑换乘次数;较为特殊的情况时,乘客还会根据个人喜好考虑途经站点、公交服务质量等多种因素。基于以上多样化的需求情况,针对公交线路选择,本文确定以下三个目标:出行耗时最短、出行费用最少、换乘次数最少。 换乘次数无上界1统计计算附录中数据,发现站点间换乘次数与到达率之间具有如下关系:图1 站点间换乘次数与到达率关系图表1 站点间换乘次数与到达率换乘次数012345到达率0.02530.40080.93930.99870.9999931分

7、析图1/表1:直达线路覆盖较少,仅为2.53%,但当换乘次数达到3次时,站点间到达率为99.87%,接近100%;换乘次数为5次时到达率为100%,故换乘三次已基本满足乘客出行需求。2.对于本问题,容易想到通过不断增加换乘次数以减少乘车时间或乘车距离,但是,查询资料后得到北京公共交通集团关于乘客对换乘次数的接受率的统计图表:图2 乘客对换乘次数的接受率表2 乘客对换乘次数的接受率换乘次数012345接受率176.04%25.32%0.04%(7.02e-4)%0分析图2/表2:几乎没有乘客接受4次换乘或更多次换乘的出行方案。从人性化角度考虑,不能无限次的增加换乘次数。因此本题仅考虑换乘次数最多

8、为3次的线路方案。2.3 问题分支分析2.3.1 问题一分析对于问题一,题目给出的公汽线路主要分为上下行线、原路折回线及环行线,线路不同,选择不同,故对每种线路需要进行抽象化处理。站点较多,可以利用图论知识描述该公交网络:即将每个站点转化为图论中图的每个节点,线路转化为邻接边,在边的信息中包含线路名、票价、行驶方向等。依据转化思想将寻求不同目标下的问题转化为图论中不同有向赋权图中内寻求最短路的问题。设计合适的算法在图论中寻求三种目标下的最佳路线。2.3.2 问题二的分析对于问题二,对于两条地铁线路,依据问题一中的抽象化方法进行抽象化处理;对于地铁站点,由地铁与邻近公汽站点可换乘的信息可知地铁站

9、点及其周围的公汽站点距离较近,考虑将其抽象化归一为新的站点,减小站点差异性,重新构造站点间的邻接矩阵。基于问题一更新数据,寻找合适的算法组合不同路线及站点分别给出三种目标下的最优方案。 问题三的分析考虑公汽站点与地铁站点的实际分布情况,在某些转乘点存在步行小段距离再转车可以节省时间或减少转车次数的情况,在求解时需确定线路中该类选择多样化的站点,然后主要优化该类站点后继线路的选择方案,达到以上三个目标。三、模型假设1、车站站点无重名; 2、相邻站点间平均行驶时间一定; 3、公交运行顺畅:无交通阻塞、无车辆故障、无道路交通事故等意外情况;4、公交准点到达,不考虑红绿灯等待时间;5、各路线公交车发车

10、频度相同;6、限制最多换乘车次为3次。四、符号说明符号符号说明相邻公汽站平均行驶时间(包括停站时间),为3分钟相邻地铁站平均行驶时间(包括停站时间),为2.5分钟公汽换乘公汽平均耗时,为5分钟(其中步行时间2分钟) 地铁换乘地铁平均耗时,为4分钟(其中步行时间2分钟) 地铁换乘公汽平均耗时,为7分钟(其中步行时间4分钟) 公汽换乘地铁平均耗时,为6分钟(其中步行时间4分钟)从站点乘车到达站点站点到达站点所用的最少时间值(分钟)站点到达站点的步行次数公汽单一票价1元公汽分段计价(020站:1元;2140站2元;40站以上:3元;=1,2,3)地铁票价3元乘客总路程所花的时间乘客总路程所花的费用乘

11、客总路程经过的公交站数(不含起始站)乘客公汽换乘公汽的次数乘客总路程经过的地铁站数(不含起始站)乘客公汽换乘地铁的次数乘客地铁换乘公汽的次数乘客乘坐的单一票价公交路线数乘客乘坐的分段公交路线数(分三个级别,=1,2,3)公汽的票价函数(元)整型函数 ,其值为1或0换车的两站之间所隔的站台数五、模型的建立与求解5.1 问题一 模型建立与求解本问题主要研究任意两公汽站点间线路选择的数学模型与算法。5.1.1 模型准备1、确定目标分别在不同行程需求下推荐最佳路线,根据实际情况得到以下三个目标:(1) 换乘次数最少;(2) 行程耗时最少;(3) 行程费用最少。2、对三种公汽线路进行抽象化处理(1)上、

12、下行线原路返回线路这种线路有两个端点站,在两个端点之间双向行车,并且两个方向上的行车路线相同,经过同样的站点序列。由于线路的方向不同,故上行线和下行线抽象为两条线路处理。(2)线路为环行线实际情况中环形路线一般是双环,但在对这两条线路进行抽象时,为保证任意两站点距离最近,把每条线路抽象为两条,即环形抽象为顺时针2个半环、逆时针2个半环共计四条线路。(3)下行线与上行线经过站点不同由于下行线与上行线经过站点不同,该种线路显然抽象为两条不同线路。图3 不同公汽线路的抽象化 3、换乘次数直观化表示换乘次数可分为:(1) 换乘0次:直达;(2) 换乘1次;(3) 换乘2次;(4) 换乘3次;如下图:图

13、4 换乘次数的抽象化4、建立公汽直达信息库:元胞结合公众出行心理,优先考虑两站点之间是否有直达公汽线路,故在查询系统内部需设有任两站点的直达线路表,以方便查询,当存在直达线路时直接输出所有直达线路;若无直达线路,再搜索换乘路线,出于以上考虑,在系统内部需建立公汽直达信息库。本问题共涉及3957 个公汽站点,站点信息量大,所以中的数据存储结构的选择非常重要:若采用数据矩阵存储,操作复杂,存储量大,转而使用MATLAB 内建元胞结构建立,并利用阵列存储站点间所有直达线路的信息。阵列数据存储类型若使用双精度实型,当部分阵列不存在直达信息时,该类型仍然占用存储,总存储量必将超过MATLAB内存限制,可

14、使用无符整型表示信息数据,当两站点间信息阵列不存在直达信息时,不占用存储,故缩小存储减少系统读取数据时间。具体元胞结构设计如下:Cell1,1Cell1,2车号耗时相隔站点数Cell1,3Cell2,1Cell2,2Cell2,3图5 元胞示意图上图中Cell1,21行2列直达阵列描述了从站点S0001到站点S0002的所有直达线路信息,其中阵列中一页内每行代表一条直达线路信息。 模型的建立需求过程如下描述:当输入起点和终点后,根据处理数据后输出直达线路,否则自动搜寻换乘次数最少的路线。若换乘次数相同情况下有多种转乘方案,提供耗时最短转乘路线(包括转乘次数、行程总时间、转乘站点及路线、行程总费

15、用)供查询者自主选择,同时系统可以向查询者推荐“时间最短”“费用最省”“换乘次数最少”的不同目标下的最佳路线。建立两站点间换乘线路数矩阵,方便用户输入起点与终点后,系统立即查询出到达终点最少转乘次数。统计中各阵列长度,得到任意两站点的直达线路数目,构造以两两站点间直达路线数目为元素的直达线路数矩阵 ,通过矩阵运算得到任两站点间换乘次数矩阵,从而可快速查询任意两站间所需的最少换乘次数。1、直达线路路数矩阵的建立根据,建立直达线路数矩阵,其矩阵元素表示站点到站点的直达线路数n,其中,当时为无效路径,设定值为0,即: (1)以表示所有公汽所经过的站点总数,则直达线路数矩阵可表示为: (2)2、换乘线

16、路数矩阵直达矩阵为阶方阵,矩阵中元素表示任意两站点间通过1次换乘的路线数,即:=· (3)下面以中1行2列元素为例对中元素来源进行举例说明:例: 假设上式中等号右边仅,其余为0,说明1站点可直达到3站点,3站点可直达2站点,当=·后,即1站点通过一次换乘到达2站点,换乘点为站点3,则中元素表示站点到站点通过1次换乘的路线数由图论与矩阵知识,可知如下推广: ,为站点的直达路线数: (4)其中的元素表示通过n-1次换乘站点的线路数。3、最少换乘次数矩阵的建立引入矩阵,其矩阵元素为使得的()的最小值,即: (5)则表示从站点必要的最少换乘次数,以矩阵表示最少换乘次数矩阵,则: (

17、6)其中,元素表示从站点必要的最少换乘次数基于最少换乘次数矩阵,每对起始站、终点站的最少换乘次数列出如下:表3 最少换乘次数表 线路编号 1 2 3 4 5 6 起始站 S3359 S1557 S0971 S0008 S0148 S0087 终到站 S1828 S0481 S0485 S0073 S0485 S3676 最少换乘 1 2 1 1 2 1 5.1.3 模型求解1、 算法步骤描述:step1:起点为,终点为,换乘次数为,直达即=0,非直达时利用邻接矩阵 由条件改进查找路径,经过站点为,记录换乘次线路最小用时 ,中间线路信息从元胞中抽取,保存线路信息;若=3,转至 step3,否则,

18、转入step2。step2:,以min()(其中)为次换乘时间上界,转至 step1;step3:结束,打印线路信息。2、约束条件描述:目标一:换乘次数最少: (7)目标二:线路用时最短仅考虑公汽路线的情况下,得到任意两站站之间的最少乘车用时(包括初始站点的等待时间3min),即:最少用时=乘车时间+换乘时间 (8)所求的最短时间要受到如下的7个条件约束: (9)以上目标函数表示从站点到站点公汽线路中行使时间和换乘时间的总和,其中:(1)表示从站点到站点条线路所经过的站点数;(2)表示总的转车次数;(3)表示出发站应满足的条件,即乘客从某线路前往某站。(4)表示目的站应满足的条件,即乘客从某线

19、路到达该站。(5)表示线路与某站点的关系,若线路不经过某站点,式子左右两边都为0,若线路经过某站点,则式子左右两边都为1。(6)分为以下几种情况:1)假如线路没有经过某站点,此时的值为0,同时的值也为0,中间的式子为0;2)假如线路经过某站点且没有转车(换乘),此时的值为1,同时的值也为1,中间的式子为0;3)假如线路经过某站点且有转车(换乘)的情况,对于转车前的线路,此时的值为1,同时的值也为0中间式子为1;对于转车后的线路有的值为0,同时的值也为1,中间式子为-1。这三种情况的结果符合模型的换乘函数。目标三:最小费用本系统在选择公汽线路时考虑花费,使到达目的地的花费最小: (10)其中表示

20、线路从站点至站点中间所经过的站点数分析公汽线路票价,有票价函数: (11)基于以上各式,得以下目标函数: (12)以上算法实现见附录。3、求解结果1)报表说明:目标:1,2,3,4,5,6分别表示S3359S1828 、S1557S0481、S0971S0485S0008S0073、S0148S0485、S0087S3676;换乘:换乘次数;时间:线路总计用时(分钟);站1:第1次换乘站点;站2:第2次换乘站点;站3:第3次换乘站点;线1:第1次乘坐的公汽线路;线2:第2次乘坐的公汽线路;线3:第3次乘坐的公汽线路;线4:第4次乘坐的公汽线路;费用:从始发站到目的站所需要的总费用(元);程序:

21、MATLAB程序运行时间(秒)。2)换乘次数最少路线:表4 换乘次数最少路线方案目标换乘时间站1站2站3线1线2线3线4费用程序111041784-436167-34.62210919193186-84189460-361.8311312184-13417-3232.64186291-15958-2209.9186400-159474-2186491-15958-21862083-46357-21862263-355345-21862303-355345-21862559-15958-31862633-159474-21862683-15958-21863053-159474-21863315

22、-15958-31863614-15958-21863917-355345-252109362210-308156417-363.92109363332-308156417-32109363351-308156417-361683496-454209-267.23)最短用时路线:表5 用时最短的路线方案目标换乘时间站1站2站3线1线2线3线4费用程序126717461784-324485167-34.626720271784-324485167-326729031784-15485167-326736971784-484485167-326737271784-484485167-3231021

23、91931869028418991254461.8310219193186903841899123943210625172159-13290469-3232.643666304835251592313281034209.9366630604525159231328103436663060952515923132810343668544835251592313281034366854604525159231328103436685460952515923132810343661383132752543232810343661691132752519823281034366172813275251

24、98140328103436622631327525355140328103436627554835253551732810343662755604525355173281034366275560952535517328103436637661327525198232810345310536042361221030881156417463.9310536042361333230881156417431053604236133513088115641746249884272123197367.24)费用最少路线:表 6 费用最少的路线方案目标换乘时间站1站2站3线1线2线3线4费用程序11104

25、1784-436167-34.626717461784-324485167-326720271784-324485167-326729031784-15485167-326736971784-484485167-326737271784-484485167-32210919193186-84189460-30.8311312184-13417-32.2210625172159-13290469-34186291-15958-20.0077186400-159474-2186491-15958-21862083-46357-21862263-355345-21862303-355345-2186

26、2633-159474-21862683-15958-21863053-159474-21863614-15958-21863917-355345-252109362210-308156417-30.62109363332-308156417-32109363351-308156417-361683496-454209-20.0019以上表中已按换乘次数最少、出行用时最短、费用最少三个目标列出最优出行路线方案,用户只需要根据实际需要选取即可。结果分析分析以上报表:1、几乎所有换乘3次的线路都可以以较短时间、较低的费用到达目的站点,说明选择三次作为换乘次数的上限是可行的。2、考虑查询系统的时效性

27、,给出MATLAB程序运行时间。由运行时间:查询换乘次数小于1次含1次的线路,程序运行时间远小于1秒;查询换乘2次程序耗时不超过5秒;查询换乘3次程序所需时间200秒左右。在实际情况中,乘客在乘车点等车时进行路线查询,以上查询时间是可以被乘客接受的。以上所述程序运行时间说明在本文描述的数据存储结构下,改进的邻接算法的可行性与较低的时间复杂度。综述,模型I求解的线路方案集使用于不同需求下的所有用户,具有较强的实用价值,很大程度上满足了乘客乘车线路多样化的需求。5.2 问题二的模型建立与求解5.2.1 模型准备1、两种地铁线路抽象处理基于对三种公汽线路路线的抽象方法,以相同的方法对两地铁线路T1、

28、T2进行抽象化处理:T1:双向线路,根据不同的方向将其抽象为两条单向行驶线路;T2:环行线路,根据公汽线路抽象方法化为4条行驶线路处理。2、归一站点由题目给出的地铁换乘公汽的数据可知:地铁站点附近存在多个公汽站点。处于同一个地铁站点附近的公汽站点地理位置应非常接近或容易换乘,定义这些站点为紧邻站点,将紧邻站点与对应的地铁站点抽象为一个新的站点,减小这类站点的差异性。例如地铁换乘公汽的数据首行“D01:S0567,S0042,S0025”,可认为这四个站点实际距离较近,为紧邻站点,将五个站点做归一处理,构造新站点,以上过程示意图如下:图6 可互换站点抽象为一个站点示意图基于这种思想,在整个交通网

29、络中将所有地铁站点及其紧邻站点分别做归一站点处理。认为在新站点所代表的站点集中的任意站点可通过步行到达,且时间忽略。3、建立公汽、地铁直达信息库综合考虑公汽与地铁时建立的实质是新站点与新站点间的直达线路信息集。用户输入起点和终点后,系统内部先自动查找两点所属的新站点,然后查找新站点间可直达的线路,并给出起点及其附近站点直达终点及其附近站点的最佳乘车线路。采用与5.1相同的思路及方法,将已知的可直达公汽线路映射到,建立新的直达线路信息库,结合地铁费用与地铁换乘公汽等待时间填充元胞内阵列描述的直达线路信息。具体元胞结构设计图如下:Cell1,1Cell1,2车号耗时相隔站点数Cell1,3Cell

30、2,1Cell2,2Cell2,3图7 直达线路信息库(3996*3996)元胞结构示意图上图中Cell1,21行2列直达阵列描述了从站点S0001到站点S0002的所有直达线路信息,其中阵列中一页内每行代表一条直达线路信息。5.2.2 模型建立需求过程如下描述:对于新站点,可等同看作问题一中的公汽站点,当用户输入起点和终点后,优先显示直达线路,否则自动搜寻转乘线路,同时,系统向查询者推荐不同目标下的最佳路线及转乘方案。考虑乘客可以乘坐地铁,依据问题一中的模型,调整如下:1、乘客选择的公交为公汽或地铁,相应有变量: (13)表示公交经过t线路有i站点到达j站点。2、乘客由公汽转乘地铁,相应有变

31、量及约束条件: (14) (15)3、乘客由地铁转乘公汽,相应有变量及约束条件: (16) (17)4、乘客可由地铁转乘地铁,相应有变量及约束条件: (18)5、乘客在公汽站可不换公汽、可转乘公汽、可转乘地铁,三种选择不同时进行,相应有变量及约束条件: (19)6、乘客在D12及D18地铁站可不换地铁线、可换乘公汽、可换乘地铁线,三种选择不同时进行,相应有变量及约束条件: (20)5.2.3 模型求解1、算法步骤描述:step1:起点为,终点为,换乘次数为,直达即=0,非直达时利用邻接矩阵 由条件改进查找路径,经过站点为,记录换乘次线路最小用时 ,中间线路信息从元胞中抽取,保存线路信息;若=3

32、,转至 step3,否则,转入step2。step2:,以min()(其中)为次换乘时间上界,转至 step1;step3:结束,打印线路信息。2、求解结果1)报表说明:目标:1,2,3,4,5,6分别表示S3359S1828 、S1557S0481、S0971S0485S0008S0073、S0148S0485、S0087S3676;换乘:换乘次数;时间:线路总计用时(分钟);站1:第1次换乘站点;站2:第2次换乘站点;站3:第3次换乘站点;线1:第1次乘坐公交路线;线2:第2次乘坐公交路线;线3:第3次乘坐公交路线;线4:第4次乘坐公交路线;费用:从始发站到目的地所需要的费用(元);程序:

33、程序运行时间(秒)。2)换乘次数最少路线方案:表7 换乘次数最少路线方案目标换乘时间站1站2线1线2线3费用程序11140S0304L469L21737110S1241L436L167104S1784L436L16722115D20:S2079,S2933,S1919,S1921,S1920S0902L084L417L25432.2112D20:S2079,S2933,S1919,S1921,S1920S2424L084L417L254109D20:S2079,S2933,S1919,S1921,S1920S3186L084L189L46031152S0872L119L41735.5134S0

34、992L013L417131S2184L013L41741110S0275L043L17035.686S0491L159L058283D13:S2633,S0399,S0401,S0400L159L47452109S0036S2210L308L156L41731.6106S3604D20:S2079,S2933,S1919,S1921,S1920L308L454L41791D02:S1487D20:S2079,S2933,S1919,S1921,S1920L02T001L417590.5D02:S1487D21:S0465,S0467,S0466,S0464L024T001L05156023T

35、00232.528T00228T0023)出行用时最短路线方案:表8 出行用时最短路线方案目标换乘时间站1站2线1线2线3费用程序1267S1746S1784L324L4851673722109D20:S2079,S2933,S1919,S1921,S1920S3186L084L189L46032.23299D01:S0567,S0042,S0025D21:S0465,S0467,S0466,S0464L094T001L05155.54258D30:S3874,S1426,S1427D25:S0526,S0528,S0527,S0525L150T002L10355.652106S3604D20

36、:S2079,S2933,S1919,S1921,S1920L308L454L41731.66023T00232.54) 费用最少路线方案:表9 费用最少路线方案目标换乘时间站1站2线1线2线3费用程序1267S1746S1784L324L4851673722109D20:S2079,S2933,S1919,S1921,S1920S3186L084L189L46032.231131S2184L013L41735.54183D13:S2633,S0399,S0401,S0400L159L4748325.652106S3604D20:S2079,S2933,S1919,S1921,S1920L30

37、8L454L41731.66023T00232.5结果分析加入地铁后,乘客有了更多的公交路线选择,可以在换乘两次之内到达任意目的站点,减少了换乘次数,优化了交通网络。5.3模型的建立与求解5.3.1 问题分析1、问题一与问题二启发分析 将步行方式考虑在了出行方式当中更符合实际。因为当站点间只相隔较少的几个站点时,选择步行方式不但节省花费同时减少换乘次数,增加步行方式可能增加新的公交路线。在解决问题一、问题二的过程中,基于换乘次数逐步分析给出了起始点与终点之间的最佳路线。对比问题一、问题二分析,可得如下启发: 1)在两个问题的最佳路线中均出现上车后只乘坐一站就下车的情况,这样情况乘客可以考虑步行

38、经过中间换乘站到达下个换乘站; 2)增加一种交通工具可使原来不能直达的站点直达,优化了交通网络。例如前两个问题中的5、6 ,增加地铁后,5找到时间更短的路线,而6找到直达路线。步行可替代交通工具实现以上功能:如果在某站点下车后没有直接换乘的车次,但较近的两行车路线上有相邻站点, 行人可选择步行到邻近路线站点进行换乘。所得到的启发1和2图形直观化描述如下:图8 采用步行方式优化路线3)公交路线都是有向的,即在站点间只能由起始方向至终点方向前进,如<,Start,>,<,end,>,只能在<>,<>中选择,不能在<>,<>中选

39、择,但步行不需要考虑此约束,可以在<>,<>中选择站点,通过沿已经过路线逆行步行方式寻求最佳路线。4)问题一问题二没有考虑站点间步行时间问题,实际情况中:在相对小于车辆行驶时间情况下,人们步行一段距离再转车,可减少出行总时间。2、模型建立分析含步行线路选择问题与四种因素相关:换乘次数、总时间、花费、步行次数n。 下面分析步行次数对前三种因素的影响,在此列举与之前相比可能优化的情形。图9 换乘抽象化图形有1个或很少的中间站点,在站点A乘坐公交到站点,换乘一次到达后,再换乘一次最终到达B,换乘次数为2,步行次数为0。考虑步行时,选择从走到,减少换乘次数同时减少花费,比如,从

40、 S3359 到 S1828的方案中,出现的从中转站S1784到S1828只有一站的情况。当路线是分段计价的时,如果步行到达最后一站,会节省花费。例如起始站点A到达站点B刚好是21/31/41站。通过上述的分析,考虑步行的模型应存在以下优点:1)增加新的可能的路径,因为步行不考虑公交线路的方向性; 2)节省费用,合理的步行安排可以降低费用或减少换乘次数,但可能以增加总时间和步行次数为代价。5.3.2模型准备1、模型假设1) 所有站点之间的步行时间是固定不变的,不受其他外界随机因素的干扰;2)只有规定步行时间 (取定的整数)之内的站点之间才可以互称为邻近站点,步行后选择邻近站点或同一站点进行车次

41、的换乘;3)只考虑公汽站点间可以步行,地铁站点中不能步行;2、新增符号说明 :任意两个相邻的公交站点间步行平均时间为t;T:判定是否为邻近站点的时间上确界 ;:站点与其邻近站点之间的步行时间。 模型I建立综合上述分析,考虑启发一,在知道所有站点间步行时间后,以最少换乘次数为目标,搜索最小换乘次数路线中所有只坐一站的换乘的情况,将其用步行来代替,以牺牲出行时间为代价减少换乘次数,求解任意两个站点间的最小换乘路线。将最小换乘次数按公交直达,一次换乘,二次换乘和三次换乘分别讨论步行优化换乘模型的策略。设起始站点和目的站点分别为站点s和e,相邻两站之间的距离基本相等为L,且L小于乘客愿意采取步行的最大

42、距离。图10 转乘图Step1:从s可以直达e:如图七中(a)所示,则建议直接从s点步行到e点,不需乘坐公交。 Step 2:从站点s经站点c转乘一次到达e:如图中(b)所示,若sc<ce(sc>ce),则路线可以根据实际状况将换乘一次优化为sc 段步行,ce段直达(或ce段直达,sc段步行)。 Step3:从站点s经站点c,d 转乘两次到达e:如图中(c)所示,若sc<L或cd<L或de<L,则路线可以根据实际交通繁忙状况或乘客自己的意愿将换乘两次优化为换乘一次的情况; 模型II准备基于前面问题的分析,本模型主要以出行总时间最少为目标,同时考虑转乘次数尽量少,行

43、程费用尽量低原则。模型I分析了换乘时步行一站的情况,在现实生活中,人们常常步行一站以上,而且乘客沿公汽线路步行也是不合理的。假设人们步行路线不受公汽线路限制,但有最大承受时间,受到问题二的启发,若已知所有站点之间的步行时间,可以认为在人们最大步行范围内,所有公汽站点都可看作相互邻接。在所有站点之间的步行时间确定的情况下,对于相距不远的两站,考虑以其中站点为圆心,以人们能接受的步行距离为半径做圆,将在该圆形区域内所有的站点抽象为一个站点。图11 依步行距离归一站点模型II的建立1、步行邻边化模型 假设乘客所能忍受的最长步行时间为T,定义站点与站点间的平均步行时间。定义以乘客所在的起始点为圆心,以

44、最长步行时间对应的距离为半径的圆,该圆形区域称为起始点的邻接圆域(如图所示)。由假设知,邻接圆域内任意公汽站点都与相邻接,且与的邻接耗时为。2、模型说明: 1)考虑步行后的总耗时等于未考虑步行的耗时加邻接耗时的和; 2)邻接耗时之和不超过乘客所能忍受的最长步行时间; 3、目标分析 1)目标一:行程总时间最短 总时间的目标函数为: (21)2)目标二:行程总费用最少 满足时间最短目标后,寻找所有可行方案中费用最小的路线,在本层目标分析时,将图中的权值赋为途中所需的费用。p表示站点到的行程费用,则行程总费用最小可表示为: (22)有以下目标函数; (23)5.3.5 模型II求解算法1、算法思想:

45、最少换乘的广度优先算法 2、算法描述如下: Step 1:输入起点目的点,根据输入的站点进行优化,映射入紧邻站点集。Step2:查找并记录经过及其紧邻站点所有路线,记录上 的所有站点;查找并记录经过目的站点及其紧邻站点的所有线路,若,则表明存在从到的一条直达线路,输出结果;否则转Step; Step3: 搜索并记录公交线路的站点,搜索并记录公交线路的站点,判断是否有,若有一个点满足要求,该站点即为一次换乘的站点。 若有几个站点满足要求,则先分别求出每一个站点的距离最短的换乘方案,然后选择所有方案中距离最短的换乘方案为最优线路,输出结果;若没有,继续。Step:搜索并记录站点所在的线路,记录上的

46、所有站点,判断是否有,若有某个站点满足要求。则站点为第二个换乘站点。从起始站点经过一次换乘(假设换乘点为站点D),可以到达站点,从站点可以换乘公交车直达目的站点。Step:按照步骤Step和Step的方法求出从起始站点到站点的一次换乘的最优线路,再按照step的方法求出从站点到目的站点的最优线路。两个换乘站点和两段最优线路即组成了从起始站点到目的站点的最优线路。若有多个站点满足,则分别求出各站点的最优换乘方案,比较各方案的线路距离,选择一种距离最短的换乘线路方案作为最后的结果,输出。六、模型检验与评价6.1 模型检验与灵敏度分析路线用时有时会有微小变动,并且公汽和地铁的票价也会随着政策的不同而

47、改变,所以对这两方面可能产生的波动进行讨论就显得十分必要。6.1.1 时间的波动与公汽和地铁行驶相关的时间有两个,分别是相邻两站间的平均行驶时间和换乘车辆所需时间,由于最优路线的选择与这两个时间的比值相关,不妨固定相邻两站间公交车和地铁的平均行驶时间,变动换乘时间,研究它对最优路线的影响。1、以S0138到S0485为例,首先固定公交车和地铁的两站间的平均行驶时间,研究公汽换公汽的时间对最优路线的影响。 图12 最优路线花费时间与公汽换公汽时间关系图从图12 中可以看出,公汽换公汽的时间对最优路线的影响非常大,当公汽换公汽的时间多于6分钟时,最优策略就会发生改变。因此,此时应尽量选择少换车的方

48、案,以减小换车时的等待造成的时间开销。2、仍以S0138到S0485为例,固定公汽换公汽的时间,研究公汽和地铁的两站间的平均行驶时间对最优路线的影响图13 最优路线花费的总时间与公汽行驶时间与地铁行驶时间比的关系图 从图13中可以看到,比值在0.8附近就对最优乘车路线产生了影响,为了避免这样的影响,建议出行时尽量选择两站间行驶时间比较稳定的地铁以减少行驶时间的变动造成的影响。6.1.2 价格的变动分析可知价格的变动对偏重时间的最优路线没有影响,以下讨论它对偏重价格的最优路线的影响。不妨固定公汽的价格,讨论地铁价格的变化对偏重价格路线的影响,以地铁价格下降为2元/次为例。地铁价格变动之前,地铁与公汽价格比为3,相当于坐一次地铁的钱可以坐3次公汽,这对于偏重出行费用的乘客来说,他们一般不会坐地铁。通过统计可知,与地铁站相邻的共117个站点间共13689条线路均可通过不超过2次换乘到达,具体乘车次数见下图:图14 地铁

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论