Melden Sie sich hier an, um auf Kommentare und die Whitepaper-Datenbank zugreifen zu können.

Kein Log-In? Dann jetzt kostenlos registrieren.

Falls Sie Ihr Passwort vergessen haben, können Sie es hier per E-Mail anfordern.

Der Zugang zur Reseller Only!-Community ist registrierten Fachhändlern, Systemhäusern und Dienstleistern vorbehalten.

Registrieren Sie sich hier, um Zugang zu diesem Bereich zu beantragen. Die Freigabe Ihres Zugangs erfolgt nach Prüfung Ihrer Anmeldung durch die Redaktion.

05.12.1980 - 

Trafic von Siemens als Planungshilfsmittel für den Fuhrpark:

Rechner optimiert Rundreise-Problem

MÜNCHEN - Die steil steigenden Treibstoffkosten bereiten distributionsorientierten Betrieben mit eigenem Fuhrpark zunehmend Sorgen. Ein großer Anteil der Gesamtkosten dieser Unternehmen entfällt auf die Warenverteilung. Es ist dringend erforderlich, diesem Gebiet besondere Aufmerksamkeit zu widmen.

Vieles deutet darauf hin, daß der Lkw heute hinsichtlich seines Leistungsvermögens technisch ausgereift ist. Das bedeutet, daß die Rationalisierungsmöglichkeiten von dieser Seite her (fast) erschöpft sind. Eine wesentliche Verbesserung im Bereich des Fuhrparks ist nur durch eine Neuplanung des Lkw-Einsatzes, verbunden mit einer Neugestaltung der Tourenplanung, zu erreichen.

Dies erfordert jedoch ein hohes Maß an planerischem Können und kann bei manueller Durchführung wegen der Vielzahl der Kombinationsmöglichkeiten nur in Ausnahmefällen zu optimalen Ergebnissen führen. Die Folgen der manuellen Planung sind in der mangelhaften Auslastung der Fahrzeugkapazitäten, in Wartezeiten für Fahrer und Kunden, in zeitraubenden Umwegen und vermeidbaren Leerfahrten zu sehen.

Hier bietet sich eine umfassende Touren- und Fuhrparkplanung unter Einsatz der Datenverarbeitung an, um die ständig steigenden Kosten im Fuhrparkbereich "in den Griff" zu bekommen.

Um die vielfältigen Probleme der Warenverteilung zu lösen und die Kosten im Fuhrparkbereich entscheidend zu reduzieren, entwickelte die Siemens AG das Programm-System Trafic (Transportoptimierung und Fuhrparkeinsatzplanung mit dem Computer).

Trafic berücksichtigt Nebenbedingungen für das Depot, den Fuhrparkbereich, die Kunden und die Touren in der Planung.

Das Programm soll die Gesamtfahrstrecke und die Anzahl der eingesetzten Fahrzeuge verringern sowie die Ausnutzung der Ladekapazität der Fahrzeuge und der verfügbaren Arbeitszeit verbessern.

Neben diesen kombinatorischen Ersparnissen erzielt Trafic auch eine organisatorische Kosteneinsparung, indem es

- automatische Ladelisten,

- detaillierte Touren- und Fahrpläne,

- Fuhrparkstatistik und

- graphische Tourenpläne erstellt.

Viele Probleme der Praxis sind in ihrer Struktur so kompliziert, daß die optimalen Lösungen nur mit einem hohen Rechenaufwand ermittelt werden können. In diesen Fällen werden die exakt optimierenden Methoden durch Näherungsverfahren - den sogenannten heuristischen Verfahren - ersetzt. Ein solcher Lösungsansatz, nämlich das erweiterte "travelling salesman"- oder

"Rundreise"-Problem liegt dem Transportoptimierungsverfahren Trafic zugrunde.

Trafic besteht aus zwei Hauptteilen:

- Erstellen des geographischen Kundennetzes,

- Einsatz der Fahrzeuge vom Depot aus zur Belieferung der Kunden in diesem Netz.

Die Netzwerkanalyse hat die Aufgabe, die Entfernungen, Fahrzeiten und Ersparnisse zwischen allen Orten, das heißt Kunden und Depot, zu bestimmen und datenverarbeitungsgerecht aufzubereiten. Das Ergebnis wird in einer Netzdatei (Plattendatei) gespeichert.

