زمان بندي خطوط ريلي و ظرفيت ايستگاه‌ها در شبكه‌هاي چندخطه با ارايه‌ي حدود بالاي ابتكاري

Train Timetabling on Multiple Track and Station Capacity Railway with Enhanced Upper Bound Heuristic Method

يكي از مهم ترين و ارزان‌ترين منابع حمل و نقل مسافر و بار «خطوط ريلي» است. مسيله‌ي زمان بندي خطوط ريلي به‌عنوان يكي از ابزارهاي افزايش بهره وري مطرح است. هدف اين مسيله استفاده‌ي بيشينه از منابع موجود، مانند لوكوموتيوها، خطوط ريلي و كاركنان است كه مي توان با استفاده از يك زمان بندي دقيق و بهينه به اين مهم دست يافت. در اين مطالعه يك مدل برنامه ريزي رياضي براي زمان بندي خطوط چندخطه ارايه شده است. تابع هدف مورد بررسي كمينه‌كردن مجموع زمان هاي سفر است. با توجه به اين كه مسيله‌ي فوق به‌لحاظ پيچيدگي NP-Hard است، براي حل مسيله چند حد بالا با استفاده از روش هاي ابتكاري نيز به دست آمده است. در نهايت با ارايه‌ي مثالي از دنياي واقعي، كارايي مدل و حدود بالا سنجيده شده و پيشنهاداتي نيز براي توسعه ي مطالعه ارايه شده است.

Railway is one the most fast and economical way of transportation. Construction of the new infrastructures is very expensive and also time consuming. So optimization of the railway network has an important role in the railway management which is divided to some major parts such as line planning, timetabling, crew scheduling and maintenance scheduling. Train scheduling is a significant issue in the railway industry in recent years because it has an important role in railway infrastructure. In this paper, the timetabling problem of a multiple tracked railway network is discussed. All of the parameters and decision variables are deterministic and static and there is no any uncerternity in the problem. More specifically, a general model with specific attention to “Tehran Metro” is presented here in which a set of operational and safety requirements are also considered. Transfer time between stations and dwell time related constraints imbedded in the model. In addition the model handles the trains overtaking in a station and innovatively considers the capacity of stations and shunt sidings. An objective function is to minimize the total travel time. It has been proved that the problem is NP-hard so the real size problem cannot be solved in acceptable amount of time. In order to reduce the processing time of the problem, first, we represent some heuristic rules to reduce the number of binary variables. These rules are based on parameters such as transfer time between two points, dwell time and safety time of stations. Furthermore, the logical conditions in the problem cause that the impracticable area from solution space is removed. These rules also allow us to reduce the memory and time considerably in compare to the original problem. Comprehensive numerical experiments with different number of trains, stations and capacities are reported to show the performance of the model and its proposed rules. The result shows that the computational time is considerably reduced and the global optimum of the optimization problem is achieved by using the heuristic rules.