注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

我快乐所以我博客--一品佳茗

每个人的心灵历程都是一首歌,我唱出我的所以我快乐。

 
 
 

日志

 
 
关于我

爱好广泛,一事无成,平生喜欢很多,至爱较少。喜欢书法,欧颜柳赵,也曾临过,但缺乏坚持,喜欢绘画,国画工写,西画彩描,也曾摹过,但缺乏深入,喜欢诗歌,诗词歌赋,也曾填过,但缺乏含蓄,喜欢舞蹈,单双多人,也曾迷过,但缺乏精巧,喜欢武术,刀枪棍棒,也曾练过,但缺乏功力,喜欢棋艺,军象跳围,也曾恋过,但缺乏心计,喜欢音乐,吹拉弹唱,也曾试过,但缺乏细胞。 不喜欢数学却上了贼船,不想当教师最终却以之为生。干一件事时间久了,可能会厌倦,也可能会喜欢。兴趣是靠自己培养的。若一个人愿意学习,相信久了会取得成绩。

网易考拉推荐

乘公交看奥运最佳线路的选择模型  

2007-11-15 21:57:10|  分类: 数学建模 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 

王升  林成功 王苗苗  指导教师 朱家明(本文获2007大学生数学建模竞赛全国二等奖)

摘 要

本文建立了乘公交看奥运最佳线路的选择模型。在仅就满足公众对乘车耗时最少和花费最低的两种需求,对三个情形:⑴仅考虑公汽的单一线路,⑵同时考虑公汽与地铁两种线路,⑶兼顾步行公汽地铁三种线路,分别建立了任意两站点之间线路选择问题的数学模型,依托matlab软件编程给出相应的的算法。并利用所建立的模型与算法,求出给定的6对起始站→终到站之间的最佳路线,并做出了清晰的评价说明。最后,本文还对模型作出了进一步分析、评价和推广。

针对问题一中仅考虑乘坐公汽,我们在对问题分析的基础上,运用matlab软件编程并搜索,就乘客的耗时最少需求,建立了模型Ⅰ(耗时最少的线路选择模型),给出了相应的算法步骤及程序框图,并针对六组得到如下结果:①S3359→S1828,换乘一次有两条线路,都经过了32个站点,所花费的时间均为101分钟;②S1557→S0481:至少需换乘两次,线路有两条,也经过32个站点,耗时101分钟;③S0971→S0485:换乘一次,通过41站,耗时128分钟;④S0008→S0073:换乘一次,有14种不同线路,经过26站,耗时83分钟;⑤S0148→S0485:至少需换乘两次,线路有6条,且都经过32个站点,耗时101分钟;⑥S0087→S3676:换乘一次,经过20站,耗时65分钟。

同样,就乘客的费用最低需求,建立了模型Ⅱ(费用最低的线路选择模型),给出了相应的算法步骤,得到结果详见正文第12页至第13页。

针对问题二,同时考虑公汽与地铁两种线路,我们建立了模型Ⅲ(分步规划模型),通过设计算法步骤,再运用Matlab编程可求出以上完成,我们可求出以上六组点的结果,详见正文第15页至第18页。

针对问题三,兼顾步行公汽地铁三种线路,我们建立了模型Ⅳ(线路综合评价模型),第三题是在前面问题的基础上,加入了步行这一较为自主化的“交通工具”,使得原本的选择最优线路模型不再适用,于是我们这里建立了一个线路综合评价模型,通过分类讨论的方式,提供适合各种情况的线路选择方案,从而解决在三种交通工具并行时的路线选择问题。

本文最后还对这一自主查询系统进行了推广,将自主查询系统推广到手机彩信或短信,给出了系统结构设计和网络拓扑结构图;同时,将这一自主查询系统应用到旅游线路选择上,并绘制了旅游线路选择系统结构图。

 

关键词:线路选择;换乘;分步规划;自主查询系统;Matlab

 

§1、问题的重述

一、问题背景

1、看奥运要出行

2008年8月8日至8月24日,我国人民翘首企盼的第29届奥运会将在北京举行,届时将会有大量观众从不同地点到达比赛现场去观看奥运盛况,其中大部分人将会乘坐公共交通工具(简称公交,包括公汽、地铁等)出行。

2、乘公交需择线

这些年来,随着科技进步、政府投资及市政部门对城市道路的不断完善,我国城市的公交系统有了很大发展,作为我国首都——北京市,它的公交线路已多达800条以上,这使得广大市民的出行更加通畅、便利。但是,同时也因线路的众多,为广大市民的出行带来一个新的问题,乘车从一个地方到另一个地方,如果都在同一条公交线路上,市民则不存在选择;如果需要换乘,特别是二次以上的换乘,市民则面临着多种选择,可分别从选最短线路、花最少时间、用最少换乘、节省票价等各个方面进行决策,以实现出行任务的完成。

3、做系统先建模

针对市场需求,某公司准备研制开发一个解决公交线路选择问题的自主查询计算机系统。为了设计这样一个系统,其核心是线路选择的模型与算法,应该从实际情况出发考虑,满足查询者的各种不同需求。

二、有关数据

1、基本参数设定

⑴相邻公汽站平均行驶时间(包括停站时间):3分钟;

⑵相邻地铁站平均行驶时间(包括停站时间):2.5分钟;

⑶公汽换乘公汽平均耗时:5分钟(其中步行时间2分钟);

⑷地铁换乘地铁平均耗时:4分钟(其中步行时间2分钟);

⑸地铁换乘公汽平均耗时:7分钟(其中步行时间4分钟);

⑹公汽换乘地铁平均耗时:6分钟(其中步行时间4分钟);

⑺公汽票价:分为单一票价与分段计价两种,标记于线路后;其中分段计价的票价为:0~20站:1元;21~40站:2元;40站以上:3元;

⑻地铁票价:3元(无论地铁线路间是否换乘)。

注:以上参数均为简化问题而作的假设,未必与实际数据完全吻合。

2、公交线路及相关信息(详见附件2中文本文档1、1.1、1.2及2、2.1、2.2)。

三、问题提出

1、问题一:⑴仅考虑公汽线路,给出任意两公汽站点之间线路选择问题的一般数学模型与算法。⑵并根据附录数据,利用你们的模型与算法,求出以下6对起始站→终到站之间的最佳路线(要有清晰的评价说明)。

①S3359→S1828;②S1557→S0481;③S0971→S0485;

④S0008→S0073;⑤S0148→S0485;⑥S0087→S3676。

2、问题二:同时考虑公汽与地铁线路,解决问题一中两个问题。

3、问题三:假设又知道所有站点之间的步行时间,请你给出任意两站点之间线路选择问题的数学模型。

§2、问题的分析

一、问题的总体分析与相关量的明确

1、问题的总体分析

乘公交看奥运公交线路选择问题涉及到数百条公汽线路与两条地铁公交线路、数千个公汽站点与几十个地铁站点、三类不同乘车票价信息、上行下行单行环形四种车行方向等多个因素,且出行查询者的通常需求分别有选最短线路、花最少时间、用最少换乘以及用最低票价,当然这些需求在小城市道路比较单一时可能是相一致的,但对拥有众多车辆及线路且道路如网的首都北京而言,这些需求则不尽然。故问题这是一类多因素多数据计算机查询信息处理及多目标决策问题,核心是算法。

2、几个重要的量

为了便于解决问题,下面我们先明确问题涉及到的几个重要相关量。运用相关的统计方法,从竞赛B题所给的压缩文本文档中,我们不难得到以下几个量的准确信息:

⑴公交线路:520条公汽线路,编号:L001~L520;两条地铁线路T1与T2。

⑵公交站点:3957个公汽站点,编号:S0001~S3957;

 39个地铁站点,编号:D01~D39。

⑶公汽线路与站点:文本文档1.1具体地给出了520条公汽线路编号,票价信息,车行线信息(详见2007年竞赛B题压缩文本文档1.1)。

⑷地铁线路与站点:文本文档1.2具体地给出了北京地铁线路T1与T2,我们通过上网搜索[1]很易获取相关的地铁图片(图1)与北京地铁T1、T2线路图(图2)。结合文档1.2所给北京地铁线路T1与T2的信息,我们不难发现,地铁T1的23个站与地铁T2的16个站相吻合,且图2中的复兴门为D12与建国门为D18是可以换乘的两个站。

   

图1  地铁图片                    图2  北京地铁T1、T2线路图

二、对具体问题的分析

1、对问题一的分析

