最佳公交线路选择模型1.ppt

最佳公交线路选择模型 报告人 7组李腾 郭志科 孙鹏鹏 1 仅考虑公汽线路 给出任意两公汽站点之间线路选择问题的一般数学模型与算法 并根据附录数据 利用你们的模型与算法 求出以下6对起始站 终到站之间的最佳路线 要有清晰的评价说明 1 S3359 S1828 2 S1557 S0481 3 S0971 S0485 4 S0008 S0073 5 S0148 S0485 6 S0087 S36762 同时考虑公汽与地铁线路 解决以上问题 3 假设又知道所有站点之间的步行时间 请你给出任意两站点之间线路选择问题的数学模型 相邻公汽站平均行驶时间 包括停站时间 3分钟相邻地铁站平均行驶时间 包括停站时间 2 5分钟公汽换乘公汽平均耗时 5分钟 其中步行时间2分钟 地铁换乘地铁平均耗时 4分钟 其中步行时间2分钟 地铁换乘公汽平均耗时 7分钟 其中步行时间4分钟 公汽换乘地铁平均耗时 6分钟 其中步行时间4分钟 公汽票价 分为单一票价与分段计价两种 标记于线路后 其中分段计价的票价为 0 20站 1元 21 40站 2元 40站以上 3元地铁票价 3元 无论地铁线路间是否换乘 一 模型假设 除具有上下行不同线路的公交外 其他公交均为对外制 乘坐环行线路经过终点站后要重新收费 同一地铁站对应的任意两个公汽站之间可以通过地铁站换乘且无需支付地铁费 两个地铁站间不通过公汽站换乘 公交系统畅通无阻 不考虑中途发生故障堵车等情况 二 符号说明 站点编号 路径换乘次数 总费用为 总耗时为 第类交通工具的第条行驶路线 三 模型建立 3 1标准形式的交通网络图在站点转车的时候 会有转车时间 这个转车时间由两个交通工具的类型来决定 即站点具有变化的权值 同时线路也有权值 如线路上的行驶时间 收费等等 由此可得标准形式的交通网络图为 其中为站点集合为交通线路集合 表示第类交通工具的第条行驶路线 表示站点权值集合 存在三个极值 换乘权值耗费时间权值 费用权值 为线路权值集合 存在三个权值 换乘权值 耗费时间权值 费用权值 3 2路线选择模型出行者在选择出行路线时 会考虑的主要因素有换乘次数 总耗时 出行费用 为此建立多目标规划模型 设给定起点和讫点 可行的乘车路线集合为表示在起点选择线路到达 换乘到达 最终到达的乘车路线 记该路径换乘次数为 总耗时为 总费用为 则一般的多目标规划模型为考虑到用户在权衡这些因素时 优先层次会不一样 故本文根据不同出行者分别建立分层多目标规划模型 1 模型一对主体人群而言 在满足换乘次数最少的前提下 总耗时与费用作标准化处理 然后利用线性加权和法得到评价函数如下其中 且 表示换乘次数最少的所有路线中总耗时的最小值 表示换乘次数最少的所有路线中所花费用的最小值 为权值系数 分别表示主体人群对总耗时与费用的重视程度 为了更客观科学地反映实际情况 其大小可通过对公众的问卷经统计方式进行确定 综上分层多目标规划模型为其中为优先因子且 表示换乘次数 时间费用函数分别属于第一 第二优先目标 且换乘次数对时间费用具有绝对优先权 2 模型二对于赶时间的乘客 时间是他们最先考虑的因素 其次考虑换乘次数 最后考虑费用 鉴于此种情况下时间与换乘次数为主要决定因素 故可以忽略费用的影响 将三目标模型简化为以时间作为第一优先目标 换乘次数为第二优先目标的分层规划模型其中为优先因子 且 3 模型三对于需要长期重复相同路线的乘客 虽然仍会考虑换乘次数 但由于他们经常性地重复相同的路线 因此他们会优先选择更加经济的路线 然后再考虑换乘次数 最后才考虑时间 鉴于费用与换乘次数为主要决定因素 故在此情况下可以忽略时间的影响 为此建立以费用为第一优先目标 换乘次数为第二优先目标的分层多目标规划模型其中为优先因子 且 以上建立的三种模型是针对用户不同的查询要求建立的 模型一适用于大部分人的查询要求 尤其适用于对北京路线不熟的外地和外国乘客 所以在设计自主查询系统时 可以考虑将模型一作为系统默认的查询模型 模型二适用于对世界要求很高的乘客 如赶时间的乘客 模型三适用于对北京非常熟悉 且需要经常重复所查零的乘客 所以在设计自主查询系统时也应顾及到这两类人群 可以考虑将模型二 模型三作为备选的查询系统 四 算法设计 1 BFS算法 步骤1读入交通网络信息 建立相应的拓扑图 读入要进行求解得出发点和终点 将出发点加入队列 步骤2将队首元素出队 x Deque queue 检查x的深度 若与目标节点的深度相同则转步骤4 否则转步骤3 步骤3依次检索由x发出的可扩展节点 若符合扩展条件则加入队列 同时存储其所有的前序节点 若y为目标节点则记录y的深度作为目标节点的深度 步骤4从目标节点出发 回溯通过结构所存储的全部前序节点 到达出发点后输出所经过的路径 即得到从起始点到达目标节点的所有换乘次数最少的路线 再根据第二层优先目标函数 求出所得到的各条路线的目标函数值 选取目标值最小的一条作为最佳路线 2 Dijkstra算法 步骤1读入交通网络信息 建立相对应的时间图 费用图 读入要求解的出发点和目的地 将出发点加入堆中 步骤2若堆为空 则转步骤4 若不为空则取堆顶元素到x中 堆大小减一 即减一 步骤3依次检索由x出发的可扩展节点 若满足以下情况之一 则把y的值更新为新的值 并存储到y的父节点 1 到x的值加上从x到y的边的权重小于y原有的值 2 到x的值加上从x到y的边的权重等于y原有的值 且到x节点的换乘次数加一小于y节点的换乘次数 若y在堆中则调用修改y节点的权值 若y不在堆中则将y节点加入堆 堆的大小增加一即 步骤4从目标节点出发 通过结构存储的父节点回溯到达出发点后输出路径 由于在算法执行过程中我们会在所有权值最小的结果中选择存储深度最小的节点 因此最后的结果是以时间 费用 最少的情况下 满足换乘次数最少的方案 六 模型改进 1深度优先搜索 V1 遍历顺序 非连通的图重复上述过程 使每个顶点均被访问 V1 V2 stack V4 V8 V5 首先访问顶点V0 然后依次从V0的各个未被访问过的邻接点出发进行深度优先搜索遍历 当一个顶点的所有临接顶点都被访问过 退回到最近被访问过的顶点 访问它的下一个临接顶点 深度优先搜索算法 booleanvisited MAX status VisitFunc intv voidDFSTraverse GraphG Status visit intv VisitFunc visit for v 0 v G vexnum v visited v FALSE for v 0 v G vexnum v if visited v DFS G v voidDFS GraphG intv visited v TRUE VisitFunc v for w FirstAdjVex G v w w NextAdjVex G v w if visited w DFS G w Breadth FirstSearch基本思想是 从图中某个顶点v出发 在访问了v之后依次访问v的各个未曾访问过的邻接点 然后分别从这些邻接点出发依次访问它们的邻接点 并使得 先被访问的顶点的邻接点 先于 后被访问的顶点的邻接点 进行访问 直至图中所有已被访问的顶点的邻接点都被访问到 如若此时图中尚有顶点未被访问 则需另选一个未曾被访问过的顶点作为新的起始点 重复上述过程 直至图中所有顶点都被访问到为止 2广度优先搜索 2广度优先搜索 12345678 遍历顺序 非连通的图重复上述过程 使每个顶点均被访问 广度优先搜索算法 voidBFSTraverse GraphG Status visit intv for v 0 v G vexnum v visited v FALSE IntiQueque Q for v 0 v G vexnum v if visited v EnQueue Q v while QueueEmpty Q DeQueue u for w FirstAdjVex G u w w NextAdjVex G u w if visited w visited w TRUE visited w EnQueue G w 25 Kruskal算法示意图 26 Kruskal 克鲁斯卡尔 算法 例 演示 27 计算机内怎样实现Kruskal算法 设计思路 设每条边对应的结构类型为 特点 将边归并 适于求稀疏网的最小生成树 故采用邻接表作为图的存储表示 取堆顶元素 加入到对应最小生成树的新邻接表中 初始为空 从堆中删除它并重新排序堆 每次耗时log2 e 重复上一步 注意每次加入时要判断是否 多余 即是否已被新表中的连通分量包含 直到堆空 显然 Kruskal算法的时间效率 O elog2e 初态 按权值排序 以堆排序为佳 堆顶即为权值最小的边 迪杰斯特拉 算法描述 1 带权有向图中信息表示 for i 0 i G vexnum i voidInit MGraphG VertexTypev final i FALSE D i G arcs v i 集合S初始为空D i 初始值为弧 v vi 权值 if D i INFINITY p i vvi elsep i 若存在弧 v vi 最短路径为 vvi 否则为空字符串 迪杰斯特拉 算法 voidShortestPath DIJ MGraphG VertexTypev Init MgraphG VertexTypev 初始化各向量 D v 0 final v TRUE 初始化 源点v放入集合S for i 1 i G vexnum i j minV S