زمان بندی حرکت قطارها با استفاده از الگوریتم شاخه و حد و الگوریتم ابتکاری جستجوی پرتو- مطالعه موردی: مسیرهای دوخطه ریلی ایران

هدف از این پژوهش، ارایه روشهای دقیق و تقریبی جهت حل مسئله زما نبندی حرکت قطارها در مسیرهای دوخطه ریلی است. به منظور حل دقیق و یافتن جواب بهینه مسئله زمان بندی حرکت قطارها، از بسته نرم افزاری CPLEX11 و نیز الگوریتم شاخه وحد زمان بندی حرکتقطارها استفاده می شود. مدل ریاضی زمان بندی حرکت قطارها در مسیر دوخطه و نیز الگوریتم شاخه و حد پیشنهادی در نرم افزار جاواپیاده سازی شدند و مسائلی با ابعاد مختلف در مسیرهای ریلی بافق-سیرجان و تهران-مشهد مورد آزمایش قرار گرفتند. مقایسه نتایج حاصل، نشان از برتری عملکرد الگوریتم شاخه و حد پیشنهادی نسبت به CPLEX بویژه در مواجهه با مسائل زمان بندی با ابعاد بزرگ دارد. نتایج نشان می دهند که CPLEX ، مسائل بزرگ را در زمانهای بسیار طولانی حل می کند؛ در حالی که الگوریتم شاخه و حد می تواند جواببهینه این گونه مسائل را در زمانهایی منطقی و بسیار کمتر از زمان حل CPLEX به دست آورد. همچنین در این پژوهش، از پنج روش تقریبی حل مبتنی بر الگوریتم جستجوی پرتو استفاده شد. نتایج بررسی روشهای تقریبی برای مسائل با ابعاد مختلف در مسیر تهران-مشهد حاکی از عملکرد مناسب تر روشهای ابداع شده پژوهش حاضر، در مقایسه با روشهای قبلی، به ویژه در مواجهه با مسائل با ابعاد بزرگ است؛ به طوری که بسته به میزان اهمیت پارامتر دقت و سرعت در شرایط مختلف، روشهای جستجوی پرتو جدید می توانند جداول زمان بندی نزدیک به بهینه را در زمانهای منطقی و با اشغال کنترل شده فضای حافظه ارایه کنند. با استفاده از نتایج این پژوهش، امکان تهیه جداول زمانی حرکت قطارها در زمانهای مناسب برای مسیرهای دوخطه به ویژه مسیرهای طولانی با تعداد زیاد قطار فراهم می شود.

کلیدواژه ها:

زما نبندی حرکت قطارها ، روشهای ابتکاری ، الگوریتم شاخه و حد ، الگوریتم جستجوی پرتو ، جواب بهینه