⑴问题:仅考虑公汽线路,给出任意两公汽站点之间线路选择问题的一般数学模型与算法。并根据附录数据,利用所给出的模型与算法,求出6对起始站→终到站之间的最佳路线,且要有清晰的评价说明。

⑵分析:要寻找两站之间的最佳公交线路,就是要满足不同乘客乘坐公交的一定要求,比如选最短线路、花最少时间、用最少换乘或花最低票价等等。为了简化对问题的解决,我们不妨假定求最佳路线,仅在乘车耗时最少、花费最低两种条件下确定最佳公交线路。

对于在同一线路上的任意两个站点,若通过两个站点的线路仅一条(如图3左),显然这一条也就是最佳路线;若通过两个站点的线路有两条及两条以上的线路,按基本参数设定⑴知,最佳路线是中间站点数最少的线路,如图3右图中蓝色的直线即最佳路线。

图3  两站间通过的线路仅一条与两站间通过的线路有两条线路图

对于不在任何一条公交线路上的两个站点,即没有直达的公交线路,则要考虑换乘,若通过起始站的所有线路和通过终到站的所有线路有且仅有一个公共站点,如图4左可知,则相交站点的线路ACB即为最佳路线;若通过起始站的所有线路和通过终到站的所有线路多于一个公共站点,如图4右C站和D站均为换乘站点,显然同样换乘次数时换乘线路所经过的站数较少的ACB线要优于ADB,从而ACB线为最佳路线。同样换乘次数时多于两条换乘线的,则换乘线路所经过站数最少的为最佳路线。

 

图4  两站间换乘一次线路仅有一条与换乘一次线路有两条线以上的线路图

如果对进行一次换乘不能完成出行任务的,我们要进行两次换行计划。类似上述的分析,我们可以得到两次的换乘情形下的最佳路线。显然这要比前两类情形复杂得多,但运用计算机进行编程一般是可以实现的。

如果对进行两次换乘仍不能完成出行任务的,我们要进行三次或三次以上的换乘。但考虑到换乘三次及三次以上研究的技术处理和实际操作太复杂且实际意义不大,故在最初建模时可不予考虑,在对建模进行改进时,可酌情考虑。

当然,对于基于最低价格的最佳模型求解,除了要考虑以上的分析外,我们还要考虑各类票价信息。首先我们要搜索出所有需要分段计价的公汽线路,然后根据题目中的分段计价要求建立一个价格矩阵,再由前述换乘法求出的结果进行价格计算,看是否满足价格最小的条件,对不满足的利用排序求出最小价格,并得到相对应的线路信息。

2、对问题二的分析

⑴问题:同时考虑公汽与地铁线路时,解决问题一的建模、算法和6条最佳路线。

⑵分析:问题二是在问题一只有公共汽车单一交通工具的基础上,通过引入地铁这一交通工具,使得转乘不仅仅是公汽转公汽,还包括公汽转地铁,地铁转地铁,地铁转公汽,使得转乘问题复杂化。为了得到用时最少的线路,我们可考虑建立了分步规划模型进行求解,将总用时最少这一规划问题,分成在每次搭乘都用时最少的分布规划问题。从而在综合考虑公汽与地铁的情况下确定了最佳线路。

3、对问题三的分析

⑴问题:假设又知道所有站点之间的步行时间,请你给出任意两站点之间线路选择问题的数学模型。

⑵分析:第三题是在前面两个问题的基础上,加入了步行这一较为自主化的“交通工具”,使得原本的选择最优线路模型不再使用,于是我们这里建立了一个线路综合评价模型,通过分类讨论的方式,提供适合各种情况的线路选择方案,从而解决在三种交通工具并行时的路线选择问题。

§3、模型的假设

1、为便于研究问题,规定每条线路起点站的位标为1,从起点站至终点站的其余各站的位标依次为2、3、……。

2、由于基本参数已设定,不再考虑发车频率和乘客到达时刻及等待时间;

3、由于公交线路的交错复杂,不考虑公交线路的编排次序和公交站点的编排次序;

4、交通状况良好,无交通阻塞及其它影响交通运营的异常情况发生;

5、作为交通系统比较发达和完善的首都北京,联通任意两站间的线路最多换乘两次,换乘三次及三次以上研究太复杂且实际意义不大,故不予考虑。

§4、名词解释与符号说明

一、名词解释

1、换乘:从一辆车下来转乘另一辆车的过程;

2、位标:为建模而自行定义的变量,规定一条线路从始发站起各站的位标依次为

1、2、3、……。

二、符号说明

1. :所有公汽线路数据处理后得到的;

2. :经过起始站S1的所有线路站台矩阵;

3. :经过终到站S2的所有线路站台矩阵;

4. , :公汽的起始站点;

5. :公汽的终到站点;

6. :只考虑公汽情况下起始站与终到站的公共站点;

7. :公共站点与起始站在同一线路上的公共站点的列标;

8. :公共站点与终到站在同一线路的公共站点的列标;

9. :与公共站点在同一条线路上的起始站的列标;

10. :与公共站点在同一条线路上的终到站的列标;

11. :只考虑公汽情况下从起始站到公共站点的站点数量,即 ;

12. :只考虑公汽情况下从公共站点与终到站的站点数量,即 ;

12. :只考虑公汽情况下从起始站到终到站的总的站点数量,即 ;

13. :只考虑公汽情况下耗费时间最少情况下得到的最佳路线的中转站;

14. :只考虑公汽情况下乘车费用最低情况下得到的最佳路线的中转站;

15. :为使得 以一个向量的形式输出,同时为了循环的方便而引进的变量,初值为1;

16. :乘车所耗费的总时间,包括等待和转乘的时间;

17. :所有分段计价线路数据组成的矩阵;

18. :只考虑公汽情况下从起始站到中转站的票价;

19. :只考虑公汽情况下从中转站到终到站的票价;

20. :耗时最少的最佳路线的乘车费用,计算得到价格并计算出最低价格;

21. :乘车费用最低的最佳路线的最低乘车费用;

22. :根据分段计价标准的不同得到的 的分段计价价格向量,由数字1,2,3组成;

23.ij:地铁相邻的公汽站台矩阵;

24.P:矩阵ij与矩阵B的交;

25.:矩阵ij与矩阵C的交;

26. :矩阵B与矩阵ij的公共元素;

27. :矩阵C与矩阵ij的公共元素;

28.ti:乘坐交通工具时经历的时间;

29.t0:交通工具换乘用时平均耗时;

30.ni:乘坐交通工具时经过的有效站台数;

31. :任意两站点ij之间的步行时间。

 

§5、模型的建立与求解

从所要解决的问题和对问题所做的假设出发,我们对问题一分别建立了模型Ⅰ(耗时最少的线路选择模型)和模型Ⅱ(费用最低的线路选择模型),我们对问题二建立了模型Ⅲ(分步规划模型),我们对问题三建立了模型Ⅳ(线路综合评价模型)。

一、问题一的分析与求解

1、问题一的分析

要寻找两站之间的最佳公交线路,就是要满足各类乘客乘坐公交的不同要求,为了简化对问题解决,我们大体上认为最佳路线即是乘车耗时最少、乘车费用最少两种情况来对问题一进行求解。为了实现这一目标,我们对题目给出的大量数据进行了相应的处理,发现对问题中列出的六组站点,都无法根据现有的公交线路直达,于是就要考虑公交车的换乘问题。在考虑到技术处理和实际操作的可行性,我们不妨假设最多换乘两次就可以到达任意站点,否则,乘客可以根据车行方向随机地选择车路,然后到一定车站后再行查询,或通过步行到能够附近站点。对于基于乘车费用最少的模型求解,我们首先搜索出所有需要分段计价的公汽线路,然后根据题目中的分段计价要求建立一个价格矩阵,首先对由模型Ⅰ求出的结果进行价格计算,看是否满足价格最小的条件,对不满足的利用排序求出最小价格,并得到相对应的线路信息。

2、建模的思想

⑴建立数据库

为了确定公汽线路的最佳路线选择,首先把附录2中的文本文档“1.1 公汽线路信息.txt”进行处理,并转换到excel软件中,形成以第一列线路为公汽线路编号,第二列为价格信息,第三列为车行性质,第四列为各线路上所有车站点的大型数据库(详见附录3),以此为基础,下面进一步研究。

⑵搜索起始站和终到站所经过的线路

