logo资料库

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

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.44M 资料格式：pdf 举报 版权申诉
第1页 / 共41页
第2页 / 共41页
第3页 / 共41页
第4页 / 共41页
第5页 / 共41页
第6页 / 共41页
第7页 / 共41页
第8页 / 共41页
资料共41页，剩余部分请下载后查看
    2007 高教社杯全国大学生数学建模竞赛 承 诺 书 我们完全明白，在竞赛开始后参赛队员不能以任何方式（包括电话、电子邮件、网 上咨询等）与队外的任何人（包括指导教师）研究、讨论与赛题有关的问题。 我们知道，抄袭别人的成果是违反竞赛规则的, 如果引用别人的成果或其他公开的 资料（包括网上查到的资料），必须按照规定的参考文献的表述方式在正文引用处和参 考文献中明确列出。 我们郑重承诺，严格遵守竞赛规则，以保证竞赛的公正、公平性。如有违反竞赛规 则的行为，我们将受到严肃处理。 我们参赛选择的题号是（从 A/B/C/D 中选择一项填写）： B 我们的参赛报名号为（如果赛区设置报名号的话）： B 甲 1802 所属学校（请填写完整的全名）： 海军航空工程学院（青岛） 参赛队员 (打印并签名) ：1. 汤志高 2. 王继利 3. 曹莹瑛 指导教师或指导教师组负责人 (打印并签名)： 曹华林 日期： 2007 年 9 月 24 日 赛区评阅编号（由赛区组委会评阅前进行编号）：
    2007 高教社杯全国大学生数学建模竞赛 编 号 专 用 页 评 阅 人 评 分 备 注 赛区评阅编号（由赛区组委会评阅前进行编号）： 赛区评阅记录（可供赛区评阅时使用）： 全国统一编号（由赛区组委会送交全国前编号）： 全国评阅编号（由全国组委会评阅前进行编号）：
    公交查询系统的最佳乘车方案研究与设计 【摘要】 本文将站点实体间的线路选择抽象为图论最短路模型采用 0-1 整数规划表述。建 立直达数据库 Q 作为数据基库，根据用户需求建立不同目标的 0-1 规划模型运用邻接 算法与 Lingo 分别求解，最终方案集通过多目标分层序列排序输出到用户终端。 第一问，在数据处理阶段将直行、环行线路分别抽象为 2、4 条路线(见 5.0)。建 立查询系统时考虑服务器要同时响应多个请求，计算任务繁重，采用空间换取时间的 策略，先建立站点至站点直达数据库 Q 来描述两两可直达站点的所有线路，用户查询 时，系统首先查询 Q，得到所有直达车方案。 在没有直达车情况下，针对不同用户需求，目标考虑：转乘次数、总耗时、总费 用、转站车辆是否始发、转乘站点负载量；在 Q 的基础上，量化不同目标为有向赋权 图的不同权矩阵(见 5.2.0)，以所求顶点u 到顶点 v 的路径是否包含 xij 弧为决策变量， 上述 5 项用户需求为目标，始、终点连通为约束建立 0-1 整数线性规划模型(见 5.2.3 模型Ⅰ)。 为了能够为用户提供多种备选方案，我们首先使用基于 Dijkstra 的邻接算法求解， 得到不同目标下的多种优化方案；对于邻接算法不易求解的多次转乘最优方案，我们 采用 Lingo 软件直接求得全局最优解；两种方法求解步骤见(5.3.1)，综合方案集见(5.3.2 表 1.1~1.6)，其中 6 条线路时间最短目标分别为 67、102、106、62、105、49(分钟)； 两种求解方法的优劣在 5.4 中给出了详细评价。 第二问考虑公汽与地铁混排方案，首先把各地铁站点 iD 和周围的公汽站点集 )iR s 抽象为同一新站点 kS ，把已知公汽线路到达 ( )iR s 都映射到 kS ，计算新直达数据 ( 库 DQ ，再结合地铁的费用与地汽换乘等待时间就可以把地铁线与公汽线结合，建立 多目标 0-1 整数线性规划模型(见 6.2.3 模型Ⅱ)；对于转乘次数少于等于 2 次的方案仍 可通过邻接算法求解；对于邻接算法不易求解的多次转乘最优方案，虽然模型规模较 大但约束与目标线性程度较好，还可用 Lingo 软件求解得出 6 条线路的全局最优解； 综合方案集(见 6.3.2 表 2.1~2.6)，其中 6 条线路时间最短目标分别为 65、102、98、56.5、 89.5、30(分钟)；随后我们在 6.4 与 6.5 中给出了模型具体的评价与应用。 第三问综合考虑所有站点间步行与乘车情况，将其抽象为最短路问题下的叠加有 向赋权图，在此基础上以换乘次数为主要约束，以总行程时间(包括步行)最短、转站 车辆始发数最大、转乘站点负载量最小、费用最低为目标，建立多目标 0-1 整数线性 规划模型(见 7.3 模型Ⅲ)，并给出了求解的一般步骤与算法。 最后本文还对实现查询系统的具体方案给出了建议，对各模型在实际中的应用价 值进行了详细讨论，并提出了改进方案。 关键字： 邻接算法 有向赋权图 直达队列表 分层序列法 叠加有向赋权图 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] 假设车站不重名； [2] 假设各路经上公交车发车频度相同； [3] 假设相邻站点间平均行驶时间一定； [4] 假设不出现交通阻塞，公交运行顺畅； [5] 假设不出现车辆故障及道路交通事故； [6] 假设始发终点出入地铁需要步行4分钟； [7] 假设公交准点到达，不考虑红绿灯等待时间。 2
    4 符号系统 ijx —— 弧 ( , ) ijf —— 第i 个站点是否为i → j 的始发站； j 是否在该有向赋权图上； i ijt —— 站点i → j 的总乘车时间； ijP —— 站点i → j 的乘车费用。 5 公汽站点之间线路选择模型（问题一） 本节主要研究任意两公汽站点间线路选择的数学模型与算法。分别在不同行程需求 下推荐最佳路线，给出更为人性化的站点负载压力及转乘点是否为始发站的提示。 通畅、便利目标：换乘次数最少； 不同的行程需求：行程耗时最少； 行程费用最少； 人性化查询设计：转乘站点是否为始发站提示； 站点负载压力提示。 基于此，本部分共分如下四小节： 5.0：数据处理，将三种公汽线路进行了图论抽象处理； 5.1：建立了可查询两站之间直达线路的“公汽直达数据库 Q”； 5.2：建立基于有向赋权图与最短路理论的 0-1 规划模型； 5.3：针对模型分别使用不同方法求解，得到多种适合不同用户的方案集。 5.0 数据处理——三种公汽线路抽象处理 根据题中信息，公汽线路分三种，下面将这三种线路进行数据处理： (1) 下行线、上行线原路返回 这种线路有两个端点站，在两个端点之间双向行车，而且两个方向上的行车路线相 同，经过同样的站点序列。由于线路的方向不同，因此，下行线和上行线可以抽象成两 条线路处理。 1S (2) 线路为环行线 2S 3S 4S 5S 6S 7S 8S 实际中环形路线一般是双环，但在对这两条线路进行抽象时，为保证任意两站点距 离最近，把每条线路再抽象成 2 条（如图所示）： ABA BAB A B 'A 'B (3) 下行线与上行线经过站点不同 A B A ' B A B ' ' ' ' ' 由于下行线与上行线经过站点不同，显然，该种线路需要抽象成两条线路处理。 1S 2S 3S 4S 5S 6S 7S 8S 5.1 “公汽直达数据库Q ”的建立 10S 11S 从实际出发，结合公众出行心理，公汽线路选择应优先考虑两站点之间是否有直达 3 12S
    车，那么在查询系统内部应设有任两站点的直达线路表，以方便查询时优先快速查询是 否有直达车，若有，则直接输出所有直达车辆；若无，再搜索换乘路线。 在建立 Q 的时候，数据结构的选择非常重要，本题共有 3957 个站点,若 Q 内每个队 列的每个数据都使用双精度实型储存，实际在 MATLAB 等软件内内存占用大约为 2GB，这 显然超越现阶段个人电脑极限，所以根据实际情况可以采用不同数据结构，本文采用 MATLAB 内建元胞结构，当元胞内队列不存在时不占用空间，具体元胞结构设计如下： Cell{1,1} Cell{1,2} Cell{1,3} 车号 费用 耗时 27 L001 L076 18 2 3 Cell{2,1} Cell{2,2} Cell{2,3} 图 1.1 元胞结构示意图 上图中 Cell{1,2}代表 Q 中第 1 行第 2 个元胞（即从站点 S0001 到站点 S0002 的直 达公交线路信息），元胞中队列的每一行代表一辆直达车信息。 5.2 模型Ⅰ分析与建立 从查询系统设计角度考虑，当输入起讫点后，系统内部通过 Q 查询无结果时，系统 内部应自动搜寻换乘次数最少的路线，若换乘次数相同时有多种转乘方案，则系统应显 示所有转乘路线方案（包括转乘次数、行程总时间、途径总站点数、转乘站点及路线、 是否始发、行程总费用、转承站点负载压力）以供查询者自主选择。 同时，系统应向查询者推荐“时间最短”，“费用最省”，“转乘站始发站最多”，“负 载压力最小”的不同目标下的最佳路线。 5.2.0 基于不同目标的有向赋权图定义 , , ) = ,G 中的每个顶点为每个不同的站点, 如果从G 引 用 图 论 相 关 知 识 ， 将 题 中 所 提 供 的 公 汽 网 络 抽 象 成 一 个 有 向 赋 权 图 中的顶点 iV 到 jV 有直达路 G V E W ( E∈ ，方向为从i 指向 j ，表示可从i 直 j 线，那么这两点之间就用有向边相连, 记做 ( , ) w v v 称为该有向边的权，这样公汽网络就抽象为一个有向赋 达 j ，相应的有一个数 ( 权图。赋权图中的权可根据不同的目标进行定义，本模型在确定不同目标时，将其分别 定义为（具体分析见 5.2.2） ) i , i j 站点 至站点 的直达时间 v i v j 无直达线路 站点 至站点 的直达费用 无直达线路 v i v i v j v j 站点 至站点 的直达线路是否始发 时间： t W = ( t ) ij n n × 其分量为 费用： P W = ( ) P ij n n × 其分量为 始发： f W = ( f ) ij n n × 其分量为 负载： r W = ( ) 1 r i n × 其分量为 t ij P ij f ij r i ) j ( t ⎧⎪= ⎨ v v , i +∞⎪⎩ P ⎧⎪= ⎨ v v ( , i +∞⎪⎩ f ⎧⎪= ⎨ v v ( , i +∞⎪⎩ r ⎧⎪= ⎨ )iv ( +∞⎪⎩ ) j ) j 无直达线路 站点 的负载量 v i 无直达线路 4
    5.2.1 最少换乘次数的确定 在用户输入起点与终点后，系统需要立即给出至少要转乘几次才能够到达目的地， 这样就需要建立以下矩阵。 统计 Q 中各元素长度，可得任意两站点的直达线路数。由此可构造表示两两站点间 ，通过矩阵运算可得到任两站点间换乘线路 A )ij n n a 直达路线数目的直达线路数矩阵 ( = 数矩阵，进而得到任两站点间的最少换乘次数矩阵 ( = 的最少换乘次数。 1）直达线路数矩阵的建立 A a= 引入直达线路数矩阵 ( C × )ij n n c × ，从而可得任两站间所需 )ij ，其矩阵元素 ija 表示第i 个站点到第 j 个站点直达线路 数 n ，其中，当i = j 时为无效路径，设定值为 0，即： a ij ⎧ = ⎨ ⎩ n 0 i ( i ( ≠ = j j ) ) (1.1) 以 N 表示所有公汽所经过的的站点总数，则直达线路数矩阵可表示为： A N N × ⎛ ⎜ ⎜ ⎜ = ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ a 11 a 21 a N 1 a 12 a 22 a N a ij 2 N N a 1 a 2 a NN ⎞ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ 2）换乘线路数矩阵的建立 直达矩阵 A 为 N N× 阶方阵，矩阵 A 的 2 次幂中元素表示任两站点间通过 1 次转乘 的路线数，即： 其中， 2 ijA 表示第i 个站点到第 j 个站点通过 1 次转乘的路线数，下面以 2A 第 1 行第 2A = ⋅ A A 2 个元素 2 12a 为例对 2A 中元素意义进行举例说明： + 《例》： = + ⋅ a 13 a 32 a 11 + a 1 N ⋅ a N 2 a 2 12 + a 12 a a ⋅ ⋅ 12 22 a = 、 32 1 假设上式中等号右边仅 13 个站点，第 3 个站点可直达到第 2 个站点，那么 到达 2 站点，换乘点为站点 3。 1 a = ，其余为 0，说明仅第 1 个站点可直达到第 3 a = ，即第 1 站点可通过一次换乘 2 12 1 以 nA 表示方阵 A 的 n 次幂， kjA 为站点 k → j 的直达路线数，则： A n ij = N ⋅∑ A− 1 kj A n ik k 1 = (1.2) 其中，元素 n 1 到站点 3 有 1 条两次换乘路线，其换乘站点可通过运算参数记录得到。 n − 次换乘从站点i → j 的线路数。如 3 A = 表示从站点 4 4,3 ijA 为通过 ( 1) 5
    3）最少换乘次数矩阵的建立 b= 引入矩阵 ( B )ij ，其矩阵元素 ijb 为使得 ijA ≠ 的 n 的最小值， [1, n n ∈ ∞ ，即： 0 ) ) ) 则 ijb -1 表示从站点i → j 必要的最少换乘次数，以矩阵 ( c= min 0 ⎧ ⎪= ⎨ ⎪⎩ n A n ij ∈ ∞ [1, i ( i ( ≠ = b ij 0, j j C ≠ n )ij { | } ) (1.3) 表示最少换乘次数 矩阵，则： C B= − 1 (1.4) 其中，元素 ijc 表示从站点i → j 必要的最少换乘次数。 基于最少换乘次数矩阵 C，每对起始站→终到站的最少换乘次数如下： 线路编号 起始站 终到站 最少换乘 1 S3359 S1828 1 2 S1557 S0481 2 3 S0971 S0485 1 表 1.0 最少换乘次数表 4 S0008 S0073 1 5 S0148 S0485 2 6 S0087 S3676 1 5.2.2 基于最短路理论的模型分析 我们结合实际，主要考虑用户如下几个需求因素： 目标一：换乘次数最少； 目标二：行程时间最短； 目标三：行程费用最少； 目标四：转乘车辆始发最多； 目标五：站点负载压力最小。 目标分析 目标一：换乘次数最少 基于 5.2.0 建立的有向赋权图，引入 0-1 决策变量 ijx 表示弧 ( , ) i j 是否在起点与终 点的路上，则： x ij 1 ⎧⎪= ⎨ 0 ⎪⎩ i j ( , ) 弧 位于顶点 至顶点 的路上 ELSE v i v j 若 iv 与 jv 之间无直接相连的弧，但可通过中间节点转跳，表明由站点i 到 j 之间不 可直达，但可通过转乘到达，则由 iv 到 jv 之间换乘次数为经过的总弧数减 1，即换乘次 数最小可表示为： Min x ij −∑ ), j E ∈ ( i 1 (1.5) 目标二：行程总时间最短 时间权值 t W = ( t ) ij n n × ，则乘车总时间为: ∑ ), i j E ∈ ( t x ij ij 6
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料