数学建模讲座CUMCMB乘公交看奥运赛题分析

©谢金星,清华大学数学科学系,2008.数学建模讲座CUMCM-2007B(乘公交，看奥运)赛题分析谢金星100084北京清华大学数学科学系Tel:010-62787812，Fax:[phone]Email:[e-mail]~jxie©谢金星,清华大学数学科学系,2008.2007B命题背景•奥运相关的题目：(时代特性,社会关注）–让运动员及时到达场馆（车辆调度，路径安排等）–应急管理（紧急疏散，应急调度等）–赛程安排（单一项目，多个项目）–成绩排名（如循环赛，体操或跳水等）–技术类，如“刘翔的运动鞋”•乘公交，看奥运：原名“自动问路机”–方沛辰（吉大），吴孟达（国防科大）提出–原拟作乙组题，似乎难度太大©谢金星,清华大学数学科学系,2008.命题背景•定位：公交路线选择（查询）模型与算法•如何给数据？–抽象数据／实际数据？（减小规模，不给地理信息）•貌似简单，实则不然–数据处理（转换）方面有一定难度–换乘次数多时简单搜索不易（计算复杂度高）–换乘时间／步行时间等需要考虑周全–标准的最短路算法（如Dijkstra算法）并不适用©谢金星,清华大学数学科学系,2008.乘公交，看奥运•公交线路选择问题的自主查询计算机系统：核心是线路选择的模型与算法•应该从实际情况出发考虑，满足查询者的各种不同需求•1:仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法•2:同时考虑公汽与地铁线路，解决以上问题•3:假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型©谢金星,清华大学数学科学系,2008.【附录1】基本参数设定•相邻公汽站平均行驶时间(包括停站时间)：3分钟•相邻地铁站平均行驶时间(包括停站时间)：2.5分钟•公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)•地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)•地铁换乘公汽平均耗时：7分钟(其中步行时间4分钟)•公汽换乘地铁平均耗时：6分钟(其中步行时间4分钟)•公汽票价：分为单一票价与分段计价两种，标记于线路后；其中分段计价的票价为：0～20站：1元；21～40站：2元；40站以上：3元•地铁票价：3元（无论地铁线路间是否换乘）•推论：换乘公汽等待３分钟，换乘地铁等待２分钟【附录2】公交线路及相关信息（见数据文件）©谢金星,清华大学数学科学系,2008.线路数据中的问题线路数据中的异常或不明确之处，同学可根据自己的理解作出假设和处理，一般不会影响实例的计算结果–个别线路相邻站点名相同，可去掉其中一点或不作处理等–L406未标明是环线，是否将其当作环线处理均可–L290标明是环线，但首尾站点分别为1477与1479，可将所有线路中1477与1479统一为1477后计算。同学也可以按照各自认为合理的方式处理，包括不当作环线，或将1479改为1477，或在1479后增加1477，等等–如果在假设中有明确约定，则环线单向或双向发车均应认可（按单向发车作假设，计算结果可能差些）©谢金星,清华大学数学科学系,2008.对通过地铁换乘的理解•“假设同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘(无需支付地铁费)”•步行：公汽站地铁站（通道）公汽站•换乘耗时11min：步行4+4=8min;等车3min•第１问（只考虑公汽）：可不考虑以上换乘–有同学也考虑了如上换乘，只是不坐地铁，应该也可以–此样处理时，第１问和第２问的难度相近©谢金星,清华大学数学科学系,2008.模型的目标•多目标优化问题（至少考虑三方面）–换乘次数最少(N)、费用最省(M)、时间最短(T)•从该问题的实际背景来看，加权太合适–不少同学用层次分析法确定权–不少同学计算时间的价值（平均收入／工作时间）•不同目标组合的模型–三个目标按优先级排序，组合成六个模型–也可将某些目标作为约束©谢金星,清华大学数学科学系,2008.多数队仅采用搜索法（70-80%?）•直达；一次换乘；二次换乘；…ststst•求出所有线路；评价其目标(容易计算)；选优©谢金星,清华大学数学科学系,2008.多数队仅采用搜索法•总体来看，技术含量较低（基本上是枚举）–几乎没有建模，完全只有算法实现，算法也没什么创新•一般只考虑不超过两次换乘–不少文章引用参考文献作为依据，实用中似乎够用–题目难度大大降低，模型不够一般•换乘作为了第一目标，或作为一个最重要的约束•任意次换乘时算法复杂度提高，难以处理–结果不佳（如：从省时考虑，有些需３－４次换乘）©谢金星,清华大学数学科学系,2008.图论模型与最短路算法•用图论做的队也不少，但往往考虑不周–弧上赋权方式交代不清–套用Dijkstra或Floyd-Warshall算法，却不清楚其原理及适用的问题•需要建立一个带权有向图，节点表示站点，有向弧表示前一站点能够直达后一站点，弧上的权表示前一站点直达后一站点所需付出的代价(时间或费用)•图（网络）如何描述和表示？–基本要素：节点，有向弧（边），弧上赋权–邻接矩阵；关联矩阵（数学上处理方便，存储量较大）–链表（存储量较小，计算机上处理方便）©谢金星,清华大学数学科学系,2008.关联矩阵(IncidenceMatrix)表示法在线路选择问题中，当从i可直达j时，定义弧(i,j)；其上的权可为１或成本(时间或费用)；多重弧可只保留一条（弧上的权可取最小的成本，如时间或费用）G=(V，A)是一个简单有向图；|V|=n，|A|=m重要数学性质：关联矩阵是全幺模矩阵图G=(V，A)的邻接矩阵C是如下定义的：C是一个的矩阵，即mn,}1,0,1{)(mnmnikbB其他。，,0),(,,1,),(,,1AijkVjAjikVjbik©谢金星,清华大学数学科学系,2008.邻接矩阵(AdjacencyMatrix)表示法图G=(V，A)的邻接矩阵C是如下定义的：C是一个的0-1矩阵，即在线路选择问题中，当从i可直达j时，定义弧(i,j)；其上的权可为１或成本(时间或费用)nnG=(V，A)是一个简单有向图；|V|=n，|A|=m,}1,0{)(nnnnijcC.),(,1,),(,0AjiAjicij有向图的“传递闭包算法”(可用于一般二元关系)权取0-1时，C(0)=C可称为直达矩阵；C(1)=C*C为１次可达矩阵；C(2)=C(1)*C为2次可达矩阵；……©谢金星,清华大学数学科学系,2008.链表（邻接表）表示法122345283904602403053036470单向链表(指针数组)A(1)={2,3}A(2)={4}A(3)={2}A(4)={3,5}A(5)={3,4}12345©谢金星,清华大学数学科学系,2008.Dijkstra算法（标号算法，1959）STEP1.如果S=V,则uj为节点s到节点j的最短路路长(最短路可以通过数组pred所记录的信息反向追踪获得),结束.否则继续.STEP0.(初始化)令S=，=V，；对V中的顶点j(js)令初始距离标号.S0)(,01spreduusjuSTEP2.从中找到距离标号最小的节点i，把它从删除，加入S.对于所有从i出发的弧,若，则令转STEP1.SSAji),(ijijwuuijpredwuuijij)(,特点：1.算法求出从源点s到所有点的最短路长2.每点给一对标号(uj,predj)，uj是从s到j的最短路长；predj是从s到j的最短路中j点的前一点©谢金星,清华大学数学科学系,2008.Example©谢金星,清华大学数学科学系,2008.Dijkstra算法（标号设定算法）•适用于正费用网络：“分层”设定标号•永久标号：S中的点，uj是最短路长•临时标号；其他点，uj是只通过S中的点的最短路长对于稠密网络，这是求解最短路问题可能达到的最小的复杂度,因为任何算法都至少必须对每条弧考虑一次.对于稀疏网络，利用各种形式的堆（Heap），其复杂度可降为或等)log(),log(nnmOnmO))log((CnmO算法复杂度O(n2+m)：如链表或邻接矩阵实现找最小标号点修改标号©谢金星,清华大学数学科学系,2008.•特点：求所有点对间最短路•基本思想：逐步逼近，迭代求解最短路方程:O(n3)Floyd-Warshall算法（标号修正算法，1962).,,1,,},,min{,,,0)()()()1()1()1(nkjiuuuujiwuukkjkikkijkijijijii临时标号是不通过k，k+1，…,n节点(i,j除外)时从节点i到节点j的最短路路长.)(kiju©谢金星,清华大学数学科学系,2008.Floyd-Warshall算法的具体实现:O(n3)由于要记录所有节点之间最短路的信息,所以这里我们要用一个二维数组P；可依据P,采用“正向追踪”的方式得到最短路.STEP2：如果k=n,结束;否则转STEP1.STEP0:k=0.对于所有节点i和j:令，,(，若节点i和j之间没有弧,认为).jpij)1(0iiwijwijijwu)1(STEP1:k=k+1.对于所有节点i和j:若,令,;否则令,.)()()(kkjkikkijuuu)()1(kijkijpp)()1(kijkijuu)(,)1(kkikijpp)()()1(kkjkikkijuuu©谢金星,清华大学数学科学系,2008.Floyd-Warshall算法的矩阵迭代法实现：O(n4)•令D为权矩阵(直达最短路长)•Dm为正好经过m条弧从i到j的最短路长©谢金星,清华大学数学科学系,2008.问题1和2的一种具体建模方法(赋权)在线路选择问题中，当从i可直达j时（同为公汽或地铁站点），定义弧(i,j)；其上的权为lij表示由i直达j付出的代价，可以为时间或费用(不包括换乘代价；多条线路可达时只保留最小代价)初始等车时间2(3)min也不包括在内，最后结果可加上注意：D=D(0)不是对称矩阵(“直达矩阵”)(0)0ijijijaijl站点往站点无直达车否则dij(0)=dij©谢金星,清华大学数学科学系,2008.问题１－２的一种具体建模方法i站点是公汽站点，j站点为地铁站点：（1）若j站点对应的所有换乘(公汽)站点k，均不能从i直达(不在i站点所在公汽线路L上)，则dij(0)=∞.（2）若j站点对应的换乘站点(k),可从i站点直达k，则费用为dij(0)=dik(0)；对于时间则需要加上k到j的步行时间.(若有多种选择，取最小成本者即可)ikj©谢金星,清华大学数学科学系,2008.问题１－２的一种具体建模方法j站点是公汽站点，i站点为地铁站点：（1）若从i站点对应的任何换乘(公汽)站点k，均不能直达j站点，则dij(0)=∞.（2）若从i站点对应的换乘(公汽)站点k，能直达j站点，则费用为dij(0)=dkj(0)；对于时间则需要加上i到k的步行时间.ikj©谢金星,清华大学数学科学系,2008.问题１－２：最小费用或时间•定义矩阵算子“⊙”如下：设A、B均为n阶方阵，C=A⊙B(考虑换乘代价),,min1,2,,ijikkjijkcabkn当考虑费用矩阵之间的运算时，,,ijk表示在k的换乘时间当考虑时间矩阵之间的运算时，,,ijk＝０•D(k)=D(k-1)⊙D表示k次换乘的最低代价(费用或时间)•该算法大体相当于求最短路的Floyd-Warshall算法，但考虑了换乘因素，可称为改进Floyd-Warshall算法•类似地,通过修改Dijkstra算法求解也可©谢金星,清华大学数学科学系,2008.问题１－２：最小费用或时间δi,j,k表示换乘时间•i=j或k=i，j时，δi,j,k=0•其他情形：若不可换乘(当i，j为公汽站点而k为地铁站点，或者i，j为地铁站点而k