通过对数据库的搜索,查询起始站和终到站是否有相同的车经过,如果有且仅有一条,即为最佳乘车线路;如果有且多于一条,则只要计算从起始站到终到站的总站数,通过比较可以得到战数最少的公交线路,推荐给乘客。我们可用VB语言编程建立计算机循环查询系统。运用此系统产生的对话框进行查询起始站和终到站是否有相同的车经过,我们只要输入起始站的站名(比如S0001),然后再输入终到站的站名(比如S0158),则在打开的excel文件前的对话框里产生一串语句,比如有,则在回答“直达”,且紧跟“直达”的后面给出了起始站到终到站的站数,结束;如果没有,则回答“不能直达”,下面再转入下一步研究。

⑶寻找一次换乘的线路

分别从数据库中搜索通过起始站的所有线路和通过终到站的所有线路,并将线路放到一起进行比较,如果存在公共的交点,则说明进行一次换乘即可完成出行计划。如果一次换乘的线路为一条,则是最佳乘车线路;如果一次换乘的线路多于一条,再通过计算通过的站点数进行比较,从而可找出站点数最小的最佳乘车线路。如果不存在公共的交点,则要进行两次或两次以上的换乘。

⑷寻找两次换乘的线路

对上一步完成对数据库搜索后,若通过起始站的线路和通过终到站的线路不存在公共的站点,则对通过起始站线路的所有站点和对通过终到站线路的所有站点再进行第③步的搜索,若存在存在公共的线路,则说明进行二次换乘即可完成出行计划。否则,我们考虑作为交通系统比较发达和完善的首都北京,联通任意两站间的线路最多换乘两次,换乘三次及三次以上研究太复杂且意义不大,故不予考虑。

3、模型Ⅰ 耗时最少的线路选择模型

⑴模型的准备

在寻找最佳线路之前,我们要给公汽线路信息给出的大量数据进行处理,即对上下行站点完全相同的数据补出它的下行数据;同时为处理简便起见,对环行线路我们以相同的线路写出它的下行路线,并对所有空白数据均补“0”。经过处理,得到一个1040行86列的的大矩阵A1040×86。下面我们以站点S3359→S1828为例来说明公汽站点的最佳路线选择问题,其具体处理步骤如下:

①查找通过起始站与终到站的线路数

利用数据库,我们运用软件 [1] 编程,可查找出通过起始站S3359和通过终到站S1828的线路数和具体线路数。

a. 通过起始站S3359的线路有26条(包括上、下行):

L015(上下行)、L123(上下行)、L132(上下行) 、L291(上下行)、L324(上下行)、L352(上下行)、L366(上下行)、L378(上下行)、L436(上下行)、L469(上下行)、L473(上下行)、L474(上下行)、L484(上下行)。

b. 通过终到站S1828的线路有10条(包括上、下行):

L041(上下行)、L167(上下行)、L182(上下行)、L217(上下行)、L238(上下行)

因此,可以得到一个以通过S3359的线路为行、每行所有站点为列的 的矩阵 ,同理得到一个以通过S1828的线路为行、每行所有站点为列的 的矩阵 。

②确定公共点的位标

为方便建模及其算法,下面定义一个新的名词。

定义:规定一条公交线路从始发站起到终点站止各站的编号为位标,位标的大小依次为1、2、3、……、n

通过分析,我们了解到题目给出我们要求计算的起始站与终到站之间没有直达的情况,于是我们要考虑换乘车的问题。首先从换乘一次车的情况入手,我们利用 的查找命令求出起始站S3359与终到站S1828所有线路上的公共站点组成了集合 ,以及这些公共站点与起始站S3359在同一线路的位标 、这些公共站点与终到站S1828在同一线路的位标 。

③求换乘一次的总站点数

通过索引,我们可以求出与对应公共站点在同一条线路上的起始站的位标 和这个公共站点在同一条线路上的终到站的位标 ,再利用公共站点与起始站在同一线路中列标的差额以及公共站点与终到站在同一线路中列标的差值就可以得到从起始站到公共站点的站点数量 和公共站点与终到站的站点数量 ,即 , 。

考虑到公汽的行驶顺序一定、无法反向行驶等实际意义,我们只对 的数据进行计算,然后把得到的 相加就可以得到总的站点数量 ,即 。

④确定目标函数

由于题目中给出了相邻公汽站平均行驶时间相等(均为3分钟)的设定,所以要达到耗时最少,我们规定使得所经过的站点最少即可,于是我们利用上述步骤求得不同路线经过的最少站点数量就可以得到耗时最少情况下的最佳线路,即可得到对应的最佳线路的中转站 。此时得到的花费时间为 ,其中包括了公汽换乘公汽平均耗时5分钟。

⑵模型的建立

通过上述分析,我们得到如下的耗时最少的线路选择模型:

目标函数

约束条件

⑶算法步骤

设起始站为 ,终到站为 ,具体的算法可按以下五个步骤来实现:

①搜索求出 与 站点的数据在矩阵 中的位置,并构造成矩阵 ;

②在 的情况下利用 查找矩阵 的公共元素 ;

③搜索出 中第 行的数据等于 以及 中第 行的数据等于 的数据所在列 ,只考虑 和 的情况;

④在循环外层引进变量 ,并赋初值 ,计算从起始站 到终到站 所经过的所有站点数 , ,其中 ,并得到与其对应的 的值,将 的数据以向量的形式显示出来;

⑤求出 的最小值,并输出对应最小 值所在的线路以及中转站。

⑷程序框图(如图5所示,程序见附录)

图5  算法流程图

⑸模型的结果

对问题一的第二小问,根据附录数据,利用上面的模型与算法,求出6对起始站→终到站之间的耗时最少的线路选择及耗时如下:

①S3359→S1828的最佳路线:首先在L436路车下行路线从S3359站开始乘车,途经S2026→S1132→S2266→S2263→S3917→S2303→S2301→S3233→S0618→S0616→S2112→S2110→S2153→S2814→S2813→S3501→S3515→S3500→S0756→S0492→S0903→S1768→S0955→S0480→S2703→S2800→S2192→S2191→S1829→S3649→S1784,然后在S1784站点换乘L217路车下行路线,下站即为S1828站;或者在S1784站点转乘L167路下行路线,下站也是S1828站。

因此,得到 =31, ,

两种换乘方式都经过了32个站点。所花费的时间为 分钟。

②S1557→S0481的最佳路线:

线路1:首先在L363路车下行路线从S1557站开始乘车,途经S3158→S2628→S3408→S2044→S1985→S2563→S2682→S2735→S0029→S0055→S0051→S1919,然后在S1919站点换乘L189路车下行路线,途经S1919→S2840→S1402→S3186,之后在S3186站点换乘L460路车下行路线,途经S3186→S3544→S2116→S2119→S1788→S1789→S1770→S2322→S0992→S2184→S2954→S3117→S2424→S1174→S0902→S903→S2101→S0481。此种转乘方式经过了S1919、S3186站点的共两次换乘,共经过了32站,所花费的时间为 分钟;

线路2:首先在L084路车下行路线从S1557站开始乘车,途经S3158→S2628→S3408→S2044→S1985→S2563→S2682→S0028→S0029→S0055→S0051→S1919,然后在S1919站点换乘L189路车下行路线,途经S1919→S2840→S1402→S3186,之后在S3186站点换乘L460路车下行路线,途经S3186→S3544→S2116→S2119→S1788→S1789→S1770→S2322→S0992→S2184→S2954→S3117→S2424→S1174→S0902→S903→S2101→S0481。此种转乘方式经过了S1919、S3186站点的共两次换乘,共经过了32站,所花费的时间为 分钟。

③S0971→S0485的最佳路线:首先在L013路车下行路线从S0971站开始乘车,途经S3832→S3341→S2237→S3565→S3333→S1180→S3494→S1523→S1520→S1988→S1743→S1742→S1181→S1879→S3405→S2517→S3117→S2954→S0531→S2184,然后在S2184站点换乘L417路车下行路线,途中经过以下站点:S2184→S0992→S2322→S1770→S1789→S2119→S2116→S3544→S3186→S3409→S2717→S1402→S2840→S0643→S2079→S1920→S2480→S2482→S2210→S3332→S3351→S0485

此种换乘方式经过了41站。所花费的时间为 分钟。

④S0008→S0073的最佳路线:首先在L463路车下行路线从S0008站开始乘车,途经S0008→S1383→S1688→S3459→S2532→S3474→S0369→S1776→S2855→S0338→S2849→S2782→S0935→S2084→S2083,然后在S2083站点换乘L057路车上行路线,途中经过以下站点:S2083→S1538→S3547→S0609→S0483→S0604→S2650→S3470→S2619→S2340→S3162→S2181→S0073

