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.

Share

COinS
 
 

To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.