On the selection of hub airports for an airline hub-and-spoke system

We consider the 1-stop multiple allocation p-hub median problem. We formulate the problem as a p-median problem and propose a branch-and-bound algorithm and a greedy-type heuristic algorithm, We report computational results for problems with airline passenger interactions between 25 US cities in 1970 evaluated by the Civil Aeronautics Board. For further investigation, we made computational experiments with some random data. The obtained results also show that the proposed algorithms work better than the well-known nested-dual algorithm, particularly for relatively small problems. (C) 1999 Elsevier Science Ltd. All rights reserved.