Algorithms and decomposition methods for multiobjective location and approximation problems

Abstract

In dieser Arbeit beschäftigen wir uns mit einer Klasse von erweiterten mehrkriteriellen Standort- und Approximationsproblemen. Die Dualitätsaussagen für diese Klasse wurden beweisen. Danach werden erweiterte mehrkriterielle Standortprobleme zerlegt, wobei das mehrkriterielle Standortproblem ein Teilproblem ist. Die geometrische Struktur der Menge der Minimallösungen dieses Problems wird danach benutzt, um eine neue Charakterisierung der Menge der schwachen Minimallösungen zu erhalten. Weiterhin wird ein implementabler Zerlegungsalgorithmus entwickelt, um die Menge der Minimallösungen des mehrkriteriellen Standortproblems zu endlich vielen Rechtecken zu zerlegen. Dieser Algorithmus ist die Basis der Entwicklung weiterer Dekompositionsalgorithmen für erweiterte mehrkriterielle Standortprobleme. Schließlich untersuchen wir skalare und mehrkriterielle N-Standortprobleme.

We study in this thesis a class of extended multiobjective location and approximation problems. After proving the duality assertions the extended multiobjective location problem is decomposed, such that a multiobjective location problem is obtained as a subproblem. We get through Pareto reducibility a new characterization of the set of weakly minimal solutions using its well-known duality-based geometrical structure. An implementable partition algorithm for the set of minimal solutions of the multiobjective location problem is also derived. This algorithm is the base for developing decomposition algorithms, which provide minimal solutions of the extended multiobjective location problem. Finally, we study scalar and multiobjective multi-facility location problems.