Two-stage Optimization Model For The Metro Transfer Problem Under Stochastic Environment

Public transportation is an important part for maintaining normal operations of the urban transportation system, and it is an important guarantee for the cities’sustainable development. In many developed cities, as a main carrier of daily public travel, the subway is undertaking more and more passenger transport task. With the rapid expansion and development of the city, the scale of the metro network is also increasing to meet the growing traffic demand. Travelers have more alternative transfer schemes during their travels as the increase of network lines and the number of transfer stations, as well as the complexity of the network structure. In order to save the travel time and improve the travel efficiency, how to choose the robust and fast transfer scheme before the trip has become an important issue.Focused on the transfer problem in metro networks, this paper investigates how to obtain the robust transfer schemes that would save travel time in static and dynamic stochastic environments respectively. Specifically, using sample-based link travel times to capture the uncertainty of the realistic network, a two-stage integer programming model related to the metro transfer problems is formulated under static and dynamic stochastic environments respectively, with the minimized expected travel time and penalty value. In the practical application, the robust transfer scheme will be used as the decision guidance before the trip, and the specific travel path will be selected by the travelers according to the current network conditions. Finally, an efficient hybrid algorithm, in which the label correcting algorithm is embedded into a branch and bound searching framework, is presented to find the approximate optimal solution of the proposed model. Then, the numerical experiments with the Beijing metro network as the background are designed, which demonstrate the effectiveness of the proposed model and algorithm. This paper mainly includes the following research contents:(1) The two-stage model of metro transfer problems in static stochastic environmentAnalyzing the uncertainty of the link travel time and transfer time during the metro trips, we use the sample-based stochastic data to capture the randomness of the link travel time and transfer time. Two networks, the transfer activity network and the practical network are corresponding to the two stages of the model, respectively. The first stage aims to find a sequence of transfer stations which can compose a feasible path from origins and destinations in the transfer activity network; and the second stage provides the scenario-based least time paths passing by the generated transfer stations in the first stage for evaluating the given transfer schemes. Finally, a two-stage optimization model related to the best transfer nodes selection problem is formulated under static stochastic environment, with the minimized expected travel time and penalty value. And the complexity of this model is analyzed in detail.(2) Metro transfer problem modeling in dynamic random environmentsIn order to describe the dynamic property of the metro transfer problem, we further treat the link travel time and transfer time of different scenarios as time-variant discrete random variables, and analyze how the network dynamics influence the travel time by using the space-time network. Using the two-stage decision-making process, with the objective of minimizing the expected travel time and transfer penalty, the transfer schemes are evaluated with the use of the scenario-based shortest path information. At last, a two-stage model of the metro transfer problems under dynamic stochastic environment is established.(3) Heuristic algorithm combining the branch and bound algorithm and the label correcting algorithmIn view of the complexity of the proposed model, a hybrid algorithm in which the label correcting algorithm is embedded into a branch and bound searching framework is presented. The label correcting algorithm, which can generate the scenario-based shortest path, is used to achieve the branching process of the searching tree, narrow the searching range, and find the feasible transfer node sequences. At the same time, the global upper bound and lower bound of the searching tree is updating continuously by figuring out the objective value, until the approximate optimal solution is found. In addition, this paper describes the branch and bound process and the cutting process in detail, and so does the algorithm flow.(4) Algorithm validation and experiments analysisA small scale network case is designed to explain the process of the algorithm. Taking Beijing metro network as the background of the large-scale network example, to demonstrate the effectiveness of the model and the algorithm, different numerical experiments are designed to analyze the solving speed, the solution quality and the robustness of the algorithm.