A Mixed Integer Linear Programming Model with Heuristic Improvements for Single-Track Railway Rescheduling Problem


Creative Commons License

Aydın G., ŞAHİN İ.

Applied Sciences (Switzerland), vol.13, no.2, 2023 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 13 Issue: 2
  • Publication Date: 2023
  • Doi Number: 10.3390/app13020696
  • Journal Name: Applied Sciences (Switzerland)
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Aerospace Database, Agricultural & Environmental Science Database, Applied Science & Technology Source, Communication Abstracts, INSPEC, Metadex, Directory of Open Access Journals, Civil Engineering Abstracts
  • Keywords: transportation, rail transport, train scheduling, train rescheduling, optimization, integer programming, speed-up heuristics
  • Yıldız Technical University Affiliated: No

Abstract

© 2023 by the authors.A rescheduling algorithm for trains on a single-track railway was developed in case of disturbances that would cause conflicts between trains. This algorithm is based on mixed integer linear programming (MILP) with speed-up routines. The model considers station capacities explicitly (i.e., the number of available tracks for meeting and overtaking operations). Because the model is too hard for the solvers (CPLEX in this study) to tackle, three speed-up routines were devised when rescheduling trains. These routines are a greedy heuristic to reduce the solution space, using the lazy constraint attribute of the solver and a multiobjective approach to find a good initial feasible solution that conforms to actual railway operation. The algorithm was tested on a hypothetical rail line for different sizes of timetable instances with disturbed trains in a maximum two-hour time horizon. It managed to solve the hardest instances within a three-minute time limit thus minimizing the total weighted delay of rescheduled trains. The optimality gap metric is used to show the effectiveness and efficiencies of the speed-up heuristics developed.