In this paper, we investigate FRB, which is the single facility Euclidean location problem in the presence of a (non-)convex polygonal forbidden region where travel and location are not permitted. We search for a new facility’s location that minimizes the weighted Euclidean distances to existing ones. To overcome the non-convexity and non-differentiability of the problem’s objective function, we propose an equivalent reformulation (RFRB) whose objective is linear. Using RFRB, we limit the search space to regions of a set of non-overlapping candidate domains that may contain the optimum; thus we reduce RFRB to a finite series of tight mixed integer convex programming sub-problems. Each sub-problem has a linear objective function and both linear and quadratic constraints that are defined on a candidate domain. Based on these sub-problems, we propose an efficient bounding-based algorithm (BA) that converges to a (near-)optimum. Within BA, we use two lower and four upper bounds for the solution value of FRB. The two lower and two upper bounds are solution values of relaxations of the restricted problem. The third upper bound is the near-optimum of a nested partitioning heuristic. The fourth upper bound is the outcome of a divide and conquer technique that solves a smooth sub-problem for each sub-region. We reveal via our computational investigation that BA matches an existing upper bound and improves two more.
Keywords: Facility location, Euclidean distance, forbidden region, reformulation, divide and conquer, nested partitioning
@article{RO_2021__55_1_141_0,
author = {Al-Mudahka, Intesar M. and Al-Jeraiwi, Marwa S. and M{\textquoteright}Hallah, Rym},
title = {Lower and upper bounds for the continuous single facility location problem in the presence of a forbidden region and travel barrier},
journal = {RAIRO. Operations Research},
pages = {141--165},
year = {2021},
publisher = {EDP-Sciences},
volume = {55},
number = {1},
doi = {10.1051/ro/2020024},
mrnumber = {4228690},
zbl = {1468.90067},
language = {en},
url = {https://www.numdam.org/articles/10.1051/ro/2020024/}
}
TY - JOUR AU - Al-Mudahka, Intesar M. AU - Al-Jeraiwi, Marwa S. AU - M’Hallah, Rym TI - Lower and upper bounds for the continuous single facility location problem in the presence of a forbidden region and travel barrier JO - RAIRO. Operations Research PY - 2021 SP - 141 EP - 165 VL - 55 IS - 1 PB - EDP-Sciences UR - https://www.numdam.org/articles/10.1051/ro/2020024/ DO - 10.1051/ro/2020024 LA - en ID - RO_2021__55_1_141_0 ER -
%0 Journal Article %A Al-Mudahka, Intesar M. %A Al-Jeraiwi, Marwa S. %A M’Hallah, Rym %T Lower and upper bounds for the continuous single facility location problem in the presence of a forbidden region and travel barrier %J RAIRO. Operations Research %D 2021 %P 141-165 %V 55 %N 1 %I EDP-Sciences %U https://www.numdam.org/articles/10.1051/ro/2020024/ %R 10.1051/ro/2020024 %G en %F RO_2021__55_1_141_0
Al-Mudahka, Intesar M.; Al-Jeraiwi, Marwa S.; M’Hallah, Rym. Lower and upper bounds for the continuous single facility location problem in the presence of a forbidden region and travel barrier. RAIRO. Operations Research, Tome 55 (2021) no. 1, pp. 141-165. doi: 10.1051/ro/2020024
[1] , and , Packing circles in the smallest circle: an adaptive hybrid algorithm. J. Oper. Res. Soc. 62 (2011) 1917–1930. | DOI
[2] and , Algorithms for Weber facility location in the presence of forbidden regions and/or barriers to travel. Transp. Sci. 28 (1994) 70–76. | Zbl | DOI
[3] and , An efficient solution method for Weber problems with barriers based on genetic algorithms. Eur. J. Oper. Res. 177 (2007) 22–41. | MR | Zbl | DOI
[4] and , Integer programming, edited by and . In: Search Methodologies: Introductory Tutorial in Optimization and Decision Support Techniques, Chapter 3. Springer, US (2005) 69–95. | DOI
[5] , Facility location in the presence of forbidden regions. Ph.D. thesis, Pennsylvania State University, University Park, PA (1994).
[6] and , An efficient algorithm for facility locations in the presence of forbidden regions. Eur. J. Oper. Res. 90 (1996) 56–70. | Zbl | DOI
[7] and , Facility location in the presence of congested regions with the rectilinear distance metric. Socio Econ. Plan. Sci. 31 (1997) 103–113. | DOI
[8] , A note on two problems in connection with graphs. Numer. Math. 1 (1959) 269–271. | MR | Zbl | DOI
[9] , Sensitivity analysis of the optimal location of a facility. Nav. Res. Log. Q. 32 (1985) 209–224. | MR | Zbl | DOI
[10] , and , Facility Layout and Location: An Analytical Approach. Prentice Hall, New York (1992).
[11] , , and , An efficient hybrid particle swarm optimization algorithm for solving the uncapacitated continuous location-allocation problem. Netw. Spat. Econ. 12 (2012) 421–439. | MR | Zbl | DOI
[12] and , An output-sensitive algorithm for computing visibility graphs. SIAM J. Comput. 20 (1991) 888–910. | MR | Zbl | DOI
[13] and , Planar Weber location problems with barriers and block norms. Ann. Oper. Res. 96 (2000) 191–208. | MR | Zbl | DOI
[14] and , Facility location in the presence of forbidden regions, II: Euclidean distance and several forbidden circles. Report OREM 79006, Department of Operations Research and Engineering Management, Southern Methodist University, Dallas, TX (1979).
[15] and , Facility location in the presence of forbidden regions, III: lp distance and polygonal forbidden regions. Report OREM 79006, Department of Operations Research and Engineering Management, Southern Methodist University, Dallas, TX (1979).
[16] and , Facility location in the presence of forbidden regions, I: formulation and the case of Euclidean distance with one forbidden circle. Eur. J. Oper. Res. 6 (1981) 166–173. | MR | Zbl | DOI
[17] , Algorithm for constrained Weber problem with feasible region bounded by arcs. Facta Univ. Ser.: Math. Inf. 28 (2013) 271–284. | MR | Zbl
[18] , Single-Facility Location Problems with Barriers. Springer Series in Operations Research. Springer, Berlin (2002). | MR | Zbl
[19] , A note on Fermat’s problem. Math. Program. 4 (1973) 98–107. | MR | Zbl | DOI
[20] , and , Facilities Location: Models and Methods. Elsevier, New York (1988). | MR | Zbl
[21] and , A global optimal approach to facility location in the presence of forbidden regions. Comput. Ind. Eng. 45 (2003) 1–15. | DOI
[22] , and , Facility location problems in the presence of mixed forbidden regions. Int. J. Appl. Eng. Res. 13 (2018) 91–97.
[23] , and , Facility location problems in the presence of single convex/non-convex polygonal barrier/forbidden region. Opsearch 41 (2004) 87–105. | MR | Zbl | DOI
[24] and , Shortest paths in Euclidean graphs. Algorithmica 1 (1986) 31–48. | MR | Zbl | DOI
[25] and , Equivalent primal and dual differentiable reformulations of the Euclidean multifacility location problem. IIE Trans. 30 (1998) 1065–1074. | DOI
[26] and , Solving Euclidean distance multi-facility location problems using conjugate subgradient and line-search methods. Comput. Optim. App. 14 (1999) 275–291. | MR | Zbl | DOI
[27] and , A new algorithm for stochastic discrete resource allocation optimization. Disc. Event Dyn. Syst. 10 (2000) 271–294. | MR | Zbl | DOI
[28] and , Optimal buffer allocation in production lines. IIE Trans. 35 (2003) 1–10. | DOI
[29] and , Nested partitions method for global optimization. Oper. Res. 48 (2000) 390–407. | MR | Zbl | DOI
[30] , and , A new hybrid optimization algorithm. Comput. Ind. Eng. 36 (1999) 409–426. | DOI
[31] , and , New parallel randomized algorithms for the traveling salesman problem. Comput. Oper. Res. 26 (1999) 371–394. | MR | Zbl | DOI
[32] , A Weiszfeld-like algorithm for a weber location problem constrained to a closed and convex set. Preprint arXiv:1204.1087 (2012).
[33] , and , Minimum trajectory pipe routing. J. Ship Res. 18 (1974) 46–49. | DOI
[34] , Sur le point par lequel la somme des distances de points donnés est minimum. Tohoku Math. J. 43 (1937) 355–386. | Zbl
Cité par Sources :
