Chulalongkorn University Theses and Dissertations (Chula ETD)

เทคนิคคอลัมน์เจเนอเรชันสำหรับปัญหาจับคู่เที่ยวบิน

Other Title (Parallel Title in Other Language of ETD)

Column generation technique for crew pairing problem

Year (A.D.)

2012

Document Type

Thesis

First Advisor

บุญฤทธิ์ อินทิยศ

Second Advisor

ชวลิต จีนอนันต์

Faculty/College

Faculty of Science (คณะวิทยาศาสตร์)

Degree Name

วิทยาศาสตรมหาบัณฑิต

Degree Level

ปริญญาโท

Degree Discipline

คณิตศาสตร์ประยุกต์และวิทยาการคณนา

DOI

10.58837/CHULA.THE.2012.807

Abstract

ปัญหาการจับคู่เที่ยวบินเป็นปัญหาของการสร้างคู่เที่ยวบิน โดยมีลำดับเที่ยวบินที่เริ่มและจบที่ฐานการบินเดียวกัน และเป็นไปตามเงื่อนไขบังคับ โดยให้มีค่าใช้จ่ายน้อยที่สุด ปัญหาดังกล่าวเป็นปัญหาการหาค่าเหมาะที่สุดเชิงการจัดที่มีขนาดใหญ่ ซับซ้อนและยากในการหาคำตอบ ในบทความวิจัยนี้ได้นำเสนอตัวแบบทางคณิตศาสตร์สำหรับปัญหาการจับคู่เที่ยวบินโดยใช้เงื่อนไขบังคับเกี่ยวกับระยะเวลาการทำงานและการพักของพนักงานสายการบินจากบริษัทการบินไทย ในการหาคำตอบเราเสนอการใช้เทคนิคคอลัมน์เจเนอเรชันซึ่งเป็นเทคนิคที่มีประสิทธิภาพในการแก้ปัญหาที่มีขนาดใหญ่โดยการแก้ปัญหาย่อยอย่างซ้ำๆจนกระทั่งได้ผลเฉลยของปัญหาเดิม นอกจากนี้เรายังนำเสนอผลการคำนวณเชิงตัวเลขและการวิเคราะห์ผลโดยใช้ตัวอย่างข้อมูลจากการบินไทยเป็นกรณีศึกษา

Other Abstract (Other language abstract of ETD)

A crew pairing problem is a problem of creating the sequences of flights that start and end at the same crew base under some constraints while minimizing the cost. This is a large-scaled combinatorial optimization problem and it is complex and difficult to solve. In this paper, a mathematical model for a crew pairing problem is presented using the working time and rest time constraints from Thai Airways. We propose a column generation technique, which is a powerful technique for solving large-scale problems by iteratively solving smaller parts of the problem until the whole problem is solved. Some numerical results are also presented and analyzed using the data sample from Thai Airways as a case study.

Link to Full Text

Share

COinS