此种换乘方式共经过了26站。所花费的时间为 分钟。

(本问有14种不同的换乘最佳方案,其他13种换乘方案详见附录)

⑤S0148→S0485的最佳路线:

首先在L308路车上行路线从S0148站开始乘车,途经S0462→S0361→S1797→S2221→S0302→S2222→S2737→S1716→S0128→S2268→S1308→S1391→S2272→S0036然后在S0036站点换乘→S路车上行路线,途经S0036→S3233→S0618→S0617→S0721→S2057→S2361→S0608→S0399→S2535→S2534→S0239→S0497→S2090→S2082→S2210,之后在S2210站点换乘L417路车下行路线,途经S2210→S3332→S3351→S0485。此种转乘方式经过了S0036、S2210站点的共两次换乘,共经过了33站,所花费的时间为 分钟。

(本问有3种不同的换乘最佳方案,其他2种换乘方案详见附录1-2)

⑥S0087→S3676的最佳路线:首先在L454路车上行线路从S0087站开始乘车,途经S0857→S0630→S1427→S1426→S0541→S0978→S3389→S1919→S0641→S2840→S3496,然后在S3496站点换乘L209路车下行路线,途中经过以下站点:

S3496→S1883→S1159→S2699→S2922→S3010→S0583→S1987→S0082→S3676

此种换乘方式共经过了20站。所花费的时间为 分钟。

4、模型Ⅱ 费用最低的线路选择模型

⑴模型的准备

我们仍以从起始站S3359到终到站S1828的线路为例进行说明。

①首先对题目给出的分段计价的信息进行数据处理,通过搜索找到所有的分段线路,然后根据分段计价对乘坐站数不同而制定的具体计价要求(0~20站:1元;21~40站:2元;40站以上:3元)建立一个价格向量,又由于共有86列的数据,于是我们得到一个前20列为1,21到40列为2,41到86列为3的向量

则 即为在分段计价情况下从起始站到中转站的公汽票价, 为分段计价情况下从中转站到终到站的票价( 、 为整数,且 )。

②在模型Ⅰ方法的基础上,得到通过在中转站的转乘所计算出来的从起始站S3359到终到站S1828所经过的站点总数 ,然后判断得到的各个方案所经过的路线是分段计价还是单一票制。因此,对从起始站到中转站的票价 和从中转站到终到站的票价 要进行分段讨论:

③在模型Ⅰ结果的基础上,为了达到在所用时间最少的同时乘车费用尽可能少的要求和便于大量数据进行比较处理以及在多种消耗时间最少的最佳线路中进行筛选,我们在模型Ⅰ计算出的最佳线路的基础上计算出一个费用 并与实际乘车的最低费用 进行比较,看其是否相等。如果 ,说明我们第一问中的最佳线路不仅满足了所消耗时间最少的目标,而且还使得其所花费的乘车成本最低,这样可以达到一举两得的效果;如果 ,说明我们在所消耗时间条件下的乘车费用不一定最低,于是我们再通过排序得到最小结果以及其所对应的行进线路和中转站。

⑵模型的建立

由以上分析,我们可以得到目标函数:

由于我们在求解时考虑了耗时最少情况下能否同时达到乘车费用最少,因此我们目标函数的求解需要分两步进行求解。首先,我们要对模型Ⅰ做出的耗时最少的最佳线路计算其费用,如果与通过排序得到的最低费用相同,就可以同时达到耗时最少、费用最低的双目标,如果大于最低费用,我们就要利用下面的约束条件来计算出最低费用情况下的具体线路及中转站 ,可以得出约束条件。结合目标函数 有模型

目标函数:

约束条件为:

⑶算法步骤

设起始站为 ,终到站为 ,具体的算法实现如下:

①对矩阵 搜索得到分段计价线路矩阵 ,并构造分段价格向量 ;

②搜索求出 与 站点的数据在矩阵 中的位置,并构造成矩阵 ;

③在 的情况下查找矩阵 的公共元素,即 ;

④搜索出 中第 行的数据等于 以及 中第 行的数据等于 的数据所在列 ,只考虑 和 的情况;

⑤在模型Ⅰ计算出的 的最小值的基础上,计算得到价格 并计算出最低价格 ;

⑥若 ,则得到最佳线路结果;若 ,输出最低费用情况下的线路及中转站点。

⑷模型结果

利用 编程实现可得到结果(程序详见附录):

①S3359→S1828的最佳路线:首先在L436路车下行路线从S3359站开始乘车,途经S2026→S1132→S2266→S2263→S3917→S2303→S2301→S3233→S0618→S0616→S2112→S2110→S2153→S2814→S2813→S3501→S3515→S3500→S0756→S0492→S0903→S1768→S0955→S0480→S2703→S2800→S2192→S2191→S1829→S3649→S1784,然后在S1784站点换乘L217路车下行路线,下站即为S1828站;

或者在S1784站点转乘L167路下行路线,下站也是S1828站。

因此,得到 =31, ,

两种换乘方式都经过了32个站点。乘车费用均为3元,与实际的最低费用相等。

②S1557→S0481的最佳路线:

③S0971→S0485的最佳路线:首先在L013路车下行路线从S0971站开始乘车,途经S3832→S3341→S2237→S3565→S3333→S1180→S3494→S1523→S1520→S1988→S1743→S1742→S1181→S1879→S3405→S2517→S3117→S2954→S0531→S2184,然后在S2184站点换乘L417路车下行路线,途中经过以下站点:S2184→S0992→S2322→S1770→S1789→S2119→S2116→S3544→S3186→S3409→S2717→S1402→S2840→S0643→S2079→S1920→S2480→S2482→S2210→S3332→S3351→S0485

此种换乘方式经过了41站。乘车费用均为3元,与实际的最低费用相等。

④S0008→S0073的最佳路线:首先在L463路车下行路线从S0008站开始乘车,途经S0008→S1383→S1688→S3459→S2532→S3474→S0369→S1776→S2855→S0338→S2849→S2782→S0935→S2084→S2083,然后在S2083站点换乘L057路车上行路线,途中经过以下站点:S2083→S1538→S3547→S0609→S0483→S0604→S2650→S3470→S2619→S2340→S3162→S2181→S0073

此种换乘方式共经过了26站。乘车费用均为2元,与实际的最低费用相等。

(本问有14种不同的换乘最佳方案,其他13种换乘方案详见附录1-1)

⑤S0148→S0485的最佳路线:

首先在L308路车上行路线从S0148站开始乘车,途经S0462→S0361→S1797→S2221→S0302→S2222→S2737→S1716→S0128→S2268→S1308→S1391→S2272→S0036然后在S0036站点换乘→S路车上行路线,途经S0036→S3233→S0618→S0617→S0721→S2057→S2361→S0608→S0399→S2535→S2534→S0239→S0497→S2090→S2082→S2210,之后在S2210站点换乘L417路车下行路线,途经S2210→S3332→S3351→S0485。此种转乘方式经过了S0036、S2210站点的共两次换乘,共经过了33站,所花费的时间为 分钟。

(本问有3种不同的换乘最佳方案,其他2种换乘方案详见附录1-2)

⑥S0087→S3676的最佳路线:首先在L454路车上行线路从S0087站开始乘车,途经S0857→S0630→S1427→S1426→S0541→S0978→S3389→S1919→S0641→S2840→S3496,然后在S3496站点换乘L209路车下行路线,途中经过以下站点:S3496→S1883→S1159→S2699→S2922→S3010→S0583→S1987→S0082→S3676

此种换乘方式共经过了20站。乘车费用均为2元,与实际的最低费用相等。

最少的乘车路线。

二、问题二的分析与求解

1、模型Ⅲ 分步线性规划模型

⑴模型的准备

我们在模型Ⅰ中只以公共汽车为交通工具的基础上,引进地铁这一快捷方便的搭乘工具,重新建立一套新的公交和地铁最佳线路选择问题的自主查询系统,使得这一系统能够自主的提供一个公交和地铁交替使用的用时最少的线路,从而为赶时间的乘客提供更加人性化的建议。

这里共给出T1、T2两条地铁线路和地铁站台相邻的若干个公汽站,且两条线路可以相互换乘,换乘只能在D12和D18两个站点。因此我们认为两个地铁是相通的,可以任意换乘,且可以在从一个地铁站到达其他任意一个地铁站。这里我们将T1、T2两条地铁线路看成一条地铁。

