zbMATH — the first resource for mathematics

A BSSS algorithm for the single facility location problem in two regions with different norms. (English) Zbl 1146.90465
Summary: Suppose the plane is divided by a straight line into two regions with different norms. We want to find the location of a single new facility such that the sum of the distances from the existing facilities to this point is minimized. This is in fact a non-convex optimization problem. The main difficulty is caused by finding the distances between points on different sides of the boundary line. In this paper we present a closed form solution for finding these distances. We also show that the optimal solution lies in the rectangular hull of the existing points. Based on these findings then, an efficient big square small square (BSSS) procedure is proposed.

90B85 Continuous location
90C26 Nonconvex programming, global optimization
Full Text: DOI
[1] Bazaraa, M.S.; Sherali, H.; Shetty, C.M., Nonlinear programming, (1993), John Wiley & Sons
[2] Bazaraa, M.S.; Sherali, H.; Jarvis, J., Linear programming and network flows, (2005), John Wiley & Sons · Zbl 1061.90085
[3] Brimberg, J.; Kakhki, H.T.; Wesolowsky, G.O., Location among regions with varying norms, Annals of operations research, 122, 87-102, (2003) · Zbl 1038.90048
[4] Brimberg, J.; Kakhki, H.T.; Wesolowsky, G.O., Locating a single facility in the plane in the presence of a bounded region and different norms, Journal of the operational research society of Japan, 48, 2, 135-147, (2005) · Zbl 1274.90192
[5] Dantzig, G.B.; Thapa, M.N., Linear programming 2: theory and extensions, (2003), Springer · Zbl 1029.90037
[6] Francis, R.L.; McGinnis, L.F.; White, J.A., Facility layout and location: an analytical approach, (1992), Prentice-Hall
[7] Hansen, P.; Peeters, D.; Thisse, J.-F., On the location of an obnoxious facility, Sistemi urbani, 3, 299-317, (1981)
[8] Hansen, P.; Peeters, D.; Richard, D.; Thisse, J-F., The minisum and minimax location problems revisited, Operations research, 33, 6, 1251-1265, (1985) · Zbl 0582.90027
[9] Love, R.F.; Morris, J.G.; Wesolowsky, G.O., Facilities location: models and methods, (1988), North-Holland · Zbl 0685.90036
[10] Luenberger, D., Linear and nonlinear programming, (1984), Addison-Wesley
[11] Mangasarian, O.L., Nonlinear programming, (1969), McGraw-Hill · Zbl 0194.20201
[12] McGarvey, R.G.; Cavalier, T.M., A global optimal approach to facility location in the presence of forbidden regions, Computers and industrial engineering, 45, 1-15, (2003)
[13] McGarvey, R.G.; Cavalier, T.M., Constrained location for competitive facilities in the plane, Computers and operations research, 359-378, (2005) · Zbl 1061.90074
[14] Parlar, M., Single facility location problem with region-dependent distance metrics, International journal of system science, 25, 3, 513-525, (1994) · Zbl 0801.90071
[15] Plastria, F., GBSSS: the generalized big square small square method for planar single-facility location, European journal of operational research, 62, 163-174, (1992) · Zbl 0760.90067
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.