بخشی از مقاله
استفاده از الگوریتم های فراابتکاری ژنتیک و PSO و مقایسه آنها در حل مسئله زمانبندی خدمه هواپیما
چکیده :
مسئله زمانبندی خدمه هواپیما (ACSP) از مهمترین مسائل در حوزه تحقیق در عملیات به شمار می رود و به طور عمومی شامل تخصیص گروه های خدمه به سفرهایی است که می بایست طبق برنامه زمانبندی از پیش تعیین شده ایی توسط ناوگان موجود پوشش داده شوند، به طوری که هزینه های مربوط به تخصیص خدمه به سفرها کمینه شود. مسئله زمانبندی خدمه به دو فاز کلی تقسیم می شود. در فاز اول تمام سفرهای رفت و برگشتی که شروع و خاتمه آنها در محل استقرار خدمه است تحت عنوان مجموعه pairing ها تعیین می شود. در فاز دوم با استفاده از مسئله Set COVering problem به مدلسازی مسئله که خواهان تخصیص بهینه خدمه به سفرها می باشد می پردازیم و سپس با استفاده از الگوریتم ژنتیک و الگوریتم بهینه سازی ذرات انبوه (PSO) به حل مسئله پرداخته و مقایسه ای بین این دو الگوریتم از لحاظ مدت زمان حل (کارائی) مسئله پرداخته می شود.
واژه های کلیدی زمانبندی خدمه هواپیما، مسئله مجموعه پوششی (Set COVering problem)، الگوریتم ژنتیک، الگوریتم PSO
1-مقدمه:
مسئله زمانبندی خدمه هواپیما ( Airline Crew Scheduling Problem) یا ACSP از معروف ترین مسائل در حوزه تحقیق در عملیات به شمار می رود. حوزه کاربرد مسئله CSP در سال های اخیر به طور وسیعی در صنایع هواپیمایی مطرح بوده، چرا که در صنایع هوایی 15 تا 20 درصد کل هزینه های عملیاتی شامل هزینه های مربوط به خدمه است و توجه به این موضوع در این صنعت بسیار قابل ملاحظه بوده است [1]. در سال های اخیر با توجه به این که بحث خصوصی سازی و برون سپاری در صنعت حمل و نقل به طور وسیعی مطرح شده است، این موضوع تا حدودی مورد توجه سازمان های ناوگان حمل و نقل قرار گرفته و استفاده از این مسئله و تکنیک های بهینه سازی برای کاهش هزینه عملیاتی و پرسنلی بسیار مورد نظر بوده است [2]. در این پژوهش هر کجا از واژه خدمه استفاده شده منظور خدمه هواپیما می باشد مگر خلاف آن بیان شود. مسئله زمانبندی خدمه (CSP) به طور عمومی شامل تخصیص گروه های خدمه به سفرهایی است که می بایست طبق برنامه زمانبندی از پیش تعیین شده ایی توسط ناوگان موجود پوشش داده شوند، به طوری که هزینه های مربوط به تخصیصی خدمه به سفرها کمینه شود. مسئله CSP خود به دو زیر مسئله اصلی و مستقل تقسیم می شود: (CPP) Crew Pairing Problem I... O (CAP) Crew Assignment Problem I... Oمسئله CPP شامل یافتن مجموعه ایی از سفرهای برگشتی تحت عنوان pairing با حداقل هزینه است که هر یک، تعدادی از سفرها را می پوشاند.
مسئله CAP نیز شامل تخصیص اعضای گروه های خدمه به سفرهاست که در این پژوهش به این قسمت مسئله یعنی تخصیص اعضای خدمه به سفرهاست، می پردازیم.
برای حل مسئله زمانبندی خدمه تا کنون روش های حل متنوعی بر پایه روش های دقیق و ابتکاری ارایه شده اند که هر کدام دارای معایب و مزایایی بوده و نتایج متفاوتی را تولید کرده اند که در ادامه مورد بررسی قرار می گیرند. در خصوص استفاده از روش های دقیق برپایه تکنیک های تحقیق در عملیات می توان به مطالعه [15] اشاره کرد که از دیدگاه های سنتی حل مسائل بهینه سازی برای این مسئله استفاده کرده است و برای مسائلی با ابعاد کوچکی نتایج خوبی را تولید کرده است. یکی از مشکلات عمده ایی که در استفاده از روش های دقیق برای حل مساله CSP پدید می آید، جستجو در فضای جواب بسیار بزرگی است که این فضا با افزایش تعداد سفرها به طور نمایی افزایش پیدا می کند و حل مسئله را در ابعاد بزرگ، بسیار استفاده از الگوریتم های فراابتکاری ژنتیک و PSO و مقایسه آنها در حل مسئله زمانبندی خدمه هواپیما پیچیده و زمان بر می کند [3]. در نتیجه در سال های اخیر با توجه به وجود مسائلی با ابعاد بزرگ در دنیای واقعی استفاده از روش های دقیق از لحاظ زمان مورد نیاز برای حل، به صرفه نیست و تمایل به استفاده از روش های ابتکاری و فراابتکاری افزایش پیدا کرده است تا جوابی مناسب و نزدیک به جواب بهینه در مدت زمان اندک بدست آید. از مهمترین مطالعاتی که در این خصوص صورت گرفته می توان به مطالعات [5,4,6] اشاره کرد که از الگوریتم ژنتیک [7] و از تکنیک شبکه های عصبی برای حل مسئله CSP استفاده کرده اند و جوابهای نسبتا خوبی را تولید کرده اند. CSP بیشتر در صنعت هواپیمایی دارای کاربرد بوده است. از از مهمترین مطالعات صورت گرفته در این خصوص می توان به مطالعات [10, 1,8,9] اشاره کرد که با استفاده از روش های برنامه ریزی ریاضی و عدد صحیح به حل مسئله CSP در حوزه صنایع هوایی پرداخته اند. همچنین در استفاده از روش های ابتکاری در این حوزه می توان به مطالعات [14 و 13 و 12 و 11] اشاره کرد که از الگوریتم های شبیه سازی آنیلینگ، شبکه های عصبی، منطق فازی و الگوریتم ژنتیک در مطالعات خود استفاده کرده اند. در مطالعه [16] به حل برنامه ریزی و زمانبندی کار خدمه و کارکنان راه آهن با استفاده از روش بهینه سازی مورچگان پرداخته شده است که یکی از روش های معروف بهینه سازی محسوب می شود و نتایج بسیار خوبی را نیز تولید کرده است. نوآوری این پژوهش در حل مسئله با استفاده از الگوریتم بهینه سازی ذرات انبوه اصلاح شده(PSO modified) می باشد که جوابهای نسبتا قابل قبولی نسبت به الگوریتم ژنتیک ایجاد می کند. در ادامه، این پژوهشی به صورت زیر ساختاردهی شده است: در بخش دوم مختصری به معرفی تعریفات و محدودیت هایی که در برنامه زمانبندی خدمه موجود می باشد می پردازیم. در بخش سوم رویه حل و الگوریتم های فراابتکاری ژنتیک و PSO برای این مسئله به طور مفصل بیان می شود. در بخش چهارم به تحلیل نتایج حاصل پرداخته می شود. در بخش پنجم جمع بندی و نتیجه گیری از بحث بیان می شود. و در بخش ششم نیز مراجع به کار رفته در این پژوهش ارائه شده است.
2 - برنامه ریزی کار خدمه و پرسنل هواپیما یکی از ورودی های اساسی برای شروع برنامه ریزی کار خدمه و پرسنل، داشتن یک جدول برنامه ریزی از سرویس ها و خدمات پروازهایی است که برای پریودهای زمانی مشخصی تنظیم شده است و شامل جابجایی بار و مسافر و تجهیزات بین ایستگاه های مختلف است. هر سرویسی که می بایست توسط هواپیماها صورت گیرد باید خود به چندین سفر متوالی و موجه تقسیم شود که هر سفر که در برخی از مطالعات یک Leg نامیده می شود - شامل قسمتی از سفرهای یک هواپیما است که می بایست
توسط یک گروه خدمه بدون وقفه و استراحت طی شود. هر سفر دارای مشخصاتی به شرح ذیل است
که باید به عنوان ورودی در نظر گرفته شود:
*زمان اعزام از مبدا حرکت، (td(i
* نام ایستگاه یا مبدا حرکت، (d(i
*زمان ورود به ایستگاه مقصد، (ta(i
* نام ایستگاه مقصد، (a(i
بعد از اینکه تمام سفرها با مشخصات بیان شده تعیین شدند می بایست به برنامه ریزی و تخصیص هر گروه خدمه به سفرها پرداخته شود، به این صورت که هر گروه خدمه موظف است، چندین سفر متوالی را تحت عنوان یک Paliring و یا یک ROSter تحت پوشش قرار دهد و به عنوان ماموریت آن را انجام دهد. پس از یافتن سفرها با مشخصات آنها می بایست به تولید pairingهایی موجه پرداخته شود که شرط موجه بودن آنها به یک سری محدودیت ها بستگی دارد که به شرح ذیل هستند و می بایست تمامی آنها رعایت شوند: 1. برای هر دو سفر متوالی در یک pairing می بایست ایستگاه مبدا حرکت سفر دوم منطبق بر ایستگاه مقصد سفر اول باشد.همچنین برای دو سفر متوالی مفروض می بایست زمان اعزام از ایستگاه مبدا برای سفر دوم بزرگ تر از زمان رسیدن به مقصد سفر اول باشد. 2. هر pairing که به یک گروه خدمه یکسان تخصیص می یابد، می بایست از محل استقرار آن خدمه آغاز شود و به آنجا نیز ختم شود. 3. برای ماموریت هر گروه خدمه که با یک pairing مشخص می شود، یک زمان ماموریت تعریف می شود که تجاوز از این زمان مجاز نیست و تا قبل از رسیدن به این زمان، گروه های خدمه می بایست به Home یا محل استقرار اولیه بازگشته شوند. 4. کل مدت زمان یک pairing که به عنوان زمان ماموریت گروه خدمه تخصیص یافته شده در نظر گرفته می شود، حاصل مجموع دو قسمت است و نباید از حداکثر زمان مجاز بیان شده تجاوز کند. یک قسمت از این زمان شامل مجموع زمان های سیری است که گروه های خدمه می بایست آنها را طی کنند و به صورت رابطه (1) بیان
می شود:
در رابطه فوق i معرف یک سفر است و P بیان کننده مجموعه سفرهایی است که در یک pairing مفروض آمده است. قسمت دوم از مدت زمان یک pairing به مجموع زمان های بیکاری گروه های خدمه در یک pairing مربوط می شود که بخشی از این زمان موجه است و به عنوان زمان های استراحت خدمه در نظر گرفته می شود و بخش دیگر مجاز نیست و تا حد امکان باید حداقل شود. رابطه شماره (2) محاسبه زمان بیکاری را برای دو سفر متوالی i و j در یک pairing نمایش می دهد که فاصله زمانی بین پایان یک سفر تا شروع سفر بعدی است. (2) (1dle Time = td(j) -- td(i 5. نکتے مھم دیگری کے می بایست مورد ملاحظه قرار گیرد این است که گاهی اوقات در یک سفر و در کنار گروه خدمه ای که به آن سفر تخصیص یافته است و در آن هواپیما در حال انجام ماموریت هستند، گروه های دیگری نیز حضور دارند که تنها به منظور رفتن به ایستگاه دیگری برای ادامه ماموریت خود در آن هواپیما حضور پیدا کرده اند. این گونه سفرها که به بیش از یک گروه خدمه تخصیص می یابند و اصطلاحا deadheading trip نامیده می شود برای شرکت مربوطه دارای هزینه ایی اضافی هستند، چرا که گروه های خدمه اضافی بدون پرداخت هزینه بلیط سوار می شوند و بدون اینکه کار کنند فضایی از صندلی ها را نیز اشغال کرده اند که می بایست به مسافران دیگری تخصیص می یافت و در حقیقت مانند مسافرانی هستند که رایگان سوار شده اند که می بایست این حالت تا حد امکان حداقل گردد. در نهایت هدف یافتن زیرمجموعه ای از مجموعه کل Pairing های موجهی است که دارای حداقل هزینه عملیاتی باشند و هر کدام به یک گروه خدمه تخصیص یافته باشند.
3- الگوریتم حل ابتکاری برای برنامه ریزی و زمان بندی کار خدمه با توجه به اینکه فضای جواب مورد جستجو بسیار بزرگ است در این پژوهش فرآیند حل مسأله به دو مرحله مستقل تقسیم شده و به شرح ذیل است: 1- مرحله تولید pairing های موجه: در این مرحله سعی می شود که تمام pairing های موجهی که از جدول زمانی سفرهای داده شده قابل استخراج هستند تعیین شوند به طوری که تمام محدودیت های مطرح شده را رعایت کرده باشند. شایان ذکر است که دیدگاه استفاده شده در این مرحله با استفاده از روش های متنوعی از s. -,32 (Depth First Search) DFS Alو کلیه pairingهای موجه یافت شده به همراه محاسبه هزینه های مربوط به آنها در مجموعه ایی نگهداری می (1 شوند و وارد مرحله بعدی می شویم. هزینه های مربوط به pairing که محاسبه می شود شامل مجموع هزینه های دستمزد انجام هر سفر، محاسبه مجموع زمان های بیکاری که در pairing مورد نظر وجود دارد و کل زمان یک pairing از شروع در Home تا رسیدن به آن است. 2- مرحله بهینه سازی و تعیین جواب بهینه: در این مرحله همانطور که بیان شد می بایست زیر مجموعه ایی از مجموعه کل pairing های بدست آمده از مرحله قبل با حداقل هزینه بدست آید به طوری که تمام سفرها را پوشش دهد و هر سفر حداقل به یک pairing تخصیص یافته باشد. شایان ذکر است که در این مرحله، مسئله مورد نظر با اطلاعات حاصل از مرحله قبل و با استفاده از ... , 63.J. Set Covering Problem all. وسپس با استفاده از الگوریتم های ژنتیک و PSO بهینه می شود. شکل زیر خلاصه ایی از این دو مرحله را به صورت گرافیکی نمایش می دهد.
1-3 تولید pairing های موجه
به منظور تولید انبوهی از pairing های موجه ابتدا می بایست جدول زمانبندی شده از سفرها به صورت یک گراف جهت دار (G=(V,E تبدیل شود که در آن V مجموعه رئوس گراف G است و هر راس i آن نیز معرف سفر i یا (T(i است. لازم به ذکر است که مشخصات هر سفر i از قبیل زمان اعزام از مبدا، ایستگاه مبدا، ایستگاه مقصد و زمان رسیدن به مقصد به عنوان ویژگی های گره i در نظر گرفته شود. با توجه به توضیحات گذشته می بایست گره هایی برای محل استقرار گروه های خدمه در نظر گرفته شود که پس از مدت زمان تعیین شده به آنجا باز شوند. در گراف جهت دار G این دپوها با di نمایش داده می شوند که محل استقرار گروه خدمه i است. علاوه بر این در گراف جهت دار فوق، E مجموعه تمام کناره های گراف است که به صورت کمان (i,j) بین هر راس i و j نمایش داده می شود. باید گفت که کمان (لیل) تنها زمانی در گراف G حضور این که بلافاصله بعد از سفر i قرار گیرد را داشته باشد. به عبارت دیگر تحت دو شرط ذیل امکان برقراری کمان (لیل) بین دو راس i و j ایجاد شود:
• انطباق مبدا سفر j با مقصد سفر i و یا (a(i)=d(j
• شرط اساسی دیگر در نظر گرفتن یک فاصله زمانی ثابتی بین هر رسیدن و اعزام است که براساس ملاحظات و دارد که سفر j با حفظ شرایط توجیه پذیری امکاننیازمندی های فنی تعیین می شود و به صورت رابطه 3زیر محاسبه می شود:
در نتیجه بعد از تشکیل گراف جهت دار G با فرضیات فوق، با
استراتژی جستجوی DFS روی گراف عمل می شود و تمام pairing های موجهی که با رعایت محدودیت های بیان شده است تعیین شده و به همراه هزینه هر کدام در مجموعه ایی نگهداری می گردند. شایان ذکر است که در پایان این مرحله می توان به منظور کاهش تعداد انبوه pairingهایی که تولید شده اند، برخی از آنها را که نامناسب هستند با تعریف شاخص هایی که با نظر تصمیم گیرنده بیان شده اند، را حذف کرد.
علاوه بر کناره های فوق کناره های دیگری نیز وجود دارند که به صورتdi) e E) و j,d)e E) هستند و برای برقراری ارتباط گره ها با گره d می باشند که نشان دهنده محل استقرار گروه های خدمه است. شایان ذکر است که کمانهای فوق به ترتیب برای هر سفر i که با dk شروع می شوند و هر سفر j که به dk ختم می شود، تعریف می شود. 4. و مقایسه آنها در حل مسئله زمانبندی خدمه هواپیما PSO استفاده از الگوریتم های فراابتکاری ژنتیک و به عنوان مثال اگر زمان بیکاری خدمه در یک pairing بیشتر از حد ثابتی است که با نظر تصمیم گیرنده تعریف شده است، می توان آن pairing را حذف کرد.
بعد از آنکه تمام pairing های موجه با استفاده از مرحله قبل تولید شدند، با استفاده از دیدگاه مسئله SCP به مدلسازی مسئله مورد نظر پرداخته می شود. در مسئله SCP یک ماتریس باینری m*n تعریف می شود که هدف در آن تعیین ستون هایی با حداقل هزینه از بین n ستون است به طوری که توسط آنها تمامی m سطر تریسی، حداقل توسط یک ستون تحت پوشش قرار داشته باشد. مدلسازی ریاضی این مسئله به فرم زیر است:
در ماتریس باینری m × n فوق، هر درایه (i,j) در ماتریس اگر یک باشد به این معناست که سطر i توسط ستون j ام تحت پوشش قرار می گیرد و اگر صفر باشد به این معناست که سطر مفروضی تحت پوشش ستون j نیست. در رابطه (4) که بیان کننده انتخاب زیر مجموعه ایی از ستونها در بین n ستون با حداقل هزینه است، متغیر باینری X نماینده ستون jام در ماتریس و 0حCj هزینه انتخاب این ستون است. بنابراین در صورتی که مقدار متغیر X برابر یک باشد، یعنی ستون jام در جواب نهایی حضور دارد و در غیر این صورت این ستون در زیر مجموعه انتخاب شده از ستون ها وجود ندارد. رابطه شماره (5) تضمین می کند که هر سطر حداقل توسط یک ستون تحت پوشش قرار داده شود و متغیر aij در این رابطه، یک متغیر باینری است که وقتی سطر i در ستون j ام وجود داشته باشد مقدار یک را به خود می گیرد و در غیر این صورت صفر در نظر گرفته می شود. به منظور مدلسازی برنامه ریزی کار خدمه با استفاده از مسئله SCP ، هر سطر از این ماتریسی (mو... و 1=i) متناظر با سفرهای (T(i و ستون های آن (n و... و 1=j) متناظر با pairingهای بدست آمده از مرحله قبل در نظر گرفته می شود و درایه های صفر و یک داخل ماتریسی براساسی اینکه هر pairing چه سفرهایی را تحت پوشش خود قرار می دهد، کامل می شوند. که پس از حل مسئله SCP مربوط به زمانبندی خدمه با استفاده از الگوریتم ژنتیک و PSO می پردازیم.
3-3 الگوریتم ژنتیک
ایده اولیه این الگوریتم نخستین بار توسط J.H. Holland در دهه 1970 میلادی در دانشگاه میشیگان مطرح شد. این الگوریتم با مجموعه ایی از کروموزوم ها که هر کدام نشان دهنده یک جواب برای مسئله مفروض اند، تحت عنوان جمعیت اولیه شروع به کار می کند و سپس با یک مکانیزم انتخاب خاصی که برای انتخاب والدین در نظر گرفته می شود، آنها را تحت اپراتورهای تقاطع و جهش قرار داده و از آنها فرزندان جدیدی تولید و جایگزین والدین می کند. تشکیل جمعیت اولیه می تواند به صورت تصادفی و یا با استفاده از روش های ابتکاری صورت گیرد که در این زمان همگرا شدن به جمعیت اولیه کمتر است. این الگوریتم آنقدر تکرار می شود تا تعداد نسل ها (تکرارها) به میزان تعریف شده رسیده باشد و یا دیگر بهبودی در جمعیت های جدید به دست آمده ایجاد نشده باشد.
3 - 1-3 نحوه ی نمایش کروموزوم ها
گام اولیه و ابتدایی در شروع الگوریتم ژنتیک نمایش جواب ها به صورت رشته ایی به نام کروزوم است. اگرچه که برای نمایش کروموزوم دو رویکرد نمایش بر مبنای ستونی یا سطری وجود دارد، اما در این پژوهشی از رویکرد نمایش ستونی برای ارائه کروموزوم استفاده شده است. بنابراین در این پژوهش هر جواب به صورت یک رشته باینری به طول تعداد ستون ها یعنی n (تعداد pairingها) در نظر گرفته می شود که هر ژن آن می تواند مقدار صفر یا یک را به خود بگیرد. بنابراین در صورتی که ژن jام مقدار یک را داشته باشد به این معناست که pairing یا ستون j ام در جواب مورد نظر حضور دارد و در صورت داشتن مقدار صفر، ستون مفروض در جواب مورد نظر وجود ندارد. به عنوان نمونه شکل زیر نمونه ایی از یک جواب را
به صورت رشته ایی باینری نمایش می دهد:
شکل 2- نمایش یک نمونه کروموزوم
3 - 2-3 تابع برازندگی
به منظور ارزیابی کیفی هر کروموزوم در جمعیت فعلی و همچنین ارزیابی کیفی هر کروموزوم در جمعیت فعلی و همچنین ارزیابی کروموزوم های جدیدی که در خلال فرایند تولید نسل به وجود می آیند، می بایست تابعی با نام تابع برازندگی تعریف شود تا به وسیله آن این امر ارزیابی صورت گیرد. در این پژوهش چندین پارامتر مهم در رسیدن به با کروموزوم و یا جواب بهینه تاثیر گذارند. یک پارامتر عمده در این پژوهشی، برنامه ریزی کار خدمه با حداقل هزینه های تخصیصی و دستمزد است که به صورت Cij
5 پاک سرشت و همکاران
نمایش داده می شود و برای انجام و اتمام سفر i و شروع سفر j تعریف می شود. در این برنامه ریزی با توجه به اینکه از مسایل پوششی بهره گرفته شده است و در آنها مطلوب است که با حداقل تعداد pairing به کلیه سفرها پوشش داده شود، که می توان یک عبارت جریمه نیز برای تعداد pairing ها در نظر گرفته شود. بنابراین تابع ارزیابی را می توان همان تابع هدف مربوط به مسئله SCP که مربوط به مجموع هزینه های تخصیص و دستمزد pairing ها می باشد، استفاده کرد.
3-3-3 تشکيل جمعيت اوليه
به منظور شروع تکرارهای الگوریتم ژنتیک می بایست در ابتدا جمعیت اولیه ایی از کروموزوم ها تحت عنوان والدین تشکیل شود و در خلال تکرارهای الگوریتم ژنتیک، فرزندان جدید تولید و جایگزین والدین شوند تا جمعیت جدیدی تشکیل شود. نکته قابل ملاحظه در این پژوهشی این است که کروموزوم های تشکیل دهنده جمعیت اولیه و همچنین کروموزوم های جدیدی که در نسل