建立地铁站台相邻公汽矩阵 :

T1,T2地铁站台相邻公汽矩阵分别为 , :

由于我们将T1、T2两条地铁线路视为一条地铁线路,因此可以得到所有地铁站台相邻公汽矩阵 :

⑵模型的算法

①在所有地铁站台相邻公汽矩阵 中搜索,是否有所要的起始站 与终到站 ,如果有则可以通过地铁从起始站 直达终到站 ;

②当在①中没有搜索到起始站 与终到站 时,这说明地铁只能作为整个线路中的中间搭乘工具,前后都必须通过搭乘公共汽车来连通起始站,如图6

图6  公汽、地铁换乘示意图

这里就涉及到在该在哪一站搭乘地铁和在哪一站下地铁这一问题。为解决这一问题,我们将矩阵 中所有元素进行迭代搜索,这一步骤分成两步完成:先搜索经过起始站 的所有线路矩阵B与矩阵 的公共元素 ,其中 ;再搜索经过终到站 的所有线路矩阵C与矩阵 的公共元素 ,其中 。

③这里我们依据时间t最小为目标,选取所有线路中的最短路线。这里t是由四部分组成,分别为乘坐公共汽车L1的时间t1、乘坐地铁T的时间t2、乘坐公共汽车L2的时间t3、交通工具换乘用时t0,其中交通工具换乘用时t0包括:换乘地铁平均耗时t01=4分钟(其中步行时间2分钟);地铁换乘公汽平均耗时t02=7分钟(其中步行时间4分钟);公汽换乘地铁平均耗时t03=6分钟(其中步行时间4分钟);因此总用时t为:

其中t1、t2、t3是由经过的站数决定的,设L1、L2、T经过的站点数依次为:n1、n2、n3,则:

由于②中我们是分两步来进行的,因此要分两步求最优线路,即两段都是最短线路时得到最优线路。

④在③中存在T1、T2两条地铁线路的转乘问题,这就涉及如何计算n2的问题。由于地铁转乘只能在D12、D18里两个站台,需要对于不同的上下地铁的站台进行分类讨论,计算出有效站台数n2。我们通过if语句将各种可能会出现的情况,分别进行了讨论,这样就能保证得到的是有效站台数n2,即符合地铁行驶和转乘实际。

模型建立:

根据上述算法可建立规划问题,目标函数为: ,根据②的叙述建立分步线性规划模型,并通过Matlab编程实现:

约束条件:

约束条件:

⑶模型的结果

①S3359→S1828:

从起始站S3359乘坐L015上行,途经S3359→S2266→S3917→S2303→S1327→S3068;在S3068下车,从D08转乘地铁T1上行,途经D08→D09→D10→D11→D12→D13→D14→D15→D16→D17→D18;从D18下地铁T1,转乘T2,途经D18-D33-D34-D35-D36-D37-D38;从D38下地铁T2,从S3262转乘L041上行,途经S3262-S1772-S0259-S0258-S1781-S1790-S0458-S1792-S1783-S1671-S1828;即到达终到站S1828。用时94分钟,与模型Ⅰ用时101分钟相比,节省时间7分钟,但比模型Ⅱ多花去3元钱。

②S1557→S0481:

线路1:从起始站S1557乘坐L363下行,途经S1557-S3158-S2628-S3408-S2044 -S1985- S2563-S2682-S2735-S0029-S0055-S0051-S1919;在S1919下车,从D20转乘地铁T1下行,途经D20→D19→D18;从D18下地铁T1,转乘T2,途经D18-D33-D34-D35-D36-D37-D38-D39-D24;从D24下地铁T2,从S0537转乘L516上行,途经S0537-S2651-S3013-S1808-S1173-S0910-S3517-S0453-S2424-S1174-S0902 -S0903-S2101-S0481;即到达终到站S0481。

线路2:从起始站S1557乘坐L084下行,途经S1557-S3158-S2628-S3408-S2044- S1985-S2563 -S2682-S0028-S0029-S0055-S0051-S1919;在S1919下车,从D20转乘地铁T1下行,途经D20→D19→D18;从D18下地铁T1,转乘T2,途经D18-D33-D34-D35-D36-D37-D38-D39-D24;从D24下地铁T2,从S0537转乘L516上行,途经S0537-S2651-S3013-S1808-S1173-S0910-S3517-S0453-S2424 -S1174-S0902 -S0903-S2101-S0481;即到达终到站S0481。

线路1和线路2用时均为117分钟,与模型Ⅰ用时分钟相比,节省时间分钟,但多花去2元钱;与模型Ⅱ

③S0971→S0485

线路1:

从起始站S0971乘坐L094上行,途经S0971-S3571-S1609-S0345-S1419-S2389 -S0567;在S0567下车,从D01转乘地铁T1上行,途经D01-D02-D03-D04-D05-D06 -D07-D08-D09-D10-D11-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21;从D21下地铁T1,从S0464转乘L469下行,途经S0464-S0964-S3189-S2810-S2385-S0485;即到达终到站S0485。

线路2:

从起始站S0971乘坐L094上行途经S0971-S3571-S1609-S0345-S1419-S2389-S0567;在S0567下车,从D01转乘地铁T1上行,途经D01-D02-D03-D04-D05-D06-D07-D08- D09-D10-D11-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21;从D21下地铁T1,从S0466转乘L051上行,途经S0466-S3189-S2810-S2385-S0071-S0485;即到达终到站S0485。

线路3:

从起始站S0971乘坐L094上行,途经S0971-S3571-S1609-S0345- S1419-S2389 -S0567;在S0567下车,从D01转乘地铁T1上行,途经D01-D02-D03-D04-D05-D06-D07- D08-D09-D10-D11-D12- D13-D14-D15-D16-D17-D18-D19-D20-D21;从D21下地铁T1,从S0464转乘L104上行,途经S0464-S0964-S3189-S2810-S2385-S0485;即到达终到站S0485。

线路4:

从起始站S0971乘坐L094上行,途经S0971-S3571-S1609- S0345-S1419 -S2389-S0567;在S0567下车,从D01转乘地铁T1上行,途经D01-D02-D03-D04-D05 -D06-D07-D08-D09-D10-D11-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21;从D21下地铁T1,从S0464转乘L395下行,途经S0464-S0964-S3189-S2810-S2385-S0485;即到达终到站S0485。

线路5:

从起始站S0971乘坐L094上行,途经S0971-S3571-S1609 -S0345-S1419 -S2389-S0567;在S0567下车,从D01转乘地铁T1上行,途经D01-D02-D03-D04-D05-D06 -D07-D08-D09-D10-D11-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21;从D21下地铁T1,从S0466转乘L450下行,途经S0466-S3189-S2810-S2385-S0071-S0485;即到达终到站S0485。

线路6:

从起始站S0971乘坐L119下行,途经S0971-S3571-S1609- S0345-S1419 -S2389- S0567;在S0567下车,从D01转乘地铁T1上行,途经D01-D02-D03-D04-D05-D06 -D07-D08-D09 -D10-D11-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21;从D21下地铁T1,从S0464转乘L469下行,途经S0464-S0964-S3189-S2810-S2385-S0485;即到达终到站S0485。

线路7:

从起始站S0971乘坐L119下行,途经S0971-S3571-S1609-S0345-S1419- S2389-S0567;在S0567下车,从D01转乘地铁T1上行,途经D01-D02-D03-D04- D05-D06-D07-D08-D09-D10-D11-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21;从D21下地铁T1,从S0466转乘L051上行,途经S0466-S3189-S2810-S2385-S0071-S0485;即到达终到站S0485。

线路8:

从起始站S0971乘坐L119下行,途经S0971-S3571-S1609-S0345-S1419-S2389 -S0567;在S0567下车,从D01转乘地铁T1上行,途经D01-D02-D03-D04-D05 -D06-D07-D08-D09-D10-D11-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21;从D21下地铁T1,从S0464转乘L104上行,途经S0464-S0964-S3189-S2810-S2385-S0485;即到达终到站S0485。

线路9:

从起始站S0971乘坐L119下行,途经S0971-S3571-S1609-S0345-S1419-S2389-;在S0567下车,从D01转乘地铁T1上行,途经S0567

D01-D02-D03-D04-D05-D06-D07-D08-D09-D10-D11-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21;从D21下地铁T1,从S0464转乘L395下行,途经S0464-S0964-S3189-S2810-S2385-S0485;即到达终到站S0485。

