Zurück Vor

Detailergebnis zu DOK-Nr. 38245

Verbesserte Tourenplanung im Straßenbetriebsdienst mit dem neuen KAT-System

Autoren	R. Roos W. Durth P. Zhu
Sachgebiete	16.1 Organisation, Tourenplanung

Straße und Autobahn 41 (1990) Nr. 2, S. 52-59, 9 B, 14 Q

Die meisten bisher im Straßenbetriebsdienst durchgeführten Tourenplanungen werden von Hand erstellt. Mit der Anwendung moderner Verfahren der elektronischen Datenverwertung kann eine wesentliche Verbesserung der Planung erreicht werden. Bisher in dieser Richtung bekannt gewordene Verfahren können jedoch nicht befriedigen. Es wird ein flexibles Verfahren vorgestellt, das im Fachgebiet Straßenentwurf und Straßenbetrieb der TH Darmstadt entwickelt wurde und bereits bei der Einsatzplanung im Winterdienst erfolgreich erprobt wurde. Die Einsatzplanung wird mit FHilfe eines Graphen zeichnerisch dargestellt, wobei ein Graph aus Knoten und Kanten besteht. Tourenplanungen gehören zu den schwierigsten Problemen der Kombinatorik. Die klassische Behandlung beschränkt sich auf den Sonderfall einer Rundreise. Nach einem Rückblick über den Stand der Forschung mit Hinweisen auf vorhandene Literatur werden die Grundgedanken des neuen Programms erläutert. Entscheidend für die Verbesserung durch das neue Verfahren ist die Zerlegung des Gerade-Graphen in einfache Schleifen mit einem Zufallsmechanismus und die Distriktverbesserung über die Methode der simulierten Abkühlung, die 1953 von Metropolis beschrieben wurde. Auf diesen Grundlagen wurde ein kantenorientiertes Tourenplanungssystem (KAT) entwickelt, das speziell auf die Problemstellungen des Straßenbetriebsdienstes abgestimmt wurde. Abschließend wird noch anhand einer Analyse des Rechenaufwandes und des Speicherplatzbedarfs die Leistungsfähigkeit des KAT-Systems nachgewiesen und anhand eines Vergleichs der Ergebnisse bei manueller und EDV-Optimierung die Qualität der Lösungen gezeigt.