การแก้ปัญหาการจับคู่เที่ยวบินของสายการบินราคาประหยัดแบบมากวัตถุประสงค์โดยใช้วิธีเมตาฮิวริสติก
Article Sidebar
Main Article Content
บทคัดย่อ
การแก้ปัญหาการจับคู่เที่ยวบินของสายการบินราคาประหยัดแบบมากวัตถุประสงค์ จัดเป็นปัญหาแบบมากวัตถุประสงค์ (Many-Objective Optimization Problems: MaOPs) และเป็นปัญหาประเภทเอ็นพี-ฮาร์ด (Non-deterministic Polynomial Hard: NP-Hard) งานวิจัยนี้เสนออัลกอริทึมที่พัฒนาเพื่อแก้ปัญหาดังกล่าว ได้แก่วิธีการเชิงวิวัฒนาการแบบหลายวัตถุประสงค์โดยยึดหลักการจำแนก (Multi-Objective Evolutionary Algorithm based on Decomposition: MOEA/D) และวิธีเชิงพันธุกรรมแบบการจัดลำดับที่ไม่ถูกครอบงำ III (Non-dominated Sorting Genetic Algorithm III: NSGA-III) โดยพิจารณาวัตถุประสงค์จำนวน 5 วัตถุประสงค์ พร้อมกันดังนี้ เวลาว่างระหว่างเที่ยวบินน้อยที่สุด ปรับดุลภาระงานให้เท่าเทียมกัน เส้นทางการบินซ้ำน้อยที่สุด ระยะทางการบินแตกต่างกันน้อยที่สุด และจำนวนคู่นักบินน้อยที่สุด ผลการวิจัยพบว่า MOEA/D มีสมรรถนะด้านการลู่เข้าสู่กลุ่มคำตอบที่แท้จริง (GD) ด้านการลู่เข้าและความหลากหลายของกลุ่มคำตอบ (IGD) ด้านการกระจายของกลุ่มคำตอบที่ได้ (Spread) ด้านอัตราส่วนของคำตอบที่ไม่ถูกครอบงำเทียบกับกลุ่มคำตอบที่อัลกอริทึมหาได้ (RNDS1) ด้านอัตราส่วนของคำตอบที่ไม่ถูกครอบงำเทียบกับกลุ่มคำตอบที่ดีที่สุด (RNDS2) และด้านเวลาที่ใช้ในการค้นหาคำตอบ (CPU Time) ดีกว่า NSGA-III
Article Details
ลิขสิทธิ์เป็นของวารสารวิศวกรรมศาสตร์ มหาวิทยาลัยศรีนครินทรวิโรฒ
เอกสารอ้างอิง
2. Q. Zhang and H. Li MOEA/D: “A Multi-objective Evolutionary Algorithm Based on Decomposition,” IEEE Transactions on Evolutionary Computation, Vol. 11, no.6, pp.712-731, 2007.
3. D. Brockhoff and E Zitzler, “Objective reduction in evolutionary multi-objective optimization: Theory and applications,” Evolutionary computation, Vol. 17, no.2, pp. 135-166. 2009.
4. M. Deveci and N. C. Demirel, “Evolutionary algorithms for solving the airline crew pairing problem. Computers & Industrial Engineering, Vol.115, pp. 389-406. 2018.
5. K. Arayikanon and P. Chutima, “Solving cockpit crew scheduling problem of a low-cost airline using metaheuristics,” AIP Conference Proceedings, 2018, Vol. 2044, no.1.
6. W. Wattanapornprom et al., “Coincidence Algorithm for Combinatorial Optimisation and Its Applications,” IEEE Congress on Evolutionary Computation, 2009.
