2007年全国大学生数学建模竞赛B题 特等奖论文

5星(超过95%的资源)
所需积分/C币:48 2011-09-09 23:07:47 452KB PDF
188
收藏 收藏
举报

这是一篇全国大学生数学建模特等奖论文,写得很不错,希望和大家一起进步
公交查询系统的最佳乘车方案研究与设计 【摘要】 木文将站点实体间的线路选择抽象为图论最短路模型采用0-1整数规划衣述。建 立直达数据库Q作为数据基库,根据用户需求建立不同口标的0-1规划模型运用邻接 算法与 分别求解,最终方案集通过多目标分层序列排序输出到用户终端。 第一问,在数据处理阶段将直行、环行线路分别抽象为、条路线见 建 立査询系统时考虑服务器要同时响应多个请求,计算任务繁重,采用空间换取时间的 策咯,先建立站点至站点直达数据库Q米描述两两可直达站点的所有线路,用户査询 时,系统首先查询Q,得到所有直达车方案 在没有自达车情況下,针对不同用户需求,目标考虑:转乘次数、总耗时、总费 用、转站车辆是否始发、转乘站点负载量;在Q的基础上,量化不同目标为有向赋权 图的不同权矩阵见,以所求顶点到顶点的路径是否包含弧为决策变量 上述项用户需求为目标,始、终点连通为约朿建立0-1整数线性规划模型见 模型Ⅰ 为了能够为用户提供多种备选方案,我们首先使用基于 的邻接算法求解, 得到不同目标下的多种优化方案;对于邻接算法不易求解的多次转乘最优方案,我们 采用 软件自接求得仝局最优解:两种方法求解步骤见,综合方案集见 表 其中条线路时间最短目标分别为 分钟 两种求解方法的优劣在中给出了详细评价 第二问考虑公汽与地铁混排方案,首先把各地铁站点和周围的公汽站点集 抽象为同一新站点,把已知公汽线路到达都映射到,计算新直达数据 库,再结合地铁的费用与地汽换乘等待时间就可以把地铁线与公汽线结合,建立 多日标0-1整数线性规划模型见模型Ⅱ;对于转乘次数少于等于次的方案仍 可通过邻接算法求解;对」邻接算法不易求解的多次转乘最优方案,虽然模型规模较 人但约東与目标线性程度较好,还可用 软件求解得出条线路的全局最优解; 综合方案集见表 其中条线路时间最短目标分别为 、分钟;随后我们在与中给出了模型具体的评价与应用。 第三问综合考虑所有站点间步行与乘车情况,将其抽象为最短路问题下的叠加有 问赋权图,在此基础上以换乘次数为主要约東,以总行程时间包括步行最短、转站 车辆始发数最人、转乘站点负毂量最小、费用最低为目标,建立多目标0-1整数线性 规划模型见模型Ⅲ,并给岀了求解的一般步骤与算法。 最后本文还对实现査询系统的具体方案给出了建议,对各模型在实际中的应用价 值进行了详细讨论,并提出了改进方案。 关键字:邻接算法有向赋权图直达队列表分层序列法叠加有向赋权图 1问题重述 我国人民翘首企盼的第29届奥运会明年8月将在北京举行,届时有大量观众到现 场观看奧运比赛,其中大部分人将会乘坐公共交通工具(简称公交,包括公汽、地铁等) 出行。这些年来,城市的公交系统有了很大发展,北京市的公交线路已达800条以上, 使得公众的出行更加通畅、便利,但同时也面临多条线路的选择问题。针对市场需求, 某公司准备硏制开发一个解决公交线路选择问题的自主査询计算机系统。 为了设计这样一个系统,其核心是线路选择的模型与算法,应该从实际情况出发考 虑,满足查询者的各种不同需求。请你们解决如下问题: 1、仅考虑公汽线路,给出任意两公汽站点之间线路选择问题的一般数学模型与算 法。并根据附汞数据,利用你们的模型与算法,求出以下6对起始站亠终到站之问的最 佳路线(要有清哳的评价说明) (1)、S3359→S1828(2)、S1557→S0481(3)、S0971→S0485 4)、S0008→S0073(5)、S0148→S0485(6)、S0087→S3676 2、同时考虑公汽与地铁线路,解决以上问题 3、假设又知道所有站点之间的步行时间,请你给出任意两站点之间线路选择问题 的数学模型。 2问题分析 本题主要在二三种不同情況下,研究仁意两站点之间的线路选择问题。联系实际,公 众乘坐公交车主要考虑的因泰包括转乘次数、行程时间、车站始发情况、车站的车次负 毂量及乘车费用等因素。为满足一般公众的乘车需求,主要按照公众对不同乘车信息的 重视程度,确定出最佳的乘车路线。 仪考虑公汽线路的情况下,首先,需要根据题目给岀的公交线路信息数据,对每条 线路进行抽象处理,将分上下行的线路、双向行驶的线路和环行线路抽象为两条。然后, 主要考虑公众最关心的乘车因素,即转乘次数。在最少转乘次数的基础上考虑共众对其 他因素的需求,按照先后顺序考虑行程时间、车站始发情氿、车站的车次负载量及乘车 费用,给出供公众选用的多种参考方案。并考虑以时间为主要目标的情况下,建立最优 化模型确定任意两站点行程时间最短的方案。 在考虑问题二的情况卜,根据地铁与邻近站点可换乘的信息,可将每个地铁站点及 其对应的所有公交站点抽象成一个点处理。对于两条地铁线路可按照与问题一相同的抽 象方法处理。在此基础上按照相冋的思路确定任意两站点问的最佳方案。 考虑公交及地铁站点的实际分布情况,有时会出现步行小段距离再转车的情况更能 节省时间或转车次数。因此,研究此种情况下的出行方案对节省出行时间具有重要的实 际意义。 3模型假设 [1]假设车站不重名 L2」假设各路经上公交车发车频度相同; [3]假设相邻站点间平均行驶时问一定; [4]假设不出现交通阻塞,公交运行顺畅; 「5]假设不出现车辆故障及道路交通事故 [6]假设始发终点出入地铁需要步行1分钟; L7」假设公交准点到达,不考虑红绿灯等待时间。 4符号系统 弧是否在该有向赋权图| 站点→的总乘车时间; 第个站点是否为→的始发站; 站点→的乘车费用。 5公汽站点之间线路选择模型(问题一) 木节主要研究任意两公汽站点间线路选择的数学模型与算法。分别在不同行程需求 下推荐最佳路线,给出更为人性化的站点负载压力及转乘点是否为始发站的提小。 ●通畅、便利目标:换乘次数最少 不同的行程需求:行程耗时最少 行程费川最少 ●人性化查询设计:转乘站点是否为始发站提示; 站点负载压力提小 基于此,本部分共分如下四小节 5.0:数据处理,将三种公汽线路进行了图论抽象处理 5.1:建立了可査询两站之间直达线路的“公汽直达数据库Q”; 5.2:建立基于有向赋权图与最短路理论的0-1规划模型; 5.3:针对模型分别使用不同方法求解,得到多种适合不同用户的方案集。 5.0数据处理—三种公汽线路抽象处理 根据题中信息,公汽线路分三种,下面将这三种线路进行数据处理: (1)下行线、上行线原路返回 这种线路有两个端点站,在两个端点之间双向行车,而且两个方向上的行车路线相 同,绎过同样的站点序列。由于线路的方向不同,因此,卜行线和上行线可以抽象成两 条线路处理 (2)线路为环行线 实际中环形路线一般是双环,但在对这两条线路进行抽象时,为保证任意两站点距 离最近,把每条线路再抽象成2条(如图所示) (3)下行线与上行线经过站点不同 由于下行线与上行线经过站点不同,显然,该种线路需要抽象成两条线路处理 5.1“公汽直达数据库”的建立 从实际出发,结合公众出行心理,公汽线路选择应优先考虑两站点之间是否有直达 午,那么在查询系统内部应设有任两站点的直达线路表,以方便查询时优先快速查询是 否有直达车,若有,则直接输岀所有直达车辆;若无,再搜索换乘路线。 在建立Q的时候,数据结构的选择非常重要,本题共有3957个站点,若Q內每个队 列的毎个数据都使用奴精度实犁储存,实际在 MATLAB等软件内内存占用大约为2GB,这 显然超越现阶段个人电脑极限,所以根据实际情况可以采用不同数据结构,本文采用 MATLAB内建元胞结构,当元胞内队列不存在时不占用空问,具体元胞结构设计如下: 车号 费用耗时 图1.1元胞结构示意图 上图中Cel11:1,2}代表Q中第1行第2个元胞(即从站点S0001到站点S002的直 达公交线路信息),元胞屮队列的每一行代表一辆直达车信息。 5.2模型Ⅰ分析与建立 从査询系统设计角度考虑,当输入起讫点后,系统内部通过Q査询无结果时,系统 内部应自动搜寻换乘次数最少的路线,若换乘次数相同时有多种转乘方案,则系统应显 小所有转乘烙线方案(包括转乘次数、行程总时间、途径总站点数、转乘站点及路线、 是否始发、行程总费用、转承站点负载压力)以供査询者自主选择。 同时,系统应冋査询者推荐“时间最短”,“费用最省”,“转乘站始发站最多”,“负 载压力最小”的不同目标下的最佳路线。 5.2.0基于不同目标的有向赋权图定义 引川图论相关知识,将题中所提供的公汽网络抽象成一个有向赋权图 中的每个顶点为每个不同的站点,如果从中的顶点到有直达路 线,那么这两点之间就用冇向边相连,记做∈,方向为从指向,表示可从直 达,相应的有一个数 称为该有向边的权,这样公汽网络就抽象为一个有向赋 权图。赋权图中的权可根据不同的目标进行定义,本模型在确定不同冂标时,将其分别 定义为(具休分析见5.2.2) 站点至站点的直达时间 时间: 其分量为 +∞无直达线路 站点至站点的直达费用 费用:-()。其分量为 +∞无直达线路 始发:=()其分量为 站点至站点的直达线路是否始发 +∞无直达线路 站点的负载量 负载 (),其分量为 +∞无直达线路 5.2.1最少换乘次数的确定 在用户输入起点与终点后,系统需要立即给出至少要转乘几次才能够到达目的地 这样就需要建立以下矩阵。 统计中各元素长度,可得任意两站点的直达线路数。由此可构造表示两两站点间 直达路线数目的直达线路数矩阵 ,通过矩阵运算可得到任两站点间换乘线路 数矩阵,进而得到任两站点间的最少换乘次数矩阵=(),,从而可得任两站间所需 的最少换乘次数 1)直达线路数矩阵的建立 引入直达线路数矩阵 其矩阵元素表示第个站点到第个站点直达线路 数,其中,当时为无效路径,设定值为,即: 以表示所有公汽所经过的的站点总数,则直达线路数矩阼可表示为 2)换乘线路数矩阵的建立 直达矩阵为×阶方阵,矩阵的次幂屮元素表示任两站点问通过次转乘 的路线数,即: 其中,表示第个站点到第个站点通过次转乘的路线数,下面以第行第 个元素为例对中元素意义进行举例说明: 《例》: 假设上式中等号右边仅= 其余为,说明仅第个站点可直达到第 个站点,第个站点可直达到第个站点,那么 ,即第站点可通过一次换乘 到达站点,换乘点为站点。 以表示方阵的次幂,为站点→的直达路线数,则 其中,元素为通过次换乘从站点→的线路数。如=表示从站点 到站点有条两次换乘路线,其换乘站点可通过运算参数记录得到。 3)最少换乘次数矩阵的建立 引入矩阵 ,其矩阵元素为使得≠的的最小值,∈∞,即: 则1表示从站点→必要的最少换乘次数,以矩阵 表示最少换乘次数 矩阵,则 其中,元素表示从站点→必要的最少换乘次数。 基于最少换乘次数矩阵C,每对起始站→终到站的最少换乘次数如下: 表1.0最少换乘次数表 线路编号 起始站 终到站 最少换乘 5.2.2基于最短路理论的模型分析 我们结合实际,主要考虑用户如下几个需求因素: 目标一:换乘次数最少; 目标二:行程时间最短; 目标三:行程费用最少; 目标四:转乘车辆始发最多; 目标五:站点负载压力最小。 目标分析 目标一:换乘次数最少 基于5.2.0建立的有向赋权图,引入0-1决策变量表示弧是否在起点与终 点的路上,则 弧位于顶点至顶点的路| 若与之间无直接相连的弧,但可通过屮问节点转跳,表明由站点到之问不 可直达,但可通过转乘到达,则由到之间换乘次数为绎过的总弧数减1,即换乘次 数最小可表示为: 目标二:行程总时间最短 时间权值=(),则乘车总时间为 公汽换公汽时间固定是5分钟,则换乘时间为 行程总时间包括起始站点等待的3分钟,行程总时间最短表示为 目标三:行程总费用最少 设表示→车辆属性 表小单一票制1元 分段计价 设表示→所过站数,那么一直达费用权=()表示为: 行程总费用最少可表示为: ∑ 目标四:转乘车辆始发最多 为考虑所选路线中转乘站点是否为所需转乘车始发站,我们引入变量表示第 个站点是否为→的始发站,即始发权=() 第个站点是弧线路的始发站 从→个站点的路线中转乘点为所转乘车的始发点最多的路线可表示为: 目标五:站点负载压力最小 首先假设终点站是奥运场馆,乘坐公车的人大多数都到达终点站,因此转车站点离 始发站的站点数越少越好(人少): 负载压力=转乘站点离始发站的站点数一转乘站点离终点站的站点数 注:若终点站不是奥运场馆则可以通过对负载取绝对值表示离始发或终点越近转车 越方便。 oC 始发 终点 如图所示,站点的负载压力-2-3--1,显然负载越小越好。根据式1.1,表 示进入第个站点的径数,表示从第个站点出站的径数矩阵,以表示第个站点的 负载压力权=() 线路负载压力最小可表示为: 约束分析 1)换乘次数约束 基于对日标一的分析,可得在有向赋权图中换乘次数表达式,以表示乘客所能接 受的最大换乘次数,则换乘次数约束可表示为: )c ∈∞且为整数 其屮,参数为人为设定值,分以下三种情况 当设定=时,为严格约束不能换乘 2」当设定=∞时,为无乘车次数约束,即可无限次换乘; [3]当设定为不为0的常数时,为约束换乘次数在次以内的情况; 《注》:参数可根据不同的计算需求进行自由选取。仅从数学模型角度考虑,为使 模型更具通用性,的选取可到∞。 从实际角度出发,查询系统中的值可由合询用户自己设定,当最小换乘次数小于 时,输出无解。 2)最短路起讫点约束 由于为有向图,则其中顶点分为“起点”、“中间点”、“讫点”三类,对」起点只 有出的边而无入的边,对于中间点既有入的也有出的边,对于讫点只有入的无出的边 对有向图而言,若求顶点 的最短路径,以表示进入第个顶点的边,以表 示出第个顶点的边,则中的三类点约束可表示为: ()e DE

