دانلود مقاله ISI انگلیسی شماره 7710 + ترجمه فارسی
ترجمه فارسی عنوان مقاله

الگوریتم مبتنی بر بهینه‌سازیِ کلونی مورچه برای مسئله‌ی زبمان‌بندیِ کارکنان هواپیمایی

عنوان انگلیسی
Ant colony optimization-based algorithm for airline crew scheduling problem
کد مقاله سال انتشار تعداد صفحات مقاله انگلیسی ترجمه فارسی
7710 2011 7 صفحه PDF 16 صفحه WORD
دانلود فوری مقاله + ترجمه آماده
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.
منبع

Publisher : Elsevier - Science Direct (الزویر - ساینس دایرکت)

Journal : Expert Systems with Applications, Volume 38, Issue 5, May 2011, Pages 5787–5793

فهرست مطالب ترجمه فارسی
چکیده

کلمات کلیدی

1.مقدمه

2. مسئله‌ی زمان‌بندیِ کارکنان هواپیمایی

3. بهینه‌سازیِ کلونی مورچه (ACO) برای زمان‌بندیِ کارکنان پرواز

شکل 1. فرآیند الگوریتم مبتنی بر ACO برای مسئله‌ی زمان‌بندیِ کارکنان

شکل 2. جدول زمانیِ نمونه برای جست‌وجوی کوتاه‌ترین مسیر

جدول 1. جدول زمانیِ Taipei–Tokyo – هشت پرواز

3.1. الگوریتم مبتنی بر ACO انتخاب قانون پرواز

3.2. قانون به‌روزرسانیِ ردهای فرمونیِ ACO

3.3. ACO با محدودیت‌ها مطابقت دارد

شکل 3. نتیجه با ACO برای جدول 2

جدول 2. یک زمان‌بندیِ کارکنان نمونه – هشت پرواز

4. نتایج رایانشی

4.1. تنظیم پارامتر برای ACO

جدول 3. مقایسه‌ی ترکیب‌های مختلف پارامترها

4.2. نتایج تجربی

جدول 4. مقایسه‌ی نتایج زمان‌بندی

جدول 5. زمان CPU میانگین

