Oliver Annen :

Das Partial Set Covering Problem und Erweiterungen: Modellierung und Lösungsverfahren

Dissertation angenommen durch: Universität Duisburg-Essen, Campus Duisburg, Fakultät für Naturwissenschaften, Institut für Mathematik, 2003-11-07

BetreuerIn: Prof. Dr. Günter Törner , Universität Duisburg-Essen, Campus Duisburg, Fakultät für Naturwissenschaften, Institut für Mathematik

GutachterIn: Prof. Dr. Günter Törner , Universität Duisburg-Essen, Campus Duisburg, Fakultät für Naturwissenschaften, Institut für Mathematik
GutachterIn: Prof. Dr. Peter Chamoni , Universität Duisburg-Essen, Campus Duisburg, Fakultät für Wirtschaftswissenschaften, Institut für Logistik und Informationsmanagement

Schlüsselwörter in Englisch: Partial Set Covering, Set Covering, Approximation Algorithms, local search, Multiple Coverage

  
   
 Klassifikation     
    MSC Primary: 90C27
Sachgruppe der DNB: 510 Mathematik
  
   
 Abstrakt     
   

Abstrakt in Deutsch

Gegenstand der vorliegenden Arbeit sind das Partial Set Covering Problem (PSCP) und Erweiterungen des PSCP. Ein Schwerpunkt ist hier die Erweiterung des PSCP unter dem Aspekt des Multiple Coverage. In der Arbeit wird die Problemstellung als Multiple Coverage Partial Set Covering Problem (MCPSCP) bezeichnet. Für die betrachteten Problemstellungen werden heuristische und approximative Algorithmen vorgestellt. Die Schwerpunkte der Arbeit liegen in der Entwicklung von Local-Search- und Lagrange-basierten Verfahren für das PSCP und das MCPSCP. Die Qualität der Algorithmen wird schließlich anhand von umfangreichen Experimenten an Probleminstanzen gemessen. Die Probleminstanzen wurden aus Benchmark-Instanzen der SCP-Literatur sowie aus realen Daten generiert. Am Beispiel eines Projekts mit der DB Cargo wird schließlich über eine Anwendung des PSCP und des MCPSCP im Schienenverkehr berichtet. Gegenstand des Projekts war eine Erfassung von Güterwaggons durch eine optimale Positionierung von Messstellen im bundesweiten Schienennetz.

Abstrakt in Englisch

In this thesis, we study the Partial Set Covering Problem (PSCP) as well as some new extensions of the PSCP. We present a new extension of the PSCP which is called the Multiple Coverage Partial Set Covering Problem (MCPSCP). The model combines the aspect of multiple coverage with the PSCP. Heuristic and approximative algorithms are proposed. Here, the focus lies on the PSCP and the MCPSCP for which several local search and Langrangean-based algorithms are presented. The heuristics are tested on a wide variety of benchmark problems. Furthermore, we report about an application of the PSCP and the MCPSCP in railway networks. The models are used to find optimal positions for vehicle testing stations.