### Abstract

This paper focuses on the development of new algorithms for the real-time train scheduling and routing problem in a complex and busy railway network. Since this is a strongly NP-hard problem and practical size instances are complex, simple heuristics are typically adopted in practice to compute feasible but low quality schedules in a short computation time. In order to compute good quality solutions, we consider a mixed-integer linear programming formulation of the problem and solve it with a commercial solver. However, the resolution of this formulation by a commercial solver often takes a too long computation time. Therefore, a new methodology based on the relaxation of some train routing constraints in the formulation is proposed for the quick computation of a good quality lower bound. The lower bound solution is then transformed via a constructive metaheuristic into a feasible schedule, representing a good quality upper bound to the problem. Computational experiments are performed on several disturbed traffic situations for two practical case studies from the Dutch and British railways. The results show that the new lower and upper bounds are computed in a few seconds and are often of similar quality to the ones computed by the commercial solver in hours of computation.

Original language | English |
---|---|

Title of host publication | IFAC-PapersOnLine - 14th IFAC Symposium on Control in Transportation Systems (CTS 2016) |

Editors | Tankut Acarman |

Publisher | Elsevier |

Pages | 215-220 |

DOIs | |

Publication status | Published - 2016 |

Event | 14th IFAC Symposium on Control in Transportation Systems - ITU Faculty of Architecture, Istanbul, Turkey Duration: 18 May 2016 → 20 May 2016 http://www.cts2016.org/en/ |

### Publication series

Name | IFAC-PapersOnLine |
---|---|

Number | 3 |

Volume | 49 |

ISSN (Print) | 2405-8963 |

### Conference

Conference | 14th IFAC Symposium on Control in Transportation Systems |
---|---|

Abbreviated title | CTS 2016 |

Country | Turkey |

City | Istanbul |

Period | 18/05/16 → 20/05/16 |

Internet address |

### Keywords

- Disjunctive Programming
- Metaheuristics
- Real-Time Railway Traffic Management

## Fingerprint Dive into the research topics of 'Lower and upper bound algorithms for the real-time train scheduling and routing problem in a railway network'. Together they form a unique fingerprint.

## Cite this

*IFAC-PapersOnLine - 14th IFAC Symposium on Control in Transportation Systems (CTS 2016)*(pp. 215-220). (IFAC-PapersOnLine; Vol. 49, No. 3). Elsevier. https://doi.org/10.1016/j.ifacol.2016.07.036