A mixed integer linear programming model with heuristic improvements for single-track railway rescheduling problem
Yükleniyor...
Dosyalar
Tarih
2023
Yazarlar
Dergi Başlığı
Dergi ISSN
Cilt Başlığı
Yayıncı
MDPI
Erişim Hakkı
Attribution-NonCommercial-NoDerivs 3.0 United States
info:eu-repo/semantics/openAccess
info:eu-repo/semantics/openAccess
Özet
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.
Açıklama
Anahtar Kelimeler
Integer Programming, Optimization, Rail Transport, Speed-up Heuristics, Train Rescheduling, Train Scheduling, Transportation
Kaynak
Applied Sciences (Switzerland)
WoS Q Değeri
Q1
Scopus Q Değeri
Q1
Cilt
13
Sayı
2
