Ding, H.; Lim, A.; Rodrigues, B.; Zhu, Y. New heuristics for over-constrained flight to gate assignments. (English) Zbl 1095.90067 J. Oper. Res. Soc. 55, No. 7, 760-768 (2004). Summary: We consider the over-constrained Airport Gate Assignment Problem where the number of flights exceed the number of gates available, and where the objectives are to minimize the number of ungated flights and the total walking distances. The problem is formulated as a binary quadratic programming problem. We design a greedy algorithm and use a Tabu Search meta-heuristic to solve the problem. The greedy algorithm minimizes ungated flights while we devise a new neighbourhood search technique, the Interval Exchange Move, which allows us flexibility in seeking good solutions, especially when flight schedules are dense in time. Experiments conducted give good results. Cited in 6 Documents MSC: 90B80 Discrete location and assignment 90C20 Quadratic programming Keywords:air transport; heuristics; tabu search PDF BibTeX XML Cite \textit{H. Ding} et al., J. Oper. Res. Soc. 55, No. 7, 760--768 (2004; Zbl 1095.90067) Full Text: DOI