Median location problem with two probabilistic line barriers: Extending the Hook and Jeeves algorithm

Saber Shiripour; Nezam Mahdavi-Amiri

doi:10.3934/jimo.2021128

Article Contents

2022, Volume 18, Issue 5: 3613-3639. Doi: 10.3934/jimo.2021128

This issue Previous Article The impacts of digital content piracy and copyright protection policies when consumers are loss averse Next Article Investigating a green supply chain with product recycling under retailer's fairness behavior

Median location problem with two probabilistic line barriers: Extending the Hook and Jeeves algorithm

Saber Shiripour^1, , and
Nezam Mahdavi-Amiri^2,

1.
Faculty of Engineering, University of Garmsar, Garmsar, Iran
2.
Faculty of Mathematical Sciences, Sharif University of Technology, Tehran, Iran

^* Corresponding author: Saber Shiripour
^* Corresponding author: Saber Shiripour

Received: October 2020

Revised: April 2021

Early access: August 2021

Published: November 2022

Abstract Full Text(HTML) Figure(13) / Table(5) Related Papers Cited by

Abstract

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.

Keywords:

Mathematics Subject Classification: Primary: 90-10; Secondary: 90C59.

Citation:

Full Text(HTML)

Figure 1. Two probabilistic line barriers on the plane.

Download: Full-size image PowerPoint slide

Figure 2. Visibility and effectiveness conditions.

Download: Full-size image PowerPoint slide

Figure 3. Examples for $ (x_{s1},x_{s2})\in \psi _1 $.

Download: Full-size image PowerPoint slide

Figure 4. Examples for $ (x_{s1},x_{s2})\in \psi _2 $.

Download: Full-size image PowerPoint slide

Figure 5. Examples for $ (x_{s1},x_{s2})\in \psi _3 $.

Download: Full-size image PowerPoint slide

Figure 6. An example for $ (x_{s1},x_{s2})\in \psi _4 $.

Download: Full-size image PowerPoint slide

Figure 7. An example for $ (x_{s1},x_{s2})\in \psi _5 $.

Download: Full-size image PowerPoint slide

Figure 8. Presentation of the location problems of type $ 1/\mathbb{R}^2/\mathcal{B} = 2ProbL/d_1/\sum $ and $ 1/\mathbb{R}^2/\mathcal{R}:\mathcal{B} = 2ProbL/d_1/\sum $.

Download: Full-size image PowerPoint slide

Figure 9. General steps of the proposed algorithm.

Download: Full-size image PowerPoint slide

Figure 10. Gaps in terms of sample problems.

Download: Full-size image PowerPoint slide

Figure 11. Solution times in terms of sample problems.

Download: Full-size image PowerPoint slide

Figure 12. Representation of the empirical study and the obtained results.

Download: Full-size image PowerPoint slide

Figure 13. Impact of lengths of the trains.

Download: Full-size image PowerPoint slide

Table 1. Literature review of facility location problems with probabilistic barriers

| Show Table

DownLoad: CSV

Table 2. Invisible regions and their corresponding distance functions for $ i\in \mathcal{I}_2 $

| Show Table

DownLoad: CSV

Table 3. Results for small and medium problems

| Show Table

DownLoad: CSV

Table 4. Results for large problems

| Show Table

DownLoad: CSV

Table 5. The Cartesian coordinates of the barrier routes

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	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.
[2]	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.
[3]	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.
[4]	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.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	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.
[10]	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.
[11]	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.
[12]	Y. Feng, S. Deb, G. G. Wang and A. H. Alavi, Monarch butterfly optimization: A comprehensive review, Expert Systems with Applications, 168 (2020), 114418.
[13]	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.
[14]	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.
[15]	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.
[16]	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.
[17]	H. W. Hamacher and S. Nickel, Classification of location models, Location Science, 6 (1998), 229-242. doi: 10.1016/S0966-8349(98)00053-9.
[18]	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.
[19]	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.
[20]	D. Kalyanmoy, Optimization for Engineering Design, Prentice Hall, New Delhi, 1988.
[21]	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.
[22]	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.
[23]	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.
[24]	K. Klamroth, Planar Weber location problems with line barriers, Optimization, 49 (2001), 517-527. doi: 10.1080/02331930108844547.
[25]	K. Klamroth, Single-Facility Location Problems with Barriers, Springer Series in Operations Research, 2002. doi: 10.1007/b98843.
[26]	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.
[27]	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.
[28]	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.
[29]	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.
[30]	J. Li, H. Lei, A. H. Alavi and G. G. Wang, Elephant herding optimization: Variants, hybrids, and applications, Mathematics, 8 (2020a), 1415.
[31]	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.
[32]	R. F. Love, J. G. Morris and G. O. Wesolowsky, Facilities location: Models and Methods, North Holland Publishing Company, New York, 1988.
[33]	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.
[34]	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.
[35]	M. Miyagawa, Continuous location model of a rectangular barrier facility, Top, 25 (2017), 95-110. doi: 10.1007/s11750-016-0424-1.
[36]	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.
[37]	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.
[38]	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.
[39]	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.
[40]	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.
[41]	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.
[42]	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.
[43]	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.
[44]	G. G. Wang, Moth search algorithm: A bio-inspired metaheuristic algorithm for global optimization problems, Memetic Computing, 10 (2018), 151-164.
[45]	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.
[46]	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.
[47]	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.
[48]	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.
[49]	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.
[50]	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.