20xx国赛b题特等奖论文

20xx国赛b题特等奖论文内容摘要：

17 0 16 3 邻接 2 67 2903 1784 15 485 167 0 9 3 邻接 2 67 2903 1784 15 485 217 0 9 3 表 二线 S1557→ S0481 部分出行方案列表 求解方法 转乘 总时 间 转站点 1 转站点 2 车辆 1 车辆 2 车辆 3 转站点始 发数 总负 载 总费 用 Lingo 3 102 1919,3186,903 L84,L189,L91,L239 4 Lingo/邻接 2 109 1919 3186 84 189 460 0 113 3 邻接 2 109 1919 3186 363 189 460 0 113 3 邻接 2 115 1919 2424 84 417 254 0 112 3 邻接 2 115 1919 2424 84 417 312 0 112 3 邻接 2 118 1919 992 84 417 460 0 126 3 邻接 2 118 1919 992 363 417 460 0 126 3 邻接 2 130 1919 417 84 497 460 1 90 4 邻接 2 130 1919 417 363 497 460 1 90 4 邻接 2 133 3389 1427 84 454 447 1 77 4 表 三线 S0971→ S0485 部分 出行方案列表 求解方法 转乘 总时 间 转站点 1 转站点 2 车辆 1 车辆 2 车辆 3 转站点始发 数 总负 载 总费 用 邻接 1 131 2184 13 417 0 6 3 邻接 1 146 2119 13 395 0 11 3 邻接 1 152 1739 119 417 0 1 3 Lingo/邻接 2 106 2517 2159 13 290 469 0 2 3 邻接 2 109 1609 2654 13 140 469 0 33 3 邻接 2 109 1609 2654 24 140 469 0 33 3 邻接 2 124 2324 2482 13 132 417 1 17 4 邻接 2 124 2324 2482 13 242 417 1 17 4 邻接 2 124 2324 2480 13 132 417 1 24 4 邻接 2 124 1520 2265 119 8 469 0 52 3 表 四线 S0008→ S0073 部分出行方案列表 求解方法 转乘 时间 转站点 1 转站点 2 车辆 1 车辆 2 车辆 3 始发数 负载 总费用 Lingo 4 62 3766,2085,483,525 L198,L476,L17,L328,L103 5 邻接 1 86 2263 355 345 0 48 2 邻接 1 89 2302 355 57 0 16 2 邻接 1 113 3415 463 118 0 46 2 邻接 1 131 3915 463 118 1 9 2 Lingo/邻接 2 70 1691 2184 198 290 345 0 0 3 邻接 2 70 1383 2184 43 290 345 0 37 3 邻接 2 79 630 1659 159 231 459 1 83 3 邻接 2 79 630 1659 159 381 459 1 83 3 邻接 2 79 854 1659 159 231 459 1 60 3 表 五线 S0148→ S0485 部分出行方案列表 求解方法 转乘 总时 间 转站点 1 转站点 2 车辆 1 车辆 2 车辆 3 转站点始发数 总负 载 总费 用 Lingo 3 105 3604,2361,2210 L308,L81,L156,L417 4 Lingo/邻接 2 109 36 2210 308 156 417 1 29 3 邻接 2 112 36 2482 308 157 417 1 47 3 邻接 2 118 3604 1381 308 129 469 0 21 3 邻接 2 118 3604 2026 308 123 469 0 14 3 邻接 2 118 3604 1383 308 129 469 0 24 3 邻接 2 121 3604 2840 308 454 417 0 22 3 邻接 2 121 302 2027 308 427 469 0 13 3 邻接 2 121 3604 1321 308 129 469 0 3 3 邻接 2 124 3604 2079 308 206 417 0 73 3 表 六线 S0087→ S3676 部分出行方案列表 求解方法 转乘 总时 间 转站点 1 转站点 2 车辆 1 车辆 2 车辆 3 转站点始发 数 总负 载 总费 用 Lingo/邻接 1 68 3496 454 209 0 36 2 Lingo/邻接 2 49 88 427 21 231 97 0 52 3 邻接 2 49 88 427 206 231 97 0 52 3 邻接 2 49 88 427 454 231 97 0 52 3 邻接 2 52 630 427 21 381 97 0 44 3 邻接 2 52 854 427 293 231 97 0 21 3 邻接 2 52 1427 427 21 381 97 0 12 3 邻接 2 55 541 2336 454 120 462 0 68 3 邻接 2 61 3874 280 21 68 462 1 13 3 邻接 2 73 3874 274 21 68 462 1 12 3 用户选线指南： 上面表中已按多目标分层序列法的默认目标排序（分别是表中转乘次数、总时间、转车站点是否始发、转车站点总负载量、总费用五个字段） ，一般用户只需要从上到下选取即可，但如果用户希望在转站时乘坐始发车（有座位）那么可以挑选始发字段为 2 的方案，若希望转站时人较少的地方则可以考虑选则站点负载较小的方案。 综述，本模型 I 求解的方案集使用于所有用户，具有很强的实用价值。 模型Ⅰ的评价 邻接算法评价 1) 建立在图论基础下能够求解出转乘次数不超过两次时的所有可行方案，并可根据公众的不同需求，给出最佳需要方案，从此角度考虑，模型实用性较强； 2) 模型求解基于直达队列 Q ，采用空间换取时间思想，适合查询系统设计标准能够较强的适应工程应用； 3) 在转乘次数超过两次的情况下，运用本模型求解计算过程复杂，计算量过大；故本模型存在一定的局限性。 01 规划 Lingo 求解方案评价 1) 在不限制最小转乘数时可以求得全局最优解，这是其他所有算法无法达到的，例如在第 5 条线路上其转车次数为 3，但是耗时相对转 2 次的要节省许多； 2)在限制最小转乘数时可以求得与邻接算法同样的方案，表明模型的通用性较强，但无法像邻接算法一样求解多种方案是用户所不能接受的； 3) 从理论角度分析，最优化模型规划角度可解具有很强的实际意义，例如从全国范围考虑求解，那么转车 3~4 次也是可以接受的，只要耗时足够短； 4) 从计算 时间来分析，尽管需要 20 分钟，但大部分时间为数据导入，只有 1%的时间是真正计算耗时，如果将所需数据存放入内存不变，其求解速度将超越邻接算法； 5) 但 Lingo 不能求解出多种方案，实用性不如邻接算法。 6 同时考虑公汽与地铁最佳线路选择模型（问题二） 本问为综合考虑公汽与地铁线路的情况，解决查询系统中混合最佳路径选择问题的 模型与算法。 数据处理 —— 公交网简化模型 1）将可互换站点抽象处理为一个站点 题中给出了地铁换乘公汽的数据文件，由地 铁与公汽互换的时间来看，可互换的两站间地理位置应非常接近且容易换乘，定义这些站点为紧邻站点，可将这些可互换的紧邻站点抽象为一个站点，使问题得到简化。 例 ：信息数据第一行为“ 01 : 05 67 , 00 42 , 00 25D S S S” ,则可认为这四个站点实际距离非常近，为紧邻站点，所以可看做一个点处理，示意图如下： 基于这种思想，根据题目中给出关于地铁换乘公交的信息数据，可以将各地铁站点 及其紧邻站点在整个交通网络中抽象为一个点处理。 2）两种地铁线路抽象处理 基于 对三种公汽线路的抽象方 法，以相同的方法对两地铁线路 1T 、 2T 进行抽象处理如下： 1T ：为双向线路，故可以根据不同的方向将其抽象为两条单向行驶线路。 2T ：为环行线路，实际中环形路线一般是对开，故该种线路可以抽象成两条线路处理。 “公汽、地铁直达数据库 DQ ”的建立 将紧邻站点处理为一个新站点，则当综合考虑公汽与地铁时，建立的 DQ 实质上是新站点与新站点间的直达路线集。 认为在新站点所代表的站点集中的任意站点可通过步行到达，且时间忽略。 则当用户输入起、讫点后，系统内部首先自动查找这两点所属的新站点，再查找新站点间可直达的线路，并给出起点及其附近站点可直达讫点及其附近站点的路线。 采用与 相同的思路及方法，把已知公汽线路到达 ()iRs 都映射到 kS ，计算新直达数据库 DQ ，再结合地铁的费用与地汽换乘等待时间就可以把地铁线与公汽线结合。 具体元胞结构设计图如下： Cell{1,1} Cell{1,2} 车号 费用 耗时 L001 2 27 T001 3 Cell{1,3} Cell{2,1} Cell{2,2} Cell{2,3} 图 元胞结构示意图 上图中 Cell{1,2}代表直达队列表中第 1 行第 2 个元胞（即从站点 S0001 到站点S0002 的直达混合线路信息） ，元胞中队列的每一行代表一辆直达车信息。 模型Ⅱ的分析与建立 经过数据处理后，紧邻站点被处理为一个新站点，该站点可等同看作问题一中的公汽站点，当用户输入起、讫点后，系统内部通过直达线路队列表查询无结果时，则搜寻转乘路线方案。 同时，系统向查询者推荐不同目标下的最佳路线及转乘方案。 最少换乘次数的确定 采用与 相同的建模思路及方法，统计 DQ 中各元素长度，可得任意两站点的直达线路数。 由此可构造表示两 两站点间直达路线数目的直达线路数矩阵 39。 A ，可确定换乘线路数矩阵： 39。 39。 39。 1 39。 1Nnnij ik kjkA A A （ ） 其中，元素 39。 nijA 为通过 ( 1)n 次换乘从站点 ij 的线路数。 其换乘站点可通过运算参数记录得到。 进而确定最少换乘次数矩阵：  39。 39。 m in { 0 , 1 , } ( )0 ( )nijijn A n i jbij       （ ） 39。 39。 1CB （ ） 表 最少换乘次数表 线路编号 1 2 3 4 5 6 起始站 S3359 S1557 S0971 S0008 S0148 S0087 终到站 S1828 S0481 S0485 S0073 S0485 S3676 最少换乘 1 2 1 1 2 0 模型分析 采用与 相同的建模思路及方法， 这里在考虑地铁后仍按目标的重要程度将 “换 乘次数最少”、“行程时间最短”、“行程费用最少”、“转乘车辆始发最多”、“站点负载压力最小”分设为第一到五层目标，基于 对各目标的分析与建立，这里不再复述分析，仅在模型建立时给出具体表达式，这里由于对站点的定义与第一问不同，所以对 时间 及 费用 的计算与第一问有所不同。 我们结合实际主要考虑用户如下几个因素： 目标一：换乘次数最少； 目标二：行程时间最短； 目标三：行程费用最少； 目标四：转乘车辆始发最多； 目标 五：站点负载压力最小。 公汽地铁混合网络图的赋权 通过 的简化，结合图论相关知识，将第二问公汽、地铁混合网络抽象成一个有向赋权图 39。 39。 39。 39。 ( , , )G V E W , 39。 G 中的每个顶点为每个不同的站点 , 如果从 39。 G 中的顶点 39。 iV 到 39。 jV有直达路线，那么这两点之间就用有向边相连 , 记做 39。 (, )i j E ，赋权图中的权可根据不同的目标进行定义 ： 39。 ( , )39。 39。 39。 () vvijijijt n n ij t v vW t t  站 点 至 站 点 的 直 达 时 间时 间 ： 其 分 量 为无 直 达 线 路 39。 ( , )39。 39。 39。 () vvijij ijijp nn P v vW P P  站 点 至 站 点 的 直 达 费 用费 用 ： 其 分 量 为无 直 达 线 路 39。 ( , )39。 39。 39。 () vvijij ijijf nn f v vW f f  站 点 至 站 点 的 直 达 线 路 是 否 始 发始 发 ： 其 分 量 为无 直 达 线 路 39。 ()39。 39。