Optimal Location of Facilities on a Network in Which Each Facility is Operating as an M/G/1 Queue

Abstract

In this paper, we consider a facility location problem in which customers and facilities are located on a network, and each facility is assumed to be operating as an M/G/1 queuing system. In many situations, the customer chooses the nearest facility to receive service. Customer satisfaction is evaluated by the probability of waiting less than or equal to a certain time for a customer that is chosen randomly from all customers who arrives to the system. By using a computational method for obtaining the probability on the waiting time, we propose the computational heuristic methods for finding the optimal location. Numerical results show the following. First, it is shown that the tabu search with an initial solution generated by random numbers gives the near-optimal solution with the highest probability among several algorithms. Second, the computation time and solution quality are not sensitive to the sharp of the service time distribution. Third, the computation time and solution quality are highly sensitive to the system utilization. Fourth, the complete enumeration might be the best solution methodology for highly utilized systems.