5. نتیجه‌گیری
ترجمه کلمات کلیدی
- بهینه سازی کلونی مورچه - برنامه ریزی هواپیمایی خدمه - ازدحام هوش
کلمات کلیدی انگلیسی
ترجمه چکیده
زمانبندیِ کارکنان هواپیمایی یک مسئله‌ی بهینه‌سازیِ ترکیبیِ محدود NP سخت است، و سیستم زمان‌بندیِ کارکنان موثر برای کاهش هزینه‌های عملیاتی در صنعت هواپیمایی ضروری است. الگوریتم بهینه‌سازیِ کلونی مورچه (ACO) با موفقیت برای حل بسیاری مسائل بهینه‌سازیِ کلاسی و دشوار اعمال شده است، به ویژه در مسائل فروش مسافرت (TSP). بنابراین، این مقاله مسئله‌ی زمان‌بندیِ کارکنان هواپیمایی را به صورت مسئله‌ی فروشنده‌ی در حال سفر فرمول‌بندی کرده و سپس برای حل آن الگوریتم بهینه‌سازیِ کلونی مورچه را پیشنهاد کرده است. عملکرد با انجام تست‌های رایانشی با توجه به موارد واقعی به عنوان مسئله‌های تست ارزیابی شده است. نتایج نشان داد که الگوریتم مبتنی بر ACO یک تکنیک احتمالی برای زمان‌بندیِ کارکنان هواپیمایی است.
ترجمه مقدمه
هزینه‌ی کارکنان، بعد از هزینه‌ی سوخت، برای عملیات‌های کاریر هواپیمایی ضروری است. زمان‌بندیِ اعضای تیم، که یعنی انتساب اعضا به یک پرواز و یا یک دوره‌ی زمانی، به مسئله‌ی زمان‌بندیِ کارکنان و مسئله‌ی وظایف کارکنان تقسیم شده است. هدف مسئله‌ی زمان‌بندیِ کارکنان این است که مجموعه‌ای از گروه‌بندی‌های ممکن را ایجاد کند که هزینه‌ی انتساب کل کارکنان را کاهش داده و همچنین زمان‌بندیِ پرواز مشخص، مسیرهای پرواز، اتحاد کارگری و قوانین دولتی، و سیاست خود شرکت را تحقق می‌دهد.برای مسائل وظیفه‌بندی، گروه‌بندی به اعضایی منتسب می‌شود که مهارت‌ها، تعطیلات و سایر نیازمندی‌های خود را مرتفع می‌کنند. این مثاله بر روی مسئله‌ی زمان‌بندیِ کارکنان متمرکز است، زیرا نتایج زمان‌بندیِ کارکنان در هزینه‌های عملیاتیِ کارکنان به صورت مستقیم و جدی تأثیرگذار است ((Yan & Chang, 2002. مسئله‌ی زمان‌بندیِ کارکنان هواپیمایی (ACSP) یک مسئله‌ی بهینه‌سازیِ ترکیبیِ دشواری است که قبلاً به صورت مجموعه‌ای از مسائل تأمینی (SCP) و یا مسائل پارتیشن‌بندی (SPP) مطرح می‌شدند و سپس از برنامه‌نویسیِ ریاضی و یا اکتشافی برای حل آن استفاده می‌شد. مطالعات بسیاری که به مسئله‌ی ACSP معطوف شده‌اند شامل این‌ها می‌شود (Gamache, Hertz, & Ouellet, 2007; Levine, 1996; Park & Ryu, 2006; Yan & Tu, 2002; Yan & Chang, 2002). با این همه، این رویکرد دارای چندین عیب است. ابتدا، این نوع رویکرد از نظر رایانشی اصلاً مطلوب نیست، به ویژه وقتی که تعداد پروازها زیاد باشد. دوم، رویکردهایی که از تکنیک‌های ساخت ستون استفاده می‌کنند معمولاً بهترین ستون‌ها را برای SCP یا SPP حفظ می‌کنند، اما گاهی اوقات ممکن است نیازمند این باشند که ستون‌ها را غیر بهینه کنند تا راه‌حل‌های بهتری ارائه شود. برای مسئله‌ی فوق، Ozdemir و Mohan (2001) رویکرد زمان‌بندیِ مبتنی بر پرواز را به ACSP اعمال کرده وسپس از الگوریتم ژنتیک برای حل آن استفاده کرده است. آزمایش‌های رایانه‌ای نشان می‌دهند که رویکرد زمان‌بندی می‌تواند نتایج بهتری نسبت به رویکرد SCP ارائه دهد. الگوریتم بهینه‌سازیِ کلونی مورچه (ACO) توسط Dorigo در سال 1992 پیشنهاد شد که یک رویکرد متااکتشافی برای مسائل بهینه سازیِ ترکیبی است. ACO که کولونیِ واقعیِ مورچه را با ویژگی‌های بازخورد واقعی تقلید می‌کند توسط پژوهشگران در حوزه‌ی بهینه سازی مورد توجه قرار گرفته است (Bonabeau, Dorigo, & Theraulaz, 1999; Dorigo, Di Caro, & Gambardella, 1999; Engelbrecht, 2005). پژوهشگران بسیاری در حوزه‌های مرتبط به موفقیت ACO را اعمال کرده‌اند تا بسیاری از مسائل بهینه‌سازیِ کلاسی و دشوار مانند مسائل فروشنده مسافر (TSP) (Dorigo & Gambardella, 1997; Wu, Zhao, Ren, & Quan, 2009)، مسائل انتساب درجه‌ی دوم (QAP) (Maniezzo & Colorni, 1999)، مسائل تحقق محدودیت (CSP) (Solnon, 2002) و مسائل چند وجهی (Tosarl, 2009) را حل کنند. هنگامی که مسائل زمان‌بندیِ کارکنان هواپیمایی به صورت مدل زمان‌بندیِ مبتنی بر پرواز فرمول‌بندی می‌شود، می‌بینیم که این مدل به شکل مسئله‌ی فروشنده‌ی مسافر محدود (تحمیلی) است. بنابراین این مقاله ACO را پیشنهاد می‌کند تا مسئله‌ی زمان‌بندیِ کارکنان هواپیمایی را با اعمال بازنمود زمان‌بندیِ مبتنی بر پرواز را حل کرده و سعی می‌کند نزدیک‌ترین مسیر از گراف پرواز مانند TSP را جست‌وجو کند. نتایج ارزیابیِ عملکردی نشان می‌دهد که ACO یک الگوریتم اکتشافیِ موثر و بهینه برای به حداقل رسانیِ کل هزینه‌های کارکنان با پروازهای زمان‌بندی است که اقامت شبانه در هتل‌ها، زمان‌های مرده و زمان انتظار برای حل زمان‌بندیِ کارکنان را کاهش می‌دهد. ادامه‌ی مقاله به این صورت سازمان یافته است. بخش 2 محدودیت‌ها و تابع هزینه‌ی مسائل زمان‌بندیِ کارکنان هواپیمایی را توصیف می‌کند. بخش 3 جزئیات الگوریتم مبتنی بر ACO را ارائه می‌کند که مسئله‌ی زمان‌بندیِ کارکنان هواپیمایی را حل می‌کند. در بخش 4 تحلیل عملکردیِ الگوریتم مبتنی بر ACO ارائه می‌شود. در نهایت در بخش 5 نتیجه‌گیری انجام شده و پیشنهادات برای پژوهش‌های آینده ارائه شده است.
پیش نمایش مقاله
پیش نمایش مقاله الگوریتم مبتنی بر بهینه‌سازیِ کلونی مورچه برای مسئله‌ی زبمان‌بندیِ کارکنان هواپیمایی

چکیده انگلیسی

Airline crew scheduling is an NP-hard constrained combinatorial optimization problem, and an effective crew scheduling system is essential for reducing operating costs in the airline industry. Ant colony optimization algorithm (ACO) has successfully applied to solve many difficult and classical optimization problems especially on traveling salesman problems (TSP). Therefore, this paper formulated airline crew scheduling problem as Traveling Salesman Problem and then introduce ant colony optimization algorithm to solve it. Performance was evaluated by performing computational tests regarding real cases as the test problems. The results showed that ACO-based algorithm can be potential technique for airline crew scheduling.

مقدمه انگلیسی

Crew cost, second to fuel cost is essential to airline carrier operations. The scheduling of crew members, which is the assignment of crew members to a flight for some period of time, is generally divided into crew scheduling problem and crew rostering problem. The objective of crew scheduling problem is to construct a set of feasible pairings that minimizes the total crew assigning cost and also satisfies the given flight schedule, the fleet routes, labor union and government regulations, and the company’s own policy. For rostering problems, the pairings are assigned to crew members that satisfy their skills, vacations, and other requirements. This paper focuses on the problem of crew scheduling problem because crew scheduling results influence crew operating costs seriously and directly (Yan & Chang, 2002). Airline crew scheduling problem (ACSP) is a difficult combinatorial optimization problem that is traditionally formulated as the set cover problem (SCP) or the set partition problem (SPP) and then used heuristic or mathematic programming to solve it. The vast studies applied this approach to ACSP include (Gamache et al., 2007, Levine, 1996, Park and Ryu, 2006, Yan and Tu, 2002 and Yan and Chang, 2002). However, this approach has significant drawbacks. First, such an approach is computationally unsatisfactory, especially when the number of flights is large. Second, approaches using column generation techniques attempt to keep the best columns for SCP or SPP but may sometimes need suboptimal columns to produce better solution. For above question, Ozdemir and Mohan (2001) applied flight-based scheduling approach to ACSP and then used Genetic Algorithms to solve. The computational experiments showed that the flights scheduling approach can get better results than the SCP-based approach. Ant colony optimization (ACO) algorithm that was proposed by Dorigo in 1992 is a meta-heuristic for combinatorial optimization problems. ACO that mimics a real ant colony with positive feedback characteristics has been noticed by researchers in the field of optimization (Bonabeau et al., 1999, Dorigo et al., 1999 and Engelbrecht, 2005). Many researchers in related fields have successfully applied ACO to solve many difficult and classical optimization problems such as the traveling salesman problems (TSP) (Dorigo and Gambardella, 1997 and Wu et al., 2009), quadratic assignment problems (QAP) (Maniezzo & Colorni, 1999) constraint satisfaction problems (CSP), (Solnon, 2002) and multimodal problems (ToksarI, 2009). When airline crew scheduling problems formulate as flight-based scheduling model, we find that this model is actually in the same form as the Traveling Salesman Problem with constrained. Therefore, this paper proposed ACO to solve airline crew scheduling problem by applying the flight-based scheduling representation and attempt to search shortest path from the flight graph such as TSP. The performance evaluation results indicate that ACO is an effective and efficient heuristic algorithm to minimize the total crew costs by effectively scheduling flights to reduce overnight stay in hotels, deadhead times and sitting time for solving airline crew scheduling problems. The rest of this paper is organized as follows. Section 2 describes the constraints and cost function of our optimizing airline crew scheduling problems. Section 3 present details of the ACO-based algorithm solving the airline crew scheduling problem. In Section 4 the analysis of the performance of ACO-base algorithm is provided. Conclusions are finally drawn in Section 5, along with recommendations for future research.

نتیجه گیری انگلیسی

In this paper, a powerful and robust algorithm which is based on ant colonies, that is used to solve airline crew scheduling problems is proposed. Performance of the proposed ACO-based algorithm is examined on real cases of airline companies. When compared with the GA used to solve airline crew scheduling problem, results show that the ACO-based algorithm has a noticeable performance to minimize the total crew costs by effectively scheduling flights to reduce overnight stay in hotels, deadhead times and sitting time for airline companies. A further study will be done on that to expand the ACO-based algorithm to consider the habits and requirements of crew members to increase satisfaction of crew members.

دانلود فوری مقاله + ترجمه آماده
پس از پرداخت، فوراً می توانید مقاله را دانلود فرمایید.