Für die Berechnung kann entweder - die Verbindungsstraßenmethode (echte Entfernungsmethode) oder

- die Koordinatenmethode verwendet werden.

Bei der Verbindungsstraßenmethode wird auf einer beziehungsweise mehreren Landkarten die genaue Lage des Depots und der zu beliefernden Kunden eingezeichnet.

Aufgrund der Lage der Kunden wird das Streckennetz betrachtet und wichtige Verkehrsknoten (zum Beispiel Autobahnauffahrten, Brücken) auf den Wegen zu diesen Kunden markiert. Bei der Erfassung der Angaben müssen jetzt von jedem Punkt zu jedem direkt erreichbaren Punkt die echten Entfernungen über die möglichen Verbindungsstraßen ermittelt werden.

In der Praxis scheitert der Einsatz diese Verfahrens meist daran, daß es fast unmöglich ist, mit der Wirklichkeit übereinstimmende Daten zu beschaffen. Die Notlösung, diese Angaben am Schreibtisch zu ermitteln, birgt aber trotz des immensen Aufwands an Erfassungs- und Rechenzeit so viele Ungenauigkeiten, daß sie sich aus wirtschaftlichen Gründen nicht durchsetzen konnte.

Daher sollte die Verbindungsstraßenmethode nur für kleine Sonderprobleme verwendet werden.

Überraschende Ergebnisse

Bei der Koordinatenmethode wird auf die Landkarten, in die Depot und Kunden eingezeichnet sind, ein rechtwinkliges Gittersystem gelegt. Die Lage des Nullpunktes dieses Systems ist beliebig. In der Netzwerkanalyse wird dann die Luftlinienentfernung zwischen den einzelnen Punkten ermittelt. Hieraus erhält man annähernd die tatsächliche, wahre Entfernung, wenn man diesen Wert mit dem sogenannten Entfernungsfaktor multipliziert. Dieser liegt im allgemeinen zwischen 1,0 und 1,5 und ist stark von dem jeweiligen Gebiet abhängig. Für das ganze Gebiet wird eine einheitliche Durchschnittsfahrgeschwindigkeit festgelegt.

Der Erfassungsaufwand ist bei der Koordinatenmethode wesentlich geringer. Sie stellt insgesamt gesehen nur eine Näherungslösung dar. Die Praxis hat jedoch gezeigt, daß sie bei wirtschaftlich vertretbarem Aufwand überraschend gute Ergebnisse liefert und deshalb fast immer der echten Entfernungsmethode vorzuziehen ist.

Die Tourenplanung bildet des Kernstück des gesamten Systems. Hier werden die Liefermengen, die innerhalb des vorgegebenen Einsatzzeitraums an die einzelnen Kunden ausgeliefert werden, zu Lkw-Touren kombiniert, wobei eine optimale Kapazitätsauslastung und Zeitausnutzung angestrebt wird. Wichtig ist dabei die gleichzeitige Zuordnung eines passenden Fahrzeugs und die Einhaltung der Nebenbedingungen für Depot, Fuhrpark, Kunden und Touren.

Zur Durchführung einer Tourenplanung mit Trafic müssen folgende Daten zur Verfügung stehen:

- Das geographische Kundennetz mit Entfernungen und Fahrzeiten zwischen allen Orten muß mit der Netzwerkanalyse aufgebaut sein.

- Größe des vorhandenen Fuhrparks: Einteilung der Fahrzeuge nach Ladekapazitäten (= Transporteinheiten) in Fahrzeugtypen (maximal 80 Typen) und Anzahl der Fahrzeuge je Fahrzeugtyp.

- Zeitangaben: Die Uhrzeit des Einsatzbeginns und des spätesten Einsatzendes müssen bekannt sein, außerdem die Zeiten für Beladung im Depot, Abladen beim Kunden und Bereitstellungszeit für Wiedereinsatz.

- Liefermenge (Bestellmenge) jedes Kunden in Transporteinheiten.

Das eigentliche Optimierungsproblem bei der Tourenplanung besteht aus drei Teilaufgaben:

1. Welche Kunden sollen auf einer gemeinsamen Tour beliefert werden (Auswahlproblem)?

2. In welcher Reihenfolge sollen die Kunden einer Tour beliefert werden (Reihenfolgeproblem)?

3. Welcher Wagen soll auf einer Tour eingesetzt werden (Zuordnungsproblem)?

