| Assigning arriving/departing planes to gates is an intrinsic activity for airport operations throughout the world. In the literature, such a problem is referred to as the gate assignment problem (GAP).; The classical formulation of the gate assignment problem has focused on passenger satisfaction by finding ways to make gate-to-flight assignments such that the distance that all travelers have to walk in the airport is minimized (Braaksma, I977; Babic et al., 1984, Mangoubi and Maithasel, I985). Of particular interest is the convenience of the transfer passengers; the larger the number of passengers transferring from flight A to flight B, the greater is the benefit to assign their gates relatively closer to each other. This formulation results in a quadratic programming version of the problem, and as such poses challenges in solving the problem efficiently. It is well known that quadratic assignment problems (QAP) are NP-hard by nature, meaning that no algorithm is known to solve the problem within a time that is polynomially bounded in the size of the problem (in the case of GAP, number of planes, number of gates, conflict size level). Most previous approaches to the problem have either ignored the transfer passengers or have come up with a linearization of the problem to make it tractable (Mangoubi and Maithasel, I985, Sherali and Brown, I994). The few attempts at solving some other variants of the quadratic versions of this problem have experimented with only small sized problems.; In order to provide good alternative solutions to large sized problems actually encountered at airports, we propose to apply a set of three relatively new heuristics and to test their performance in solving the GAP. The set of heuristics consists of rollout algorithms (Bertsikas et al., I997), two versions of the beam search heuristics based on two branching rules schemes (Ow and Morton, 1988), and a multi-start tabu based/adaptive memory programming heuristic (Glover, 1977, 1989, 1990). The dynamic aspect in the GAP lends itself more freely to constructive type of algorithms, which motivated the choice of these particular heuristics.; The main incentive is to come up with a computationally viable way of explicitly solving the quadratic version of the gate assignment problem. Perhaps more interesting is the by product which should result from this research: the quadratic version of the GAP clearly encompasses a very large collection of practical operations kind of problems such as facility layout, warehouse docking, class scheduling problems, etc. If these heuristics do turn out to be efficient for the GAP, then they would also hold promise for other applications to similar problems as well.; An empirical study was conducted to study the performance of the above mentioned heuristics along three criteria: solution quality (average performance of the heuristics), computational time dimension, and robustness dimension (effect of various factors on performance variability). (Abstract shortened by UMI.)... |
