×

zbMATH — the first resource for mathematics

A planar single facility location and border crossing problem. (English) Zbl 1349.90558
Summary: In this study, we tackle the problem of locating a facility in a region where a fixed line barrier divides the region into two. The resulting subregions communicate with each other through a number of passage points located on the line barrier. Our contribution is threefold. First, we formulate the problem as a Mixed Integer Nonlinear Programming (MINLP) model and provide an optimal solution methodology based on an Outer Approximation (OA) algorithm. Second, we discuss the minimax version of this problem for locating an emergency facility and use the OA algorithm to solve the problem. We then provide simple example problems and extensive computational results for both problems. Finally, we propose a one-infinity approximation approach for the latter problem which yields a linear model. Practical uses of the models have been discussed in the border crossing context.

MSC:
90B80 Discrete location and assignment
90C11 Mixed integer programming
Software:
BARON; DICOPT; MINOS
PDF BibTeX XML Cite
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, 1, 70-76, (1994) · Zbl 0799.90072
[2] Bischoff, M.; Klamroth, K., An efficient solution method for Weber problems with barriers based on genetic algorithms, European journal of operational research, 177, 1, 22-41, (2007) · Zbl 1111.90064
[3] Bosch R, Trick M. Chapter 3: Integer programming in search methodologies. US: Springer; 2005.
[4] Butt, S.E.; Cavalier, T.M., An efficient algorithm for facility location in the presence of forbidden regions, European journal of operational research, 90, 1, 56-70, (1996) · Zbl 0916.90177
[5] Canbolat, M.S.; Wesolowsky, G.O., The rectilinear distance Weber problem in the presence of a probabilistic line barrier, European journal of operational research, 202, 1, 114-121, (2010) · Zbl 1173.90447
[6] Dearing, P.M.; Klamroth, K.; Segars, R., Planar location problems with block distance and barriers, Annals of operations research, 136, 1, 117-143, (2005) · Zbl 1114.90056
[7] Duran, M.A.; Grossman, I.E., An outer-approximation algorithm for a class of mixed-integer nonlinear programs, Mathematical programming, 36, 307-339, (1986) · Zbl 0619.90052
[8] Glover, F., Improved linear integer programming formulations of nonlinear integer problems, Management science, 22, 4, 455-460, (1975) · Zbl 0318.90044
[9] Katz, I.; Cooper, L., Formulation and the case of Euclidean distance with one forbidden circle, European journal of operational research, 6, 166-173, (1981) · Zbl 0451.90042
[10] Klamroth, K., Planar Weber location problems with line barriers, Optimization, 49, 5-6, 517-527, (1996) · Zbl 0995.90065
[11] Klamroth, K., A reduction result for location problems with polyhedral barriers, European journal of operational research, 130, 3, 486-497, (2001) · Zbl 0981.90042
[12] Klamroth K. Single facility location problems with barriers. Springer series in operations research; 2002. · Zbl 1027.90055
[13] Klamroth, K., Algebraic properties of location problems with one circular barrier, European journal of operational research, 154, 1, 20-35, (2004) · Zbl 1036.90045
[14] Kocis, G.R.; Grossmann, I.E., Computational experience with dicopt solving MINLP problems in process systems engineering, Computers and chemical engineering, 13, 307-315, (1989)
[15] Larson, R.C.; Sadiq, G., Facility location with the Manhattan metric in the presence of barriers to travel, Operations research, 31, 652-669, (1983) · Zbl 0521.90045
[16] Love, R.F.; Walker, J.H., An empirical comparison of block and round norms for modelling actual distances, Location science, 2, 1, 1-43, (1994) · Zbl 0926.90056
[17] 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, 1-15, (2003)
[18] Murtagh BA, Saunders AM. Minos user’s guide. Technical Report SOL 77-9, Department of Operations Research, Stanford University; 1997.
[19] Sahinidis, N.V., Baron: a general purpose global optimization software package, Journal of global optimization, 8, 2, 201-205, (1996) · Zbl 0856.90104
[20] Torres, F.E., Linearization of mixed-integer products, Mathematical programming, 49, 427-428, (1991) · Zbl 0725.90069
[21] Ward, J.E.; Wendell, R.E., A new norm for measuring distance which yields linear location models, Operations research, 28, 3, 836-844, (1980) · Zbl 0443.90029
[22] Ward, J.E.; Wendell, R.E., Using block norms for location modelling, Operations research, 33, 5, 1074-1090, (1985) · Zbl 0582.90026
[23] Nandikonda, P.; Batta, R.; Nagi, R., Locating a 1-center on a Manhattan plane with arbitrarily shaped barriers, Annals of operations research, 123, 1-4, 157-172, (2003) · Zbl 1036.90047
[24] Frieß, L.; Klamroth, K.; Sprau, M., A wavefront approach to center location problems with barriers, Annals of operations research, 136, 1, 35-48, (2005) · Zbl 1114.90058
[25] Sarkar, A.; Batta, R.; Nagi, R., Placing a finite size facility with a center objective on a rectangular plane with barriers, European journal of operational research, 179, 3, 1160-1176, (2007) · Zbl 1127.90046
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.