Transportation Science · 1985 · 178 citations · 0 references
BusinessDecision SciencesOperations ManagementOperations PlanningOperations ResearchOptimizationAssignment ProblemsBranch And BoundCombinatorial OptimizationInteger ProgrammingLayout OptimizationNetwork OptimizationAirport Terminal LayoutGate Opening OptimizationGate OperationsGate PlacementTerminal Layout Planning
The study aims to minimize passenger walking distances in the terminal by optimizing gate assignments. The authors compare two approaches—a linear‑programming relaxation of an integer program and a heuristic—using a real Toronto International Airport flight schedule to evaluate walking distances. The original assignment increased average walking distance by 32 % over the LP optimum; the heuristic achieved only 3.9 % higher than the optimum, ran in 3.4 s versus 386 s for the LP, and using the heuristic as a warm start reduced total CPU to 42 s.
The airport flight-to-gate assignment problem is solved using two methods: (1) a linear programming relaxation of an integer program formulation and (2) a heuristic. The objective is to minimize passenger walking distances within the airport terminal area through a judicious gate assignment policy. An actual flight schedule for an average day at Toronto International Airport is used to compare existing walking distances, obtained from the original assignment, with results from the two methods. The results indicated that the original assignment had a 32% higher average per passenger walking distance than the minimum possible distance given by the LP solution. The heuristic’s performance was near optimal; it gave an average walking distance which was only 3.9% greater than the minimum. Computation times for the heuristic are 3.4 CPU seconds per run, while the linear program consumes 386 seconds per run on an IBM 370/168. In addition, if the heuristic is solved first and its solution is used as an initial feasible basis for the LP relaxation of the IP, the total CPU used to obtain optimality is reduced to 42 seconds.