A new solution approach for solving the 2-facility location problem in the plane with block norms

  • Motivated by the time-dependent location problem over T time-periods introduced in Maier and Hamacher (2015) we consider the special case of two time-steps, which was shown to be equivalent to the static 2-facility location problem in the plane. Geometric optimality conditions are stated for the median objective. When using block norms, these conditions are used to derive a polygon grid inducing a subdivision of the plane based on normal cones, yielding a new approach to solve the 2-facility location problem in polynomial time. Combinatorial algorithms for the 2-facility location problem based on geometric properties are deduced and their complexities are analyzed. These methods differ from others as they are completely working on geometric objects to derive the optimal solution set.

Volltext Dateien herunterladen

Metadaten exportieren

Verfasserangaben:Andrea Maier
URN (Permalink):urn:nbn:de:hbz:386-kluedo-41282
Schriftenreihe (Bandnummer):Report in Wirtschaftsmathematik (WIMA Report) (156)
Sprache der Veröffentlichung:Englisch
Veröffentlichungsdatum (online):24.07.2015
Jahr der Veröffentlichung:2015
Veröffentlichende Institution:Technische Universität Kaiserslautern
Datum der Publikation (Server):24.07.2015
Fachbereiche / Organisatorische Einheiten:Fachbereich Mathematik
DDC-Sachgruppen:5 Naturwissenschaften und Mathematik / 510 Mathematik
MSC-Klassifikation (Mathematik):90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
Lizenz (Deutsch):Standard gemäß KLUEDO-Leitlinien vom 13.02.2015