Wegen der Kompliziertheit dieses "Rundreise"-Problems kann nur ein mathematisches Näherungsverfahren verwendet werden. Von vielen untersuchten Methoden hat sich für die Praxis das "Ersparnis"- oder Saving-Verfahren nach Clarke und Wright am besten bewährt.

Ersparnis-Matrix

Aus den Fahrzeiten, die zwischen allen Orten einerseits und dem Depot und den einzelnen Orten andererseits ermittelt wurden, und unter Berücksichtigung der Barrieren und Netzkorrekturen werden die Ersparnisse berechnet.

Bei der Bildung der Ersparnisse zwischen den einzelnen Kunden wird der Vorteil errechnet, der sich dadurch ergibt, daß man zwei Kunden zu einer Tour miteinander verbindet, anstatt jeden Kunden unmittelbar vom Lager aus im Pendelverkehr zu bedienen.

Die Ersparnis ist um so größer, je weiter zwei Kunden vom Depot entfernt sind und je näher sie zusammenliegen.

Analog zum vorigen Beispiel werden aus den Fahrzeiten die Fahrzeitersparnisse für jede Kombination (Verbindung) von zwei Orten berechnet. Diese Ersparnisse werden in einer (Ersparnis-) Matrix gespeichert.

Indem fortgesetzt die Ortspaare mit der verbleibenden größten Ersparnis verbunden werden, entstehen gleichzeitig mehrere Tourenstücke, die immer länger werden. Das Wachsen jeder Tour ist begrenzt durch die Bedingungen "maximale Einsatzdauer" und "Kapazität des vorhandenen Fuhrparks", die nicht überschritten werden dürfen.

Diese Bedingungen sowie alle weiteren Nebenbedingungen für Kunden, Depot, Fuhrpark und Touren werden bei jeder Verknüpfung überprüft, und nur wenn alle Bedingungen erfüllbar sind, wird die Verbindung geschlossen.

Wenn schließlich alle Ersparnisse bis zur kleinsten überprüft sind, werden aus den dann vorhandenen Tourenstücken geschlossene Touren gemacht, indem jeweils der Hinweg vom Depot zum ersten Kunden und der Rückweg vom letzten Kunden zum Depot hinzugefügt wird.

Da die größten Ersparnisse für die am weitesten vom Depot entfernten Kunden gegeben sind, beginnt der Aufbau der ersten Touren vom Rand des Liefergebiets her.

Wenn zusätzliche Orte nicht mehr angehängt werden können, werden neue Touren weiter innen begonnen, so daß sich meistens ineinandergreifende "blütenblattförmige" Touren ergeben.

Gegen Ende der Planung werden dann die Orte verknüpft, die nahe am Depot liegen.

Nach Beendigung des Tourenaufbaus muß gesichert sein, daß für jede Tour ein Wagen ausreichender Kapazität vorhanden ist.

Daher wird bereits beim Aufbau der Touren jedem Tourenstück ein passender Lkw zugeordnet. Wenn kein freier Lkw vorhanden ist, kann eine Verknüpfung nicht durchgeführt werden.

Zu Beginn der Tourenplanung wird für die noch kurzen Tourenstücke jeweils der kleinste Lkw ausreichen, bei zunehmender Länge einer Tour wird der kleine durch den passenden nächstgrößeren Lkw ersetzt. Auf diese Weise wird während des Tourenaufbaus eine dauernde Umverteilung und optimale Zuordnung der Lkws durchgeführt.

Während des Tourenaufbaus mittels des Ersparnis-Verfahrens wird versucht, jede Tour immer weiter zu verlängern. Hierbei sind zwei Begrenzungen wirksam:

1. Die Einsatzzeit ist voll ausgenutzt: Dann bleibt der Tour der kapazitätsmäßig gerade ausreichende Lkw zugeordnet.

2. Die Kapazitätsbegrenzung: Einer Tour wird so lange der nächstgrößere Lkw zugewiesen, bis kein größerer Lkw mehr vorhanden oder frei ist. Dann kann die Tour nicht weiter verlängert werden, obwohl möglicherweise noch genügend Einsatzzeit übrig wäre. In diesem Fall wird der Lkw zu einer weiteren Tour eingesetzt.

- Dietmar Schmidtgen ist Leiter des Vertriebs Konsumgüterindustrie der Siemens AG, München.