地铁网络中最优的传输方案

地铁网络中最优的传输方案(中文7000字,英文4000字)
摘要
本研究旨在找出地铁网络中最优的传输方案。摘要利用基于样本的不变线路运行时间来获取真实网络的不确定性，建立了一个具有最小期望运行时间和传输活动代价的两阶段随机整数规划模型。第一阶段的目标是找到一个序列的潜在转移节点(站),可以组成一个从起源到目的地转移活动网络的可行的路径,第二阶段提供的时间最少路径所生成的转运站，再结合第一阶段评估给定的传输方案,然后输出最佳的路线信息。为了解决我们提出的模型，提出了一种有效的混合算法，该算法将标签校正算法嵌入到分支和绑定搜索框架中，从而找到所考虑问题的最优解。最后，对不同尺度的地铁网络进行了数值实验。计算结果表明，即使是在北京地铁的大型网络中，所提出的方法也是有效的。
 
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.