nach oben

Erschienen in:

2018 | OriginalPaper | Buchkapitel

Branch and Bound Method for the Weber Problem with Rectangular Facilities on Lines in the Presence of Forbidden Gaps

verfasst von : Gennady G. Zabudsky, Natalia S. Veremchuk

Erschienen in: Optimization Problems and Their Applications

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The problem of location of connected rectangular facilities on parallel lines in the presence of forbidden gaps is studied. The rectangular metric is used. The centers of the placed facilities are connected with the centers of the gaps. The facilities are impossible to place in forbidden gaps. It is necessary to place the facilities on the lines so that the total cost of connections between the facilities and between facilities and gaps was minimized. The problem is an adequate model of many practical situations. It is known that the original continuous problem for one–line variant is reduced to discrete subproblems. In this paper, the review of the properties and the algorithms for solving of the problem on one line are described. The branch and bound method for solving the problem is proposed. Results of computational experiments on comparison of the branch and bound method and a heuristic proposed in [27] are reported. In the experiments, a integer programming model and IBM ILOG CPLEX package are used.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel A New Model of Competitive Location and Pricing with the Uniform Split of the Demand

Nächstes Kapitel Inapproximability Lower Bounds for Open Shop Problems with Exact Delays

Bischoff, M., Klamroth, K.: An efficient solution method for Weber problems with barriers based on genetic algorithms. Eur. J. Oper. Res. 177, 22–41 (2007)MathSciNetCrossRef

Butt, S.E., Cavalier, T.M.: Facility location in the presence of congested regions with the rectilinear distance metric. Socio-Econom. Plan. Sci. 31, 103–113 (1997)CrossRef

Cabot, A.V., Francis, R.L., Stary, M.A.: A network flow solution to a rectilinear distance facility location problem. AIIE Trans. II(2), 132–141 (1970)CrossRef

Erzin, A.I., Cho, J.D.: Concurrent placement and routing in the design of integrated circuits. Autom. Remote Control 64(12), 1988–1999 (2003)MathSciNetCrossRef

Foulds, L.R., Hamacher, H.W., Wilson, J.M.: Integer programming approaches to facilities layout models with forbidden areas. Ann. Oper. Res. 81, 405–417 (1998)MathSciNetCrossRef

Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman, San Francisco (1979). Mir, Moscow (1982)

Kacprzyk, J., Stanczak, W.: Discrete approximation of the Weber problem with the Euclidean distance (in Polish). Applicationes Mathematicae XVIII, 257–270 (1984)CrossRef

Kafer, B., Nickel, S.: Error bounds for the approximative of restricted planar location problems. Eur. J. Oper. Res. 135, 67–85 (2001)MathSciNetCrossRef

Katz, N., Cooper, L.: 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, 166–173 (1981)MathSciNetCrossRef

10.

Klamroth, K.: Single-Facility Location Problems with Barriers. Springer Series in Operations Research. Springer, New York (2002). https://doi.org/10.1007/b98843CrossRefMATH

11.

Kochetov, Yu.A., Panin, A.A., Plyasunov, A.V.: Comparison of metaheuristics for the bilevel facility location and mill pricing problem. Diskret. Anal. Issled. Oper. 22(3), 36–54 (2015)MathSciNetCrossRef

12.

Kuhn, H.W.: A note on Fermat’s problem. Math. Program. 4, 98–107 (1973)MathSciNetCrossRef

13.

Nickel, S., Puerto, J.: Location Theory: A Unified Approach. Springer, Heidelberg (2005). https://doi.org/10.1007/3-540-27640-8CrossRefMATH

14.

Legkih, S.A., Nagornay, Z.E., Zabudsky, G.G.: Automation of design of plans of production sites and shops of the sewing enterprises (in Russian). Nat. Tech. Sci. 4, 261–266 (2005)

15.

Love, R.F., Wong, J.Y.: On solving a one-dimentional space allocation problem with integer programming. INFORR 14(2), 139–143 (1976)MATH

16.

McGarvey, R.G., Cavalier, T.M.: Constrained location of competitive facilities in the plane. Comput. Oper. Res. 32, 539–378 (2005)MathSciNetCrossRef

17.

Panyukov, A.V.: The problem of locating rectangular plants with minimal cost for the connecting network. Diskret. Anal. Issled. Oper. Ser. 2 8(1), 70–87 (2001)MathSciNetMATH

18.

Panyukov, A.V., Shangin, R.E.: Algorithm for the discrete Weber’s problem with an accuracy estimate. Autom. Remote Control 77(7), 1208–1215 (2016)MathSciNetCrossRef

19.

Picard, J.C., Ratliff, D.H.: A cut approach to the rectilinear distance facility location problem. Oper. Res. 26(3), 422–433 (1978)MathSciNetCrossRef

20.

Rudnev, A.S.: Probabilistic tabu search algorithm for the packing circles and rectangles into the strip. Diskret. Anal. Issled. Oper. 16(4), 61–86 (2009)MATH

21.

Simmons, D.M.: One-dimensional space allocation: an ordering algorithm. Oper. Res. 17(5), 812–826 (1969)MathSciNetCrossRef

22.

Chen, W.-K.: The VLSI Handbook. CRC Press, Boca Raton (2000)

23.

Zabudsky, G.G.: On the problem of the linear ordering of vertices of parallel-sequential graphs. Diskret. Anal. Issled. Oper. 7(1), 61–64 (2000)MathSciNet

24.

Zabudskii, G.G., Amzin, I.V.: Algorithms of compact location for technological equipment on parallel lines (in Russian). Sib. Zh. Ind. Mat. 16(3), 86–94 (2013)MathSciNetMATH

25.

Zabudsky, G.G., Legkih, S.A.: Mathematical model of optimization of flexible modules of processing equipment (in Russian). Appl. Math. Inf. Technol. 20–28 (2005)

26.

Zabudsky, G., Veremchuk, N.: About local optimum of the Weber problem on line with forbidden gaps. In: Proceedings of the DOOR 2016, Vladivostok, Russia, 19–23 September 2016, vol. 1623, pp. 115–124. CEUR-WS (2016). CEUR-WS.org. http://ceur-ws.org/Vol-1623/paperco17.pdf

27.

Zabudskii, G.G., Veremchuk, N.S.: An algorithm for finding an approximate solution to the Weber problem on a line with forbidden gaps. J. Appl. Ind. Math. 10(1), 136–144 (2016)MathSciNetCrossRef

28.

Zabudsky, G.G., Veremchuk, N.S.: Solving Weber problem on plane with minimax criterion and forbidden gaps (in Russian). IIGU Ser. Matematika 9, 10–25 (2014)MATH

29.

Zabudsky, G., Veremchuk, N.: Weber problem for rectangles on lines with forbidden gaps. In: IEEE Conference 2016 Dynamics of Systems, Mechanisms and Machines, Omsk, 15–17 November 2016 (2016)

Titel: Branch and Bound Method for the Weber Problem with Rectangular Facilities on Lines in the Presence of Forbidden Gaps
verfasst von: Gennady G. Zabudsky
Natalia S. Veremchuk
Verlag: Springer International Publishing
Buch: Optimization Problems and Their Applications
Print ISBN: 978-3-319-93799-1

Electronic ISBN: 978-3-319-93800-4

Copyright-Jahr: 2018
DOI: https://doi.org/10.1007/978-3-319-93800-4_3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"