随机环境下的地铁换乘问题两阶段优化模型

作     者：张妍 

作者单位：北京交通大学 

学位级别：硕士

导师姓名：杨立兴

授予年度：2016年

学科分类：08[工学] 082303[工学-交通运输规划与管理] 0823[工学-交通运输工程] 

主      题：地铁换乘问题 两阶段随机优化模型 分支定界算法 标号修正算法 

摘      要：公共交通是维系城市交通系统正常运转的重要部分,是城市可持续发展的重要保障。在许多发达城市,地铁作为日常公共交通出行的主要载体,正承担着越来越多的客运任务。随着城市的迅速扩张与发展,为满足人们日益增长的交通需要,地铁网络的规模也在不断增大。网络线路的增加、换乘站数量的增多以及网络结构的复杂使得出行者在出行时的可选换乘方案也存在多样性。为节省出行时间、提高出行效率,如何在出行前选择鲁棒、快速的换乘方案已逐渐成为人们关注的重要问题。本文以地铁网络中的换乘问题为研究对象,分别在静态和动态随机环境中探讨如何获得能够节省出行时间的鲁棒换乘方案。具体的,利用基于场景的路段通行时间与换乘时间表示现实网络的不确定性,以最小期望出行时间和换乘惩罚为目标函数,分别建立静态随机环境和动态随机环境下的地铁换乘问题两阶段整数规划模型。在实际应用过程中,鲁棒换乘方案将作为出行前的决策指导,而具体出行路径则由出行者根据当前网络状态自适应地进行选择。最后,将标号修正算法嵌入到分支定界算法的框架中设计启发式算法求解模型的近似最优解。并以北京地铁网络为背景,设计数值算例,验证了模型与算法的有效性。本文主要包括以下研究内容：(1)静态随机环境下地铁换乘问题两阶段模型详细分析地铁出行过程中路段通行时间和换乘时间的不确定性,采用基于场景的随机数据表示路段通行时间及换乘时间的随机性。利用换乘活动网络与实际网络分别对应模型的两个阶段,模型第一阶段在换乘活动网络中找到能够连接起点与终点的换乘节点序列；模型第二阶段生成通过固定换乘节点的场景最短路径对第一阶段的换乘方案进行评价。最后,以最小期望出行时间和换乘惩罚为目标函数,建立静态随机环境下地铁最优换乘点选择问题的两阶段优化模型,并详细分析模型的复杂性。(2)动态随机环境下的地铁换乘问题建模为描述地铁换乘问题的动态性,进一步将不同场景下的路段通行时间和换乘时间处理为时间相关的离散随机变量,并利用时空网络详细分析网络动态性对出行时间的影响。依然采用两阶段决策过程,以最小期望出行时间和换乘惩罚为目标,利用生成的场景最短路径信息评价不同的换乘方案,建立动态随机环境下的地铁换乘问题两阶段模型。(3)分支定界与标号修正相结合的启发式算法针对网络模型的复杂性,将标号修正算法嵌入到分支定界算法的框架之中,设计分支定界与标号修正相结合的启发式算法。利用标号修正算法生成的场景最短路径信息实现搜索树的分支过程,缩小搜索范围,找到可行的换乘节点序列。同时,不断更新搜索树的全局上界与全局下界,直到找到近似最优解。本文对算法的分支、定界及剪支过程做了详细描述,并对算法流程进行了说明。(4)算法有效性验证及算例分析设计小规模网络算例详细说明算法的求解过程。以北京地铁网络作为大规模网络算例的背景,设计数值实验对算法的求解速度、算法解的质量以及算法的鲁棒性等性质进行分析,验证模型与分支定界算法的有效性。