دانلود رایگان مقاله مروری بر مدل ها و الگوریتم های آنلاین پویا برای مدیریت ترافیک

چکیده

      جداول زمانی راه‌آهن برای انجام عملیات قوی و انعطاف‌پذیر و با تأخیر کم توسعه‌یافته‌اند. به هر حال، تغییرات برنامه‌های روزانه موجب رخداد اختلالاتی در جداول زمانی می‌گردد و برنامه‌ریزان، تلاش می‌کنند تا جداول زمانی را تا حد امکان، شدنی نگه داشته و از انتشار تأخیر  جلوگیری کنند. هدف روش‌های زمان‌بندی مجدد، به‌روز کردن جداول زمانی در حالت آفلاین و به بهترین شکل ممکن می‌باشد. ما مروری را بر روی روش‌های اخیر در زمینه مسائل زمان‌بندی مجدد ترافیک راه‌آهن به صورت آنلاین انجام داده‌ایم که بر جنبه‌های پویا و تصادفی (یا حداقل نه کاملاً قطعی) دلالت دارند. در حقیقت، اگر چه زمان‌بندی ایستای آنلاین، منجر به درجه بالایی از انتشار تأخیر می‌گردد، اما هنوز با توجه به طبیعت احتمالی مشکلات حاصل از مسائل زمان‌بندی مجدد و توانایی آن در محاسبه عدم قطعیت در برنامه‌های آتی مورد استفاده قرار می‌گیرد. در نهایت چالش‌های مطرح برای تحقیقات آتی بیان می‌گردند.

