Chulalongkorn University Theses and Dissertations (Chula ETD)
Other Title (Parallel Title in Other Language of ETD)
Solving many-objective cockpit crew pairing problem of low-cost airline
Year (A.D.)
2019
Document Type
Thesis
First Advisor
ปารเมศ ชุติมา
Faculty/College
Faculty of Engineering (คณะวิศวกรรมศาสตร์)
Department (if any)
Department of Industrial Engineering (ภาควิชาวิศวกรรมอุตสาหการ)
Degree Name
วิศวกรรมศาสตรมหาบัณฑิต
Degree Level
ปริญญาโท
Degree Discipline
วิศวกรรมอุตสาหการ
DOI
10.58837/CHULA.THE.2019.1312
Abstract
ปัญหาการจับคู่เที่ยวบินของสายการบินราคาประหยัดแบบมากวัตถุประสงค์ จัดเป็นปัญหาแบบมากวัตถุประสงค์ และเป็นปัญหาประเภทเอ็นพี-ฮาร์ด งานวิจัยนี้เสนออัลกอริทึมที่พัฒนาเพื่อแก้ปัญหาดังกล่าว ได้แก่วิธีการเชิงวิวัฒนาการแบบหลายวัตถุประสงค์โดยยึดหลักการจำแนก (Multi-Objective Evolutionary Algorithm based on Decomposition: MOEA/D) วิธีเชิงพันธุกรรมแบบการจัดลำดับที่ไม่ถูกครอบงำ III (Non-dominated Sorting Genetic Algorithm III: NSGA-III) และวิธีการเชิงวิวัฒนาการโดยใช้ผลต่างแบบหลายวัตถุประสงค์ (A Multi-Objective Differential Evolution Algorithm: MODE) โดยพิจารณาวัตถุประสงค์จำนวน 5 วัตถุประสงค์ พร้อมกันดังนี้ เวลาว่างระหว่างเที่ยวบินน้อยที่สุด ปรับดุลภาระงานให้เท่าเทียมกัน เส้นทางการบินซ้ำน้อยที่สุด ระยะทางการบินแตกต่างกันน้อยที่สุด และจำนวนคู่นักบินน้อยที่สุด ผลการวิจัยพบว่า MOEA/D มีสมรรถนะด้านการลู่เข้าของคำตอบ (GD) ด้านการลู่เข้าและความหลากหลายของคำตอบ (IGD) ด้านอัตราส่วนของจำนวนคำตอบที่ไม่ถูกครอบงำเทียบกับจำนวนคำตอบที่อัลกอริทึมหาได้ (RNDS I) ด้านอัตราส่วนของจำนวนคำตอบที่ไม่ถูกครอบงำเทียบกับจำนวนคำตอบที่แท้จริง (RNDS II) และด้านเวลาในการดำเนินงาน (CPU Time) ที่ดีกว่า NSGA-III และ MODE ในปัญหาขนาดเล็กและกลาง แต่ MOEA/D มีสมรรถนะด้านอัตราส่วนของจำนวนคำตอบที่ไม่ถูกครอบงำเทียบกับจำนวนคำตอบที่อัลกอริทึมหาได้ (RNDS I) พอกับ NSGA-III ในปัญหาขนาดใหญ่ โดยรวม MOEA/D มีสมรรถนะที่ดีกว่า NSGA-III และ MODE ในทุกๆ ด้าน ทั้งปัญหาขนาดเล็ก กลาง และใหญ่
Other Abstract (Other language abstract of ETD)
Many-objective cockpit crew pairing problem of low-cost airline is classified as many- objective optimization problems (MaOPs) and non-deterministic polynomial hard (NP-Hard). The purpose of research is to compare the efficiency of two algorithms as follows multi-objective evolutionary algorithm based on decomposition (MOEA/D) and non-dominated sorting genetic algorithm III (NSGA-III). The objectives considered in this research are minimizing idle time, balancing workload, minimizing repeat flight leg, minimizing the difference of nautical mile between each flight code, and minimizing number of pairs of cockpit crews. The experiments show that MOEA/D outperforms NSGA-III and MODE in terms of GD, IGD, RNDS I, RNDS II, and CPU Time for small and medium size problems conversely, MOEA/D is equivalent to NSGA-III in term of RNDSI for large problem size. Overall, MOEA/D has better performance than NSGA-III and MODE in every algorithm performance measurement for small, medium, and large size problems.
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Recommended Citation
กฤษณพันธุ์, ณิชา, "การแก้ปัญหาการจับคู่เที่ยวบินของสายการบินราคาประหยัดแบบมากวัตถุประสงค์" (2019). Chulalongkorn University Theses and Dissertations (Chula ETD). 9688.
https://digital.car.chula.ac.th/chulaetd/9688