On strategic multistage operational two-stage stochastic 0–1 optimization for the Rapid Transit Network Design problem

The Rapid Transit Network Design planning problem along a time horizon is treated by considering uncertainty in passenger demand, strategic costs and network disruption. The problem has strategic decisions about the timing to construct stations and edges, and operational decisions on the available network at the periods. The uncertainty in the strategic side is represented in a multistage scenario tree, while the uncertainty in the operational side is represented in two-stage scenario trees which are rooted with strategic nodes. The 0–1 deterministic equivalent model can have very large dimensions. So-called fix-and-relax and lazy matheuristic algorithms, which are based on special features of the problem, are proposed, jointly with dynamic scenario aggregation/de-aggregation schemes. A broad computational experience is presented by considering a network case study taken from the literature, where the problem was only treated as a deterministic 0–1 model. 40 nodes in the strategic multistage tree are considered for passenger demand and investment cost and 8 uncertainties are considered for network disruption in each strategic node, in total 320 uncertain situations are jointly considered. For assessing the validity of the proposal, a computational comparison is performed between the plain use of a state-of-the-art optimization solver and the proposals made in this work. The model is so-large (2.6M constraints and 1.6M binary variables) that the solver alone cannot provide a solution in an affordable time. However, a mixture of the both matheuristics provides a solution with a good optimality gap requiring an affordable elapsed time.