乘公交看奥运2007B

null全国竞赛B题评讲全国竞赛B题评讲主讲: 龚劬 2009.52007年B题: 乘公交，看奥运2007年B题: 乘公交，看奥运问题 竞赛总体情况 几种典型模型 几种典型求解方法 模型和方法的 评价 LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载 B题概况主要内容null 部分B题高等教育学费标准探讨 (2008B) 乘公交，看奥运（2007B)  DVD在线租赁 (2005B) 电力市场的输电阻塞管理问题（2004B) 露天矿生产的车辆安排 (2003B) 公交车调度 (2002B)  钢管订购和运输 (2000B)  钻井布局优化问题（1999B)  灾情巡视路线 (1998B)2007年B题: 乘公交，看奥运2007年B题: 乘公交，看奥运问题 竞赛总体情况 几种典型模型 几种典型求解方法 模型和方法的评价 乘公交，看奥运乘公交，看奥运公交线路选择问题的自主查询计算机系统：核心是线路选择的模型与算法 应该从实际情况出发考虑，满足查询者的各种不同需求 1. 仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法 2. 同时考虑公汽与地铁线路，解决以上问题 3. 假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型 null　【附录1】基本参数设定 相邻公汽站平均行驶时间(包括停站时间)： 3分钟 相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟 公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟) 地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟) 地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟) 公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟) 公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元 地铁票价：3元（无论地铁线路间是否换乘） 推论：换乘公汽等待３分钟，换乘地铁等待２分钟 　【附录2】公交线路及相关信息 （见数据文件）模型的目标模型的目标多目标优化问题（至少考虑三方面） 换乘次数最少(N)、费用最省(M)、时间最短(T) 从该问题的实际背景来看，加权不太合适 不少同学用层次分析法确定权 不少同学计算时间的价值（平均收入／工作时间） 不同目标组合的模型 三个目标按优先级排序，组合成六个模型 也可将某些目标作为约束多数队仅采用搜索法（70-80%?）多数队仅采用搜索法（70-80%?）直达； 　一次换乘；　 二次换乘；　…s ts ts t求出所有线路；评价其目标(容易计算)；选优 同学 论文 政研论文下载论文大学下载论文大学下载关于长拳的论文浙大论文封面下载 中存在的主要问题同学论文中存在的主要问题2. 目标不当，或不完整 1. 几乎没有模型，只有算法（一般是搜索法）3. 算法使用不当4. 对第３问，几乎是没有多少时间来认真进行讨论和建模5. 全文表达不太清楚，思路混乱null问题一:公汽站点之间线路选择模型: 通畅、便利目标： 换乘次数最少 不同的行程需求： 行程耗时最少； 行程费用最少. 人性化查询设计： 转乘站点是否为始发站提示； 站点负载压力提示.null问题一:公汽站点之间线路选择模型: 1.数据处理，将三种公汽线路进行处理； 2.建立可查询两站之间直达线路的“公汽直达数据库Q”； 3.建立基于有向赋权图与最短路理论的0-1 规划模型； 4.针对模型分别使用不同方法求解，得到多种适合不同用户的 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 集。 null1.数据处理——三种公汽线路抽象处理 (1) 下行线、上行线原路返回 (2) 线路为环行线 (3) 下行线与上行线经过站点不同 null2. “公汽直达数据库Q”的建立 查询系统内部应设有任两站点的直达线路表，以方便查询时优先快速查询是否有直达车，若有，则直接输出所有直达车辆；若无，再搜索换乘路线。 本题共有3957 个站点, 元胞结构 null3. 模型Ⅰ分析与建立 当输入起讫点后，系统内部通过Q 查询无结果时，系统内部应自动搜寻换乘次数最少的路线，若换乘次数相同时有多种转乘方案，则系统应显示所有转乘路线方案（包括转乘次数、行程总时间、途径总站点数、转乘站点及路线、是否始发、行程总费用、转乘站点负载压力）供查询者自主选择。 系统应向查询者推荐“时间最短”，“费用最省”，“转乘站始发站最多”，“负载压力最小”的不同目标下的最佳路线。null基于不同目标的带权有向图定义 建立一个带权有向图，节点表示站点，有向弧表示前一站 点能够直达后一站点，弧上的权表示前一站点直达后一站点所需付出的代价(时间,费用等) 时间： 费用： 始发： 负载： null最少换乘次数的确定 统计Q 中各元素长度，可得任意两站点的直达线路数。由此可构造表示两两站点间直达路线数目的直达线路数矩阵 通过矩阵的幂运算可得到任两站点间换乘线路数矩阵，进而得到任两站点间的最少换乘次数矩阵 从而可得任两站间所需的最少换乘次数。 null最少换乘次数的确定 1.直达线路数矩阵 2. 换乘线路数矩阵的建立 矩阵A 的2 次幂中元素表示任两站点间通过1 次转乘的路线数，即 如: A2 的第1 行第2 列元素 以An 表示方阵A 的n 次幂， A kj 为站点k → j 的直达路线数，则： null3.最少换乘次数矩阵的建立 引入矩阵B =( bij )，其矩阵元素b ij 为使得aijn ≠0 的n 的最小值， n∈[1,∞) ， 则: b ij -1 表示从站点i → j 必要的最少换乘次数，以矩阵C=(cij) 表示最少换乘次数矩阵， 则： cij=bij-1 (当i≠j时)null基于最短路理论的模型分析 目标一：换乘次数最少； 目标二：行程时间最短； 目标三：行程费用最少； 目标四：转乘车辆始发最多； 目标五：站点负载压力最小。 null目标一：换乘次数最少 引入0-1 决策变量xij 表示弧( i, j) 是否在起点与终点的路上 目标二：行程总时间最短 时间权值 行程总时间=乘车时间+换乘时间+起始站等待时间 null目标三：行程总费用最少 直达费用权 目标四：转乘车辆始发最多 引入0-1 变量 null目标五：站点负载压力最小 以ri 表示第i 个站点的负载压力权 null约束分析 1) 换乘次数约束 2）最短路起讫点约束 null多目标最短路 线性规划模型 关联矩阵是全么模矩阵，因此0-1决策变量可以松弛为区间[0,1]中的实数 不含负圈，变量直接松弛为所有非负实数xij 可以不限定为{0，1} (0-1规划) ?null模型求解的4 种方法 方法一、修正Floyd-Warshall算法 在线路选择问题中，当从i可直达j时,定义弧(i,j)；其上的权为lij表示由i直达j付出的代价，可以为时间或费用等 (多条线路可达时只保留最小代价) 初始等车时间2(3)min也不包括在内，最后结果可加上.最小费用或时间最小费用或时间 定义矩阵算子“⊙”如下：设A、B均为n阶方阵， C = A ⊙ B (考虑换乘代价) D(k)= D(k-1) ⊙ D 表示k次换乘的最低代价(费用或时间) 该算法大体相当于求最短路的Floyd-Warshall算法，但考虑了换乘因素 类似地,　通过修改Dijkstra算法求解也可方法二 修正Dijkstra算法方法二 修正Dijkstra算法STEP1. 若S=V, 则uj为节点s到节点j的最短路路长(最短路可以通过数组pred所 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 的信息反向追踪获得),结束.否则继续. STEP0. (初始化) 令S= ， =V， ；对V 中的顶点j(j s), 令初始距离标号 . STEP2. 从 中找到距离标号最小的节点i，把它从 删除，加入S. 对于所有从i出发的弧 , 若 ,其中k=pres(i),则令 ,转STEP1. 特点：1. 算法求出从起点s到所有点的最短路长(时间等) 2. 每点给一对标号 (uj, predj)，uj是从s到j的最短路长；pred(j)是从s到j的最短路中j点的前一点 3. 输入权矩阵W=(wij)(时间或费用或其他)null方法三、基于数据库Q 的“邻接搜索算法”求解 Step 1：输入乘车始点i 终点j ，（注： 为最少换乘次数矩阵） 若cij =0, 则有直达线路，输出Q中所有直达信息，结束程序， 若cij =1, 则有转乘1次线路，转Step 2 ， 若cij = 2 , 则有转乘2次线路，转Step 4， 若cij > 2, 则存在转乘cij次线路，但全局计算时间复杂度较高，终止邻接算法，采用Lingo求解； Step 2：求线路s(i)的直达站点E(i,U),及线路t(j)的直达站点F(j,V)； Step 3：若存在E(i,U)=F(j,V) ，线路s(i)、t(i)可能不止一种，即为一次转车的线路,保存队列U1，转Step6； Step 4：求经过E(i,U)的线路r(K)求线路r(K)的站点G(K,W)； Step 5：若存在G(K,W)=F(j,V) ，线路s(i)、t(j) 、r(K)可能不止一种，即为两次转车的线路，保存队列U2，转Step6; Step 6：修改队列U1、U2 中的成员，按其属性(路过的站点数，乘坐的车辆)根据不同目标计算总行程时间、费用等. null 方法四、使用Lingo 软件求解无转乘次数限制的方案（针对不同目标分别求解）null模型的评价 1 邻接算法评价 1) 建立在图基础下能够求解出转乘次数不超过两次时的所有可行方案，并可根据公众的不同需求，给出最佳需要方案，从此角度考虑，模型实用性较强； 2) 模型求解基于直达队列Q，采用空间换取时间思想，适合查询系统设计标准能够较强的适应 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 应用； 3) 在转乘次数超过两次的情况下，运用本算法求解计算过程复杂，计算量过大.故本模型存在一定的局限性。null模型的评价 2. 图论的最短路径算法评价 1) 修正 Floyd-Warshall算法和修正Dijkstra算法均可以求得不限制最小转乘数时的全局最优路线(单目标)，这是其他所有算法无法达到的； 2) 修正 Floyd-Warshall算法可以求得在限制最小转乘数时与邻接算法同样的方案，表明模型的通用性较强 3) 从理论角度分析，最优化模型规划角度可解具有很强的实际意义，例如从全国范围考虑求解，那么转车3~4 次也是可以接受的，只要耗时足够短； 4) 只要增加一些记录, 修正 Floyd-Warshall算法和修正Dijkstra算法还能求解出多种方案，实用性强。null模型的评价 3 0-1 规划Lingo 求解方案评价 1) 在不限制最小转乘数时可以求得全局最优解，这是其他所有算法无 法达到的，例如在第2、4、5 条线路上其转车次数为3、4、3，但是耗时相对转2 次的要节省许多； 2) 在限制最小转乘数时可以求得与邻接算法同样的方案，表明模型的通用性较强，但无法像邻接算法一样求解多种方案是用户所不能接受的 3) 从理论角度分析，最优化模型规划角度可解具有很强的实际意义，例如从全国范围考虑求解，那么转车3~4 次也是可以接受的，只要耗时足够短； 4) 从计算时间来分析，尽管需要20 分钟，但大部分时间为数据导入，只有1%的时间是真正计算耗时，如果将所需数据存放入内存不变，其求解速度将超越邻接算法； 5) 但Lingo 不能求解出多种方案，实用性不如邻接算法。 null模型改进方向 1) 考虑通过站点周围建筑物进行查询； 2) 考虑提示观光路线 对于许多乘客而言，更希望乘车路线沿途可观赏到北京的特色景观及建筑，所以从宣扬首都文化角度考虑，应在系统内部将沿途有特色景观（如奥运场馆、名胜古迹等）的路径段进行特别标注或分区存放数据，在用户查询时，系统应在给出常规最佳路线的同时，提示一条观光路线供乘客自由选择。