51CTO下载-乘公交看奥运2007B

1、全国竞赛全国竞赛B B题评讲题评讲主讲主讲: : 龚劬龚劬20072007年年B B题题: : 乘公交，看奥运乘公交，看奥运 问题问题 竞赛总体情况竞赛总体情况 几种典型模型几种典型模型 几种典型求解方法几种典型求解方法 模型和方法的评价模型和方法的评价 B B题概况题概况主要内容主要内容 部分部分B B题题高等教育学费标准探讨 (2008B)乘公交，看奥运（2007B) DVD在线租赁 (2005B)电力市场的输电阻塞管理问题（2004B)露天矿生产的车辆安排 (2003B)公交车调度 (2002B) 钢管订购和运输 (2000B) 钻井布局优化问题（1999B) 灾情巡视路线 (1998B

2、)2007年年B题题: 乘公交，看奥运乘公交，看奥运 问题问题 竞赛总体情况竞赛总体情况 几种典型模型几种典型模型 几种典型求解方法几种典型求解方法 模型和方法的评价模型和方法的评价 乘公交，看奥运乘公交，看奥运 公交线路选择问题的自主查询计算机系统：核心是公交线路选择问题的自主查询计算机系统：核心是线路选择的线路选择的模型与算法模型与算法 应该从应该从实际情况出发实际情况出发考虑，满足查询者的考虑，满足查询者的各种不同各种不同需求需求1. 1. 仅考虑公汽线路，给出任意两公汽站点之间线路仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的选择问题的一般一般数学模型与算法数学模型与算法 2.

3、2. 同时考虑公汽与地铁线路，解决以上问题同时考虑公汽与地铁线路，解决以上问题3. 3. 假设又知道所有站点之间的步行时间，给出任意假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型两站点之间线路选择问题的数学模型 【附录【附录1】基本参数设定】基本参数设定 相邻公汽站平均行驶时间(包括停站时间)： 3分钟 相邻地铁站平均行驶时间(包括停站时间)： 2.5分钟 公汽换乘公汽平均耗时： 5分钟(其中步行时间2分钟) 地铁换乘地铁平均耗时： 4分钟(其中步行时间2分钟) 地铁换乘公汽平均耗时： 7分钟(其中步行时间4分钟) 公汽换乘地铁平均耗时： 6分钟(其中步行时间4分钟

4、) 公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：020站：1元；2140站：2元；40站以上：3元 地铁票价：3元（无论地铁线路间是否换乘） 推论：换乘公汽等待分钟，换乘地铁等待分钟【附录【附录2】公交线路及相关信息】公交线路及相关信息 （见数据文件）（见数据文件）模型的目标模型的目标 多目标优化问题多目标优化问题（至少考虑三方面）（至少考虑三方面） 换乘次数最少换乘次数最少(N)(N)、费用最省、费用最省(M)(M)、时间最短、时间最短(T)(T) 从该问题的实际背景来看，从该问题的实际背景来看，加权不加权不太合适太合适 不少同学用层次分析法确定权不少同学用层次

5、分析法确定权 不少同学计算时间的价值（平均收入工作时间）不少同学计算时间的价值（平均收入工作时间） 不同目标不同目标组合组合的模型的模型 三个目标按优先级排序，组合成六个模型三个目标按优先级排序，组合成六个模型 也可将某些目标作为约束也可将某些目标作为约束多数队多数队仅仅采用搜索法（采用搜索法（70-80%?） 直达；直达； 一次换乘；一次换乘； 二次换乘；二次换乘；ststs t 求出所有线路；评价其目标求出所有线路；评价其目标(容易计算容易计算)；选优；选优同学论文中存在的主要问题同学论文中存在的主要问题2. 目标不当，或不完整目标不当，或不完整 1. 几乎没有模型，只有算法（一般是搜索法

6、）几乎没有模型，只有算法（一般是搜索法）3. 算法使用不当算法使用不当4. 对第问，几乎是没有多少时间来认真进行讨论对第问，几乎是没有多少时间来认真进行讨论和建模和建模5. 全文表达不太清楚，思路混乱全文表达不太清楚，思路混乱问题一:公汽站点之间线路选择模型: 通畅、便利目标： 换乘次数最少 不同的行程需求： 行程耗时最少； 行程费用最少. 人性化查询设计： 转乘站点是否为始发站提示； 站点负载压力提示.问题一:公汽站点之间线路选择模型:1.数据处理，将三种公汽线路进行处理；2.建立可查询两站之间直达线路的“公汽直达数据库Q Q”；3.建立基于有向赋权图与最短路理论的0-1 规划模型；4.针对

