An adaptive neighborhood search metaheuristic for the integrated railway rapid transit network design and line planning problem. (February 2017)

• Record Type: Journal Article
• Authors: Canca, David; De-Los-Santos, Alicia; Laporte, Gilbert; Mesa, Juan A.
• Is Part Of: Computers & operations research. Volume 78(2017)
• Page Start: 1
• Page End: 14
• Publication Date: 2017-02
• Subjects: Railway rapid transit -- Network design -- Line planning -- Adaptive large neighborhood search; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2016.08.008
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: We model and solve the Railway Rapid Transit Network Design and Line Planning (RRTNDLP) problem, which integrates the two first stages in the Railway Planning Process. The model incorporates costs relative to the network construction, fleet acquisition, train operation, rolling stock and personnel management. This implies decisions on line frequencies and train capacities since some costs depend on line operation. We assume the existence of an alternative transportation system (e.g. private car, bus, bicycle) competing with the railway system for each origin–destination pair. Passengers choose their transportation mode according to the best travel times. Since the problem is computationally intractable for realistic size instances, we develop an Adaptive Large Neighborhood Search (ALNS) algorithm, which can simultaneously handle the network design and line planning problems considering also rolling stock and personnel planning aspects. The ALNS performance is compared with state-of-the-art commercial solvers on a small-size artificial instance. In a second stream of experiments, the ALNS is used to design a railway rapid transit network in the city of Seville. Abstract : Highlights: We model and solve the Railway Rapid Transit Network Design and Line Planning (RRTNDLP) problem. We take into account costs relative to the network construction, fleet acquisition, operation, rolling stock and personnel. We assume the existence of an alternative transport mode competing with the railway for each origin-destination pair. We develop an Adaptive Large Neighborhood Search algorithm, which simultaneously solve the network design and line planning problems. The ALNS performance is compared with state-of-the-art commercial solvers. We apply the ALNS to areal-size instance concerning the design of a railway rapid transit network in the city of Seville.