学术活动

当前位置:首页  学术活动

学术前沿讲座——Integrated Airline Crew Pairing and Rostering Problem: Column-and-Row Generation vs. Benders Decomposition

发布时间:2023-03-22访问量:270


报告题目

Integrated Airline Crew Pairing and Rostering Problem: Column-and-Row Generation vs. Benders Decomposition

报告人(单位)

梁哲 教授(同济大学)

主持人(单位)

李泳臻(东南大学)

会议时间

2023032415:00

会议地点

腾讯会议直播链接:

https://meeting.tencent.com/l/Mw7tWc2gjhPn

提醒:请参会者以真名进入,否则可能会被移出会议!

报告人简介

Zhe Liang, Professor in Department of Management Science & Engineering, Tongji University, Shanghai, China. He received his BEng from the Department of Computer Engineering at the National University of Singapore in 2001, and his Ph.D. from Department of Industrial and Systems Engineering of Rutgers University in 2011. His research focuses on the design and implementation of exact and heuristic algorithms for large-scale optimization problems in logistics and transportation, especially in Aviation Management. He has more than 40 cited publications, including papers that appeared in journals such as INFORMS Journal on Computing, Transportation Science, Transportation Research Part B, and others. He has been funded by the National Science Foundation of China, Ministry of Education of China, and Ministry of Science and Technology of China. The systems and algorithms designed by his team have been used in dozens of airlines and airports.


报告内容提要

Crew scheduling is one of the most critical tasks for airlines. A common strategy for solving the crew scheduling problem is to divide it into two sequential subproblems: a crew pairing problem followed by a crew rostering problem. It is widely acknowledged that the sequential approach would lead to suboptimal solutions. In this paper, we first present a nested integrated model and a nested column-and-row generation framework to solve the two problems simultaneously. Furthermore, we propose three strategies to improve the performance of the column-and-row-based approach: we combine the intermediate variable-generating subproblem and row-generating subproblem into a single subproblem to generate more effective columns and rows than generic column-and-row generation algorithm; we tighten the reduced costs of variables by using the duals of the most elementary constraints rather than directly related constraints; we design a flexible switch mechanism among all types of subproblems to alleviate the long tail effect of the column generation procedures. We carry out computational experiments using real-world data from a regional Chinese carrier. Our results indicate that the solution quality can be significantly improved within a reasonable time. We also compare the column-and-row generation method to the widely-used Benders decomposition method, and show that the column-and-row generation method outperforms Benders decomposition method both theoretically and computationally, and this statement can be applied to a wide range of nested decision problems, because it can fully utilize all relevant information to achieve faster convergence.




返回原图
/