Location models for airline hubs behaving as M/D/c queues
Introduction
Networks involving hubs are important in transportation and telecommunications. In both settings, when there is traffic between several origins and several destinations, there are economic benefits if this traffic is concentrated through some nodes and/or arcs of the network. A hub is a node of the network that concentrates traffic from several origins and distributes it to the final destinations. In multi-hub networks, the traffic is concentrated at a hub and sent from there to a second hub, which distributes it to the final destinations. The transportation between hubs is less expensive per unit flow than the transportation between a hub and a non-hub, because of the economies of scale. The problem is to find the least expensive hub network, given the traffic volumes between each origin–destination node pair (optimal selection of certain nodes as hubs). We focus on airline hubs.
As traffic increases, hub airports are more congested than non-hub airports, because they receive higher traffic levels. We propose models and solution methods for the hub location problem, when there is congestion at hub airports, for either designing new hub networks or optimally assigning new runways to the existing hub networks. Congestion at airports is hard to deal with, because of several issues. First of all, the arrival rate of the planes is highly variable throughout the day. Although flights follow a schedule, they are subject to delays at their origin airports and during the flight itself, which make their arrival non-deterministic. Secondly, although the service rate can be considered constant during short periods of time, it is also variable over longer periods, depending on weather conditions and the type of planes that are serviced. Also, since there are passengers transferring between flights, the service time for a flight may depend on the arrival time of other flights. Thus, service times are not independent and identically distributed. Finally, at their arrival to the airport, airplanes have to go through three stages of service: landing at a landing runway, service at a gate and departure through a take-off runway. Thus, the probabilistic distributions of these service times are very difficult to determine. Due to these issues, it is useless to develop detailed models of congestion for planning purposes, and approximation models are much more useful.
We analyze the queue formed by airplanes waiting for landing. Under certain assumptions, the analysis is applicable to take-off runways or combined landing–departure runways. We use a peak hour analysis, assuming that during the peak hour the average arrival rate and the service rate are both constant. This allows us to model an airport as an M/D/c queuing system, i.e. Poisson arrivals, deterministic service time and c servers. This election of probabilistic modeling is justified in the body of the paper. We state an analytic formula for the steady-state probabilities of different numbers of customers in an M/D/c system, found using an approach similar to the one used by Gross and Harris [1] for single server queues and Prabhu [2] for waiting time distributions. Later, we use this formula for the development of a deterministic equivalent of a probabilistic constraint in an integer optimization formulation for the location of congested hubs.
In the next section, we review briefly the related literature. We then develop the probabilistic analysis and the probabilistic constraint. Finally, we present the full model and show some computational experience obtained through the use of exact and heuristic algorithms together with an example.
Section snippets
Hubs
As opposed to what happens in other location problems, facilities (hubs) interact with each other. This interaction results in non-linear models (O'Kelly [3], [4], Aykin [5]), which can be linearized through the replacement of non-linear products in the objective by new variables (Campbell [6]) or through flow models, as in Ernst and Krishnamoorthy [7], [8]. Many models and algorithms have been proposed for the hub location problem, both on a plane and on a network. A good classification of the
Location of congested hubs, with a fixed number of runways at the hubs
In order to construct the optimal location model, we use a peak-hour analysis. This is a worst-case analysis, in the hope that improving the performance at peak hours will reduce also the queuing effects during off-peak time. We concentrate on the landing runways. Take-off runways could be assumed to behave in the same way as landing runways, only delayed by the service time at the gate. For the sake of clarity, we assume that there are different runways for landing and take-off, so the demand
Model for allocation of runways
If the number of runways at each airport must be optimized, new variables and parameters must be defined. The model is
HLRA2:In this model, the new variable yck is one if a hub with c runways is located at node k. Constraints , have the same meaning as , . Constraint (26) states that,
A heuristic procedure to solve the model
The models presented in the previous section, although linear, have thousands of variables and constraints for relatively small networks. Thus, traditional optimal solution methods such as linear programming plus branch and bound can become useless in terms of computing times. Furthermore, when using these methods, the number of branches is likely to increase dramatically because of the capacity constraints; see ReVelle [28]. Therefore, we offer a heuristic for the HLRA1 model.
For a fixed
Computational experience
In order to test the heuristic, we randomly generated 900 instances of a 30-node network, with traffic between nodes uniformly distributed in [0,5]. The right-hand side of the capacity-like constraint was set to 1200, 1400 and 1600 to see how the tightness of the constraint affects the solution of the algorithm. The transportation costs between vertices were obtained by computing their Euclidean distances. Savings in hub-to-hub transportation were set to 50%. Fixed costs were set to 10,000,
Examples using the CAB data set
The model was also applied to the standard hub location CAB data set, which corresponds to 25 US cities and can be downloaded from http://www.mscmga.ms.ic.ac.uk (Fig. 1). References to the source and prior results for these data can be found in O'Kelly et al. [31]. In this set, flows represent intercity passengers. Despite their size (not representative of airplane flows), note that by scaling the parameters of the problem, these flows can be used in our models without loss of generality. In
Conclusions
In this paper, a new hub location model has been formulated. This model locates hubs so as to minimize total (fixed and transportation) costs while taking into account congestion. The model also considers the number of runways to open in each hub. Two versions of the model are offered: in the first, the number of runways is fixed a priori, while in the second, the number of runways to open at each hub is determined by the model itself. The key feature of the model is the transformation of the
Acknowledgements
The authors gratefully acknowledge the careful work and valuable contributions made by the editor and three anonymous referees.
Vladimir Marianov is a Professor at the Department of Electrical Engineering at the Pontificia Universidad Católica de Chile. He earned his Ph.D. degree in 1989, in the Department of Geography and Environmental Engineering at the Johns Hopkins University (Baltimore). His interests include formulation and applications of models and algorithms for facility location, as well as the design and planning of telecommunications networks.
References (31)
A quadratic integer program for the location of interacting hub facilities
European Journal of Operational Research
(1987)Integer programming formulations of discrete hub location problems
European Journal of Operational Research
(1994)- et al.
Location of hubs in a competitive environment
European Journal of Operational Research
(1999) - et al.
On the single-assignment p-hub center problem
European Journal of Operational Research
(2000) - et al.
The capacitated multiple allocation hub location problem: formulations and algorithms
European Journal of Operational Research
(2000) Hub facility location with fixed costs
Papers in Regional Science: The Journal of the RSAI
(1992)Facility siting and integer friendly programming
European Journal of Operational Research
(1993)- et al.
Hub network with single and multiple allocation: a computational study
Location Science
(1996) - et al.
Fundamentals of queuing theory
(1974) Queues and inventories
(1965)
On the location of hub facilities
Transportation Science
Exact and heuristic algorithms for the uncapacitated multiple allocation p-hub median problem
European Journal of Operational Research
Solution algorithms for the capacitated single allocation hub location problem
Annals of Operations Research
Hub location and the p-hub median problem
Operations Research
Cited by (181)
The capacitated r-hub interdiction problem with congestion: Models and solution approaches
2024, Transportation Research Part E: Logistics and Transportation ReviewA stochastic hub location and fleet assignment problem for the design of reconfigurable park-and-ride systems
2024, Transportation Research Part E: Logistics and Transportation ReviewHub location with congestion and time-sensitive demand
2024, European Journal of Operational ResearchFifty Tears of Location Theory - A Selective Review
2024, European Journal of Operational ResearchMulti-period hub location problem considering polynomial time-dependent demand
2023, Computers and Operations ResearchMultiple allocation hub location with service level constraints for two shipment classes
2023, European Journal of Operational Research
Vladimir Marianov is a Professor at the Department of Electrical Engineering at the Pontificia Universidad Católica de Chile. He earned his Ph.D. degree in 1989, in the Department of Geography and Environmental Engineering at the Johns Hopkins University (Baltimore). His interests include formulation and applications of models and algorithms for facility location, as well as the design and planning of telecommunications networks.
Daniel Serra is professor of Management in the Department of Economics and Business, Universitat Pompeu Fabra (Barcelona, Spain). He earned his Ph.D. in 1989, in the Department of Geography and Environmental Engineering at the Johns Hopkins University (Baltimore). He has been working in the development and application of operations research models to logistic problems and to health care, with special emphasis on location and transportation modeling. He is also vice-chancellor of the Universitat Pompeu Fabra.
- 1
This research was partially funded by FONDECYT Research Grant No. 1980815.