> ') ;?> ') ;?> '); ?>

Steinerprobleme

Umladeprobleme spielen eine wachsende Rolle in der modernen Transportlogistik. Dabei wird bei einem Pickup-and-Delivery-Problem erlaubt, Güter kurzzeitig in einem sogenannten Konsolidierungszentrum zwischenzulagern und dann mit einem anderen Fahrzeug weiterzutransportieren. Dieser zusätzliche Freiheitsgrad erschwert jedoch die Modellierung erheblich.

Um ein tieferes Verständnis für die Eigenschaften solcher Probleme zu erhalten, haben wir zwei kombinatorische Optimierungsprobleme entwickelt. Diese sind zwar zu stark idealisiert, um direkt für die Anwendung nutzbar zu sein, wir denken jedoch, dass sie wichtige strukurelle Eigenschaften der Probleme abbilden. Zudem konnten wir die algorithmische Lösung eines der Probleme erfolgreich in einer Heuristik für die Anwendung einsetzen (s. Abschnitt 2.3.3).

Beim sogenannten $k$-Star-Hub-Problem gehen wir davon aus, dass jeder Auftrag einzeln direkt ausgeliefert wird oder alle Aufträge eines Kunden zu einem von $k$ Konsolidierungszentren gebracht werden können. Dieses Problem lässt sich für nur ein Konsolidierungszentrum als bipartites Vertex Cover Problem modellieren, für $k=2$ kann es mit Netzwerkflussmethoden ebenfalls effizient gelöst werden. Bei mehr als zwei Zentren ist es jedoch $\mathcal{NP}$-vollständig.

Die zweite Art von Problemen haben wir Steiner-Diagram-Problem genannt. Das Problem kann auch als Umladeproblem interpretiert werden, bei dem jeder Auftrag auf seinem Weg beliebig oft umgeladen werden darf. Es ist verwandt mit dem generalisierten gerichteten Steinernetzwerk-Problem und dem minimalen äquivalenten Netzwerk-Problem. Bei dem behandelten Problem kommt zusätzlich die Forderung nach Kreisfreiheit hinzu, welche es uns zu zeigen erlaubt, dass sich das Problem in polynomieller Zeit lösen lässt, falls die Anzahl der Aufträge beschränkt, das zugrundeliegende Netzwerk transitiv abgeschlossen und die Dreiecksungleichung erfüllt ist. Die beiden letzten Bedingungen werden in einem Anwendungsproblem immer erfüllt sein.

Kontakt: combopt@zpr.uni-koeln.de

') ;?> ') ;?> '); ?>