线路10:

从起始站S0971乘坐L119下行,途经S0971-S3571-S1609 -S0345-S1419-S2389-S0567;在S0567下车,从D01转乘地铁T1上行,途经

D01-D02-D03-D04-D05-D06-D07-D08-D09-D10-D11-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21;从D21下地铁T1,从S0466转乘L450下行,途经S0466-S3189-S2810-S2385-S0071-S0485;即到达终到站S0485。

10条线路用时均为93分钟,与模型Ⅰ用时128分钟相比,节省时间35分钟,但多花去2元钱;与模型Ⅱ

④S0008→S0073

从起始站S0008乘坐L200上行,途经S0008-S3412-S2743 -S2544-S2953 -S0778 -S2534;在S2534下车,从D15转乘地铁T1下行,途经

D15-D14-D13-D12;从D12下地铁T1,转乘T2,途经D12- D26- D25;从D25下地铁T2,从S0525转乘L103上行,途经S0525-S3162-S0073;即到达终到站S0073。

线路用时均为53.5分钟,与模型Ⅰ用时83分钟相比,节省时间29.5分钟,但多花去2元钱;与模型Ⅱ

⑤S0148→S0485

线路1:

从起始站S0148乘坐L024下行,途经S0148-S0927-S2830-S2070-S1487;在S1487下车,从D02转乘地铁T1上行,途经D02-D03-D04-D05-D06-D07-D08-D09- D10-D11-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21;从D21下地铁T2,从S0464转乘L469下行,途经S0464-S0964-S3189-S2810-S2385-S0485;即到达终到站S0485。

线路2:

从起始站S0148乘坐L024下行,途经S0148-S0927-S2830-S2070-S1487;在S1487下车,从D02转乘地铁T1上行,途经D02-D03-D04-D05-D06-D07-D08-D09-D10-D11 -D12-D13-D14-D15-D16-D17-D18-D19-D20-D21;从D21下地铁T2,从S0466转乘L051上行,途经S0466-S3189-S2810-S2385-S0071-S0485;即到达终到站S0485。

线路3:

从起始站S0148乘坐L024下行,途经S0148-S0927-S2830-S2070-S1487;在S1487下车,从D02转乘地铁T1上行,途经D02-D03-D04-D05-D06-D07-D08-D09- D10-D11-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21;从D21下地铁T2,从S0464转乘L104上行,途经S0464-S0964-S3189-S2810-S2385-S0485;即到达终到站S0485。

线路4:

从起始站S0148乘坐L024下行,途经S0148-S0927-S2830-S2070-S1487;在S1487下车,从D02转乘地铁T1上行,途经D02-D03-D04-D05-D06-D07-D08-D09-D10-D11

D12-D13-D14-D15-D16-D17-D18-D19-D20-D21;从D21下地铁T2,从S0464转乘L395下行,途经S0464-S0964-S3189 -S2810-S2385-S0485;即到达终到站S0485。

线路5:

从起始站S0148乘坐L024下行,途经S0148-S0927-S2830-S2070-S1487;在S1487下车,从D02转乘地铁T1上行,途经D02-D03-D04-D05-D06-D07-D08-D09-D10-D11

-D12-D13-D14-D15-D16-D17-D18-D19-D20-D21;从D21下地铁T2,从S0466转乘L450下行,途经S0466-S3189-S2810-S2385-S0071-S0485;即到达终到站S0485。5条线路用时均为117分钟,与模型Ⅰ用时分钟相比,节省时间分钟,但多花去2元钱;与模型Ⅱ

⑥S0087→S3676

从起始站S0087,在D27乘坐地铁T2,途经D27-D28-D29-D30-D31-D32-D18-D33

-D34-D35-D36;在D36下地铁T2,即到达终到站S3676。

三、问题三的分析与求解

1、问题三的分析

第三题是在前面问题的基础上,加入了步行这一较为自主化的“交通工具”,使得原本的选择最优线路模型不再使用,于是我们这里建立了一个线路综合评价模型,通过分类讨论的方式,提供适合各种情况的线路选择方案,从而解决在三种交通工具并行时的路线选择问题。

2、模型Ⅳ 线路综合评价模型

我们使用综合评价的方法对不同的情况进行分类,分类的标准是:乘坐的交通工具。由于这里有三种交通工具:步行、地铁、公共汽车,所有我们有 种不同的搭乘方式,可分为三类:搭乘一种交通工具,搭乘两种交通工具,搭乘三种交通工具。下面我们来分别讨论。

⑴搭乘一种交通工具

①搭乘公共汽车

这时可以根据模型1和模型2来解决选择线路问题。

②搭乘地铁

这种方式只适用于起始站 、 属于地铁的相邻公汽站台矩阵 ,这时可以通过在地铁直达。

③步行

步行可以到达任何终点站,但从实际出发,我们认为步行距离不能过长,这里我们认为当起始站 、 相隔不到两站时,可以采取步行;起始站相隔超过两站时,我们认为步行不实际。

⑵搭乘两种交通工具

①搭乘公共汽车和地铁

这时就是等同于问题2,即模型3的选择线路方法。

②搭乘公共汽车和步行

这时我们可以在问题1的基础上考虑加入步行。这里我们只提供在以下情况下采取步行较合适:

a.为减少换乘次数:两公汽站台只相隔一站,可采取步行,从而减少了一次的换乘;

b.为减少路费:因为分段计价的公共汽车票价为:0~20站:1元;21~40站:2元;40站以上:3元。所以在终点站或换乘站 在21站处时,我们可提前在20站出下车,再步行1站到达终点站或换乘站,从而节省1元;

c.当出现两站之间出现如图示情况时,可考虑不行到达终到站。

注:红线为汽车线路,蓝线为步行线路

图6 两站间乘车线路远比步行远的示意图

③搭乘地铁和步行

a. 当起始站 、 不属于或不全属于地铁的相邻公汽站台矩阵 时,需要通过步行才能到达终点;

b. 由于地铁只有T1、T2两条线路,且两条线路只能在D12和D18处转乘,因此在需要换乘地铁时,可考虑步行到达地铁站D12或D18。

⑶搭乘三种交通工具(地铁、公共汽车、步行)

已知所有站点之间的步行时间,假设任意两站点i、j之间的步行时间为 ,通过转乘从i站到达j站所用时间t,转乘用时t0,则我们可在模型Ⅲ的基础上加入一个判断语句,即t+t0与 比较大小,如果t+t0较小,则说明通过转乘更省时;反之,步行更省时同时也省钱,则采取步行从i站到达j站。于是可以将模型Ⅲ中的规划问题进行一定的修改,得到规划问题如下:

目标函数为: ,建立分步规划模型:

约束条件:

约束条件:

 

§6、模型的进一步分析

一、可靠性分析

一个好的自主查询计算机系统不能由于初始数据的改变而导致无法得到最优方案。这里由于整个系统完全是通过计算机模拟实现的,因此对输入数据库的所有数据都可以进行处理,从而得到最优方案。

二、实时性分析

由于本题中的所有最优路线都是完全通过计算机模拟实现的,所以完全可以推广为一个解决公交线路选择问题的自主查询计算机系统。把现实中某城市的所有公共汽车线路和地铁线路传输到这一系统内,使得这一系统可以真正投入使用。可以在各个公交和地铁站点、商场、街市处安放这个自主查询系统的服务器,从而提高公共交通的普适性,方便市民出行的同时为其提供高效省时的回家或上班路线,改善公共交通的服务水平和提高乘客的舒适度以及公交公司以及公交公司的经济、社会效益,从而为北京迎接奥运所提出的“绿色出行”提供了更好的解决方案。

§7、模型的评价与推广

一、模型的评价

1、模型的优点:

⑴本文针对各种人群对乘坐公交观看北京奥运会的不同选择,分别考虑了不同层次的选择需求,对耗时最少和乘车费用最低的情况进行了细致地讨论,得到了这两种情况下从某一起始站到终到站的详细乘车路线以及换乘车的站点信息,同时在只考虑公汽、考虑公汽与地铁以及考虑步行等交通方式的情况下逐步深入、层层递进,得到了基本上可以满足所有乘客的各种不同出行需求的线路选择方案,方便了人们的出行。

⑵本文在对公汽线路的大量数据进行处理时,我们对环行线路与双向线路(上下行一致的线路)等特殊的路线都进行了符合生活实际的处理,使得我们处理的数据较为科学、合理,因此得到的结果也较为准确。