1. مقدمه

       تهیه خدمات به موقع و قابل‌اعتماد، هدف اصلی صنایع ریلی به منظور حفظ و بهبود مزیت رقابتی در این صنعت است که به سرعت در حال رشد است. جداول زمانی قطارها به عنوان برنامه‌های تاکتیکی، برنامه‌ریزی‌شده و سالانه یا در هر فصل (آفلاین) به‌روز می‌شوند تا مسیرها و زمان‌بندی قطارها را تعیین کنند. در عملیات روزانه قطارها، منابع مختلفی از آشفتگی وجود دارد که ممکن است همانند حوادث مختلف تصادف و غیره بر روی زمان‌های حرکت قطارها تأثیر گذارد و موجب تأخیر اولیه در برنامه زمانی قطارها باشند. به دلیل وابستگی متقابل بین قطارها، تأخیر اولیه می‌تواند انتشاریافته و موجب تأخیر در سایر قطارها بر روی شبکه حرکت قطارها گردد.

        غالباً انتظار می رود که یک جدول زمانی باید قادر به تحمل اختلالات جزئی در زمان واقعی باشد: این مورد اعتبار و صحت نامیده می‌شود که به اختلالات ایجادشده در شبکه ترافیک راه‌آهن حساس است (مانند برخی از بخش‌های جدول زمانی که تحت تأثیر توزیع انتشار تأخیر قرار می‌گیرند) ([24] را ببینید). مطالعات بسیاری برای ساختن جداول زمانی قوی  انجام‌شده‌اند. به طور مثال، Carey [10]، Carey and Kwiecinski [11]، Goverde [34]، Khan and Zhou [49] و Vromans et al. [75]. به هر حال، هیچ برنامه آفلاینی نمی‌تواند به حد کافی در برابر آشفتگی و بی‌برنامگی‌های ایجادشده قوی باشد (مثل اختلالات عمده‌ای که موجب انسداد یک راه می‌گردند) و بهره‌وری ترافیک راه‌آهن را به خطر نیندازد (Kauppi et al. [47]، Zaroliagis et al. [82]). روش‌های مدیریت ترافیک آنلاین، برنامه‌هایی را برای تغییر وضعیت ترافیک در شرایط رخداد ترافیک و یا خرابی و انتشار تأخیر دارند.

         کنترل ترافیک راه‌آهن، یک مسئله تنظیم جداول زمانی قطارها مطابق با شرایط زمان واقعی است تا تأثیرات منفی رخدادهای غیرمنتظره کاهش یابد. این مسئله به صورت مسئله توزیع امکانات  راه‌آهن یا قطارها و یا کنترل ترافیک راه‌آهن تعریف می‏گردد. فرآیند تنظیم نقشه برای شرایط واقعی پیچیده است (Informs-RAS را ببینید [42] ONTIME [65] و Schaafsma and Bartholomeus [70]).

        روش‌های آنلاین دارای محاسبات زمانی کوتاه (در حد چند ثانیه یا چند دقیقه) هستند و به داده‌های زمان واقعی و آدرس‌دهی توابع هدف خاصی برای بازیابی مسیر اولیه نیاز دارند. روش‌های آنلاین می‌توانند ایستا باشند، اگر فقط یک بار و با تمام اطلاعات اجرا گردند و یا می‌توانند پویا باشند، اگر اطلاعات در طی زمان تغییر یابند. تعامل بین عملیات، کنترل و عملیات مجدد به زمان زیادی نیاز دارد. به عنوان مثال، تنها اتفاقات آتی را می‌توان کنترل کرد. این تمایز منجر به ایجاد دو روش کنترل حلقه باز و حلقه بسته می‌گردند. جزئیات بیشتر را در ادامه ببینید.

       علاوه بر این، ما می‌توانیم بین روش‌های reactive که از تصمیمات آتی غفلت می‌کنند و روش‌های proactive تمایز قائل شویم. مورد دوم، آشفتگی و وضعیت آتی شبکه را بررسی کرده و شبکه را به صورتی احتمالی و وابسته به زمان در نظر می‌گیرد. بنابراین، احتمال زمان انتظار حوادث آتی (مانند ورود به ایستگاه) در طول زمان تغییر می‌یابد. فرآیند کنترلِ زمانی به منظور کاهش زمان تصمیم‌گیری به کار می رود.

       زمان‌بندی مجدد قطار، درواقع همان به‌روزرسانی جداول زمانی است (انتشار برنامه‌ای برای خروج قطار، زمان عبور و زمان رسیدن قطار و همچنین مسیر قطار در شبکه راه‌آهن) که باید مکان جاری و سرعت قطار و تأخیر آن را به عنوان محدودیتی در نظر بگیرد. گردش قطارها باید با ارائه روشی برای حرکت شدنی قطارها در شبکه راه‌آهن با اندازه‌گیری موقعیت و سرعت و امنیت و پویایی انجام گیرد. مسئله، زمانی مشکل می‌گردد که هیچ دو قطاری نمی‌توانند به دلیل محدودیت ظرفیت زیرساخت به صورت همزمان بر روی یک ریل و یا در یک ایستگاه باشند. نظریه مسدود کردن زمان (به [37] مراجعه کنید)، برای بررسی امنیت حرکت قطارها در سطح میکروسکوپ (به صورت کاملاً جزئی) مورد استفاده قرار می‌گیرد. با توجه به سطح جزئیات مورد نیاز، روش‌های بهینه‌سازی غالباً قادر به مدیریت افق زمانی کوتاه (معمولاً در حدود یک ساعت و نه بیشتر از آن) و مکان کوچکی (معمولاً دو حدود 50 کیلومتر و نه بیشتر از آن) هستند.

       این مقاله روش‌های پویای آنلاین را برای زمان‌بندی مجدد ترافیک راه‌آهن مرور می‌کند. در واقع با وجود اینکه، کنترل شبکه راه‌آهن فرآیندی تصادفی و عدم قطعی است، عمدتاً مورد غفلت قرار گرفت‎اند. این موارد موجب ایجاد انگیزه برای بررسی و تمرکز بر روی این موضوع گردید. ما بررسی‌های اخیر [15] و [31] و تحقیقات اخیر شامل [14]، [15]، [57]، [63]، [71] را با جزئیات مورد بررسی قراردادیم.

        ادامه مقاله به این صورت سازمان‌دهی شده است. ما ابتدا روش‌های موجود را بر اساس تنظیمات کنترلی، زمان  پویا، مدل ریاضی و جزئیات مورد بررسی قراردادیم. سپس ارتباط مسائل را با سایر مسائل موجود بررسی کرده و در انتها به نتیجه‌گیری پرداخته‌ایم.

Abstract

        Railway timetables are developed to make operations robust and resilient to small delays. However, disturbances perturb the daily plan, and dispatchers adjust the plan to keep operations feasible and to limit delay propagation. Rescheduling approaches aim at updating the offline timetable at best, in the presence of delays. We present a survey of the recent approaches on online railway traffic rescheduling problems, which exhibit dynamic and stochastic (or, at least, not completely deterministic) aspects. In fact, while online static rescheduling has reached a wide degree of dissemination, much is still to be done with regard to the probabilistic nature of the railway traffic rescheduling problems, and also how to best take uncertainty into account for future states. Open challenges for the future research are finally outlined.

