طراحي برنامه پرواز و تخصيص ناوگان بر اساس الگوريتم هاي هوشمند اصلاح يافته

Schedule Design and Fleet Assignment Based on Modified Intelligent Algorithms

طراحي برنامه پرواز و تخصيص ناوگان دو زير مساله اصلي برنامه‌ريزي پرواز هستند كه بيشترين تاثير را در هزينه‌ها و سود هواپيمايي دارند. در اين مقاله، مساله يكپارچه طراحي برنامه پرواز و تخصيص ناوگان تشريح شده و يك الگوريتم‌ ژنتيك جهت حل اين مساله توسعه داده شده است. اين مساله چندين قيد داشته و كروموزوم‌هاي آن از نوع جايگشتي با طول متغير و چند لايه است. بنابراين ايجاد جمعيت اوليه تصادفي و استفاده از عملگرهاي معمول الگوريتم‌هاي تكاملي كارآمد نخواهد بود، زيرا احتمال امكان‌پذير بودن پاسخ‌ها بسيار كم است. براي اين منظور، تابع ايجاد جمعيت اوليه بر اساس مفهوم حلقه و عملگرهاي جديد تركيب و جهش ابداع شده‌اند. همچنين از يك الگوريتم ژنتيك در داخل حلقه اصلي، جهت بازهدايت بهينه مسافران استفاده شده است. چهار مدل‌ با تعداد فرودگاه و ناوگان مختلف به عنوان ورودي مساله تعريف شده و توسط الگوريتم‌هاي ژنتيك دو و سه جزيره‌اي مورد حل قرار گرفتند. نتايج نشان مي‌دهد كه در هر تكرار حلقه اصلي، پاسخ‌هايي امكان‌پذير به دست آمده و در پايان، بهبود مناسبي در هزينه‌ها ايجاد شده است. در مدل‌هاي بزرگتر، بهبود بيشتر در هزينه‌ها و اختلاف بيشتر ميان حالت دو و سه جزيره‌اي قابل مشاهده است. حالت سه جزيره‌اي پاسخ‌هاي بهتري را در زمان بيشتر نتيجه داده است. الگوريتم‌ توسعه داده شده موفق به يافتن جواب‌هاي امكان‌پذير بهينه شده است و در مسائل با ابعاد بالا كه امكان يافتن جواب بهينه با استفاده از روش‌هاي مرسوم مانند برنامه‌ريزي خطي وجود ندارد مي‌تواند كارامد باشد.

Flight schedule design and fleet assignment are the main sub problems of the airline schedule planning which have the most effect on the costs and profit of the airline. In this paper, integrated flight schedule design and fleet assignment problem is described and genetic algorithm has been developed to solve this problem. It has a number of constraints and multi-layer permutation chromosomes with variable length. So, creating the initial population randomly and use of customary operators of evolutionary algorithms will not be efficient since the probability of feasibility is very low. For this purpose, a new function based on loop concept to create an initial population and new crossover and mutation operators has been developed. A genetic algorithm has been used within the main loop to optimize the redirection of the passengers. Four models with different numbers of airports and fleets are created as an input for the problem which has been solved by two and three islands genetic algorithms. Results show that in each iteration of the main loop, feasible answers are obtained, and finally there was a proper improvement in the costs. In larger models, there is a better Improvement in the costs and more difference between two and three islands algorithms. Three islands mode results in a better solution within a longer time. The developed algorithm can successfully find feasible optimal solution and it can be used for high-dimensional problems in which there is no possibility of finding the optimal solution by using conventional methods such as MILP.