An M/M/c queue model for hub covering location problem

Abstract

The hub location problem appears in a variety of applications including airline systems, cargo delivery systems, and telecommunication network design. Hub location problems deal with finding the location of hub facilities and the allocation of demand nodes to these located hub facilities. We consider a hub-and-spoke network problem with crowdedness or congestion in the system. The transportation time and the rate of arrived trucks to each hub are random variables. In addition, a hub cannot service all trucks simultaneously and it has some restrictions like capacity constraint and the service time limitations. Hubs, which are the most crowded parts of network, are modeled as M/M/c queuing systems. In the application of the proposed model for a cargo transportation system, the number of trucks follows Poisson probability distribution in the queuing system. In this paper at first a nonlinear mathematical programming is presented to find an optimal solution for the considered problem. A probabilistic constraint is included to ensure that the probability of $b$ trucks in a queue is less than a threshold value $\theta$ for each hub. Then, we transfer the introduced nonlinear constraints of the mathematical programming model to the linear constraints. Due to the computational complexity of the resulted model, we propose an improved meta-heuristic based on Imperialist Competitive Algorithm and Genetic Algorithm to find near optimal solution of the problem. The performance of the solutions found by the proposed improved meta-heuristic is compared with those of pure GA and those of the mathematical programming model.