A Finite Dominating Set Algorithm for a Dynamic Location Problem in the Plane

  • A single facility problem in the plane is considered, where an optimal location has to be identified for each of finitely many time-steps with respect to time-dependent weights and demand points. It is shown that the median objective can be reduced to a special case of the static multifacility median problem such that results from the latter can be used to tackle the dynamic location problem. When using block norms as distance measure between facilities, a Finite Dominating Set (FDS) is derived. For the special case with only two time-steps, the resulting algorithm is analyzed with respect to its worst-case complexity. Due to the relation between dynamic location problems for T time periods and T-facility problems, this algorithm can also be applied to the static 2-facility location problem.

Download full text files

Export metadata

Metadaten
Author:Andrea Maier, Horst W. Hamacher
URN:urn:nbn:de:hbz:386-kluedo-40174
Series (Serial Number):Report in Wirtschaftsmathematik (WIMA Report) (155)
Document Type:Preprint
Language of publication:English
Date of Publication (online):2015/03/05
Year of first Publication:2014
Publishing Institution:Technische Universität Kaiserslautern
Date of the Publication (Server):2015/03/05
Page Number:16
Faculties / Organisational entities:Kaiserslautern - Fachbereich Mathematik
DDC-Cassification:5 Naturwissenschaften und Mathematik / 510 Mathematik
MSC-Classification (mathematics):90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C27 Combinatorial optimization
Licence (German):Standard gemäß KLUEDO-Leitlinien vom 13.02.2015