乘公交看奥运2007B.ppt

《乘公交看奥运2007B.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、路选择问题的自主查询计算机系统：核心是线路选择的模型与算法应该从实际情况出发考虑，满足查询者的各种不同需求1.仅考虑公汽线路，给出任意两公汽站点之间线路选择问题的一般数学模型与算法2.同时考虑公汽与地铁线路，解决以上问题3.假设又知道所有站点之间的步行时间，给出任意两站点之间线路选择问题的数学模型【附录1】基本参数设定相邻公汽站平均行驶时间(包括停站时间)：3分钟相邻地铁站平均行驶时间(包括停站时间)：2.5分钟公汽换乘公汽平均耗时：5分钟(其中步行时间2分钟)地铁换乘地铁平均耗时：4分钟(其中步行时间2分钟)地铁换乘公汽平均耗时：7分

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

4、型三个目标按优先级排序，组合成六个模型也可将某些目标作为约束多数队仅采用搜索法（70-80%?）直达；　一次换乘；　二次换乘；　…ststst求出所有线路；评价其目标(容易计算)；选优同学论文中存在的主要问题2.目标不当，或不完整1.几乎没有模型，只有算法（一般是搜索法）3.算法使用不当4.对第３问，几乎是没有多少时间来认真进行讨论和建模5.全文表达不太清楚，思路混乱问题一:公汽站点之间线路选择模型:通畅、便利目标：换乘次数最少不同的行程需求：行程耗时最少；行程费用最少.人性化查询设计：转乘站点是否为始发站提示；站点负载压力提示.问题一

5、:公汽站点之间线路选择模型:1.数据处理，将三种公汽线路进行处理；2.建立可查询两站之间直达线路的“公汽直达数据库Q”；3.建立基于有向赋权图与最短路理论的0-1规划模型；4.针对模型分别使用不同方法求解，得到多种适合不同用户的方案集。1.数据处理——三种公汽线路抽象处理(1)下行线、上行线原路返回(2)线路为环行线(3)下行线与上行线经过站点不同2.“公汽直达数据库Q”的建立查询系统内部应设有任两站点的直达线路表，以方便查询时优先快速查询是否有直达车，若有，则直接输出所有直达车辆；若无，再搜索换乘路线。本题共有3957个站点,元胞结构

6、3.模型Ⅰ分析与建立当输入起讫点后，系统内部通过Q查询无结果时，系统内部应自动搜寻换乘次数最少的路线，若换乘次数相同时有多种转乘方案，则系统应显示所有转乘路线方案（包括转乘次数、行程总时间、途径总站点数、转乘站点及路线、是否始发、行程总费用、转乘站点负载压力）供查询者自主选择。系统应向查询者推荐“时间最短”，“费用最省”，“转乘站始发站最多”，“负载压力最小”的不同目标下的最佳路线。基于不同目标的带权有向图定义建立一个带权有向图，节点表示站点，有向弧表示前一站点能够直达后一站点，弧上的权表示前一站点直达后一站点所需付出的代价(时间,费用

7、等)时间：费用：始发：负载：最少换乘次数的确定统计Q中各元素长度，可得任意两站点的直达线路数。由此可构造表示两两站点间直达路线数目的直达线路数矩阵通过矩阵的幂运算可得到任两站点间换乘线路数矩阵，进而得到任两站点间的最少换乘次数矩阵从而可得任两站间所需的最少换乘次数。最少换乘次数的确定1.直达线路数矩阵2.换乘线路数矩阵的建立矩阵A的2次幂中元素表示任两站点间通过1次转乘的路线数，即如:A2的第1行第2列元素以An表示方阵A的n次幂，Akj为站点k→j的直达路线数，则：3.最少换乘次数矩阵的建立引入矩阵B=(bij)，其矩阵元素bij为使

8、得aijn≠0的n的最小值，n∈[1,∞)，则:bij-1表示从站点i→j必要的最少换乘次数，以矩阵C=(cij)表示最少换乘次数矩阵，则：cij=bij-1(当i≠j时)基于最短路理论的模型分析目标一：换