We consider a median location problem in the presence of two probabilistic line barriers on the plane under rectilinear distance. It is assumed that the two line barriers move on their corresponding horizontal routes uniformly. We first investigate different scenarios for the position of the line barriers on the plane and their corresponding routes, and then define the visibility and invisibility conditions along with their corresponding expected barrier distance functions. The proposed problem is formulated as a mixed-integer nonlinear programming model. Our aim is to locate a new facility on the plane so that the total weighted expected rectilinear barrier distance is minimized. We present efficient lower and upper bounds using the forbidden location problem for the proposed problem. To solve the proposed model, the Hooke and Jeeves algorithm (HJA) is extended. We investigate various sample problems to test the performance of the proposed algorithm and appropriateness of the bounds. Also, an empirical study in Kingston-upon-Thames, England, is conducted to illustrate the behavior and applicability of the proposed model.
Table 1. Literature review of facility location problems with probabilistic barriers
Invisible regions and their corresponding distance functions for
Table 3. Results for small and medium problems
Table 4. Results for large problems
Table 5. The Cartesian coordinates of the barrier routes
|||M. Amiri-Aref, R. Z. Farahani, M. Hewitt and W. Klibi, Equitable location of facilities in a region with probabilistic barriers to travel, Transportation Research Part E: Logistics and Transportation Review, 127 (2019), 66-85. doi: 10.1016/j.tre.2019.04.010.|
|||M. Amiri-Aref, N. Javadian, R. Tavakkoli-Moghaddam and M. B. Aryanezhad, The center location problem with equal weights in the presence of a probabilistic line barrier, International Journal of Industrial Engineering Computations, 2 (2011), 793-800. doi: 10.5267/j.ijiec.2011.06.002.|
|||M. Amiri-Aref, N. Javadian, R. Tavakkoli-Moghaddam and A. Baboli, A new mathematical model for the Weber location problem with a probabilistic polyhedral barrier, International Journal of Production Research, 51 (2013), 6110-6128. doi: 10.1080/00207543.2013.796422.|
|||M. Amiri-Aref, N. Javadian, R. Tavakkoli-Moghaddam, A. Baboli and S. Shiripour, The center location-dependent relocation problem with a probabilistic line barrier, Applied Soft Computing, 13 (2013), 3380-3391. doi: 10.1016/j.asoc.2013.01.022.|
|||M. Amiri-Aref, R. Zanjirani Farahani, N. Javadian and W. Klibi, A rectilinear distance location-relocation problem with a probabilistic restriction: Mathematical modelling and solution approaches, International Journal of Production Research, 54 (2016), 629-646. doi: 10.1080/00207543.2015.1013642.|
|||R. Batta, A. Ghose and U. S. Palekar, Locating facilities on the Manhattan metric with arbitrarily shaped barriers and convex forbidden regions, Transportation Sci., 23 (1989), 26-36. doi: 10.1287/trsc.23.1.26.|
|||M. Bischoff, T. Fleischmann and K. Klamroth, The multi-facility location-allocation problem with polyhedral barriers, Comput. Oper. Res., 36 (2009), 1376-1392. doi: 10.1016/j.cor.2008.02.014.|
|||M. Bischoff and K. Klamroth, An efficient solution method for Weber problems with barriers based on genetic algorithms, European J. Oper. Res., 177 (2007), 22-41. doi: 10.1016/j.ejor.2005.10.061.|
|||M. S. Canbolat and G. O. Wesolowsky, The rectilinear distance Weber problem in the presence of a probabilistic line barrier, European J. Oper. Res., 202 (2010), 114-121. doi: 10.1016/j.ejor.2009.04.023.|
|||P. M. Dearing, H. W. Hamacher and K. Klamroth, Dominating sets for rectilinear center location problems with polyhedral barriers, Naval Res. Logist., 49 (2002), 647-665. doi: 10.1002/nav.10038.|
|||P. M. Dearing, K. Klamroth and R. Segars, Planar location problems with block distance and barriers, Ann. Oper. Res., 136 (2005), 117-143. doi: 10.1007/s10479-005-2042-4.|
|||Y. Feng, S. Deb, G. G. Wang and A. H. Alavi, Monarch butterfly optimization: A comprehensive review, Expert Systems with Applications, 168 (2020), 114418.|
|||Y.-H. Feng and G.-G. Wang, Binary moth search algorithm for discounted 0-1 knapsack problem, IEEE Access, 6 (2018), 10708-10719. doi: 10.1109/ACCESS.2018.2809445.|
|||Y. Feng, G.-G. Wang, W. Li and N. Li, Multi-strategy monarch butterfly optimization algorithm for discounted 0-1 knapsack problem, Neural Computing and Applications, 30 (2018), 3019-3036. doi: 10.1007/s00521-017-2903-1.|
|||Y. Feng, X. Yu and G.-G. Wang, A novel monarch butterfly optimization with global position updating operator for large-scale 0-1 Knapsack problems, Mathematics, 7 (2019), 1056. doi: 10.3390/math7111056.|
|||L. Friebß, K. Klamroth and M. Sprau, A wavefront approach to center location problems with barriers, Ann. Oper. Res., 136 (2005), 35-48. doi: 10.1007/s10479-005-2037-1.|
|||H. W. Hamacher and S. Nickel, Classification of location models, Location Science, 6 (1998), 229-242. doi: 10.1016/S0966-8349(98)00053-9.|
|||A. A. Heidari, S. Mirjalili, H. Faris, I. Aljarah, M. Mafarja and H. Chen, Harris hawks optimization: Algorithm and applications, Future Generation Computer Systems, 97 (2019), 849-872. doi: 10.1016/j.future.2019.02.028.|
|||N. Javadian, R. Tavakkoli-Moghaddam, M. Amiri-Aref and S. Shiripour, Two meta-heuristics for a multi-period minisum location-relocation problem with line restriction, The International Journal of Advanced Manufacturing Technology, 71 (2014), 1033-1048. doi: 10.1007/s00170-013-5511-y.|
|||D. Kalyanmoy, Optimization for Engineering Design, Prentice Hall, New Delhi, 1988.|
|||I. N. Katz and L. Cooper, Facility location in the presence of forbidden regions, I: Formulation and the case of Euclidean distance with one forbidden circle, European J. Oper. Res., 6 (1981), 166-173. doi: 10.1016/0377-2217(81)90203-4.|
|||H. Kelachankuttu, R. Batta and R. Nagi, Contour line construction for a new rectangular facility in an existing layout with rectangular departments, European Journal of Operational Research, 180 (2007), 149-162. doi: 10.1016/j.ejor.2006.04.029.|
|||K. Klamroth, A reduction result for location problems with polyhedral barriers, European J. Oper. Res., 130 (2001), 486-497. doi: 10.1016/S0377-2217(99)00399-9.|
|||K. Klamroth, Planar Weber location problems with line barriers, Optimization, 49 (2001), 517-527. doi: 10.1080/02331930108844547.|
|||K. Klamroth, Single-Facility Location Problems with Barriers, Springer Series in Operations Research, 2002. doi: 10.1007/b98843.|
|||K. Klamroth, Algebraic properties of location problems with one circular barrier, European J. Oper. Res., 154 (2004), 20-35. doi: 10.1016/S0377-2217(02)00800-7.|
|||K. Klamroth and M. M. Wiecek, A bi-objective median location problem with a line barrier, Oper. Res., 50 (2002), 670-679. doi: 10.1287/opre.50.4.670.2857.|
|||R. C. Larson and V. O. Li, Finding minimum rectilinear distance paths in the presence of barriers, Networks, 11 (1981), 285-304. doi: 10.1002/net.3230110307.|
|||R. C. Larson and G. Sadiq, Facility locations with the Manhattan metric in the presence of barriers to travel, Oper. Res., 31 (1983), 652-669. doi: 10.1287/opre.31.4.652.|
|||J. Li, H. Lei, A. H. Alavi and G. G. Wang, Elephant herding optimization: Variants, hybrids, and applications, Mathematics, 8 (2020a), 1415.|
|||S. Li, H. Chen, M. Wang, A. A. Heidari and S. Mirjalili, Slime mould algorithm: A new method for stochastic optimization, Future Generation Computer Systems, 111 (2020b), 300-323. doi: 10.1016/j.future.2020.03.055.|
|||R. F. Love, J. G. Morris and G. O. Wesolowsky, Facilities location: Models and Methods, North Holland Publishing Company, New York, 1988.|
|||M. Miyagawa, Distributions of rectilinear deviation distance to visit a facility, European J. Oper. Res., 205 (2010), 106-112. doi: 10.1016/j.ejor.2009.12.002.|
|||M. Miyagawa, Rectilinear distance to a facility in the presence of a square barrier, Ann. Oper. Res., 196 (2012), 443-458. doi: 10.1007/s10479-012-1063-z.|
|||M. Miyagawa, Continuous location model of a rectangular barrier facility, Top, 25 (2017), 95-110. doi: 10.1007/s11750-016-0424-1.|
|||P. Nandikonda, R. Batta and R. Nagi, Locating a 1-center on a Manhattan plane with "arbitrarily" shaped barriers, Ann. Oper. Res., 123 (2003), 157-172. doi: 10.1023/A:1026175313503.|
|||M. Oğuz, T. Bektaş and J. A. Bennell, Multicommodity flows and Benders' decomposition for restricted continuous location problems, European J. Oper. Res., 266 (2018), 851-863. doi: 10.1016/j.ejor.2017.11.033.|
|||M. Oğuz, T. Bektaş, J. A. Bennell and J. Fliege, A modelling framework for solving restricted planar location problems using phi-objects, Journal of the Operational Research Society, 67 (2016), 1080-1096.|
|||M. A. Prakash, K. V. L. Raju and V. R. Raju, Facility location problems in the presence of mixed forbidden regions, International Journal of Applied Engineering Research, 13 (2018), 91-97.|
|||K. S. Prasad, C. S. Rao and D. N. Rao, Application of Hooke and Jeeves algorithm in optimizing fusion zone grain size and hardness of pulsed current micro plasma arc welded AISI 304L sheets, Journal of Minerals and Materials Characterization and Engineering, 11 (2012), 869-875. doi: 10.4236/jmmce.2012.119081.|
|||A. Sarkar, R. Batta and R. Nagi, Placing a finite size facility with a center objective on a rectangular plane with barriers, European Journal of Operational Research, 179 (2007), 1160-1176. doi: 10.1016/j.ejor.2005.08.029.|
|||S. Savaş, R. Batta and R. Nagi, Finite-size facility placement in the presence of barriers to rectilinear travel, Oper. Res., 50 (2002), 1018-1031. doi: 10.1287/opre.50.6.1018.356.|
|||S. Shiripour, I. Mahdavi, M. Amiri-Aref, M. Mohammadnia-Otaghsara and N. Mahdavi-Amiri, Multi-facility location problems in the presence of a probabilistic line barrier: A mixed integer quadratic programming model, International Journal of Production Research, 50 (2012), 3988-4008. doi: 10.1080/00207543.2011.579639.|
|||G. G. Wang, Moth search algorithm: A bio-inspired metaheuristic algorithm for global optimization problems, Memetic Computing, 10 (2018), 151-164.|
|||G. G. Wang, S. Deb and L. D. S. Coelho, Elephant herding optimization, In 2015 3rd International Symposium on Computational and Business Intelligence (ISCBI), IEEE, (2015), 1–5.|
|||G. G. Wang, S. Deb and L. D. S. Coelho, Earthworm optimisation algorithm: A bio-inspired metaheuristic algorithm for global optimisation problems, International Journal of Bio-Inspired Computation, 12 (2018), 1-22.|
|||G.-G. Wang, S. Deb and Z. Cui, Monarch butterfly optimization, Neural Computing and Applications, 31 (2019), 1995-2014. doi: 10.1007/s00521-015-1923-y.|
|||G. G. Wang, S. Deb, X. Z. Gao and L. D. S. Coelho, A new metaheuristic optimisation algorithm motivated by elephant herding behavior, International Journal of Bio-Inspired Computation, 8 (2016), 394-409.|
|||G. G. Wang and Y. Tan, Improving metaheuristic algorithms with information feedback models, IEEE Transactions on Cybernetics, 49 (2017), 542-555. doi: 10.1109/TCYB.2017.2780274.|
|||A. Weber, Über den Standort der Industrien, Teil I: Reine Theorie des Standorts, JCB Mohr, Tübingen, (English ed. by CJ Friedrichs, Univ. Chicago Press, 1929), 1909.|
Two probabilistic line barriers on the plane.
Visibility and effectiveness conditions.
An example for
An example for
Presentation of the location problems of type
General steps of the proposed algorithm.
Gaps in terms of sample problems.
Solution times in terms of sample problems.
Representation of the empirical study and the obtained results.
Impact of lengths of the trains.