應用基因演算法於轉機組合最佳化之研究

Optimization on flights combination using genetic algorithm

陳琬婷(Wan-Ting Chen)

指導教授 ： 張淳智

國立臺中科技大學/資訊與流通學院/流通管理系碩士班/碩士(2016年)

摘要

近年來出國觀光旅遊是深受國人們喜愛的休閒活動，自助旅行也是受歡迎的出國旅遊方式之一，但是如遇天候不佳或是航班誤點時，又該如何選擇可替代之航班？因此本研究主要是針對考慮時間與成本兩個目標選擇飛航班機到達旅行目的地。
本研究使用基因演算法以單性生殖的演化方式，發展出一套演算法，並針對亞洲地區求解出兩國間航班的組合最佳化，使用柏拉圖的受支配個數法得到柏拉圖最佳解之前緣解集合，而研究結果顯示本研究所發展出的演算模式設定在母體大小50、演化代數800、突變率為0.2時可得到最佳化的解集合。
另外本研究發展之演算法除了應用於旅遊航線路徑規劃外，也可應用至其他不同的研究領域，像是國與國之間的海運承攬問題，或是貨物裝載以達到最佳載貨量之相關研究，用以達成現在這時代所講求的效率與品質兩者兼具，這也是目前國際貿易業者所要面臨之問題。

關鍵字

航班組合最佳化 ； 多目標規劃 ； 基因演算法 ； 柏拉圖最佳化

並列摘要

In recent years, travel abroad have become a popular activity for tourists and backpacking is among the most popular ways to do it. However, in the case of bad weather or flight delays, how should one choose an alternative flight? This research aims to find the answer to this problem under minimizing time and minimizing cost for choosing an alternative flight for a given travel destination.
The research used genetic algorithms to develop a solving algorithm that are based on the evolution of parthenogenesis. In addition, for combinatorial optimization of flights between two countries in Asia, Plato’s genetic algorithm for multi-objective optimization was used to determine the Pareto-optimal front solution set. The results show that the optimized setting of parameters for the algorithm developed by this research are 50 for the population size, 800 for the generation size, and 0.2 for the mutation rate.
Moreover, in addition to travel route planning, the proposed algorithm can be applied to other fields, such as solving freight forwarder problems or optimizing cargo loading. Our algorithm can balance between efficiency and quality, which are two important factors emphasized in this era and challenges to international traders.

並列關鍵字

Flights combination optimization ； Multi-objective programming ； Gene algorithm ； Pareto optimality

參考文獻

藍柏鼎（民94）。以基因演算求解航段指派為基之前艙機員與後艙組員排班問題。中原大學，桃園市。

梁新潁，陳彥儒，鐘國珍（民100）。具低運算量之改良型部分傳輸序列技術。朝陽科技大學，臺中市。

陳庭彰（民101）。利用危險值分佈流暢對進離場飛機產生最佳化排序。國立成功大學，臺南市。

鄭啟瑞（民98）。多機隊航空班表之擾動管理 - 利用不等式法為基礎的多目標基因演算法。國立成功大學，臺南市。

蔡宜衿（民100）。空服員排班問題之研究。長榮大學，臺南市。