×

zbMATH — the first resource for mathematics

Airport gate scheduling with time windows. (English) Zbl 1138.90397
Summary: In contrast to the existing airport gate assignment studies where flight have fixed schedules, we consider the more realistic situation where flight arrival and departure times can change. Although we minimize walking distances (or travel time) in our objective function, the model is easily adapted for other material handling costs including baggage and cargo costs. Our objectives are achieved through gate assignments, where time slots alloted to aircraft at gates deviate from scheduled slots minimally. Further, the model can be applied to cross-docking optimization in areas other than airports, such as freight terminals where material arrival times (via trucks, ships) can fluctuate. The solution approach uses insert and interval exchange moves together with a time shift algorithm. We then use these neighborhood moves in Tabu Search and Memetic Algorithms. Computational results are provided and verify that our heuristics work well in small cases and much better in large cases when compared with CPLEX solver.

MSC:
90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
68T05 Learning and adaptive systems in artificial intelligence
Software:
CPLEX; Tabu search
PDF BibTeX XML Cite
Full Text: DOI
References:
[5] Braaksma, J. & Shortreed, J. (1971). Improving Airport Gate Usage with Critical Path Method. Transportation Engineering Journal of ASCE 97 187-203.
[6] Cheng, Y. (1998a). Network-based Simulation of Aircraft at Gates in Airport Terminals. Journal of Transportation Engineering 188-196.
[8] Ding, H., Lim, A., Rodrigues, B. & Zhu, Y. (2003a). New Heuristics for the Over-constrained Flight to Gate Assignments. Journal of the Operational Research Society, to appear. · Zbl 1095.90067
[9] Ding, H., Lim, A., Rodrigues, B. & Zhu, Y. (2003b). The Over-constrained Airport Gate Assignment Problem. Computers & Operational Research, to appear. · Zbl 1075.90006
[10] Glover, F. & Laguna, M. (1997). Tabu Search. Kluwer Acadamic Publishers. · Zbl 0930.90083
[11] Goldberg, D. & Lingle, R. (1985). Alleles, Loci, and The Traveling Salesman Problem. · Zbl 0674.90095
[13] Holland, J. (1975). Adaptation in Natural and Artifical Systems. The University of Michigan Press.
[15] Moscato, P. (1989). On Evolution, Search, Optimization, Genetic Algorithms and Martial Arts: Towards Memetic Algorithms. Technical Report, Caltech Concurrent Computation Program, C#P Report 826.
[17] Oliver, I., Smith, D. & Holland, J. (1987). A Study of Permutation Crossover Operators on the TSP.
[20] Xu, J. & Bailey, G. (2001). The Airport Gate Assignment Problem: Mathematical Model and a Tabu Search Algorithm. In Proceedings of the 34th Hawaii International Conference on System Sciences-2001.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.