×

An efficient solution method for Weber problems with barriers based on genetic algorithms. (English) Zbl 1111.90064

Summary: We consider the problem of locating one new facility with respect to a given set of existing facilities in the plane and in the presence of convex polyhedral barriers. It is assumed that a barrier is a region where neither facility location nor travelling are permitted. The resulting non-convex optimization problem can be reduced to a finite series of convex subproblems, which can be solved by the Weiszfeld algorithm in case of the Weber objective function and Euclidean distances. A solution method is presented that, by iteratively executing a genetic algorithm for the selection of subproblems, quickly finds a solution of the global problem. Visibility arguments are used to reduce the number of subproblems that need to be considered, and numerical examples are presented.

MSC:

90B80 Discrete location and assignment
90C26 Nonconvex programming, global optimization
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aneja, Y. P.; Parlar, M., Algorithms for Weber facility location in the presence of forbidden regions and/or barriers to travel, Transportation Science, 28, 70-76 (1994) · Zbl 0799.90072
[2] Batta, R.; Leifer, L. A., On the accuracy of demand point solutions to the planar, Manhattan metric, \(p\)-median problem, with and without barriers to travel, Computers and Operations Research, 15, 253-262 (1988) · Zbl 0638.90033
[3] Batta, R.; Ghose, A.; Palekar, U. S., Locating facilities on the Manhattan metric with arbitrarily shaped barriers and convex forbidden regions, Transportation Science, 23, 26-36 (1989) · Zbl 0672.90044
[4] Ben-Moshe, B., Katz, M.J., Mitchell, J.S.B., 2001. Farthest neighbors and center points in the presence of rectangular obstacles. In: Proceedings of the 17th ACM Symposium on Computational Geometry.; Ben-Moshe, B., Katz, M.J., Mitchell, J.S.B., 2001. Farthest neighbors and center points in the presence of rectangular obstacles. In: Proceedings of the 17th ACM Symposium on Computational Geometry. · Zbl 1377.68260
[5] Butt, S. E.; Cavalier, T. M., An efficient algorithm for facility location in the presence of forbidden regions, European Journal of Operational Research, 90, 56-70 (1996) · Zbl 0916.90177
[6] Choi, J.; Shin, C.-S.; Kim, S. K., Computing weighted rectilinear median and center set in the presence of obstacles, (Proceedings of the 9th Annual International Symposium on Algorithms and Computation. Proceedings of the 9th Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, vol. 1533 (1998), Springer-Verlag: Springer-Verlag Berlin), 29-38
[7] Dearing, P. M.; Hamacher, H. W.; Klamroth, K., Center problems with barriers and the Manhattan metric, Naval Research Logistics, 49, 647-665 (2002) · Zbl 1037.90044
[8] Fekete, S. P.; Mitchell, J. S.B.; Beurer, K., On the continuous Fermat-Weber problem, Operations Research, 53, 61-76 (2005) · Zbl 1165.90553
[9] Hamacher, H. W.; Klamroth, K., Planar location problems with barriers under polyhedral gauges, Annals of Operations Research, 96, 191-208 (2000) · Zbl 0997.90043
[10] Hamacher, H. W.; Nickel, S., Restricted planar location problems and applications, Naval Research Logistics, 42, 967-992 (1995) · Zbl 0845.90082
[11] Hansen, P.; Peeters, D.; Richard, D.; Thisse, J.-F., The minisum and minimax location problems revisited, Operations Research, 33, 1251-1265 (1985) · Zbl 0582.90027
[12] Hansen, P.; Jaumard, B.; Tuy, H., Global optimization in location, (Drezner, Z., Facility Location. Facility Location, Springer Series in Operations Research (1995)), 43-68
[13] Holland, J. H., Adaptation in Natural and Artificial Systems (1975), University of Michigan Press
[14] Katz, I. N.; Cooper, L., Facility location in the presence of forbidden regions, I: Formulation and the case of Euclidean distance with one forbidden circle, European Journal of Operational Research, 6, 166-173 (1981) · Zbl 0451.90042
[15] Klamroth, K., Planar Weber location problems with line barriers, Optimization, 49, 517-527 (2001) · Zbl 0995.90065
[16] Klamroth, K., A reduction result for location problems with polyhedral barriers, European Journal of Operational Research, 130, 486-497 (2001) · Zbl 0981.90042
[17] K. Klamroth, Single-Facility Location Problems with Barriers, Springer Series in Operations Research, 2002.; K. Klamroth, Single-Facility Location Problems with Barriers, Springer Series in Operations Research, 2002. · Zbl 1027.90055
[18] Klamroth, K., Algebraic properties of location problems with one circular barrier, European Journal of Operational Research, 154, 20-35 (2004) · Zbl 1036.90045
[19] Klamroth, K.; Wiecek, M. M., A bi-objective median location problem with a line barrier, Operations Research, 50, 670-679 (2002) · Zbl 1163.90620
[20] Kusakari, Y.; Nishizeki, T., An algorithm for finding a region with the minimum total \(L_1\) from prescribed terminals, (Proceedings of ISAAC’97. Proceedings of ISAAC’97, Lecture Notes in Computer Science, vol. 1350 (1997), Springer-Verlag: Springer-Verlag Berlin)
[21] Larson, R. C.; Sadiq, G., Facility locations with the Manhattan metric in the presence of barriers to travel, Operations Research, 31, 652-669 (1983) · Zbl 0521.90045
[22] McGarvey, R. G.; Cavalier, T. M., A global optimal approach to facility location in the presence of forbidden regions, Computers & Industrial Engineering, 45, 1-15 (2003)
[23] Nandikonda, R.; Batta, P.; Nagi, R., Locating a 1-center on a Manhattan plane with barriers, Annals of Operations Research, 123, 157-172 (2003) · Zbl 1036.90047
[24] 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
[25] Sarkar, A.; Batta, R.; Nagi, R., Commentary on “Facility location in the presence of congested regions with the rectilinear distance metric”, Socio-Economic Planning Sciences, 38, 291-306 (2004)
[26] Savaş, S.; Batta, R.; Nagi, R., Finite-size facility placement in the presence of barriers to rectilinear travel, Operations Research, 50, 1018-1031 (2002) · Zbl 1163.90623
[27] Topcuoglu, H.; Corut, F.; Ermis, M.; Yilmaz, G., Solving the uncapacitated hub location problem using genetic algorithms, Computers and Operations Research, 32, 967-984 (2005) · Zbl 1071.90025
[28] Wang, S.-J.; Bhadury, J.; Nagi, R., Supply facility and input/output point locations in the presence of barriers, Computers and Operations Research, 29, 685-699 (2002) · Zbl 0994.90004
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.