Multiple-server facility location problem with stochastic demands along the network edges

Mahmoud Golabi, Gokhan Izbirak, Jamal Arkat

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.


Keywords


Logistics; Facility location; Distributed demand; Queuing theory; Metaheuristics

Full Text:

PDF

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.


Refbacks

  • There are currently no refbacks.