A Bi-Objective Model for Location-Allocation Problem within Queuing Framework
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.
[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.
[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.
@article{"International Journal of Information, Control and Computer Sciences:63219", author = "Amirhossein Chambari and Seyed Habib Rahmaty and Vahid Hajipour and Aida Karimi", title = "A Bi-Objective Model for Location-Allocation Problem within Queuing Framework", 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", volume = "5", number = "6", pages = "681-8", }
