Capacitated Multiple Allocation Hub Location with Service Level Constraints for Multiple Consignment Classes

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 aff ect the quality of service to customers. These systems are further characterized by di fferent classes of customers who need di fferent 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 diff erent service levels required by them. We present a model for designing a capacitated multiple allocation hub location problem with a service level constraint, defi ned 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 signifi cantly diff erent network confi guration. 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.