...展开详情
试读 41P 2007年全国大学生数学建模竞赛B题 特等奖论文
立即下载
限时抽奖 低至0.43元/次
身份认证后 购VIP低至7折
一个资源只可评论一次,评论内容不能少于5个字
沼泽星星 数模选手可以参考
2019-03-26
回复
adam55890 高手,大牛啊。
2016-09-23
回复
xht523 good,帮助挺大的,范文。。。
2015-05-08
回复
keli21cn 范文,建议做数学建模的读一下
2015-01-09
回复
hhhhff110112 太好了,着急用啊
2014-08-14
回复
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
  • 分享学徒

关注 私信
上传资源赚钱or赚积分
最新推荐
2007年全国大学生数学建模竞赛B题 特等奖论文 48积分/C币 立即下载
1/41
2007年全国大学生数学建模竞赛B题 特等奖论文第1页
2007年全国大学生数学建模竞赛B题 特等奖论文第2页
2007年全国大学生数学建模竞赛B题 特等奖论文第3页
2007年全国大学生数学建模竞赛B题 特等奖论文第4页
2007年全国大学生数学建模竞赛B题 特等奖论文第5页
2007年全国大学生数学建模竞赛B题 特等奖论文第6页
2007年全国大学生数学建模竞赛B题 特等奖论文第7页
2007年全国大学生数学建模竞赛B题 特等奖论文第8页
2007年全国大学生数学建模竞赛B题 特等奖论文第9页

试读结束, 可继续读4页

48积分/C币 立即下载