An adaptive neighborhood search metaheuristic for the integrated railway rapid transit network design and line planning problem

David Canca, Alicia De-Los-Santos, Gilbert Laporte, Juan A. Mesa

Research output: Contribution to journalArticle

36 Citations (Scopus)

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.

Original languageEnglish
Pages (from-to)1-14
Number of pages14
JournalComputers and Operations Research
Volume78
DOIs
Publication statusPublished - 1 Feb 2017

Keywords

  • Adaptive large neighborhood search
  • Line planning
  • Network design
  • Railway rapid transit

ASJC Scopus subject areas

  • Computer Science(all)
  • Modelling and Simulation
  • Management Science and Operations Research

Cite this