A Train Dispatching Model Under a Stochastic Environment: Stable Train Routing Constraints and Reformulation

Lingyun Meng, Xiaojie Luan, Xuesong Zhou

Research output: Contribution to journalArticlepeer-review

18 Scopus citations


After major capacity breakdown(s) on a railway network, train dispatchers need to generate appropriate dispatching plans to recover the impacted train schedule from perturbations and minimize the expected total train delay time under stochastic scenarios. In this paper, we propose a cumulative flow variables-based integer programming model for dispatching trains under a stochastic environment on a general railway network. Stable Train Routing (STR) constraints are introduced to ensure that trains traverse on the same route across different capacity breakdown scenarios, which are further reformulated to equivalent linear inequality constraints. Track occupancy and safety headways are modelled as side constraints which are dualized through a proposed Lagrangian relaxation solution framework. The original complex train dispatching problem is then decomposed to a set of single-train and single-scenario optimization subproblems. For each subproblem, a standard label correcting algorithm is embedded for finding the time dependent least cost path on a space-time network. The resulting dual solutions can be transformed to feasible solutions through priority rules. Numerical experiments are conducted to demonstrate the efficiency and effectiveness of the proposed solution approach.

Original languageEnglish (US)
Pages (from-to)791-820
Number of pages30
JournalNetworks and Spatial Economics
Issue number3
StatePublished - Sep 1 2016


  • Lagrangian relaxation
  • Robust solution
  • Stable Train Routing (STR)
  • Train dispatching

ASJC Scopus subject areas

  • Software
  • Computer Networks and Communications
  • Artificial Intelligence


Dive into the research topics of 'A Train Dispatching Model Under a Stochastic Environment: Stable Train Routing Constraints and Reformulation'. Together they form a unique fingerprint.

Cite this