2、模型的缺点:

⑴由于北京市交通发达,公汽以及地铁的站点较多,交通网络复杂,增加了人们在选择乘车方案时候的盲目性。

⑵由于我们得到的最佳路线选择是对耗时最少与乘车费用最低分开考虑的,所以在很多情况下我们不能达到两个目标同时实现的目的,因此不能达到一种完全最佳状态。

⑶本文在考虑时做了相邻站平均行驶时间相等的简化,而在实际中那种不相等的情况随处可见,因此模型具有一定的局限性。

二、模型的推广

由于本题的模型可以推广成为一个线路选择的自主查询计算机系统,所以我们可以将其应用到以下方面:

1、将自主查询系统推广到手机彩信或短信

建立一个公交线路手机彩信MMS或短信SMS查询平台,让用户查询不受地点、时间限制。其中彩信可以将查询结果以电子地图的方式发回到用户手机上,让外来游客更容易找到目的地和乘车线路;同时短信费用比彩信费用低,因此短信将更具普适性[7]。其系统结构设计如图7所示。

图7系统结构设计图:

 

网络拓扑结构图[8]:

图8 网络拓扑结构图

 

2、建立旅游线路选择系统

在出游之前,旅游者一定都会根据自己的具体情况 (比如假期长短,资金多少,兴趣爱好等)做一些适合自己的选择。这就需要收集一些相关的信息(如景点,交通等)。在信息社会里,与传统的获取信息的方式相比,通过网络获得旅游信息具有速度快、信息全、内容新等优点。所以旅游者更多的倾向于用互联网来寻找自己所需的信息。一次旅行往往都不止去一个景点,那么在众多景点中,就曾在一个最佳的旅游线路。这个系统就可以让旅游者在不同的需求下(时间,金钱,兴趣)实现旅游线路的最佳选择,通过人机对话方式给旅游者提供理想的决策方案[9]。旅游线路选择系统结构图9:

图9  旅游线路选择系统结构图

同时这个自主选择系统还有很多方面的应用,这里不再赘述。

参考文献

[1]胡守信,李柏年.基于Matlab的数学实验[M].北京:科学出版社,2004年第1版;

[2]朱方生,李大美,李素珍.计算方法[M].武汉:武汉大学出版社,2003年第1版;

[3]喻文健译.MATLAB数值计算[M].北京:机械工业出版社,2006年第1版;

[4]钱颂迪等.运筹学[M].北京:清华大学出版社,1990年第2版;

[5]姜启源,谢金星,叶俊.数学模型[M].北京:高等教育出版社,2003年第3版;

[6]杨启帆等.数学模型案例集[M].北京:高等教育出版社,2006年第1版;

[7] 艾菊梅,周书民,陆玲.基于WebGIS公交查询平台与移动增值服务[J].微计算机信息(测控自动化)2007年第23卷4—1期;

[8] 艾菊梅,蒋年德.基于WebGIS公交查询平台的MMS技术及实现[J],微计算机信息(测控自动化),2007年第23卷6—1期;

[9] 陈旺亮,查良松,杜美庆.基于WebGIS的旅游线路选择决策支持系统研究[J],国土资源科技管理(2007)P84~P86.

附录1

 

1-1  S0008→S0073在所用时间最少情况下的其余最佳路线

最佳线路2

最佳线路3

最佳线路4

最佳线路5

最佳线路6

第一次乘车

L159路下行线

第一次乘车

L159路下行线

第一次乘车

L159路下行线

第一次乘车

L159路下行线

第一次乘车

L159路下行线

中转站

S0400

中转站

S2633

中转站

S3053

中转站

S0291

中转站

S2683

第二次乘车

L474路上行线

第二次乘车

L474路上行线

第二次乘车

L474路上行线

第二次乘车

L058路下行线

第二次乘车

L058路下行线

所经站点数

26

所经站点数

26

所经站点数

26

所经站点数

26

所经站点数

26

花费时间(分)

83

花费时间(分)

83

花费时间(分)

83

花费时间(分)

83

花费时间(分)

83

 

最佳线路7

最佳线路8

最佳线路9

最佳线路10

最佳线路11

第一次乘车

L159路下行线

第一次乘车

L159路下行线

第一次乘车

L159路下行线

第一次乘车

L159路下行线

第一次乘车

L159路下行线

中转站

S3614

中转站

S0491

中转站

S2559

中转站

S3315

中转站

S2559

第二次乘车

L058路下行线

第二次乘车

L474路上行线

第二次乘车

L474路上行线

第二次乘车

L058路下行线

第二次乘车

L464路上行线

所经站点数

26

所经站点数

26

所经站点数

26

所经站点数

26

所经站点数

26

花费时间(分)

83

花费时间(分)

83

花费时间(分)

83

花费时间(分)

83

花费时间(分)

83

 

最佳线路12

最佳线路13

最佳线路14

第一次乘车

L355路下行线

第一次乘车

L355路下行线

第一次乘车

L355路下行线

中转站

S2263

中转站

S3917

中转站

S2303

第二次乘车

L345路上行线

第二次乘车

L345路上行线

第二次乘车

L345路上行线

所经站点数

26

所经站点数

26

所经站点数

26

花费时间(分)

83

花费时间(分)

83

花费时间(分)

83

 

1-3  S0008→S0073在乘车费用最低情况下的其余最佳路线

最佳线路2

最佳线路3

最佳线路4

最佳线路5

最佳线路6

第一次乘车

L159路下行线

第一次乘车

L159路下行线

第一次乘车

L159路下行线

第一次乘车

L159路下行线

第一次乘车

L159路下行线

中转站

S0400

中转站

S2633

中转站

S3053

中转站

S0291

中转站

S2683

第二次乘车

L474路上行线

第二次乘车

L474路上行线

第二次乘车

L474路上行线

第二次乘车

L058路下行线

第二次乘车

L058路下行线

所经站点数

26

所经站点数

26

所经站点数

26

所经站点数

26

所经站点数

26

乘车费用(元)

2

乘车费用(元)

2

乘车费用(元)

2

乘车费用(元)

2

乘车费用(元)

2

 

最佳线路7

最佳线路8

最佳线路9

最佳线路10

最佳线路11

第一次乘车

L159路下行线

第一次乘车

L159路下行线

第一次乘车

L355路下行线

第一次乘车

L355路下行线

第一次乘车

L355路下行线

中转站

S3614

中转站

S0491

中转站

S2263

中转站

S3917

中转站

S2303

第二次乘车

L058路下行线

第二次乘车

L474路上行线

第二次乘车

L345路上行线

第二次乘车

L345路上行线

第二次乘车

L345路上行线

所经站点数

26

所经站点数

26

所经站点数

26

所经站点数

26

所经站点数

26

乘车费用(元)

2

乘车费用(元)

2

乘车费用(元)

2

乘车费用(元)

2

乘车费用(元)

2

 

 

 

 

1-2  S0148→S0485二次换乘时的其余两种在所用时间最少情况下的最佳路线

起始站

开始行使路线

第一换乘站

换乘线路

第二中转站

最后行使路线

终到站

S0148

L308上行

S0036

L156上行

S3332

L417下行

S0485

S0148

L308上行

S0036

L156上行

S3351

L417下行

S0485

 

 

1-4  S0148→S0485二次换乘时的其余两种在乘车费用最低情况下的最佳路线

起始站

开始行使路线

第一换乘站

换乘线路

第二中转站

最后行使路线

终到站

价格(元)

S0148

L308上行

S0036

L156上行

S3332

L417下行

S0485

3

S0148

L308上行

S0036

L156上行

S3351

L417下行

S0485

3

 

附录2

2-1   模型Ⅰ 第一组数据程序

[m,n]=find(A==3359);

[M,N]=find(A==1828);

B=A(m,:);

C=A(M,:);

k=1;

for i1=1:numel(m)

    for j1=1:86

        if B(i1,j1)~=0,

           for i2=1:numel(M),

               for j2=1:86,

                   if C(i2,j2) == B(i1,j1) ,

         [k1,h1]=find(B(i1,:)==3359);

        [k2,h2]=find(C(i2,:)==1828);

                     if (j1-h1>0)&( h2-j2>0)

           S(k)=j1-h1+h2-j2;

           ii1(k)=i1;

           jj1(k)=j1;

           ii2(k)=i2;

           jj2(k)=j2;

           k=k+1;

   

                         end

                      end

                 end

            end

        end

    end

