Effizient lösbare Varianten von Standortproblemen

Das beantragte Projekt beschäftigt sich mit effizient lösbaren Varianten von Standortproblemen. Das Projekt gliedert sich in die folgenden drei Unterbereiche: Standortprobleme mit teilweise unerwünschten Einrichtungen, inverse Standortproblemen und Standortprobleme mit Budgetrestriktionen. In allen Bereichen wird der Schwerpunkt der Untersuchungen auf der Entwicklung effizienter Algorithmen zur Lösung der betrachteten Standortprobleme liegen. Im Gegensatz zum klassischen Fall von Standortproblemen, wo es Ziel jedes Kunden ist, das ihm nächstgelegene Service-Zentrum so nah wie möglich zum eigenen Standort zu haben, widmet sich dieses Projekt dem Fall von Einrichtungen, deren Nähe für einen Teil der Kunden unerwünscht ist. Bei inversen Standortproblemen geht es darum, ausgewählte Problemparameter in einer solchen Weise zu verändern, dass die resultierenden Kosten minimiert werden unter Einhaltung des Zieles, dass eine vorgegebene Wahl von Standorten für die Einrichtungen eine Optimallösung des zugrundeliegenden Standortproblems darstellt. Im dritten Projektbereich werden Standortprobleme mit Budgetrestriktionen untersucht. Die Aufgabe von Verbesserungs- bzw. Verschlechterungsproblemen ist es, unter Einhaltung eines vorgegeben Budgets für die Modifikationskosten vorgegebene Eingabeparameter so zu verändern, dass je nach der betrachteten Problemvariante die Qualität einer vorgegebenen Lösung des Standortproblems oder der neuen Optimallösung in maximaler Weise verbessert bzw. verschlechtert wird.

Standortprobleme gehören zu den grundlegensten Operations Research Problemen und spielen eine wichtige Rolle in der Praxis. In Standortproblemen ist eine Menge von Anbietern und eine Menge von Kunden gegeben. Die Aufgabenstellung ist es, die Anbieter so gegebenen Standorten zuzuordnen, dass die Kunden in optimaler Weise versorgt werden und die resultierenden Gesamtkosten minimiert werden. Die Kosten hängen typischerweise von der Distanz zwischen den Klienten und den Anbietern, von denen diese versorgt werden, ab. Das zentrale Ziel dieses Projekts ist es, ein tieferes Verständnis von Varianten von Standortproblemen zu erzielen, in denen einige der Eingabedaten innerhalb bestimmter Grenzen verändert werden dürfen. Unsere Forschungsarbeit konzentrierte sich auf die folgenden zwei Klassen von Standortproblemen: Inverse Standortprobleme: Es ist eine zulässige Lösung gegeben und es ist das Ziel ausgewählte Eingabeparameter in minimaler Weise zu verändern, so dass die vorgegebene zulässige Lösung optimal wird. Standortprobleme mit Budgetbedingungen: Es ist ein Budget vorgegeben, das in die Veränderung bestimmter Eingabeparameter investiert werden kann. Das Ziel ist es, die Qualität der Lösung maximal zu verändern. Im Verbesserungsfall soll die Lösung verbessert werden, im Verschlechterungsfall verschlechtert. Im Rahmen dieses Projekts haben wir nachgewiesen, dass eine Reihe von Varianten von Standortproblemen der oben beschriebenen Typen aus algorithmischer Sicht schwer lösbar sind (sogenannte NP-schwere Probleme). Ferner haben wir Strukturen identifiziert, die schwere Probleme in effizient lösbare übergehen lassen. Wir entwickelten problemabhängige Optimalitätskriterien für eine Reihe von Varianten von Standortproblemen. Dies ermöglichte uns in weiterer Folge die Entwicklung von effizienten Algorithmen zu deren Lösung.