Abstract
In this paper we study the design and optimization of train timetabling adapted to a dynamic demand environment. This problem arises in rapid train services which are common in most important cities. We present three formulations for the problem, with the aim of minimizing passenger average waiting time. The most intuitive model would consider binary variables representing train departure times but it yields to non-linear objective function. Instead, we introduce flow variables, which allow a linear representation of the objective function. We provide incremental improvements on these formulations, which allows us to evaluate and compare the benefits and disadvantages of each modification. We present a branch-and-cut algorithm applicable to all formulations. Through extensive computational experiments on several instances derived from real data provided by the Madrid Metropolitan Railway, we show the advantages of designing a timetable adapted to the demand pattern, as opposed to a regular timetable. We also perform an extensive computational comparison of all linear formulations in terms of size, solution quality and running time
چکیده
در این تحقیق ما طراحی و بهینه سازی تنظیم جدول زمانی آموزش را مطابق با محیط تقاضای دینامیک مورد مطالعه قرار میدهیم. این مسئله بیشتر در خدمات آموزش سریع شهرهای بزرگ نمود پیدا میکند. ما از سه فرمولاسیون با هدف مینیمم سازی میانگین زمان انتظار مسافر در مسئله استفاده کردیم. مدلی که در این تحقیق به کار گرفته شد یک مدل شهودی است که متغیرهای دودویی را برای نشان دادن زمان حرکت قطار در نظر میگیرد اما با توجه به نتایج به دست آمده مدل فوق به نظر میرسد یک تابع هدف غیرخطی باشد. متغیرهای جریانی که در این تحقیق مورد استفاده قرار گرفتند امکان نمایش خطی تابع هدف را فراهم میآورند. بهبودهای نهایی بر روی سه فرمولاسیون انجام شدند، درنتیجه میتوان به راحتی مزیت و معایب هر کدام از اصلاحات را ارزیابی کرد و آنها را مورد مقایسه قرار داد. در تمامی فرمولاسیونها از الگوریتم برش/ انشعاب استفاده گردید. اگرچه آزمایشات محاسباتی گسترده بر روی نمونه های به دست آمده از دادههای واقعی انجام شد( تهیه شده به وسیله دفتر راه آهن شهر مادرید )، ولی برخلاف یک جدول زمانی منظم، ما توانستیم مزیتهای مربوط به طراحی جدول زمانی را مطابق با الگوی تقاضا انجام دهیم. علاوه بر آن، یک مقایسه محاسباتی گسترده بر روی تمامی فرمولاسیونهای خطی و بر حسب اندازه، کیفیت راه حل و زمان راه اندازی انجام گردید.
1-مقدمه
فرایند برنامه ریزی خطوط مسافربری ریلی یک فعالیت پیچیده است که معمولا به مراحل مختلفی مانند طراحی شبکه، طراحی خطوط، برنامه زمان بندی، جدول زمانی، ترنهای روی خط آهن و برنامه ریزی پرسنل تقسیم میشود. در طراحی جدول زمانی مقولههایی مانند تعیین زمان حرکت و رسیدن به مقصد برای هرکدام از خدمات قطار، ایستگاه و خطوط راه آهن در نظر گرفته میشود. در این مقاله خدمت به عنوان سفر از یک مبداء به ایستگاه مقصد نهایی تعریف میگردد. همچنین قطار به خدمتی که خود ارائه مینماید، اشاره میکند. ما از یک خط ترانزیت سریع مسیر دوبل در دو خط آهن استفاده کردیم به طوری که در آن زمانهای حرکت و رسیدن به مقصد بدون برخورد قطار بر روی یک مسیر یعنی بخشهای ریلی بین دو ایستگاه متوالی طراحی میشوند. جدولهای زمانی بر طبق قیدهای منظم و متناوب و با استفاده از ماتریس تقاضاساعت/ اوج مبداء/ مقصد ثابت به وجود میآیند....