摘要
本研究旨在找出地铁网络中最优的传输方案。摘要利用基于样本的不变线路运行时间来获取真实网络的不确定性，建立了一个具有最小期望运行时间和传输活动代价的两阶段随机整数规划模型。第一阶段的目标是找到一个序列的潜在转移节点(站),可以组成一个从起源到目的地转移活动网络的可行的路径,第二阶段提供的时间最少路径所生成的转运站，再结合第一阶段评估给定的传输方案,然后输出最佳的路线信息。为了解决我们提出的模型，提出了一种有效的混合算法，该算法将标签校正算法嵌入到分支和绑定搜索框架中，从而找到所考虑问题的最优解。最后，对不同尺度的地铁网络进行了数值实验。计算结果表明，即使是在北京地铁的大型网络中，所提出的方法也是有效的。
目录
摘要 1
第1章介绍 2
1.1动机 2
1.2文献综述 2
1.3重点和提出的方法。 3
第2章 问题陈述 4
2.1 网络结构 4
2.2地铁系统不确定性分析 5
第3章 模型公式 7
第4 章 结论 9
第1章介绍
1.1 动机
由于地铁守时,运输能力大,高效等特点，为了满足乘客日常旅行的需求,大量的地铁线路投入运营或在建的很多城市。例如,2015年，在北京城市,现有和准备建设地铁线路的总长度已超过500公里,导致现有地铁网络的大幅扩张。通常，在一个庞大而复杂的城市轨道交通网络中，优化出行选择行为通常被认为是旅行者在规划和指定出行时所关心的一个关键问题。网络中有效的路线策略不仅可以为旅行者提供有效的导航信息，还可以对现有资源和基础设施进行潜在的利用优化。这可能涉及到在出发前选择最喜欢的换乘方案(或路径)，或者当你的出发地和目的地位于不同的地铁线路上时，选择在途中进行换乘。
在上海进行的一项调查显示，在地铁系统中，大约有50%的出行时间是由换乘过程占用的。在北京地铁网络中,超过百分之四十的乘客需要互相传递他们的旅行经验,其中大部分转移过程是相当复杂的，其中包括复杂的基础设施转运站和大型客运流(有超过一千万名乘客在地铁系统在每个工作日)。因此，超过10个换乘站必须为超过12万的日客运量提供服务，而大多数换乘活动都发生在高峰时段。由于迁移活动在路径查找中的重要性，如何在当前情况下选择最受欢迎的和稳健的转移策略，对于交通参与者的实际应用来说是一个理论上的重大问题。
在文献中，网络中的路径查找总是集中在生成最少的旅行时间路径。然而，需要注意的是，所涉及的旅行时间不仅包括火车上的旅行时间，还包括乘客在从一条地铁线路到另一条地铁线路的换乘活动发生的站台上的行走时间和等待时间。因此，由于客流干扰、转运站布局、列车延时等不确定性因素的影响，大型地铁网络的出行时间必然与随机特征相关联。结合这些不确定性信息，我们打算通过两阶段决策过程生成传递方案，在求解框架中集成先验优化和自适应决策。本研究将明确解决上述问题。
1.2 文献综述
摘要在随机最短路径问题的框架下，寻找地铁网络中最优的换乘方案，是乘客在地铁支路系统或出行前的一种常见行为。通常，经典的最短路径问题通常采用确定的弧长或弧行时间来表示网络特征。利用Bellman(1958)、Dijkstra(1959)、Dreyfus(1969)提出的标签设置或者校正算法有效地解决了0-1整数规划模型，可用于制定最短路径选择过程。然而，请注意，现实交通网络中的线路旅行时间通常是随机的和不确定的。为了在不确定的决策环境中处理这一问题，文献中许多研究者基于随机规划方法提出了多种建模方法和求解算法(关于随机规划的更多细节，请参见Ben-Tal和Nemirovski, 2000;Birge Louveaux,1997;陈等等,2007;Goel 和 Grossmann,2006;Heitsch Romisch,2003;Kall 和 Mayer,2005。例如，Frank(1969)、Mirchandani(1976)和Sigal等(1980)研究了随机网络中最短路径长度的概率分布。Mirchandani和Soroush(1986);Murthy 和Sarkar ,(1996);Loui(1983)从决策者效用的角度考虑了不同类型的成本函数来确定随机网络的最优路径。
据我们所知，现有文献的大部分主要集中在路径选择的两个评价指标，即期望效用和非期望效用(见Chen和Nie, 2015;Fan 和Nie,2006;Fu和Rilett,1998;Huang 和 Gao,2012;尼尔森,2003;Miller-Hooks,2001;Nie 和Wu,2009;沃勒和Ziliaskopoulos,2002;杨等等,2013;杨和周,2014;范等等,2005;王等等,2016;(Wu, 2015)，其中最常用的目标是找到最少的预期旅行时间。Hall(1986)首先说明了标准的最短路径算法不能用于在网络中寻找最不期望的旅行时间路径，它的旅行时间是随机的和依赖时间的，然后他提出了一个有效的方法来解决这个问题。Fu和Rilett(1998)将线路旅行时间定义为连续时间随机过程，并开发了一个基于一般概率的公式来计算动态随机网络中给定路径的旅行时间的均值和方差。Miller-Hooks和Mahmassani(2000)提出了两种改进的标签校正算法，即期望值算法和期望值下界算法，用于确定随机变化网络中最不期望的时间路径。此外，Miller-Hooks(2001)提出了一种有效的标签设置算法来确定随机网络中的自适应最小期望时间超路径。Yang和Miller-Hooks(2004)考虑了由于信号在信号通信网中的操作而导致的额外延迟，以获得信号随机网络中最不期望的旅行时间超路径。Gao和Chabini(2006)对最不期望的旅行时间路径提出了更通俗的解释，认为最不期望的时间路径问题是带有附加边约束的最优路径策略问题。他们建立了随机网络中最优路线策略问题的框架，并给出了精确的算法。
1.3 重点和提出的方法。
在此，值得注意的是，本研究的重点不是先验路径生成，而是地铁网络中传输活动的选择。与大城市的公路网相比，地铁网络的特点有很大的不同，因为大多数列车运行都需要遵循预先设计的、组织有序的进度表。然而，由于运行环境的复杂性，实际的地铁线路仍具有明显的随机特性。例如，由于高峰时段客流量较大(这是北京地铁系统的情况)，在乘客上下车的过程中，繁忙站台上列车的实际停留时间总是在一定的预定值上下波动。因此，从乘客的角度来看，如果一个人从他/她的起点坐火车到目的地，那么他/她坐火车的总时间通常是不确定的。此外，如果需要在某些车站换乘，所需要的换乘时间将完全取决于当前客运量、车站内部结构等一系列因素。因此，在大多数情况下，换乘时间也是随机的。 此外，高峰时段的客流控制是转运站管理铁路交通和交通状况的常用方法，对旅客的出行造成潜在的不确定因素。面对这些问题，如何有效地捕捉和处理地铁网络中现实的随机性，成为制定实用的出行指南的一个难题。
注意，文献中很少有研究评估过公共交通系统的转移成本(Guo和Wilson, 2011)，也有很多论文由于其复杂性而没有考虑转移随机性(Shafani和Khani, 2010)。然后，为了在大型地铁网络中给出一个有效的传输方案，我们只关注给定的OD对上的传输策略，而不是生成一个最喜欢的先验路径，使用基于样本的表示方法来描述所涉及的传输时间的随机性。实际上，这种类型的解决方案有两个优点:(1)它本质上以足够的实时性为旅行者提供最简单的传输信息，而且从行为选择的角度来看，这可以被认为是最有用的路线指南;(2)根据先进的旅游信息系统(如北京地铁网)所实现的交通状况，旅行者可以通过预先指定的转运站自适应地选择实际路径，可以预期的减少总行程时间。通常，我们提出的方法是先验优化和自适应路径选择的结合。与一个先验最小期望时间(LET)路径发现相比，这个发现可能导致单个或仅几个试验的高风险，本研究进一步放宽了唯一路径假设，因为它只需要修复在网络中的关键站点(即关键节点)，而不是整个旅行前的路径。此外，通过这些传输节点的实际路径可以根据所访问的当前旅行信息进行自适应指定，这使得乘客在实际应用中具有潜在的灵活性选择。
本研究旨在对大型地铁网络的路线导航方法做出如下贡献。
第2章 问题陈述
在这一节中，我们将首先就本研究的完整性对感兴趣的问题给出一个详细的说明。
2.1 网络结构
考虑城市地铁网络(N, E)，其中N为站点集合，E为相邻站点之间的连接集。让i和j表示站点的索引。指示连接从车站i到车站j可以表示成向量形式(i,j)。在现实中,不同地铁线路通常分别属于不同的物理空间(例如,在北京,中国),一组转运站一般需要为方便乘客转移。不失一般性，让M表示整个地铁网络中的传输节点集。下面我们将图1清晰地显示出感兴趣的地铁网络节点网络结构。
图1
图1所示。地铁网络图示。
显然，在这个说明性网络中显示了三条地铁线路，即:，第1行，第2行和第3行。这些线路互相交叉，形成一个小的网络，其中有两个固定站和三个换乘站。站4和站5是内部结构和功能简单的站，即只在这些站运送装卸货物和乘客。相比之下，除了运送乘客外，1、2、3站在传递平台上产生的客流方面也起着至关重要的作用。例如,给定OD(例如,节点4和节点5),两个可能的转移策略可以表示为“节点4→节点1→3→节点节点5”和“节点4→节点1→节点2→节点5”。以第二种转移策略为例。首先需要在地铁2号线4号站坐火车;然后沿着这条线到达2号站，他/她需要下车，然后到3号线的站台换乘，在那里他/她可以再乘一趟车到达目的地。在这个过程中，给定的OD对只有一个传递活动，即在车站2。有趣的是，人们在出行行为选择中提出的一个问题是，如何在地铁网络中生成最喜欢的传输策略，从而最小化相应的出行成本，因为在考虑的网络中可能存在各种潜在的路线计划。一般来说，出行行为选择可以考虑多种交通特征，如出行距离、出行时间、票价、出行舒适性、便利性等，其中出行时间往往是影响出行方式选择的关键因素。然而,我们注意到,尽管地铁交通是一个组织良好的交通模式,实际旅行时间并不是一个常数，实际上，由于不可预测的操作环境,如大客流,信号错误、机械故障、旅客流量控制,等等。因此,现实(链接或路径)旅行时间是在本质上与随机性相关联。在接下来的讨论中，我们的目标是对地铁系统中不同的出行时间进行不确定的分析。
2.2 地铁系统不确定性分析
如上所述，地铁网络的实际运行时间可以受到各种随机事件的影响。考虑到这个问题，即使我们考虑每天相同的时间段，整个网络上的链接传输时间可能在不同的日子都会有所不同。为了描述地铁系统的不确定性，下面的讨论特别采用基于样本的随机数据表示来确定不确定性。该数据也适用于将特定日的实际线路旅行时间包含到模型中，以反映操作过程中的现实随机性。
一般来说，一个人整个旅行的时间包括在车站停留的时间，在火车上运行的时间和在换乘站的时间。建模简单,本文结合了居住时间和运行时间在每个铁路段的连接旅行时间Tijomega;链接(i,j),其中omega;表示不同的样品描述的随机性。换句话说，即使一列火车要停下来卸货和装载乘客，每个车站也不需要额外的时间。换乘时间是指乘客从当前列车上下来，穿过换乘平台，到达换乘列车的登机口的时间。所以,它可以分为转移步行时间Wmomega;和转让等待时间Vmomega;转运站m。正如上面分析的,每个OD的旅行时间实际上是不确定的,因为这肯定不能确定出行的每一个部分。下面的讨论旨在详细说明每个部分的具体特性。
(1)链接出行时间的不确定性。
为了指定链路运行时间，我们特别给出了图2，在图中描述列车运行时间、停留时间和装卸乘客过程，到站或离站节点表示列车到站或离站活动。如图所示，列车计划从节点i出发到达节点j，其中t1对应于两个站点之间的运行时间。然而，受信号误差、延迟传播、突发事件等诸多因素的影响，现实运行时间在各种情况下可能会随机波动。在j站，使用t0持续时间的居住电弧用来表示这列火车在卸货和装载乘客时的停留时间，而队列弧线表示等待上车的客流。实际上，居住时间完全取决于客流的体积。如果预定的等待时间足够安全运行，那么这应该是列车运行的理想时间。另一方面，对于一些繁忙的换乘站来说，大量的客流必然会增加列车的实际停留时间，尤其是在工作日的高峰时段，导致列车的停留时间的不确定性。在这种情况下，列车的运行时间和停留时间在实践中本身都是不确定的。因此，将线路旅行时间作为具有随机分布的不确定变量是合理的。
图2所示。与铁路线路运行和停留时间有关的不确定性的说明。
(2)转移时间的不确定性
如图1所示，当乘客在m号换乘站(如节点1)从1号换乘到2号换乘时，我们在此指定换乘过程。为了便于描述，在交通网络中特别增加了两条人工弧线，这两条弧线将这两条线的平台以相反的方向连接起来，以表示连接性。通过这种方法,这两个平台将被视为两个分离的节点,节点用m和m线1和线2′表示。在m号线1号线下车后，他/她通常需要穿过一段长通道(即:弧(m m′)连接这两条线:2号线列车。假设一位乘客下车后从1号线到达2号线的平台需要他/她Wm<sup
全文共8033字，剩余内容已隐藏，支付完成后下载完整资料</sup
Abstract
This research focuses on finding the best transfer schemes in metro networks. Using sample-based time-invariant link travel times to capture the uncertainty of a realistic network, a two-stage stochastic integer programming model with the minimized expected travel time and penalty value incurred by transfer activities is formulated. The first stage aims to find a sequence of potential transfer nodes (stations) that can compose a feasible path from origins to destinations in the transfer activity network, and the second stage provides the least time paths passing by the generated transfer stations in the first stage for evaluating the given transfer schemes and then outputs the best routing information. To solve our proposed model, an efficient hybrid algorithm, in which the label correcting algorithm is embedded into a branch and bound searching framework, is presented to find the optimal solutions of the considered problem. Finally, the numerical experiments are implemented in different scales of metro networks. The computational results demonstrate the effectiveness and performance of the proposed approaches even for the large-scale Beijing metro network.
目录
1. Introduction 2
1.1. Motivations 2
1.2. Literature review 3
1.3. The focus and proposed methods 5
2. Problem statements 7
2.1. Network structure 7
2.2. Uncertainty analysis in metro systems 9
3. Model formulation 12
4. Conclusions 14
1. Introduction
1.1. Motivations
To meet the daily travel demands of passengers, a large number of metro lines have been put into operations or being under construction in a lot of cities, due to the characteristics of punctuality, large transportation capacity, high-efficiency, etc. For instance, in Beijing city, the total length of the current and in-construction metro lines have been over 500 km up to 2015, causing the drastic expansion of exiting metro networks. Typically, in a large and complex urban rail transit network, optimizing travel choice behavior is usually regarded as a key issue concerned by travelers in planning and specifying their trips. An effective routing strategy in the network can not only provide efficient guidance information for travelers, but also lead to the potential utilization optimization of existing resources and infrastructure. This might involve in selecting favorite transfer schemes (or paths) before the departure or en route when onersquo;s origin and destination locate on different metro lines.
A survey in Shanghai city shows that, about fifty percent of travel time is usually occupied by the transfer process when one travels in the metro system1. Also in Beijing metro network, more than forty percent of passengers need to experience the transfer activities during their trips, in which most transfer processes are fairly complicated due to the complex infrastructure of transfer stations and large passenger flows (there are more than ten million passengers in the metro system on each weekday)(Wang, 2014)2. Consequently, more than ten transfer stations have to provide services for daily passenger volume over 120 thousand where most transfer activities occur during the peak hours3. Due to the importance of transfer activity in path finding, how to choose favorite and robust transfer strategies in the current situations turns out to be a theoretically significant issue for the real-world applications of traffic participants.
In the literature, the path finding in a network always focuses on producing the least travel time route. However, note that the involved travel time not only includes the travel time in a train, but also consists of passengerrsquo;s walking time and waiting time at platforms incurred by transfer activities from one metro line to another. Thus, the travel time in a large-scale metro network is inevitably associated with stochastic features due to the disturbances of passenger flows, layout of transfer stations, train delay propagation and other indeterminate factors. Combining with these uncertain information, we intend to generate the robust transfer scheme through a two-stage decision making process, in which both a priori optimization and adaptive decision are integrated in the solution framework. This research will explicitly address the above mentioned problems.
1.2. Literature review
Finding the best transfer scheme in a metro network, which is a common behavior when passengers take the sub-way system or pre-plan their trips, can be included in the framework of stochastic shortest path problems. Generally, the classical shortest path problem often adopts deterministic arc lengths or arc travel times to represent network characteristics. A 0-1 integer programming model, which is efficiently solved by the label setting/correcting algorithms proposed by Bellman (1958), Dijkstra (1959), Dreyfus (1969), can be used to formulate the shortest path choice process. Note that, however, the link travel time in real-world transportation networks is often stochastic and uncertain. To handle this problem within uncertain decision environments, a variety of modelling methods and solution algorithms have been proposed by many researchers in the literature based on the sto
全文共30863字，剩余内容已隐藏，支付完成后下载完整资料
资料编号：[16439]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
