بخشی از مقاله
چکیده :
تخصیص هواپیما به پرواز از جمله زیر مسائل برنامهریزی پرواز در شرکتهای هواپیمایی است. در این مسأله با معلوم بودن زمان پروازها و مشخصات هواپیماهای آماده پرواز، نوع هواپیمای هر پرواز تعیین میشود. در چند مطالعه اخیر، این مسأله بصورت یک مسأله جریان در شبکه چند کالایی با متغیرهای صحیح مدلسازی و حل شده است. در این مطالعه یک روش حل ، با استفاده از روش جستجوی ابتکاری Simulated Annealing پیشنهاد شده و چند مسأله نمونه مورد حل قرار گرفته است. مقایسه نتایج روش حل پیشنهادی با نتایج نرمافزار بهینهسازی GAMS حاکی از قابلیت خوب روش، برای حل مسأله تخصیص هواپیما است.
١- مقدمه
از دیرباز استفاده از برنامهریزی ریاضی در برنامهریزی پرواز مورد توجه تصمیمگیرندگان و محققین بوده است]١.[ بدلیل بزرگ بودن مسأله بهینهسازی، معمولا مسأله اصلی را به چند مسأله کوچکتر تقسیم میکنند. عناوین اصلی این مسائل عبارتند از: برآورد تقاضای پرواز، زمانبندی پرواز، تخصیص هواپیما به پرواز، تعیین مسیر پرواز، برنامهریزی خدمه پرواز و برنامهریزی نگهداری هواپیما ]٢و١٢.[ مطالعه حاضر به بررسی و حل مسأله تخصیص هواپیما به پرواز اختصاص یافته است. در ابتدا یکی از مدلهای موجود بیان شده و برای تطبیق بهتر با شرایط ایران بمیزان مختصری اصلاح شده است. سپس بعنوان یک رویکرد نو در حل این مسأله، از روش جستجوی ابتکاری SA استفاده شده است. پس از طراحی و پیادهسازی روش با زبان C ، چند مسأله نمونه برای بررسی کارایی روش حل شده است.
٢- تخصیص هواپیما به پرواز
در مسأله تخصیص هواپیما به پرواز، نوع هواپیمای هر پرواز بنحوی تعیین میشود که کل هزینه ناشی از انجام پروازها حداقل گردد. در این مسأله، برنامه زمانبندی پروازها - شامل مدت زمان آمادهسازی هواپیما برای برخاست بعدی - ، تقاضای هر پرواز و مشخصات ناوگان آماده برای عملیات - ظرفیت و هزینه عملیات - معلوم فرض میشود. محدودیتهای مربوط به برنامه خدمه و تعمیرات هواپیما نیز در این مسأله لحاظ نمیگردد.
همچنین دوره زمانی برنامهریزی بصورت تکراری فرض میگردد - یک شبانهروز - . مقاله آبارا ]٣[ از نخستین مطالعات چاﭖ شده است که مسأله را بعنوان مسأله تخصیص هواپیما و با رویکرد یک مدل اعداد صحیح بررسی و حل مینماید. سابرامانیان و جمعی از کارشناسان امر پرواز ]٤[ در خطوط هوایی دلتا، بعنوان یک مسأله در مقیاس بسیار بزرگ، مسأله را مدل و حل مینمایند. در سال ١٩٩٥ هِین و همکارانش ]٥[ مسأله تخصیص هواپیما را بعنوان یک مسأله جریان در شبکه چند کالایی بنحو مطلوبی مدلسازی نمودند.
آنها با ارائه مدلی مرکب از متغیرهای صحیح و حقیقی - MIP - ، سه روش مختلف را برای حل مسأله بکار میگیرند. پس از آنها کلارک ]٦[ بهمراه جمعی از محققین، محدودیت برنامه تعمیر هواپیماها و محدودیت پرواز خدمه را به مطالعه قبل میافزایند. از جمله مطالعات تکمیلی انجام شده بر مسأله تخصیص هواپیما میتوان به مقاله گو ]٧[ ، کلاینسویچ ]٨[ و رکسینگ ]٩[ اشاره نمود. مقاله اول به بررسی برخی خواص و ویژگیهای محاسباتی مسأله میپردازد، مقاله دوم امکان وارد کردن استثنائات یک برنامه پرواز را به مسأله تخصیص هواپیما فراهم میکند و در مقاله سوم امکان تصحیح زمانبندی پرواز به مدل هِین افزوده میشود.
در این بخش از مقاله، مدل مورد استفاده در این تحقیق که از مقاله هِین اقتباس شده است ارائه میگردد. این مدل بصورت یک مسأله جریان در شبکه چند کالایی، گسترده در زمان، بیان می شود. شبکه دارای دو نوع کمان است ؛ کمانهای پرواز و کمانهای زمینی. در شکل - ١ - مثال سادهای از یک شبکه پرواز با یک نوع هواپیما، ٣ شهر و ٤ پرواز نشان داده شده است. کمانهای ١، ٢، ٣ و ٤ از نوع پروازی و کمان ٥، ٦، ٧، ٨ و ٩ زمینی هستند.
فرض کنید C مجموعه فرودگاهها ، F مجموعه انواع ناوگان آماده پرواز، S - f - تعداد هواپیمای نوع f، L مجموعه پروازها در برنامه زمانبندی شده، اعضاﺀ این مجموعه به صورت {i} یا {odt} نشان داده میشوند که o معرف شهر مبدأ، d معرف شهر مقصد و t معرف یک زمان است، O - f - زیرمجموعهای از کمانهای پرواز شبکه هواپیمای نوع f که تا پایان دوره زمانی - یک شبانهروز - هنوز به مقصد نرسیدهاند، H مجموعه پروازهای زنجیرهوار - برخی از پروازها که باید توسط یک هواپیما انجام شوند - ، c fi هزینه تخصیص هواپیمای نوع f به پرواز i ، N مجموعه گرههای شبکه با اعضاﺀ {fot} که در آن f معرف نوع هواپیما، o معرف یک شهر و t معرف زمان است که میتواند مربوط به زمان فرود در o یا زمان برخاست از o باشد.
