بخشی از مقاله
چکیده
مسالهی برنامهریزی خدمه یکی از مسائل مهم در مدیریت شبکههای حملونقلی میباشد. در این مقاله، موضوع برنامهریزی اعزام خدمهی قطار در شبکهی ریلی ایران برای قطارهای مسافری مرزبه مرز و با توجه به نیاز دورهای به این افراد، مورد بررسی قرار گرفته است. در ابتدا، با استفاده از مفاهیم گراف و شبکه، گراف معادل شبکه ریلی بدست آمد و با استفاده از الگوریتم تولید ماموریتها، به تولید تمام ماموریتهای ممکن در شبکه پرداخته شد.
در مرحله بعد، مدل ریاضی مربوط به بهینهسازی ماموریتها ایجاد شد که این مدل با تمرکز بر حداقل کردن زمان استراحت غیر مجاز خدمه، حداکثر زمان ماموریتها را محدود مینماید و منجر به موثرتر شدن برنامهریزی و درنتیجه کاهش هزینههای مربوط به پرسنل خواهد شد، این مدل در نهایت برای یک مسالهی واقعی برایراهآهن جمهوری اسلامی ایران حل شد و نتایج بدست آمده، در بخش نتایج ارائه شد.
-1 مقدمه
مسالهی برنامهریزی خدمه قطار، شامل یافتن مجموعهای از نوبت های کاری است که ضمن پوشش دادن همهی سفرهای جدول زمانبندی حرکت قطارها، تمامی محدودیتها در آن رعایت شده و مجموع هزینهها کمینه شود. رویکرد رایج برای حل مساله برنامه ریزی خدمه، تجزیهی این مساله و حل آن در دو مرحلهی بهینه سازی ماموریتها و بهینه سازی نوبتکاری است. در مرحلهی بهینهسازی ماموریتها، هدف یافتن ماموریت-های بهینه است، به طوری که مجموعه سفرها پوشش داده شوند. در مرحلهی بهینهسازی نوبت کاری، هدف تعیین بهترین ترتیب انجام ماموریتها توسط خدمه است. [16]
زمانبندی خدمه، تعیین برنامهی زمانی ماموریتهای راهآهن با حداقل هزینه میباشد که ضمن پوشش دادن تمام وظیفهها همراه با رعایت زمانبندی حرکت قطارها، هر ماموریت از یک قرارگاه شروع شده و پس از طی زنجیره ای از وظایف و انتقال به همان قرار گاه ختم شود .[2] در نتیجه برنامهی زمانی هر ماموریت، در برگیرندهی زمان ابتدا و انتهای هر وظیفه و هر انتقال تشکیل دهندهی آن ماموریت میباشد.
در کل، در راه آهن ایران زمانبندی خدمه شامل زمانبندی موارد زیر میشود:
▪ لکوموتیوران
▪ رییس قطار باری
▪ رییس قطار مسافری
▪ رییس رستوران
▪ خدمه ی فنی همراه قطار و مهمانداران ×
▪ و....
در این تحقیق به ارایهی یک الگوریتم برای تولید ماموریتهای ممکن و همچنین ارائه مدل قطعی بهینه سازی ماموریتها در برنامهریزی خدمه پرداختیم. ساختار مقاله نیز در ادامه به این شرح خواهد بود؛ ابتدابه مرور ادبیات موضوع پرداخته میشود سپس تعریف مسئله تحقیق و مفروضات اصلی آن ارائه میشوند. در بخش چهارم الگوریتم تولید ماموریتها طبق جدول زمانبندی قطارها بیان و سپس مدل ریاضی مسئله ارائه میشود. در بخش پنجم، نتایج محاسباتی، یک مسالهی واقعی برای زمانبندی لکوموتیورانان قطارهای مسافری برای سفرهای مرزبه مرز در راهآهن جمهموری اسلامی ایران حل شده و نتایج آن ارایه میشود. سرانجام، در بخش پایانی از تحقیق نتیجهگیری لازم به عمل آمده و زمینههای تحقیقاتی بعدی ذکر خواهد شد.
-2مرور ادبیات
موضوع برنامهریزی خدمه قطار اولین بار توسط کاپرارا و همکاران[7]، مورد توجه قرار گرفت. کاپرارا و همکاران با تجزیهی مسئلهی برنامهریزی خدمه قطار به دو زیر مسئله، روش ابتکاری برای حل آن ارائه دادهاند و سپس مسئله را برای راه آهن ایتالیا پیاده سازی نموده اند. یقینی و قنادپور[5] ، با ارائهی مدلی برای برنامهریزی کار خدمه در راه آهن، مدل را به دو فاز مستقل تقسیم کردهاند، به این صورت که در فاز اول وظایف،×با استفاده از الگوریتم جستجو در عمق5 تعیین شدند.
در فاز دوم با مسالهی پوشش مجموعهای×به مدلسازی مسئله پرداخته و سپس با الگوریتم ژنتیک حل نموده اند، نتایج حاکی از آن است که مدل، جواب هایی با کیفیت بسیار خوب را در مدت مناسبی تولید کرده است. پورسیدآقایی و صلاحی[1]، با در نظر گرفتن جدول زمانی حرکت قطارها و مسیرهای ریلی راه آهن کشور تحت عنوان گراف، اقدام به برنامه ریزی اعزام روسای قطار کرده است. این مدل، کاهش تعداد خدمه و کاهش زمان سفر را درپی داشته است.
آبینک و همکاران [6]، به منظور افزایش رضایت لوکوموتیورانان و روسای قطار، یک مدل پوشش مجموعهای، با تابع هدف کاهش هزینهی وظایف، ارائه داده اند و از روش تولید ستون پویا و روش لاگرانژ برای حل آن استفاده نمودند. نتیجهی این بررسی، علاوه بر افزایش رضایت کارکنان، کاهش هزینه های پرسنل بوده است. یقینی و فتحی پور[4]، با استفاده از رویکرد تولید ستون به عنوان روش حلی برای مسائل با مقیاس بزرگ به حل مسئله ی برنامه ریزی خدمه پرداخته اند. از آنجا که جوابهای تولید شده یا روش تولید ستون، صحیح نبود، با استفاده از الگوریتم شاخه و کران، جواب هایی صحیح حاصل شد. نتایج حاصل از این پژوهش علاوه بر تسهیل روند برنامه ریزی، کاهش هزینه را نیز در بر داشت.
پاتوف و همکاران[14]، با ارائه ی الگوریتمی برپایهی ترکیب تکنیک تولید ستون با روش آزاد سازی لاگرانژ به حل برنامه ریزی مجدد خدمهی قطار پرداخته اند. استفاده از این روش در مسائل دنیای واقعی به تولید جواب های خوب در مدت زمان کمی منجر شد. جوته و تنمن[10]، یک الگوریتم تجزیهی مبتنی بر رویکرد تولید ستون را که جواب هایی با کیفیت بالا در زمانی معقول تولید میکنند را ارائه دادهاند. الگوریتم تقسیم و قیمت4 ارائه شده در مقاله، مسئله را به دو مسئلهای که باهم همپوشانی دارند، تقسیم میکند و به طور همزمان و موازی مسئلهها را حل میکند.
ویلنتراف و همکاران[21]، به مدلسازی برنامه ریزی مجدد خدمه و حل آن پرداخته اند. الگوریتم بیان شده، روی برنامه ریزی مجدد لوکوموتیورانان تمرکز دارد و براساس روش تولید ستون میباشد که با روش های ابتکاری ترکیب شده است.طبق نتایج بدست آمده، استفاده از این روش نسبت به روش های قدیمی، جواب های بهتری می دهد. حنفی و کوزان[10]، مدلی ریاضی را با هدف کمینه کردن تعداد وظایف خدمه به وسیله کم کردن زمان بیکاری را مطرح نمودهاند.
این مساله امکان دیرکرد در اعزام قطار را برای زمانبندی مجدد لوکوموتیورانها، در نظر گرفته است. سپس با روش هیبرید - ابتکاری - تبرید شبیه سازی شده - ، جوابهایی نزدیک به جواب بهینه تولید کرده است. نیشی و همکاران[16]، از الگوریتم تجزیه دو مرحلهای برای تخصیص نوبت کاری در برنامهریزی خدمه، با هدف شرایط کاری متعادل برای خدمه، استفاده کردهاند. همچنین برای حل مسئله اصلی، از الگوریتم شاخهوکران استفاده شده است. پرز و همکاران[8]، روش ابتکاری لاگرانژ را برای برنامهریزی همزمان دو منبع راه آهن - معمولا ناوگان و لوکوموتیوران - ارائه داده است که منجر به کاهش هزینه و ارائهی جوابهایی با کیفیت خوب شده است؟
-3تعریف مسئله
مسئلهی برنامهریزی خدمه، از مسائل مهم در زمینهی زمانبندی میباشد و هدف آن تخصیص وظایف تعریف شده با زمان شروع و پایان معین، به خدمه میباشد. برنامهریزی خدمه در راه آهن شامل برنامهریزی مهمانداران، خدمهی فنی، روسای قطارها، لوکوموتیورانها، رئیس رستوران و... میباشد.[3] در این پژوهش فاز اول مسئله برنامهریزی خدمه یعنی بهینه سازی ماموریتها، مورد مطالعه قرار گرفتهاست.
در برنامهریزی خدمه قطار، حرکت هر قطار بین مبدا و مقصد مشخص را سفر مینامیم. هر سفر بخشی از مسافرت قطار است که باید توسط یک گروه خدمه پوشش داده شود و در طول سفر، امکان تغییر گروه خدمه وجود ندارد. هر سفر در یک وسیلهی نقلیه را میشود به قطعات کوچکتری تقسیم کرد، که به آن ها "تکه مسیر" میگویند. هر تکه مسیر به مسیرهای مختلفی تقسیم میشود. و ما در زمان بندی خدمه آن را فاصلهی بین دو× ایستگاه یا دو نقطه که امکان تعریف خدمه است، تعریف میکنیم؟ همچنین به توالی ممکن از سفرها که توسط خدمه پوشش داده میشود و از دپوی محل زندگی خدمه آغاز و به همان دپو نیز ختم میشود، ماموریت گفته میشود.
یکی از ورودیهای اساسی برای شروع برنامهریزی کار خدمه و پرسنل، داشتن یک جدول برنامهریزی از سرویسها و خدمات قطارهایی است که برای پریودهای زمانی نشخص تنظیم شدهاست و شامل جابجایی بار و مسافر و یا انتقال واگنهای خالی و تجهیزات بین ایستگاههای مختلف است. هر سرویسی که میبایست توسط قطارها صورت گیرد، میتواند به چندین سفر متوالی و موجه تقسیم شود،که میبایست بدون وقفه و استراحت توسط یک گروه خدمه طی شود. هر سفر دارای مشخصاتی به شرح زیر میباشد،
· زمان اعزام از ایستگاه مبداء
· ایستگاه مبداء
· زمان ورود به ایستگاه مقصد
· ایستگاه مقصد
پس از اینکه تمام سفرها با مشخصات بیان شده تعیین شدند، میبایست به برنامهریزی و تخصیص هر گروه خدمه به سفرها پرداخته شود، به این صورت که هرگروه خدمه موظف است، چندین سفر متوالی را تحت عنوان یک ماموریت و یا نوبت کاری تحت پوشش قرار دهد و آن را به عنوان ماموریت انجام دهد. در شبکهی مفروض، یک سری ایستگاهها به نام دپو قرار دارند، که گروههای خدمه میتوانند پستهای کاری خود را در آنجا تعویض نمایند.
در مرحلهی تولید همهی ماموریتهای ممکن، سفرهای موجود در شبکهی راهآهن، ابتدا به سفرهای بین دپویی، تبدیل شده و این سفرهای بین دپویی گرههای گراف را تشکیل میدهند. و پس از یافتن سفرها با مشخصاتشان میبایست به تولید ماموریتهای ممکن پرداخته شود که شدنی بودن این ماموریتها به در نظرگرفتن فرضیات و محدودیتهای زیر بسته است و میبایست تمام این فرضیات رعایت شوند.
این فرضیات و محدودیتها یه شرح زیر میباشند:
-1 هر ماموریت که مربوط به یک گروه خدمه میباشد، میبایست از دپوی محل استقرار خدمه شروع شده و پس از طی ماموریتهای لازم به همان دپو ختم شود.
-2 برای هر دو سفر متوالی زمان اعزام از ایستگاه مبدا برای سفر دوم میبایست بزرگتر از زمان رسیدن به مقصد سفر اول باشد.
-3 برای هر دو سفر متوالی در یک ماموریت میبایست ایستگاه مبدا سفر دوم با ایستگاه مقصد سفر اول منطبق باشد.
-4 هر خدمه بین دو سفر در یک ماموریت باید کمینه زمان استراحت داشته باشد.
-5 هر ماموریت نباید بیش از مقدار مشخصی سفر داشته باشد.
