Hub-and-spoke systems have wide applications ranging in airline transportation, freight
transportation, urban traffic, postal delivery, telecommunications and distribution in supply
chains. These systems are usually characterized by stochastic demand and congestion, which
adversely affect the quality of service to customers. These systems are further characterized
by different classes of customers who need different levels of service. In this paper, we
study the problem of hub-and-spoke network design under conditions wherein customer
demands are stochastic and consignments from one class are served at hubs with priority
over those from the other class to maintain the different service levels required by them.
We present a model for designing a capacitated multiple allocation hub location problem
with a service level constraint, defined using the distribution of time spent at hubs, for
each priority class. The model seeks to determine the hub-and-spoke network design at
the minimum total cost, which includes the total fixed cost of equipping open hubs with
sufficient processing capacity and the variable transportation costs, subject to a service
level constraint for each consignment class. The network of hubs, given their locations,
is thus modeled as spatially distributed preemptive priority M/M/1 queues. The problem
is challenging to solve, especially in absence of any known analytical expression for the
sojourn time distribution of low priority customers in a preemptive priority M/M/1 queue.
To resolve this problem, we exploit the concavity of the sojourn time distribution of low
priority consignments to eliminate the non-linearity in their service level functions at the
expense of a large number of tangent hyperplanes, which are determined numerically using
matrix geometric method. The problem is solved to optimality using a cutting plane method.
Computational results based on the US Civil Aeronautics Board (CAB) data are provided.
The results show that an explicit account for service level constraints at hubs may result in a
significantly different network configuration. Further, it is interesting to note that increasing
the fraction of consignments that receive priority in service or/and that have a lower value
of the maximum threshold on sojourn time may not necessarily increase the total cost of
the network design.
