×

The \(K\)-connection location problem in a plane. (English) Zbl 1114.90060

Summary: This paper determines the optimal location of \(K\) connections in the plane, where a connection links pairs of existing facilities. Both uncapacitated and capacitated versions of the problem are considered. Discretization results for general polyhedral gauges and other properties are established. Two heuristic algorithms are developed for each case using the concept of a shortest path flow set coupled with a sequential location and allocation approach. Computational results show that the algorithms are efficient and accurate.

MSC:

90B80 Discrete location and assignment
90C35 Programming involving graphs or networks
90C60 Abstract computational complexity for mathematical programming problems
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aykin, T. (1988). ”On the location of hub facilities.” Transportation Science 22, 155–157. · Zbl 0642.90034
[2] Aykin, T. and G.F. Brown. (1992). ”Interacting New Facilities and Location-Allocation Problem.” Transportation Science 26, 212–222. · Zbl 0758.90053
[3] Brandeau, M.L. and S.S. Chiu. (1993). ”Sequential Location and Allocation: Worst Case Performance and Statistical Estimation.” Location Science 1, 289–298. · Zbl 0926.90053
[4] Cooper, L. (1963). ”Location-Allocation Problems.” Operations Research 11, 331–343. · Zbl 0113.14201
[5] Cooper, L. (1964). ”Heuristic Methods for Location-Allocation Problems.” SIAM Review 6, 37–53. · Zbl 0956.90014
[6] Cooper, L. (1972). ”The Transportation-Location Problem.” Operations Research 20, 94–108. · Zbl 0237.90036
[7] Daskin, M.S. (1995). Network and Discrete Location: Models, Algorithms, and Applications. Wiley, New York. · Zbl 0870.90076
[8] Durier, R. and C. Michelot. (1985). ”Geometrical Properties of the Fermat-Weber Problem.” European Journal of Operational Research 20, 332–343. · Zbl 0564.90013
[9] Eilon, S., C.D.T. Watson-Gandy, and N. Christofides. (1971). Distribution Management: Mathematical Modelling and Practical Analysis. Hafner, New York.
[10] Francis, R.L., T.J. Lowe, and M.B. Rayco. (1996). ”Row-Column Aggregation for Rectilinear Distance p-Median Problems.” Transportation Science 30, 160–174. · Zbl 0865.90087
[11] Hodgon, M.J., K.E. Rosing, and F. Shmulevitz. (1993). A Review of Location-Allocation Applications Literature. Studies in Locational Analysis 5, 2–29.
[12] Huang, S., R. Batta, and R. Nagi. (2003). Variable capacity sizing and selection of connections in a facility layout. IIE Transactions 35, 49–59.
[13] Huang, S., R. Batta, and R. Nagi. (2004). Selection and sizing of congested connections for a transportation network. Naval Research Logistics, submitted. · Zbl 1278.90063
[14] Mirchandani, P.B. and R.L. Francis. (1990). Discrete Location Theory. John Wiley, New York. · Zbl 0718.00021
[15] Montreuil, B. and H.D. Ratliff. (1988). Optimizing the Location of Input/Output Stations within Facilities layout. Engineering Costs and Production Economics 14, 177–187.
[16] Nickel, S. (1995). Discretization of Planar Location Problems. Shaker Verlag, Aachen. · Zbl 0845.90082
[17] O’Kelly, M. (1986). ”The Location of Interacting Hub Facilities.” Transportation Science 20, 92–106.
[18] O’Kelly, M. (1992). ”A Clustering Approach to the Planar Hub Location Problem.” Annals of Operations Research 40, 339–353. · Zbl 0782.90063
[19] Plastria, F. (1995). ”Continuous location problems.” In Z. Drezner, (ed.), Facility Location: A Survey of Applications and Methods. Springer, NY, pp. 225–260.
[20] Robenhymer, B. and S. Estrada. (1998). ”Designing Transit at the World’s Busiest International Border Crossing.” Presented at the 68th Annual Meeting of the Institute of Transportation Engineers, Toronto.
[21] Ward, J.E. and R.E. Wendell. (1985). ”Using Block Norms for Location Modelling.” Operations Research 33, 1074–1090. · Zbl 0582.90026
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.