بخشی از مقاله
چکیده
مساله زمانبند حرکت قطارها از مهمترین مسائل برنامه ریز حمل و نقل ریلی محسوب می شود. یکی ازرویکردها مدل ساز و حل مساله مذکور استفاده از چارچوب زمانبند کارگاهی است. با توجه به اینکه این مساله در زمره مسائل دشوار قرار دارد، با افزایش ابعاد مساله روش ها شمارشی دقیق قادر به حل آن در زمان محاسباتی معقول نبوده و ناگزیر به استفاده از روش ها ابتکار و فراابتکار هستیم. الگوریتم انتقال گلوگاه ازموفق ترین روش ها ابتکار حل مساله زمانبندکارگاهی به شمار می رود. در این مقاله تعداد مساله آزمایشی زمانبند حرکت قطارها در ابعاد متفاوت با هدف کمینه ساز طول افق زمانبند ، با استفاده از ساختارگراف انفصال و الگوریتم انتقال گلوگاه به عنوان روش ابتکار و نرم افزار CPLEX به عنوان روش دقیق حل شده و نتایج حاصل مورد تجزیه و تحلیل قرار گرفته است. نتایج محاسباتی نشان دهنده برتر الگوریتم انتقال گلوگاه نسبت به نرم افزار CPLEX می باشد.
واﮊهها کلیدی: زمانبندحرکت قطارها، زمانبندکارگاهی، الگوریتم انتقال گلوگاه، گراف انفصال
۱-مقدمه
صنعت حمل و نقل ریلی از مدها اصلی حمل و نقل بوده و نقش بسیار مهمی در جابهجایی کالا و مسافر ایفامی کند. زمانبند حرکت قطارها از مهمترین مسائل برنامه ریز در صنعت حمل و نقل ریلی است. حرکتقطارها در طول شبکه بر اساس زمانبند ها انجام شده صورت می گیرد. این زمانبند شامل حرکت قطارها ازایستگاه مبدا، ورود به ایستگاه هابین راهی و خروج از آنها، زمان توقف در ایستگاه ها بین راهی و زمان رسیدن به ایستگاه مقصد می باشد]۱.[متخصصان ریلی جهت کمینهکردن هزینهها و استفاده صحیح از امکانات و تجهیزات راهآهن، از انواع روشهابرنامهریز استفاده مینمایند. از جمله روشها پرکاربرد جهت برنامهریز در راهآهن استفاده از مدلها ریاضی است.
این مدلها قادرند دنیا واقعی را به صورت یک شماتیک ریاضی نمایش دهند و به مابرا تصمیمگیر در محدودیتها دنیا واقعی با استفاده از روشها ریاضی و علوم کامپیوتر کمک کنند. به دلیل زیرساخت ها بسیار هزینه بر ریلی حتی کوچکترین بهبود در فرآیندها تصمیم گیر می تواند منجر به صرفه جویی ها اقتصاد فراوان شود، لذا تصمیم گیر مناسب جهت استفاده بهینه از تجهیزات موجود از اهمیت فراوانی برخوردار است.حرکت قطارها1 به کمک الگوریتم انتقال گلوگاه2 که از روش ها هیوریستیک3در این مقاله مساله زمانبند هیوریستیک3 حل مساله زمانبند کارگاهی4 می باشد، حل شده و نتایج مورد تحلیل قرار گرفته است. در بخش ۲ پیشینه تحقیق زمانبند حرکت قطارها بیان شده است، بخش ۳ به تشریح مدل ریاضی مساله می پردازد. روش حل مساله و پیاده سازو نتایج محاسباتی به ترتیب در بخش ها۴ و ۵ بررسی شده و نهایتا در بخش ۶ نتیجه گیرو جمع بند مقاله بیان می شود.
-2 مرور ادبیات موضوع
از آنجا که مساله زمانبند حرکت قطارها از حوزهها مورد توجه در برنامه ریز حمل و نقل ریلی می باشد، تاکنون تلاش ها متعدد جهت مدل ساز و حل مساله مذکور صورت گرفته است. با توجه به اینکه مدل ارائه شده در این مقاله بر اساس مدل زمانبندکارگاهی می باشد، پژوهش ها صورت گرفته در زمانبندحرکت قطارها بر اساس این رویکرد مدل ساز بیان می شود.نخستین بار اشپیگل به منظور زمانبندمسیرهاتک خطه در برزیل از مدل زمانبند کارگاهی استفاده کرد و مساله حاصل را با استفاده از الگوریتم شاخه وکران5 حل نمود]۲.[ اولیویرا و اسمیت به منظور زمانبند مجدد6 مساله زمانبند راه آهن تک خطه از روش زمانبند کارگاهی بهره جستند]۳.[ پاسیارلی و پرانزو با معرفی یک الگوریتم جستجوممنوع - TS - 7 و با بهره گیر از گراف جایگزین8 که بسطی از گراف انفصال کلاسیک9 می باشد، مساله زمانبندحرکت قطارها را با هدف کمینه کردن بیشینه تاخیرات حل نمودند]۴.[
ﮊو و ﮊانگ برا مسیرها دو خطه، دو هدف زمان توقف براقطارها پرسرعت و کل زمان سفر برا قطارها پرسرعت و با سرعت متوسط را مورد تحلیل قرار دادند]۵.[د آریانو و همکاران به منظور به دست آوردن یک جدول زمانبند بدون ناسازگار از مدل زمانبندکارگاهی و گراف جایگزین استفاده کرده و با حداقل کردن تاخیرات ثانو برا تمام قطارها در نظر گرفتهشده، محدودیت ها عدم وجود فضا حائل را لحاظ کردند]۶.[ لیو و کوزان حرکت قطارها را به صورت یکمساله زمانبند کارگاهی با ماشین ها مواز و محدودیت ها بلاک کننده در گراف جایگزین مدلکردند]۷.[ بوردت و کوزان زمانبندقطارهااضافی را با توجه به محدودیت ها عمومی پنجره زمانی و با هدفحداقل کردن طول افق زمانبندو تضاد با برنامه زمانبندفعلی انجام دادند]۸.[ همین نویسندگان با توسعهیک گراف انفصال جدید، عواملی چون طول قطار و مسیرها جایگزین را در مدل ساز خود لحاظ نمودند]۹.[نایبی و کیانفر مساله را به صورت حالت خاصی از جریان کارگاهی منعطف1 در نظر گرفته و محدودیت هاتوقف قطارها جهت فریضه نماز برا راه آهن ایران را مورد توجه قرار دادند]۰۱.[
۳- مدل برنامه ریز عدد صحیح2
یک مساله زمانبند حرکت قطار را می توان به یک مساله زمانبند کارگاهی تبدیل کرد. ابتدا شبکه ریلی به قطعه ها خط یا بلاک ها تقسیم می شود. هر سفر قطار از مبدا به مقصد به عنوان یک کار تعریف شده وقطعه ها خط یا بلاک ها به عنوان ماشین ها در نظر گرفته می شوند. طی نمودن هریک از بلاک ها در مسیر سفررا می توان با انجام یک عملیات در مساله زمانبند کارگاهی معادل ساز نمود. زمان ها عملیات برابر با زمانمورد نیاز برا عبور از بلاک ها می باشد. از آنجا که در هر زمان تنها یک قطار می تواند در هر بلاک حضورداشته باشد، در صورت اشغال بودن بلاک، قطار بعد باید تا آزاد شدن آن بلاک منتظر بماند.
در سراسر این مقاله سفر هریک از قطارها معادل یک کار، ماشین معادل بلاک و عملیات معادل طی یک بلاک در سفر هریک ازقطارها بوده و این عبارات می توانند جایگزین یکدیگر شوند. یک زمانبندشامل تخصیص عملیات به بلاک ها ویا به عبارتی تعیین ترتیب قطارها رو بلاک ها می باشد. ورودها مساله شامل تک خطه و یا دو خطه بودنخطوط، مسیر هریک از قطارها شامل ایستگاه مبدا و مقصد و ایستگاه ها بین راهی و زمان سیر در بلاک ها میباشد. مدل برنامه ریز عدد صحیح با روابط - ۱ - الی - ۸ - بیان شده است، رابطه - - i , j - - k , j بیانگر اینمطلب است که قطارj از بلاک i قبل از بلاک k عبور می کند.
