Multiple-server facility location problem with stochastic demands along the network edges
Abstract
This paper investigates the network location problem for multiple-server facilities,which are subject to congestion. A number of facilities are to be selected among several candidate locations in order to satisfy customers’ demands. For each network edge, the corresponding customers are uniformly distributed along the edge, and their demands are generated according to the Poisson process. Furthermore, the number of servers in each established facility is considered as a decision variable, and the service time for each server follows an exponential distribution. Using queuing system analysis, a mathematical model is developed to minimize the customers’ aggregate expected traveling times and the aggregate expected waiting times. Since network location problems are NPhard, three metaheuristic algorithms including genetic algorithm, memetic algorithm, and simulated annealing are then investigated and developed to solve the proposed problem. The results of implementing the algorithms on some test problems demonstrate that the proposed memetic
algorithm outperforms theother two algorithms in terms of objective values.
References
Aboolian, R., Berman, O. & Drezner, Z. 2009. The multiple server center location problem. Annals of
Operations Research, 167(1):337–352.
Alp, O., Erkut, E. & Drezner, Z. 2003. An Efficient Genetic Algorithm for the p-Median Problem. Annals
of Operations Research, 122(1):21–42.
Arkat, J. & Jafari, R. 2016. Network Location Problem with Stochastic and Uniformly Distributed Demands.
International Journal of Engineering (IJE), TRANSACTIONS B: Applications, 29(5):654–662.
Berman, O. & Drezner, Z. 2007. The Multiple Server Location Problem. The Journal of the Operational
Research Society, 58(1):91–99.
Bieniek, M. 2015. A note on the facility location problem with stochastic demands. Omega, 55:53–60.
Boffey, B., Galvão, R. & Espejo, L. 2007. A review of congestion models in the location of facilities with
immobile servers. European Journal of Operational Research, 178(3):643–662.
Boloori Arabani, A. & Farahani, R.Z. 2012. Facility location dynamics: An overview of classifications and
applications. Computers & Industrial Engineering, 62(1):408–420.
Brimberg, J. & Drezner, Z. 2013. A new heuristic for solving the p-median problem in the plane. Computers
& Operations Research, 40(1):427–437.
Černý, V. 1985. Thermodynamical approach to the traveling salesman problem: An efficient simulation
algorithm. Journal of Optimization Theory and Applications, 45(1):41–51.
Eiben, A.E. & Smith, J.E. 2003. Introduction to Evolutionary Computing, Berlin, Heidelberg: Springer
Berlin Heidelberg.
Falah, A.H. & Khorshid, E.A. 2014. Optimum modeling of a flexible multi-bearing rotor system. Journal of
Engineering Research, 2(2):155–181.
Farahani, R. Z., Asgari, N., Heidari, N., Hosseininia, M.& Goh, M. 2012. Covering problems in facility
location: A review. Computers & Industrial Engineering, 62(1):368–407.
Garey, M.R. & Johnson, D.S. 1979. Computers and Intractability: A Guide to the Theory of NP-Completeness,
New York, NY, USA: W. H. Freeman & Co.
Gross, D., Shortle, J. F., Thompson, J. M.& Harris, C. M. 2008. Fundamentals of Queueing Theory 4th
ed., New York, NY, USA: Wiley-Interscience.
Hajipour, V., Rahmati, S. H. A., Pasandideh, S. H. R.& Niaki, S. T. A. 2014. A multi-objective harmony
search algorithm to optimize multi-server location–allocation problem in congested systems. Computers
& Industrial Engineering, 72:187–197.
Hale, T.S. & Moberg, C.R. 2003. Location Science Research: A Review. Annals of Operations Research,
(1):21–35.
Hamaguchi, T. & Nakadeh, K. 2010. Optimal Location of Facilities on a Network in Which Each Facility is
Operating as an M/G/1 Queue. Journal of Service Science and Management, 3(3):287–297.
Hodgson, M.J. 1990. A Flow-Capturing Location-Allocation Model. Geographical Analysis, 22(3):270–279.
Hu, D., Liu, Z.W. & Hu, W. 2013. Congestion service facilities location problem with promise of response
time. Mathematical Problems in Engineering, 2013(3):1–11.
Kariv, O. & Hakimi, S.L. 1979. An Algorithmic Approach to Network Location Problems. I: The p-Centers.
SIAM Journal on Applied Mathematics, 37(3):513–538.
Khodaparasti, M., Ganji, M., Amirgholipour, S.& Sharifi, A. M. 2016. A new multi-objective cluster
ensemble based on modularity maximization. Journal of Engineering Research, 4(2):1–16.
Kirkpatrick, S., Gelatt, C.D. & Vecchi, M.P. 1983. Optimization by Simulated Annealing. Science,
(4598):671–680.
Klose, A. & Drexl, A. 2005. Facility location models for distribution system design. European Journal of
Operational Research, 162(1):4–29.
Kuby, M., Lines, L., Schultz, R., Xie, Z., Kim, J.-G.& Lim, S. 2009. Optimization of hydrogen stations
in Florida using the Flow-Refueling Location Model. International Journal of Hydrogen Energy,
(15):6045–6064.
Kuby, M. & Lim, S. 2007. Location of Alternative-Fuel Stations Using the Flow-Refueling Location Model
and Dispersion of Candidate Sites on Arcs. Networks and Spatial Economics, 7(2):129–152.
Kumar, R. 2012. Blending Roulette Wheel Selection & Rank Selection in Genetic Algorithms. International
Journal of Machine Learning and Computing, 2(4):365–370.
Larson, R.C. 1974. A hypercube queuing model for facility location and redistricting in urban emergency
services. Computers & Operations Research, 1(1):67–95.
Larson, R.C. 1975. Approximating the Performance of Urban Emergency Service Systems. Operations
Research, 23(5):845–868.
Lozano, M., Herrera, F. & Cano, J.R. 2008. Replacement strategies to preserve useful diversity in steadystate
genetic algorithms. Information Sciences, 178(23):4421–4433.
Marianov, V. & Serra, D. 2011. Location of Multiple-Server Common Service Centers or Facilities, for
Minimizing General Congestion and Travel Cost Functions. International Regional Science Review,
(3):323–338.
Mladenović, N., Brimberg, J., Hansen, P.& Moreno-Pérez, J. A. 2007. The p-median problem: A survey of
metaheuristic approaches. European Journal of Operational Research, 179(3):927–939.
Moeini, M., Jemai, Z. & Sahin, E. 2015. Location and relocation problems in the context of the emergency
medical service systems: a case study. Central European Journal of Operations Research, 23(3):641–658.
Moré, J.J., Garbow, B.S. & Hillstrom, K.E. 1981. Testing Unconstrained Optimization Software. ACM
Trans. Math. Softw., 7(1):17–41.
Moscato, P. & Norman, M. 1992. A memetic approach for the traveling salesman problem implementation of
a computational ecology for combinatorial optimization on message-passing systems. Parallel computing
and transputer applications, 1(1):177–186.
Mousavi, S. M., Niaki, S. T. A., Mehdizadeh, E.& Tavarroth, M. R. 2013. The capacitated multi-facility
location–allocation problem with probabilistic customer location and demand: two hybrid meta-heuristic
algorithms. International Journal of Systems Science, 44(10):1897–1912.
Pasandideh, S.H.R. & Niaki, S.T.A. 2012. Genetic application in a facility location problem with random
demand within queuing framework. Journal of Intelligent Manufacturing, 23(3):651–659.
Pasandideh, S.H.R., Niaki, S.T.A. & Hajipour, V. 2013. A multi-objective facility location model with
batch arrivals: two parameter-tuned meta-heuristic algorithms. Journal of Intelligent Manufacturing,
(2):331–348.
Qin, J., Xiang, H., Ye, Y.& Ni, L. 2015. A Simulated Annealing Methodology to Multiproduct Capacitated
Facility Location with Stochastic Demand. The Scientific World Journal, 2015(1):1–9.
Rahmaniani, R. & Ghaderi, A. 2015. An algorithm with different exploration mechanisms: Experimental
results to capacitated facility location/network design problem. Expert Systems with Applications,
(7):3790–3800.
Rahmaniani, R., Saidi-Mehrabad, M. & Ashouri, H. 2013. Robust capacitated facility location problem:
Optimization model and solution algorithms. Journal of Uncertain Systems, 7(1):22–35.
Snyder, L. V. 2006. Facility location under uncertainty: a review. IIE Transactions, 38(7):547–564.
Tavakkoli-Moghaddam, R., Safaei, N. &Sassani, F. 2009. A memetic algorithm for the flexible flow line
scheduling problem with processor blocking. Computers & Operations Research, 36(2):402–414.
Wang, Q., Batta, R. & Rump, C.M. 2002. Algorithms for a Facility Location Problem with Stochastic
Customer Demand and Immobile Servers. Annals of Operations Research, 111(1):17–34.
Yeniay, Ö. 2005. Penalty function methods for constrained optimization with genetic algorithms. Mathematical
and Computational Applications, 10(1):45–56.