end

[F,i]=sort(S)       

x=i(1);

S=min(S)         %所用的最少站

t=3*S+5          %乘车总耗时

l1=m(ii1(x))/2     %乘坐线路1

l2=M(ii2(x))/2     %转乘坐线路2

B(ii1(x),jj1(x))    %求转换站

C(ii2(x),jj2(x))

 

 

2-2  模型Ⅱ  第一组数据程序

a=[1,2,5,6,7,8,10,11,12,13,14,15,16,17,18,19,21,22,25,26,27,28,29,33,37,38,39,40,42,43,44,46,47,50,51,53,54,56,57,58,59,62,63,64,65,66,68,71,72,75,77,79,81,82,84,85,88,90,91,94,97,98,99,100,103,104,105,109,112,115,116,118,119,121,122,123,124,125,127,128,129,130,131,132,133,134,135,137,139,140,141,142,145,148,152,154,155,157,159,160,163,164,166,167,170,171,175,177,180,184,186,187,189,190,191,192,194,196,198,199,201,204,205,210,211,218,221,222,223,227,229,230,232,233,236,240,242,244,248,249,255,256,257,259,260,261,262,263,264,266,267,271,275,276,277,280,282,283,285,286,287,289,290,295,296,297,299,300,301,302,304,305,308,309,311,312,314,315,317,318,320,321,323,324,325,329,330,331,332,337,338,339,340,345,347,348,351,353,354,355,358,359,360,361,363,365,366,368,372,373,374,375,377,378,382,384,386,387,391,392,395,399,401,405,406,409,411,413,415,417,418,419,422,423,424,427,428,429,430,435,436,437,439,440,441,442,443,446,447,448,449,450,454,456,457,460,461,464,465,468,469,470,473,474,475,476,477,478,481,482,484,485,486,496,497,498,502,503,510,511,513,516,518,519];

a1=2*a;

a2=2*a-1;

a=[a1,a2];      %分价计算的线路

w=[ones(1,20),2*ones(1,20),3*ones(1,46)];     %便于计算分价计算线路的价格

k=1;

[m,n]=find(A==3359);

[M,N]=find(A==1828);

% for i=1:numel(m);

%     for j=1:numel(M);

%         if m(i)==M(j),

%             if N(j)>n(i),

%                 S=N(j)-n(i);

%                 if find(a==m(i))

%                     O(k)=w(S);  %向量O用来存放价钱

%                 else  O(k)=1;

%                 end

%                 L(k)=m(i);

%                 k=k+1;

%             end

%         end

%     end

%  end

% [F,p]=sort(O)       

% x=p(1);

% o=min(O)

% l=L(x)/2

% k=1

B=A(m,:);

C=A(M,:);

for i1=1:numel(m)

    for j1=1:86

        if B(i1,j1)~=0,

           for i2=1:numel(M),

               for j2=1:86,

                   if C(i2,j2) == B(i1,j1) ,

                      [k1,h1]=find(B(i1,:)==3359);

                      [k2,h2]=find(C(i2,:)==1828);

                      if (j1-h1>0)&( h2-j2>0)

                          S(k)=j1-h1+h2-j2;

                          if  find(a==m(i1))

                              O1=w(j1-h1);

                          else O1=1;

                          end

                          if find(a==M(i2))

                              O2=w(h2-j2);

                          else O2=1;

                          end

                          OO(k)=O1+O2;

                          ii1(k)=i1;

                          jj1(k)=j1;

                          ii2(k)=i2;

                          jj2(k)=j2;

                          k=k+1;

                      end

                     end

                end

            end

        end

    end

end

[F,i]=sort(S)       

x=i(1);

s=min(S)

oo=min(OO)  %所需的最小价格

oo1=OO(x)    %最小路程对应的实际价格

l1=m(ii1(x))/2  

l2=M(ii2(x))/2  

B(ii1(x),jj1(x)) 

C(ii2(x),jj2(x))

if oo~=oo1    %两个价格不同时,求出最小价格对应的路径

  

   [F,q]=sort(OO)        

   x=q(2);

   ll1=m(ii1(x))/2   %所要求的路径

   ll2=M(ii2(x))/2  

   B(ii1(x),jj1(x)) 

   C(ii2(x),jj2(x))

   S(x)              %价格最小时所经过的站台数目

End

 

 

2-3  模型Ⅲ  第一组数据程序

 [m,n]=find(A==3359);

[M,N]=find(A==1828);

B=A(m,:);

C=A(M,:);

D=[567   42    25    0     0

1487       0     0     0     0

303  302  0     0     0

566  0     0     0     0

436  438  437  435  0

392  394  393  391  0

386  388  387  385  0

3068       617  619  618  616

1279       0     0     0     0

2057       721  722  720  0

70    2361       3721       0     0

609  608  0     0     0

2633       399  401  400  0

3321       2535       2464       0     0

3329       2534       0     0     0

3506       167  168  0     0

237  239  238  236  540

668  0     0     0     0

180  181  0     0     0

2079       2933       1919       1921       1920

465  467  466  464  0

3457       0     0     0     0

2512       0     0     0     0

537  3580       0     0     0

526  528  527  525  0

3045       605  607  0     0

609  608  0     0     0

87    88    86    0     0

855  856  854  857  0

631  632  630  0     0

3874       1426       1427       0     0

211  539  541  540  0

978  497  498  0     0

668  0     0     0     0

1894       1896       1895       0     0

1104       576  578  577  0

3010       583  582  0     0

3676       427  61    60    0

1961       2817       455  456  0

3262       622  0     0     0

1956       289  291  0     0

];

k=1;

for i1=1:numel(m)

    for j1=1:86

        if B(i1,j1)~=0,

           for i3=1:41,

               for j3=1:5,                 

                   [k1,h1]=find(B(i1,:)==3359);

                   [k2,h2]=find(D==D(i3,j3));

                    if D(i3,j3)==B(i1,j1)

                       if (j1-h1>0)

                           if (i3<24)&(k2<24)                              %无需换乘地铁,乘坐地铁T1

                              S1(k)=3*(j1-h1)+2.5*(abs(k2-i3));

                           end

                           if (i3>=24)&(k2>=24)                            %无需换乘地铁,乘坐地铁T2

                              S1(k)=3*(j1-h1)+2.5*(abs(k2-i3));

                           end

                           if (i3<24)&(k2>=24)&(k2<31)                     %需换乘地铁,在D12换乘

                              S1(k)=3*(j1-h1)+2.5*(abs(k2-27)+abs(12-i3));

                           end

                           if (i3<24)&(k2>=38)                             %需换乘地铁,在D12换乘

                              S1(k)=3*(j1-h1)+2.5*(abs(k2-27)+abs(12-i3));

                           end

                           if (i3<24)&(k2>=31)&(k2<38)                     %需换乘地铁,在D18换乘

                              S1(k)=3*(j1-h1)+2.5*(abs(k2-34)+abs(18-i3));

                           end

                          ii1(k)=i1;

                          jj1(k)=j1;

                          ii3(k)=i3;

                          jj3(k)=j3;

                          k=k+1;

                       end

                   end

               end

           end

        end

    end

end

s1=min(S1)            %最少时间1

[F1,i]=sort(S1);       

x=i(1);

l1=m(ii1(x))/2       %乘坐线路1

l2=ii3(x)            %转乘的地铁站台

b1=B(ii1(x),jj1(x))  %求转乘站(上地铁站)

p=1;

for i2=1:numel(M)

    for j2=1:86

        if C(i2,j2)~=0,

           for i4=1:41,

               for j4=1:5,

                   [k1,h1]=find(D==D(i4,j4));

                   [k2,h2]=find(C(i2,:)==1828);

                   if D(i4,j4)==C(i2,j2)

                       if h2-j2>0

                          S2(p)=3*(h2-j2);

                          ii1(p)=i4;

                          jj1(p)=j4;

                          ii2(p)=i2;

                          jj2(p)=j2;

                          p=p+1;

                       end                    

                   end

               end

            end

        end

    end

end

s2=min(S2)            %最少时间2

[F2,i]=sort(S2);       

x=i(1);

l3=M(ii2(x))/2       %乘坐线路1

l4=ii1(x)            %转乘的地铁站台

b2=C(ii2(x),jj2(x))  %求转乘站(下地铁站)

t=s1+6+s2+7          %所用总时间

  评论这张
 
阅读(2716)| 评论(5)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017