کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
7534859 | 1488268 | 2017 | 8 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
A MILP-based heuristic for a commercial train timetabling problem
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
علوم انسانی و اجتماعی
علوم اجتماعی
تحقیقات ایمنی
پیش نمایش صفحه اول مقاله

چکیده انگلیسی
Using mathematical methods to support the yearly timetable planning process has many advantages. Unfortunately, the train timetabling problem for large geographical areas and many trains is intractable for optimization models alone. In this paper, we therefore present a MILP-based heuristic that has been designed to generate good-enough timetables for large geographical areas and many trains. In the incremental fix and release heuristic (IFRH), trains are added to the timetable in batches. For each batch of trains, a reduced timetable problem is solved using a mathematical integer program and CPLEX. Based on the solution, the binary variables defining meeting locations and stops are fixed, and the next batch of trains is added to the timetable. If previously fixed variables make the problem infeasible, a recovery algorithm iteratively releases fixed variables to regain feasibility. The paper also introduces a simple improvement heuristic (IH) that uses the same idea of working with batches of trains. The heuristics are tested on a real case-study from Sweden consisting of both small problem instances (approximately 300 trains and 1400 possible interactions) and large problem instances (approximately 600 trains and 5500 possible interactions). IFRH returns a feasible timetable within 30 minutes for all problem instances, and after running IH the optimality gaps are less than 5%. Meanwhile, if CPLEX is used without the heuristic framework to solve the total optimization problem, a feasible timetable is not returned within 2 hours for the large problem instances.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Transportation Research Procedia - Volume 27, 2017, Pages 569-576
Journal: Transportation Research Procedia - Volume 27, 2017, Pages 569-576
نویسندگان
Sara Gestrelius, Martin Aronsson, Anders Peterson,