A Bi-Objective Model for Location-Allocation Problem within Queuing Framework

Authors: Amirhossein Chambari, Seyed Habib Rahmaty, Vahid Hajipour, Aida Karimi

Abstract:

This paper proposes a bi-objective model for the facility location problem under a congestion system. The idea of the model is motivated by applications of locating servers in bank automated teller machines (ATMS), communication networks, and so on. This model can be specifically considered for situations in which fixed service facilities are congested by stochastic demand within queueing framework. We formulate this model with two perspectives simultaneously: (i) customers and (ii) service provider. The objectives of the model are to minimize (i) the total expected travelling and waiting time and (ii) the average facility idle-time. This model represents a mixed-integer nonlinear programming problem which belongs to the class of NP-hard problems. In addition, to solve the model, two metaheuristic algorithms including nondominated sorting genetic algorithms (NSGA-II) and non-dominated ranking genetic algorithms (NRGA) are proposed. Besides, to evaluate the performance of the two algorithms some numerical examples are produced and analyzed with some metrics to determine which algorithm works better.

Keywords: Queuing, Location, Bi-objective, NSGA-II, NRGA

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1082569

References:

[1] O. Al Jadaan, C. R. Rao, L. Rajamani, non-dominated ranked genetic algorithm for solving multi-objective optimization problems: NRGA. Journal of Theoretical and Applied Information Technology, 2, 60-67, 2008.
[2] O. Al Jadaan, C. R. Rao, L. Rajamani, improved selection operator GA. Journal of Theoretical and Applied Information Technology, 2, 269-277, 2008.
[3] R. Batta, J.M. Dolan, N. N. Krishnamurthy, The maximal expected covering location problem: Revisited. Transportation Science, 23, 277- 287, 1989.
[4] O. Berman, D. Krass, J.Wang, Locating service facilities to reduce lost demand. IIE Transactions, 38, 933 - 946, 2006.
[5] O. Berman, The maximizing market-size discretionary facility location problem with congestion. Socio-Economic Planning Sciences, 29, 39- 46, 1995.
[6] O. Berman, M. J. Hodgson, D. Krass, Flow-interception problems, in: Facility Location: A Survey of Applications and Methods, ed. Z. Drezner, Springer Series in Operations Research, 1995.
[7] O. Berman, R.C. Larson, S.S. Chiu, Optimal server location on a network operating as an M/G/1Queue. Operations Research, 33, 746- 771, 1985.O. Berman, R.C. Larson, N. Fouska, Optimal location of discretionary service facilities. Transportation Science, 26, 201-211, 1992.
[8] B. Boffey, R. Galvao, L. Espejo, A review of congestion models in the location of facilities with immobile servers.European Journal of Operational Research, 178, 643-662,2007.
[9] J. Current, M. Daskin, D. Schilling, discrete network location models, in: drezner, z., hamacher, h.w., (eds.), facility Location: applications and theory. Springer, Heidelberg, 14, 80-118, 2002.
[10] K. Deb, S. Agrawal, A. Pratap, T. Meyarivan, A fast elitist nondominated sorting genetic algorithm for multi-Objective Optimization: NSGA-II. In: Proceedings of the parallel problem solving from nature VI (PPSN-VI) conference, 849-858, 2000.
[11] D. Gross, C. M. Harris, Fundamental of queuing theory (3nd ed.). New York, NY: Wiley-Interscience, 1998.
[12] N. Gautam, Performance analysis and optimization of web proxy servers and mirror sites. European J Oper Res, 142, 396-418, 2002.
[13] M.J. Hodgson, A flow-capturing location-allocation model, geographical analysis, 22, 270 - 279, 1990.
[14] B. Li, , M.J. Golin, G. F. Italiano, X. Deng, K. Sohraby, On the optimal placement of web proxies in the Internet. Proc INFOCOM, 99, 1282- 1290, 1999.
[15] V. Marianov, M. Rios, A probabilistic quality of service constraint for a location model of switches in ATM Communications networks. Ann Oper Res 96, 237-243,2000.
[16] V. Marianov, d. Serra, Probabilistic maximal covering locationallocation for congested system. Journal of Regional Science, 38, 401- 424, 1998.
[17] S. H. R. Pasandideh, S. D. A. Niaki, Genetic application in a facility location problem with random demand within Queueing framework. J Intell Manuf, 21, 269-278, 2010.
[18] J. R. Schott, Fault tolerant design using single and multicriteria genetic algorithms optimization. Master-s thesis, Department of Aeronautics and Astronautics, Massachusetts Institute of Technology, Cambridge, MA, 1995.
[19] H. Shavandi, H. Mahlooji, A fuzzy queuing location model with a genetic algorithm for congested systems. Applied Mathematics and Computation, 181, 440-456, 2006.
[20] Q. Wang, R. Batta, C. M. Rump, Algorithms for a facility location problem with stochastic customer demand and immobile Servers. Annals of operations Research, 111, 17-34, 2002.
[21] O. Yeniay, B. Ankare, Penalty function methods for constrained optimization with genetic algorithms.Mathematical and computational application,10, 45-56, 2005.
[22] E. Zitzler, L. Thiele, Multiobjective optimization using evolutionary algorithms a comparative case study. In A. E.Eiben, T. Back, M. Schoenauer and H. P. Schwefel (Eds.), Fifth International Conference on Parallel Problem Solving from Nature (PPSN-V), Berlin, Germany, 292 - 30, 1998.