7、模型分别使用不同方法求解，得到多种适合不同用户的方案集。1.数据处理三种公汽线路抽象处理(1) 下行线、上行线原路返回(2) 线路为环行线(3) 下行线与上行线经过站点不同2. “公汽直达数据库Q”的建立 查询系统内部应设有任两站点的直达线路表，以方便查询时优先快速查询是否有直达车，若有，则直接输出所有直达车辆；若无，再搜索换乘路线。 本题共有3957 个站点, 元胞结构3. 模型分析与建立 当输入起讫点后，系统内部通过Q 查询无结果时，系统内部应自动搜寻换乘次数最少的路线，若换乘次数相同时有多种转乘方案，则系统应显示所有转乘路线方案（包括转乘次数、行程总时间、途径总站点数、转乘站点及路线、是

8、否始发、行程总费用、转乘站点负载压力）供查询者自主选择。 系统应向查询者推荐“时间最短”，“费用最省”，“转乘站始发站最多”，“负载压力最小”的不同目标下的最佳路线。基于不同目标的基于不同目标的带权有向图带权有向图定义定义 建立一个带权有向图，节点表示站点，有向弧表示前一站 点能够直达后一站点，弧上的权表示前一站点直达后一站点所需付出的代价(时间,费用等)时间：费用：始发：负载： 最少换乘次数的确定 统计Q 中各元素长度，可得任意两站点的直达线路数。由此可构造表示两两站点间直达路线数目的直达线路数矩阵 通过矩阵的幂运算可得到任两站点间换乘线路数矩阵，进而得到任两站点间的最少换乘次数矩阵 从而可

9、得任两站间所需的最少换乘次数。 最少换乘次数的确定最少换乘次数的确定1.1.直达线路数矩阵直达线路数矩阵2. 2. 换乘线路数矩阵的建立换乘线路数矩阵的建立 矩阵矩阵A A 的的2 2 次幂中元素表示任两站点间通过次幂中元素表示任两站点间通过1 1 次转乘次转乘的路线数，即的路线数，即 如如: A: A2 2 的的第第1 1 行第行第2 2 列列元素元素 以以A An n 表示方阵表示方阵A A 的的n n 次幂，次幂， A A kj kj 为站点为站点k k j j 的直的直达路线数，则：达路线数，则： 3.3.最少换乘次数矩阵的建立最少换乘次数矩阵的建立 引入矩阵引入矩阵B B =( =(

10、 b bijij ) )，其矩阵元素其矩阵元素b b ijij 为使得为使得a aijijn n 00 的的n n 的最小值的最小值， n n1,) 1,) ， 则则: : b b ijij -1 -1 表示从站点表示从站点i i j j 必要的最少换乘必要的最少换乘次数，以矩阵次数，以矩阵C C= =( (c cijij) ) 表示最少换乘次数矩阵表示最少换乘次数矩阵， 则：则： c cijij=b=bijij-1 (-1 (当当i ij j时时) )基于最短路理论的模型分析 目标一：换乘次数最少； 目标二：行程时间最短； 目标三：行程费用最少； 目标四：转乘车辆始发最多； 目标五：站点负载

11、压力最小。目标一：换乘次数最少 引入0-1 决策变量xij 表示弧( i, j) 是否在起点与终点的路上目标二：行程总时间最短 时间权值行程总时间=乘车时间+换乘时间+起始站等待时间 目标三：行程总费用最少 直达费用权目标四：转乘车辆始发最多 引入0-1 变量 目标五：站点负载压力最小 以ri 表示第i 个站点的负载压力权 约束分析1) 换乘次数约束2）最短路起讫点约束 多目标最短路线性规划模型 关联矩阵是全么模关联矩阵是全么模矩阵，因此矩阵，因此0-10-1决策决策变量可以松弛为区变量可以松弛为区间间0,10,1中的实数中的实数 不含负圈不含负圈，变量直，变量直接松弛为所有非负接松弛为所有非

