MIP-based heuristics for solving robust gate assignment problems

• Published in: Computers & industrial engineering 2016-03, Vol.93, p.171-191
• Main Authors: Yu, Chuhang, Zhang, Dong, Lau, H.Y.K.
• Format: Article
• Language: English
• Subjects: Algorithms; Approximation; Assignment problem; Customer satisfaction; Diving; Gate assignment problem; Gates; Heuristic; Linear transformation; Mathematical models; MIP-based heuristics; Passenger satisfaction; Passengers; Quadratic programming; Robustness; Scheduling algorithms; Studies; Transportation problem (Operations research)
• ISSN: 0360-8352; 1879-0550
• DOI: 10.1016/j.cie.2015.12.013

•We transit the quadratic objective function to an equivalent linear one.•The first one to adapt general MIP solving methods to solve GAP.•Propose four methods for solving GAP.•Relationship between different objectives is analyzed. This paper considers the problem of robust gate assignment. Three factors having significant impact on gate assignment are considered: schedule robustness, facility and personnel cost during tows, and passenger satisfaction level. To precisely evaluate passenger satisfaction level, especially for transfer passengers, a model with quadratic terms is formulated. The quadratic model can exactly represent the traveling distance of transfer passengers, which cannot be precisely considered by traditional approximate models. However, the quadratic model is rather difficult to solve. Therefore, we then transform the model to an equivalent MIP model which is proven to be more efficient than the linearized models proposed in previous literature. In addition, in order to handle large size instances, we developed four different algorithms including diving, local branching, and relaxation induced neighborhoods (RINS), which are popular algorithms for solving general MIP models, together with a new algorithm which hybridizes the strength of RINS and diving. Extensive experiments are performed to compare the performance of the proposed algorithms.