I. INTRODUCTION

       PROVIDING punctual and reliable services is a main goal of rail industries in order to maintain and further improve their competitive advantages in the rapidly changing multimodal transportation market. Train timetables as tactical plans are programmed and updated every year or every season (offline) to define routes and schedules of trains. In daily train operations, various sources of perturbations may influence train running times, as well as dwell and departing events, thus causing primary delays to the planned train schedule. Due to the high interdependency between trains, primary delays could propagate as secondary delays to other trains on a network.

        It has been widely recognized that a timetable should be able to handle minor disturbances that occur in real time: this is called robustness, which is also viewed as the sensitivity to disturbances with stochastic variables (e.g., some segment running times follow some distribution) in a macroscopic level (see [24]). A great number of studies have been devoted to building robust timetables, by, e.g., Carey [10], Carey and Kwiecinski [11], Goverde [34], Khan and Zhou [49], and Vromans et al. [75]. However, no offline plans can be made robust enough against all kind of perturbations (e.g., major disruptions due to track blockage) without compromising strongly its efficiency (Kauppi et al. [47], Zaroliagis et al. [82]). To this end, online railway traffic rescheduling approaches have been defined that adjust plans to the actual ever-changing situation of delayed traffic.

        Railway traffic control is the problem of adjusting train timetables according to real-time conditions, to minimize the negative effects of unexpected events. This problem has also been called the Train or Railway Dispatching Problem, Railway Dynamic Traffic Management, Railway Traffic Control. The process of adjusting the plan to the actual situation is complex and offers rich opportunities of improvement (see Informs-RAS [42] ONTIME [65], and Schaafsma and Bartholomeus [70]).

       Online approaches are characterized by short computational time (few seconds up to few minutes), need for real-time data, and addressing specific objective functions aiming at recovering the original plan. The online approaches can be static if they are performed only once, with full information, or dynamic if the information they are able to use changes over time. The interaction between operations, control, and operations again is clearly happening along a time dimension, i.e., only future actions can be controlled. This distinction coincides with the difference between open-loop control and closed-loop control. More details follow.

       Moreover, we can distinguish between reactive approaches, which neglect a view of the future when taking decisions and proactive approaches. The latter considers the perturbations and the prognosis of future statuses of the network, which is known in a probabilistic and time-dependent manner. Thus, probabilities of the expected time of future events (such as an arrival at the station) would change over time and will be known with full precision only when the event actually occurs. The time resolution of the control process considered here relates to an extent in the order of magnitude of hours and involving a set of multiple trains.

        The train path rescheduling is the process of updating the timetable (the published plan of train departures, passing times and train arrivals, and routes over rail network), by taking into account the current position and speed of trains, and their delays. The circulation of trains is represented, so that feasible train movements are computed, complying with the measured position and speed, train dynamics, and safety system. In particular, the crucial problem is that no two trains can be at the same time on the same block section, due to the limited capacity of the infrastructure. The blocking time theory (see, e.g., [37]) is to be used to check the safety of train movements, at the microscopic level of switches, tracks, and individual infrastructure elements. Due to the microscopic level required, optimization approaches are generally able to manage only relatively small time horizon (usually no more than 1 h) and areas (usually no more than a single dispatching area of 50 km).

        This paper reviews online dynamic approaches for a railway traffic rescheduling problem. In fact, despite control of a railway network is a phenomenon that is triggered by external random processes, the uncertainty is mostly neglected in current schemes. This motivates this review and its specific focus. We refer to the recent reviews [15], [31], and [63], and the recent research works [14], [15], [57], [63], [71] for more details and a larger scope.

       The rest of this paper proceeds as follows. We first analyze and cluster literature based on control setup, time dynamics, mathematical model, and details, and then, we draw connections with other railway problems and finally conclude the review.

چکیده

1. مقدمه

2. تنظیمات کنترلی

A. اندازه‌گیری داده

B. عملیات کنترل

C. روش‌های حلقه باز

D. روش‌های حلقه بسته

3. پیش‌بینی پویا

A. دانش کاملی از آینده

B. به‌روزرسانی اطلاعات به صورت مداوم

C. به‌روزرسانی اطلاعات گسسته

D. نبود اطلاعات در مورد آینده

4. مدل‌سازی ریاضی

A. مدل‌سازی زمان و ظرفیت

B. اهداف

C. درجه اکتشافی بودن

D. جزئیات و طرح زیرساخت

5. ارتباط با مسائل دیگر راه‌آهن

A. زمان‌بندی Crew

B. زمان‌بندی Rolling Stock

C. مدیریت تأخیر

D. بحث

6. نتیجه‌گیری

منابع

Abstract

1. INTRODUCTION

2. CONTROL SETUP

A. Measured Data

B. Control Actions

C. Open-Loop Approaches

D. Closed-Loop Approaches

3. DYNAMICS OF FORECASTS

A. Complete Knowledge of the Future

B. Continuous Information Updates

C. Discrete Information Updates

D. No Knowledge of the Future

4. MATHEMATICAL MODELS

A. Modeling Time and Capacity

B. Objective

C. Degree of Stochasticity

D. Level of Detail and Layout of Infrastructure

5. INTERRELATION WITH OTHER RAILWAY PROBLEMS

A. Crew Scheduling

B. Rolling Stock Scheduling

C. Delay Management

D. Discussion

6. CONCLUSION

REFERENCES