12、负实数实数x xijij 可以不限定为可以不限定为00，1 (0-11 (0-1规划规划) ?) ?模型求解的模型求解的4 4 种方法种方法方法一、修正方法一、修正Floyd-WarshallFloyd-Warshall算法算法 在线路选择问题中，当从i可直达j时,定义弧(i,j)；其上的权为lij表示由i直达j付出的代价，可以为时间或费用等 (多条线路可达时只保留最小代价)初始等车时间2(3)min也不包括在内，最后结果可加上.(0)0ijijijaijl站点往 站点无直达车否则d dijij(0)(0)= =d dijij最小费用或时间最小费用或时间 定义矩阵算子“”如下：设A、B均为n阶

13、方阵， C = A B (考虑换乘代价), ,min1,2,ijikkji j kcabkn当考虑费用矩阵之间的运算时，, ,i j k表示在k的换乘时间 当考虑时间矩阵之间的运算时，, ,i j k D(k)= D(k-1) D 表示k次换乘的最低代价(费用或时间) 该算法大体相当于求最短路的Floyd-Warshall算法，但考虑了换乘因素 类似地,通过修改Dijkstra算法求解也可方法二方法二 修正修正DijkstraDijkstra算法算法kijijijwuuSTEP1. 若S=V, 则uj为节点s到节点j的最短路路长(最短路可以通过数组pred所记录的信息反向追踪获得),结束.否则

14、继续. STEP0. (初始化) 令S= ， =V， ；对V 中的顶点j(j s), 令初始距离标号 . S0)(, 01spreduusjuSTEP2. 从 中找到距离标号最小的节点i，把它从 删除，加入S. 对于所有从i出发的弧 , 若,其中k=pres(i),则令 ,转STEP1. SSAji),(特点：1. 算法求出从起点s到所有点的最短路长(时间等) 2. 每点给一对标号 (uj, predj)，uj是从s到j的最短路长；pred(j)是从s到j的最短路中j点的前一点 3. 输入权矩阵W=(wij)(时间或费用或其他)ijpredwuukijijij)(,方法三、基于数据库方法三、基

15、于数据库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)可能不止一种，即为一次转车的线路,保存

16、队列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 中的成员，按其属性(路过的站点数，乘坐的车辆)根据不同目标计算总行程时间、费用等. 方法四、使用方法四、使用Lingo Lingo 软件求解无转乘次数限软件求解无转乘次数限制的方案（针对不同目标分别求解）制的方案（针对不同目标分别求解）模型的评价模型的评价1 1 邻接算法评价邻接算法评价 1) 1) 建立在图

17、基础下能够求解出转乘次数不超过两次时的所有可行方案，并可根据公众的不同需求，给出最佳需要方案，从此角度考虑，模型实用性较强； 2) 2) 模型求解基于直达队列Q，采用空间换取时间思想，适合查询系统设计标准能够较强的适应工程应用； 3) 3) 在转乘次数超过两次的情况下，运用本算法求解计算过程复杂，计算量过大.故本模型存在一定的局限性。模型的评价模型的评价2. 图论的最短路径算法图论的最短路径算法评价评价 1) 修正修正 Floyd-Warshall算法和算法和修正修正Dijkstra算法均算法均可以求得不限制最小转乘数时的全局最优路线(单目标)，这是其他所有算法无法达到的； 2) 修正修正 F

18、loyd-Warshall算法算法可以求得在限制最小转乘数时与邻接算法同样的方案，表明模型的通用性较强 3) 从理论角度分析，最优化模型规划角度可解具有很强的实际意义，例如从全国范围考虑求解，那么转车34 次也是可以接受的，只要耗时足够短； 4) 只要增加一些记录, 修正修正 Floyd-Warshall算法和算法和修正修正Dijkstra算法算法还能求解出多种方案，实用性强。模型的评价模型的评价3 0-1 规划规划Lingo 求解方案评价求解方案评价 1) 在不限制最小转乘数时可以求得全局最优解，这是其他所有算法无 法达到的，例如在第2、4、5 条线路上其转车次数为3、4、3，但是耗时相对转2 次的要节省许多； 2) 在限制最小转乘数时可以求得与邻接算法同样的方案，表明模型的通用性较强，但无法像邻接算法一样求解多种方案是用户所不能接受的 3) 从理论角度分析，最优化模型规划角度可解具有很强的实际意义，例如从全国范围考虑求解，那么转车34 次也是可以接受的，只要耗时足够短； 4) 从计算时间来分析，尽管需要20