کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
482310 1446187 2007 15 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
A branch and bound algorithm for scheduling trains in a railway network
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر علوم کامپیوتر (عمومی)
پیش نمایش صفحه اول مقاله
A branch and bound algorithm for scheduling trains in a railway network
چکیده انگلیسی

The paper studies a train scheduling problem faced by railway infrastructure managers during real-time traffic control. When train operations are perturbed, a new conflict-free timetable of feasible arrival and departure times needs to be re-computed, such that the deviation from the original one is minimized. The problem can be viewed as a huge job shop scheduling problem with no-store constraints. We make use of a careful estimation of time separation among trains, and model the scheduling problem with an alternative graph formulation. We develop a branch and bound algorithm which includes implication rules enabling to speed up the computation. An experimental study, based on a bottleneck area of the Dutch rail network, shows that a truncated version of the algorithm provides proven optimal or near optimal solutions within short time limits.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: European Journal of Operational Research - Volume 183, Issue 2, 1 December 2007, Pages 643–657
نویسندگان
, , ,