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

Luis Cadarso, Laureano F. Escudero and Angel Marín

European Journal of Operational Research, 2018, vol. 271, issue 2, 577-593

Abstract: 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.

Keywords: Transportation; Rapid Transit Network Design planning; multistage multi-horizon scenario trees; Pure 0–1 models; Matheuristic algorithms (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0377221718304521
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:ejores:v:271:y:2018:i:2:p:577-593

DOI: 10.1016/j.ejor.2018.05.041

Access Statistics for this article

European Journal of Operational Research is currently edited by Roman Slowinski, Jesus Artalejo, Jean-Charles. Billaut, Robert Dyson and Lorenzo Peccati

More articles in European Journal of Operational Research from Elsevier
Bibliographic data for series maintained by Catherine Liu ().