Tourenplanungsprobleme bei der Fahrzeugdisposition


Diplomarbeit, 2010
60 Seiten, Note: 1,0

Leseprobe

Inhalt

1 Einleitung

2 Erläuterung verkehrswirtschaftlicher Grundbegriffe
2.1 Bedeutung, Funktion und Ziele der Logistik
2.2 Einordnung der Tourenplanung in die betriebswirtschaftliche Logistik
2.3 Stellenwert des Gütertransportes auf der Straße
2.4 Dispositionsaufgaben im Güterverkehr
2.5 Die Fahrzeugdisposition als Instrument der Tourenplanung

3 Grundlagen der Tourenplanung bei der Fahrzeugdisposition
3.1 Einführung in die Tourenplanung
3.2 Unterscheidungskriterien von Tourenplanungsproblemen
3.3 Graphische Darstellungen von Tourenplanungsproblemen
3.4 Die Standardprobleme der Tourenplanung
3.5 Zielsetzungen der Tourenplanung bei der Fahrzeugdisposition
3.6 Berücksichtigung von dynamischen Einflussfaktoren

4 Anwendungen der Tourenplanung
4.1 Problemvarianten in der Tourenplanung
4.1.1 Knotenorientiertes Tourenproblem: Travelling- Salesman-Problem
4.1.2 Kantenorientiertes Tourenproblem: Vehicle- Routing- Problem
4.1.3 Vehicle Scheduling Problem
4.2 Rechnergestützte Tourenplanung

5 Erweiterungen des Basisproblems durch zeitkritische Restriktion
5.1 Tourenplanungen unter Berücksichtigung einer eingeschränkten Fahrzeit
5.2 Tourenplanungen unter Beachtung von Zeitfenstern
5.3 Tourenplanungen bei mehrfachem Einsatz von Fahrzeugen
5.4 Fahrzeugzuordnung bei heterogenem Fuhrpark

6 Klassische heuristische Verfahren
6.1 Eröffnungsverfahren
6.1.1 Lösungsverfahren des Sweep- Algorithmus
6.1.2 Tourenbildung durch das Saving-Verfahren
6.2 Verbesserungsverfahren
6.2.1 Das 2-opt und das 3-opt- Verfahren zur Lösungsfindung
6.2.2 Or-opt-Lösungsverfahren von Tourenplanungsprobleme
6.3 Branch-and-Bound-Verfahren

7 Neuere heuristische Lösungsverfahren
7.1 Metastrategie des Tabu Search
7.2 Lösungsansätze durch Künstliche Neuronale Netze
7.3 Theorie der Unscharfen Mengen (Fuzzy Logik)

8 Zusammenfassung

Literaturverzeichnis

Abkürzungsverzeichnis

Abbildungsverzeichnis

Tabellenverzeichnis

1 Einleitung

Das Gebiet der Tourenplanung beschäftigt schon seit Jahren die Mitarbeiter in der Unternehmensforschung und zählt somit zu den ältesten Anwendungsbereichen dieser Forschungsrichtung. Durch die langjährige Forschung in diesem Bereich hat das Gebiet in den letzten Jahren eine stürmische Entwicklung erlebt. So werden ständig neue Softwarepakete entwickelt und so fanden und finden immer mehr Methoden des Operations Research Anwendung bei der Lösung praktischer Probleme.[1]

Tourenplanungsprobleme treten immer dann auf, wenn zum Erreichen eines bestimmten logistischen Zieles das Anfahren von mehreren unterschiedlichen Standorten erforderlich ist. Das Grundproblem der Tourenplanung lässt sich wie folgt beschreiben: Eine bestimmte Anzahl von Kunden an unterschiedlichen Standorten sollen von einem oder mehreren Lagerorten beliefert werden. Die Nachfrage jedes Kunden ist bekannt und für den Transport der Güter stehen Fahrzeuge mit genau einer gegebenen Kapazität zur Verfügung. Die Nachfrage der Kunden nach Gütern sei homogen bezüglich der Einheit und der Kapazität, in der die Ladefähigkeit der Transportmittel gemessen wird. Das Ziel besteht nun darin, die Routen für die Fahrzeuge unter Beachtung der Kriterien so optimal wie möglich festzulegen.[2]

Da sich diese Voraussetzungen von Branche zu Branche und von Fall zu Fall hinsichtlich zahlreicher Kriterien unterscheiden, existierten keine einheitlichen Grundprobleme. Dementsprechend unterscheiden sich auch die jeweiligen zu empfehlenden Lösungsverfahren. Das steigende Güteraufkommen im Straßenverkehr, die immer komplexeren Anforderungen an die Spediteure (z.B. durch Zeitfenstervorgaben beim Beladen bzw. Entladen), die Einhaltung bestimmter Richtlinien im Emissionsbereich gestalten die Problemstellung und den Lösungsansatz noch umfangreicher. Die negativen Auswirkungen dieser Entwicklung auf die Umwelt lassen sich in ihrem ganzen Ausmaß nur erahnen.

Für die Industrie- und Handelsunternehmen wird es auf Grund dieser Entwicklung immer schwieriger werden, mit den Abnehmern verlässliche Terminabsprachen für den Transport zu treffen. Vom Blickpunkt eines Logistikers sollte versucht werden die Rahmenbedingungen, wie z.B. die Standorte der Zentrallager und der Produktionsstätten sowie die Infrastruktur effektiver und langfristiger zu gestalten. Mittel- und kurzfristig sollte der eigene Fuhrpark gut ausgelastet sein und unnötige Fahrten vermieden werden. Die Zusammenstellung der auszuliefernden Aufträge zu den entsprechend effektiven Touren, die von betriebseigenen Fahrzeugen bedient werden, ist die Aufgabe der Tourenplanung. Sie soll die Kosten bzw. den zeitlichen Ablauf für das Unternehmen minimieren, um es so konkurrenzfähig zu machen. Damit dient die Tourenplanung insgesamt betrachtet der Reduzierung des Güteraufkommens.[3]

Aus dieser Formulierung lässt sich die Komplexität der Tourenplanungsprobleme sowie deren Lösungsverfahren bereits vermuten. Die vorliegende Thesis beschreibt die Problem- und Lösungsansätze der Tourenplanung in allgemeiner Weise. Sie zeigt zu Beginn wichtige verkehrswirtschaftliche Grundlagen und charakterisiert im späteren Verlauf den Umfang der Tourenplanungsprobleme. Anwendungsbereiche der Tourenplanung in der betriebswirtschaftlichen Logistik sollen erarbeitet und klassische und moderne Lösungsverfahren verglichen werden. Die größte Aufmerksamkeit wird dabei auf Tourenplanungsprobleme im Straßengüterverkehr gelegt, denn er gilt als „Hauptnerv“ der Verkehrslogistik. Es wird versucht, alltägliche, uns allen bekannte Probleme, z.B. das Briefträgerproblem oder Probleme bei der Abfallentsorgung, durch logisches Vorgehen zu optimieren, zu minimieren bzw. zu lösen.

2 Erläuterung verkehrswirtschaftlicher Grundbegriffe

2.1 Bedeutung, Funktion und Ziele der Logistik

Das gesamte Transportgewerbe ist ein wesentlicher Bestandteil der Logistik und gewinnt mit der Zeit immer mehr an Bedeutung. Es ist notwendiger Bestandteil einer funktionierenden Volkswirtschaft. Unter dem Begriff Logistik versteht man „die Gesamtheit aller Tätigkeiten, welche auf eine bedarfsgerechte Verfügbarkeit von Objekten, Personen, Sachgütern, Dienstleistungen, Informationen und Energie ausgerichtet ist“.[4]

„Ein weiterer zentraler Begriffsinhalt der Logistik ist die zielgerichtete Über-windung von Raum und Zeit.“[5]

Nach Ehrmann ist die Aufgabe der Logistik, die richtige Menge der richtigen Güter, am richtigen Ort im System, zum richtigen Zeitpunkt, in der richtigen Qualität und zu den richtigen Kosten zu transportieren. Dabei laufen diese Prozesse nicht nur in Logistikunternehmen ab, sondern auch in Handels-, Industrie- und Dienstleistungsunternehmen, die mit dem Transport von Waren nur bedingt in Verbindung stehen. Betrachtet man die verschiedenen Güterströme lässt sich das Logistiksystem in drei Phasen unterscheiden. Unter der ersten Phase, der Beschaffungslogistik, versteht man den Güterstrom (z.B. Roh-, Hilfs- und Betriebsstoffe) vom Beschaffungsmarkt zum Eingangslager eines Industrieunternehmens, das sich unmittelbar in der Nähe der Produktionsstätte befindet. In der zweiten Phase durchlaufen die Güterströme (Rohstoffe) den Produktionsprozess und verlassen die Produktionsstätten, z.B. als Fertigfabrikate. Die Logistik der dritten Phase bezeichnet man als Distributionslogistik. Diese beinhaltet den Transport der Güter vom Absatzlager der Produktionsstätte zum Kunden.[6]

Der Ursprung der Logistik findet sich unmittelbar im Dienstleistungsbereich des Material- und Warenflusses wieder. Durch technische Entwicklungsfortschritte (z.B. automatische Hochregallager, fahrerlose Transportsysteme) und steigendes Aufkommen in diesen Bereichen erlangt die Logistik einen immer höheren Stellenwert im Unternehmen. Legt das Unternehmen den Fokus auf eine Material- und Warenfluss gerichtete Gestaltung, ist es in der Lage die Komplexität der Absatz-, Produktions- und Beschaffungslogistik ebenso wie die steigenden Aufgaben in Bezug auf Transportzeiten und Kundenzufriedenheit zu bewältigen.

Aufgabe der Logistik ist es nun Entscheidungen zu treffen, insbesondere über die Kontrolle, Planung, Überwachung und Steuerung der Güterströme, um z.B. Risiken und Fehlentscheidungen zu reduzieren, Probleme im Voraus zuerkennen und zu beheben, flexibel auf Änderungen reagieren zu können, Kosten zu minimieren und die Qualität der Leistung zu maximieren.

Des Weiteren soll durch einen optimalen Planungsprozess eine hohe Kundenzufriedenheit erreicht werden. Damit einhergehend vermindert eine optimale Auftrags- und Transportabwicklung die ökologischen Belastungen der Umwelt.[7]

2.2 Einordnung der Tourenplanung in die betriebswirtschaftliche Logistik

Die Gesamtheit eines logistischen Systems kann in Anlehnung an den o.g. Güterfluss in die Bereiche Beschaffung, Produktion, Absatz und Entsorgung gegliedert werden. Somit lassen sich die einzelnen Prozesse und Aufgaben innerhalb dieser Bereiche zusammenfassen. (vgl. Abb.1:).

Abbildung in dieser Leseprobe nicht enthalten

Abb. 1: Systemeinteilung anhand des Güterstromes[8]

Die Tourenplanung als Teilbereich der Transport- und Standortplanung lässt sich hierbei dem Bereich der Distributionslogistik zuordnen. In diesem Bereich können Planungsprobleme des Transportbereiches je nach ihrer unterschiedlichen Bedeutung und nach Länge ihres Zeitraums von strategischer, taktischer oder operativer Natur sein. Die Abb. 2 zeigt in diesem Zusammenhang einen Überblick der wichtigsten Aufgaben und ihrer Fristigkeit für den Bereich der Distributionslogistik. Die Tourenplanung stellt innerhalb dieser Einteilung eine operative und kurzfristige Planungsaufgabe dar.

Abbildung in dieser Leseprobe nicht enthalten

Abb. 2.: Aufgaben/ Bedeutung der Distributionslogistik[9]

Speditionen und viele andere Transportunternehmen müssen auf Grund der wechselnden Bedingungen ihre Touren täglich neu optimieren, was diese Einteilung rechtfertigt. Touren, die mittelfristig geplant und über einen längeren Zeitraum hinweg unverändert abgefahren werden (sogenannte Standard- bzw. Rahmentouren), werden in die strategische Entscheidungsebene einzuordnen und bilden die Ausnahme in der Branche. Hierzu zählt beispielsweise die Fahrplangestaltung im Buslinien oder Zugverkehr.

Trotz dieser Einteilung müssen alle Planungsbereiche der Distributionslogistik in ihrer Gesamtheit betrachtet werden, sie sind wechselseitig voneinander abhängig. Es ist keine Isolierung der Tourenplanung möglich, demnach beeinflusst die Anzahl der Auslieferlager die Länge der Touren, während umgekehrt die Kosten der daraus resultierenden Auslieferung bei der Tourenplanung beachtet werden müssen. Oft lässt sich das eine Problem ohne das andere nicht sinnvoll lösen. Die zu transportierende Gütermenge bestimmt die Planung der Zusammensetzung des Fuhrparks. Folglich ist eine Planung anzustreben, die über alle drei Ebenen hinweg die Ziele der Unternehmenslogistik als Ganzes zu erreichen versucht.[10]

2.3 Stellenwert des Gütertransportes auf der Straße

In der deutschen Volkswirtschaft nimmt der wachsende Gütertransport eine bedeutende Rolle ein. In Deutschland stieg in den letzten Jahren das Güteraufkommen, das jährlich auf der Straße transportiert wird, von ca. 2,9 Mrd. Tonnen im Jahr 1990 auf 3,4 Mrd. Tonnen im Jahr 2007 an. Im gleichen Zeitraum aber verdreifachte sich fast die erbrachte Verkehrsleistung von ca. 170 Mrd. km (1990) auf 466 Mrd. km (2007). Demnach stieg der Anteil des Straßengüterverkehrs an der Gesamtverkehrsleistung 2007 auf 82,9% an.

Diese wachsende Transportindustrie trägt damit in erheblichem Maße zur Wertschöpfung der Volkswirtschaft bei.[11]

Dieser Anstieg, insbesondere im Bereich der Kilometerauslastung, ist auf die veränderten Anforderungen der Wirtschaft zurückzuführen. Durch die Öffnung der osteuropäischen Märkte sowie die steigende Anzahl der Just-in-Time-Verkehre konnte der flexible Straßengüterverkehr besser reagieren als der Bahnverkehr oder die Binnenschifffahrt und somit seinen Stellenwert in der Wirtschaft erhöhen. Wird ein Unternehmen nach logistischen Aufgabenbereichen unterteilt, so stellt der Gütertransport neben der Lagerhaltung, der Auftragsabwicklung, dem Lagerhaus und der Verpackung eine der fünf Hauptaufgaben im Logistiksystem dar.[12]

Unter dem Begriff „Transport“ versteht man die Raumüberbrückung oder Ortsveränderung von Transportgütern mit Hilfe von Transportmitteln. Dabei kann das Transportgut hinsichtlich der Güterart (Verbrauchsgüter, Gebrauchsgütern), den speziellen Transporterfordernissen (Kühlgut, Flüssiggut) sowie der Sendungsgröße (Stückgut, Komplettladung) charakterisiert werden. Die zeitbezogene Beförderung wird als Transportprozess definiert und ist mit dem Transportgut und den Transportmittel Teil des Transportsystems.[13]

Die Zunahme des Gütertransportes, speziell im Straßengüterverkehr, führte in den letzten Jahren zu einer erhöhten Belastung der Bevölkerung und der Umwelt. Problematisch sind besonders eine wachsende innerstädtische Verkehrsbelastung, ein deutlicher Rückgang im Eisenbahn- und Binnenschifffahrtsverkehr (die von Experten als umweltfreundlicher eingestuft werden) und ein hoher Ressourcenverbrauch für die Umsetzung der Transportwege auf der Straße. Durch den wachsenden Anteil von Stückgütern (Ware die auf dem Transportweg noch gesammelt, umgeladen und verteilt werden muss) ist es erforderlich, die Verbindung zwischen Fern- und Nahverkehr so zu gestalten, dass die gesamtwirtschaftliche und betriebswirtschaftliche Effektivität steigt. Durch eine optimale Tourenplanung kann eine erhöhte Auslastung der Fahrzeuge und eine Reduzierung der Leerfahrten verwirklicht werden.[14]

2.4 Dispositionsaufgaben im Güterverkehr

In der Literatur existiert keine genaue Definition über die Dispositionstätigkeit im gewerblichen Güterverkehr, die eine eindeutige mathematische Beschreibung beinhaltet. Demnach wird eine Abgrenzung der Aufgabenstellung zu anderen Planungsproblemen vorgenommen. Im folgenden Kapitel werden vereinzelte Merkmale der Dispositionsaufgaben im gewerblichen Güterfernverkehr beschrieben, die den Unterschied zur depotbezogenden Tourenplanung verdeutlichen.[15]

Die Transportrelation gilt als wichtigstes Unterscheidungsmerkmal im Güterfernverkehr. Sie ist durch die Lage der Be- und Entladeorte und die Bedienreihenfolge bestimmt. In der depotbezogenen Tourenplanung ist das Depot zum einen Quelle (Ausliefertouren) und zum anderen Ziel (Sammeltouren). Wird ein Auftrag nicht direkt abgewickelt (Haus-zu-Haus Transport), sondern wird er durch Umladen unterbrochen, ändert sich die Transportrelation (gebrochener Verkehr). Beispiel hierfür ist der Transport von Speditionssammelgut. Im Vorlauf werden sämtliche Teilladungen bei den einzelnen Auftraggebern abgeholt und zum Sammelspediteur (Depot 1) transportiert. Von dort wird die gesammelte Ware zum Auslieferspediteur (Depot 2) geliefert. Schließlich erfolgt im Nachlauf die Zustellung beim Kunden. Die einzelnen Transporte erfolgen mit unterschiedlichen Fahrzeugen, so entsprechen die Dispositionsaufgaben im Vor- und Nachlauf der depotbezogenen Tourenplanung und im Hauptlauf der Tourenplanung im Güterfernverkehr (Haus-zu-Haus-Verkehr). Es wird also als erstes unterschieden, ob ein Transport direkt vom Absender zum Empfänger erfolgt oder ob zwischenzeitlich umgeladen wird. Zum zweiten muss zwischen Komplettladungen und Teilladungen unterschieden werden, d.h. es wird die gesamte Fahrzeugkapazität oder nur ein Teil zum Transport benötigt. Das dritte Merkmal der Dispositionsaufgabe ist die zeitliche Verteilung des Auftragseingangs. Sie bestimmt ob Aufträge regel- oder unregelmäßig erteilt werden. Die Wahl des Verkehrsmittels für den Transport zeigt ein weiteres Merkmal für Dispositionsentscheidungen. So kann ein Disponent entscheiden, ob der Auftrag von den eigenen Fahrzeugen abgewickelt wird oder ob ein fremder Frachtführer eingesetzt werden soll.[16]

Zielsetzung bei eigener Auftragsabwicklung sollte es sein, den Deckungsbeitrag zu maximieren. Der Deckungsbeitrag eines Auftrags ist die Differenz aus dem Erlös und den anfallenden Transportkosten. Da der Erlös des Auftrages zu Beginn bekannt ist, kann der Deckungsbeitrag durch Minimierung der Transportkosten maximiert werden.[17]

Die Transportkosten setzen sich aus auftrags-, einsatzzeit-, strecken- und den entfernungsbezogenen Fahrzeugeinsatzkosten zusammen. Die Fahrzeugdisposition errechnet die zur Transportabwicklung zu fahrenden Gesamtkilometer und die dadurch entstandene Gesamtdauer. Die Strecke mit dem geringsten Zeitaufwand und der kürzesten Gesamtentfernung bildet die kostenminimale Strecke. Der Fahrzeugeinsatzplan mit kostenminimaler Strecke besitzt somit den maximalen Deckungsbeitrag. Die meisten praktischen Aufgabenstellungen des Güterverkehrs lassen sich in Teilbereiche aufgliedern. Bei der Verfahrensentwicklung wird eine Trennung in Komplett- und in Teilladungsdisposition vorgenommen. Die hierbei auftretenden Sammel- und Verteilfahrten lassen sich als Tourenplanungsprobleme modellieren.[18]

2.5 Die Fahrzeugdisposition als Instrument der Tourenplanung

Die Fahrzeugdisposition bildet den Rahmen für die parallel verlaufende Tourenplanung und versucht die theoretischen Ansätze aus der Tourenplanung so optimal wie möglich in der Realität umzusetzen. Der Vorgang der Fahrzeugdisposition für sich kann als ausführendes Instrument der Tourenplanung gesehen werden. Es müssen individuelle Entscheidungen getroffen werden um kurzfristige Problemsituationen zu bewältigen. Zu den Aufgaben der Fahrzeugdisposition gehören die termingerechte Durchführung der Transportaufträge mit minimalem Kostenaufwand sowie die Gewährleistung von kurzen Auftragswartezeiten und Ausführungszeiten. Dabei werden eine hohe Fuhrparkauslastung, die maximale Kapazitätsauslastung der einzelnen Fahrzeuge, die Minimierung der Leerfahrten oder auch die Minimierung der Fahrzeugzahl zur Durchführung der Transportaufträge als Ziele angestrebt. Denn nur ausgelastete Verkehrsmittel führen auch zu einzelwirtschaftlich und gesamtwirtschaftlich effizientem Nutzen. Dieser wird sowohl in der Verkehrsinfrastruktur wie auch in den Verkehrsmitteln gebundenen Ressourcen deutlich. Die Fahrzeugdisposition lässt sich in vier Phasen unterteilen: die Annahme von Transportbedarfen, die Zuteilung der Aufträge, die Auftragsanweisung und die Fertigmeldung und Verbuchung. Bei der Annahme von Aufträgen wird entschieden, ob dieser mit eigenen Fahrzeugen oder durch Subunternehmer erfüllt wird. Dabei liegen die Optimierungsmöglichkeiten speziell in der Zuteilung von Aufträgen zu Fahrzeugen. Diese kann bei der „Leermeldung“ eines Fahrzeuges geschehen (Dispatching) oder bereits bei der Auftragsentstehung (Vorplanung = Scheduling) erfolgen. .[19]

Beim Dispatching (deutsch: Abfertigung) wird ein aktuell anstehenden Auftrag dem Fahrzeug zugeteilt, das leer ist bzw. die kürzeste Anfahrtsstrecke besitzt. Da das Dispatching den jeweils nächsten, freigegebenen Auftrag bearbeitet, reagiert das System schnell und flexibel. Es bietet sich bei dynamischen Umgebungen an. Das Ziel der Vorplanung ist die Zuweisung mehrerer Aufträge oder mehrere Fahrzeuge zu einem idealen Fahrplan und somit auch die Erstellung einer optimalen Auftragsreihenfolge. Voraussetzung ist die Sammlung von Aufträgen in einem „Pool“, auf den jederzeit zurück gegriffen werden kann. In der Praxis wird meist eine Mischform der beiden Verfahren eingesetzt, die in den Prioritäten immer berücksichtigt werden können.[20]

Eine effiziente Erbringung von diesen Güterverkehrsleistungen basiert auf der Beschaffung, Verknüpfung und Interpretation einer Vielzahl an Informationen. Mobile elektronische Informationssysteme stehen heute zur Unterstützung der Leistungserbringung zur Verfügung und zählen wie Ortungs- und Identifikationssysteme zu den Basissystemen. Sie bilden die Grundlage für die weitere Bearbeitung der Informationen. Durch Ortungssysteme lassen sich aktuelle Fahrzeugstandorte exakt bestimmen. Ihre Darstellung auf einer topographischen Landkarte unterstützt die Disponenten bei der Fahrzeugeinsatzplanung. Dadurch ist z.B. eine Terminierung der Ankunftszeiten bei kurzfristigen Abholaufträgen möglich, des Weiteren haben die Kunden die Möglichkeit (via Internet) ihre Sendung parallel zum Transport zu verfolgen.[21]

Nicht zu vernachlässigen ist die Servicequalität. Sie soll durch eine intelligente und solide Fahrzeugdisposition und Tourenplanung maximiert werden. Das resultierende Image in der Öffentlichkeit ist im heutigen Wettbewerb „überlebensnotwendig“, da für die Wahl des Kunden qualitative Aspekte im Vordergrund stehen. Eine sich daraus ergebene positive „Mundpropaganda“ kann dem Unternehmen den entscheidenden Vorteil verschaffen.

3 Grundlagen der Tourenplanung bei der Fahrzeugdisposition

3.1 Einführung in die Tourenplanung

Auf dem Gebiet der Tourenplanung hat in den letzten Jahren eine rasante Entwicklung stattgefunden. Die Kundenzufriedenheit sowie die Kostenminimierung stehen hier im Vordergrund. Diese Prämissen sollen durch eine optimale Planung unter Einhaltung sämtlicher Restriktionen erreicht werden. Größen wie die Anzahl der Kunden und Fahrzeuge, Bestell- bzw. Abholmengen, Kapazitätsgrenzen, Standorte und die einzelnen Entfernungen bekannt sind.[22]

Als Tourenplanungsprobleme wird eine ganze Klasse von Problemen bezeichnet, die meist stellvertretend für Auslieferungsprobleme stehen, sich aber in zahlreichen Details unterscheiden. Zu nennen sind beispielsweise das Schulbusproblem, Tourenprobleme mit Kundenzeitfenstern oder tageszeitabhängigen Fahrzeiten, Mehr-Depot-Auslieferungsprobleme, depotfreie Auslieferung, die reine Zuordnungsoptimierung, Briefträgerprobleme sowie die Travelling-Salesman-Probleme, siehe Kapitel 4.

Um dennoch eine Systematisierung und Einordnung vorzunehmen, werden Klassifizierungsschemata herangezogen. Sie zeigen, ohne Anspruch auf Vollständigkeit die Vielfalt der Nebenbedingungen die berücksichtigt werden müssen und die Komplexität in der Praxis.[23] In Anlehnung an ein solches Klassifizierungsschema zeigt Tabelle 1 einen Merkmalkatalog. Er führt die Darstellung der Merkmale in sieben Hauptkategorien (Netzwerk, Planungshorizont, Aufträge, Fuhrpark, Touren, Kostenfunktion und Zielsetzung) auf.

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 1: Merkmalkatalog für Tourenplanungsprobleme[24]

Die genannten Tourenprobleme lassen sich hinsichtlich der Lösungsansätze in knotenorientierte Probleme (verallg. Travelling- Salesman- Probleme) und kantenorientierte Probleme (verallg. Briefträgerprobleme)

aufteilen. Bei einem knotenorientierten Tourenproblem werden die Kunden als „Knoten“ (Orte in bestimmten Regionen) eines gegebenen Graphen (Transportstrecke) interpretiert. Jeder Kunde ist genau einmal zu besuchen. Die Auslieferung von Gütern eines Zentrallagers zu den vereinzelten Regionallagern gilt als solches Problem. Ziel ist, die Bedürfnisse, die an einzelnen Punkten (Knoten) entstehen, zu bedienen. Dem gegenüberstehen die kantenorientierten Tourenplanungsprobleme. Jeder Kunde ist mindestens einmal zu besuchen und wird als „Kante“ eines gegebenen Graphen gesehen. Das Ziel besteht darin, den Bedarf, der bezogen auf die einzelnen Wege (Kanten) entsteht, zu bedienen. Die Kundenstandorte sind dabei gleichmäßig über das Straßennetz verteilt (Müllabholung oder Zustellung der Post).[25]

Um die Probleme und Modelle der Tourenplanung leichter beschreiben zu können, werden folgende Grundbegriffe kurz erläutert:

- Als Depot bezeichnet man den Ort, an dem alle Fahrten beginnen oder enden.
- Werden alle Kunden und Kanten auf ein und derselben Fahrt (die im Depot beginnt und endet) bedient, spricht man von einer Tour.
- Die Route legt die Reihenfolge in der die Kunden bedient werden, fest.
- Der Tourenplan bezeichnet eine zuverlässige Lösung des Tourenproblems. Somit entspricht er der Menge von Touren, die alle Bedingungen des betrachtenden Problems erfüllen[26].

3.2 Unterscheidungskriterien von Tourenplanungsproblemen

Die Mehrheit der Tourenplanungsprobleme lässt sich im Hinblick auf vier Hauptcharakteristika unterscheiden: Depot- und Kundencharakteristik, Fahrzeugcharakteristik, Problem- oder Zusatzcharakteristik sowie vorgegebene Zielsetzungen. Jede dieser Charakteristika besitzt eine Menge von Attributen mit verschiedenen Ausprägungen.

Die Depot- und Kundencharakteristik gibt Auskunft über: die Anzahl der vorhandenen Depots, entstehende Bedarfsmengen, Ort der Bedarfsentstehung, zeitliche Beschränkungen, mögliche Reihenfolgebeziehungen und räumliche Zusammenhänge bei Teilmengen. Liegen keinerlei Zeitrestriktionen vor, so bezeichnet man das entstehende Tourenproblem als Vehicle- Routing- Problem. Bestehen jedoch feste Zeitvorgaben, spricht man von einem reinen Scheduling-Problem. Sind bei diesem Problem keine festen Zeitpunkte gegeben sondern Zeitfenster, die in einer Richtung offen sind, entstehen Bedienungsintervalle.

Die Fahrzeugcharakteristik informiert über die Anzahl der verfügbaren Fahrzeuge, ihre Kapazitäten, über die Zeitbeschränkungen der Fahrzeuge und der Touren sowie über die Anzahl der Touren pro Fahrzeug.

Die Eignung der Fahrzeuge zur Bedienung der einzelnen Kunden (nicht jeder Kunde kann durch jedes Fahrzeug bedient werden) und das Festlegen eines Plans (für eine Periode oder mehrere) zeigt die Problem- oder Zusatzcharakteristik. Die wichtigsten Zielsetzungen sind die Minimierung der zurückgelegten Entfernung, der Fahrzeiten, der benötigten Fahrzeuge und der aufgebrachten Fahrtkosten.[27]

3.3 Graphische Darstellungen von Tourenplanungsproblemen

Straßennetze lassen sich mit Hilfe der Graphentheorie sehr einfach darstellen. So werden die Entfernungen zwischen den einzelnen Kunden und dem Depot als bewertete Graphen(Knoten oder Kantenmenge und Bewertung) gesehen. Die Knoten repräsentieren z.B. die anzufahrenden Orte, die Kanten die Straßenabschnitte zwischen den Kunden und die Bewertungen entsprechen der Längen (Fahrzeiten- oder kosten) der Straßenabschnitte.[28]

Die Abbildung 3.1 zeigt beispielsweise ein Streckennetz für ein Ein-Depot-Problem mit 8 Kunden. Das Depot ist mit 0 und die Kundenorte mit den Nummer 1 bis 8 gekennzeichnet. Um das Problem zu vereinfachen sind die 8 Kunden vom Depot aus mit dem gleichen Bedarfsvolumen zu beliefern. Zeit- bzw. Längenrestriktion je Tour sowie eine Ausgeglichenheit der Tourenlängen spielen dabei keine Rolle. Ein Fahrzeug kann maximal 3 Kunden beliefern.

Die Abbildung. 3.2 zeigt die dazugehörige Entfernungsmatrix und die Abbildungen 3.3 und 3.4 mögliche Lösungsansätze.

Abbildung in dieser Leseprobe nicht enthalten

Abb.3.1: Streckennetz für ein Ein-Depot-Problem mit 8 Kunden

Abbildung in dieser Leseprobe nicht enthalten

Tabelle 2: Entfernungsmatrix

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.2.1: Erster Lösungsansatz

Abbildung in dieser Leseprobe nicht enthalten

Abbildung 3.2.2: Zweiter Lösungsansatz

Während der Tourenplan in Abbildung 3.2.1 aus den drei Touren (D,1,2,D), (D,3,4,6,5,D), (D,7,8,D) und einer Gesamtlänge von 16 Längeneinheiten besteht, enthält der Tourenplan in Abbildung 3.2.2 die drei Touren (D,2,3,D), (D,4,6,5,D), (D,7,8,1,D) mit einer Gesamtlänge von 19 Längeneinheiten. Im Vergleich der beiden Varianten erweist sich die Lösung in Abbildung 3.2.1 als sinnvoller, da die Streckenlänge geringer ist.

3.4 Die Standardprobleme der Tourenplanung

Durch die vorangegangenen grundlegenden Begriffsdefinitionen lassen sich die sogenannten Standardprobleme wie folgt beschreiben:

Innerhalb einer Periode (z.B. einem Arbeitstag) ist eine bestimmte Anzahl von Kunden vom Depot aus zu bedienen (zu beliefern oder zu entsorgen). Der Standort des Depots, Standorte der Kunden und die kürzeste Entfernung zwischen den Kunden sowie zwischen dem Depot sind bekannt. Es stehen beliebig viel gleichaltrige Fahrzeugtypen K mit der Ladekapazität Q bereit. Die Fahrzeuge sind am Depot, wo die Touren beginnen und enden, stationiert. Wird jeder Kunde vom Depot aus in einer Periode exakt einmal bedient, d.h. der Bedarf eines Kunden ist durch eine Bedienung zu decken (keine Splittung in Teilladungen möglich), handelt es sich um eine Kapazitätsrestriktion. In der Literatur wird dies auch als Capacitated- Vehicle- Routing- Problem bezeichnet. Das Ziel besteht in der Minimierung der zurückgelegten Entfernung aber auch in der Kosten- und Fahrzeitminimierung. Ein typisches Beispiel hierfür findet sich bei Paketdiensten oder bei Möbelspediteuren, bei denen die Ladekapazität begrenzt ist.[29]

Eine Zeitrestriktion erfolgt, wenn die für eine Tour erforderliche Fahrzeit nicht überschritten werden darf, wie z. B. bei Organtransporten. Sind darüber hinaus noch Zeitfenster bei der Belieferung zu beachten, spricht man von einem Vehicle- Routing- Problem mit Time Windows bzw. eine Zeitfensterrestriktion. (siehe Kapitel 4.1.2) Sie ergeben sich speziell aus Öffnungszeiten und treten bei einer Vielzahl von Tourenproblemen auf. Ziel ist es eine Minimierung der Fahrtkosten, um sowohl die Streckenlänge als auch die Fahrzeiten inklusive der durch die Zeitfenster entstehenden Wartezeiten zu kontrollieren.[30]

[...]


[1] Vgl. Domschke, Logistik: Rundreisen und Touren, 1997, S. 204

[2] Vgl. Vaterrodt, H.-J., Tourenplanung: Modelle und Verfahren, 1975, S. 2ff

[3] Vgl. Gietz, M., (Computergestützte Tourenplanung , 1993), S. 2ff.

[4] Vgl. Isermann, H., (Logistik 1998), S.21

[5] Ihde, G., (Transport 1991), S.2

[6] Vgl. Pfohl H.- Ch., (Logistiksysteme 1996), S.21

[7] Vgl. Isermann, H., (Logistik 1994), S. 34

[8] Vgl. Pfohl, H.- Ch., (Logistiksysteme 1996), S.18

[9] Vgl. Becker, J., (Logistik und CIM 1993), S. 7

[10] Vgl. Vogt, M., Vahrenkamp, R., (Tourenplanung in Ballungsgebieten, 1998), S. 18f

[11] Vgl. Verkehr in Zahlen, 2008/2009 (37, S. 232f., S. 236f.)

[12] Vgl. Stumpf, 1998, (Tourenplanung im speditionellen Güterfernverkehr), S.9f

[13] Vgl. Pfohl, H.- Ch., (Logistiksysteme 1996), S.157f.

[14] Vgl. Stumpf, P., (Tourenplanung 1998), S. 30f

[15] Vgl. Schmidt, J., (Fahrzeugeinsatzplanung, 1994), S. 20

[16] Vgl. Schmidt, J., (Fahrzeugeinsatzplanung, 1994), S. 21-23

[17] Vgl. Diederich, H., (Verkehrsbetriebslehre, 1977), S. 407f

[18] Vgl. Schmidt, J., (Fahrzeugeinsatzplanung, 1994), S. 30

[19] Vgl. Arnold, D., (Handbuch Logistik, 2004), S. B 5-26f

[20] Vgl. Hompel, M., Schmidt, T., (Warehouse Management, 2008), S. 59

[21] Vgl. Buchholz, J., Clausen, U., (Handbuch der Verkehrslogistik, 1998), S. 244f

[22] Vgl. Domschke, W., (Logistik,1997), S. 204

[23] Vgl. Vogt, M., (Tourenplanung in Ballungsgebieten 1998), S. 20

[24] Vgl. Bodin, M. ET AL., (Routing and scheduling of vehicles and crews, 1983), S. 81-83

[25] Vgl. Lackner, A., (Dynamische Tourenplanung 2004), S. 11-12

[26] Vgl. Domschke, W., (Logistik 1997), S. 204f.

[27] Vgl. Domschke, W. (Logistik 1997), S. 207-211

[28] Vgl. Vogt, M. (Tourenplanung in Ballungsgebieten 1997), S.22f

[29] Vgl. Domschke, W. (Logistik 1997), S. 211

[30] Vgl. Vogt, M. (Tourenplanung in Ballungsgebieten 1998), S. 25

Ende der Leseprobe aus 60 Seiten

Details

Titel
Tourenplanungsprobleme bei der Fahrzeugdisposition
Hochschule
Verwaltungs- und Wirtschafts-Akademie Göttingen
Veranstaltung
Abendstudium
Note
1,0
Autor
Jahr
2010
Seiten
60
Katalognummer
V164664
ISBN (eBook)
9783668750012
ISBN (Buch)
9783668750029
Dateigröße
895 KB
Sprache
Deutsch
Schlagworte
Logistik, Tourenplanung, Fahrzeugdisposition
Arbeit zitieren
Stefan Thume (Autor), 2010, Tourenplanungsprobleme bei der Fahrzeugdisposition, München, GRIN Verlag, https://www.grin.com/document/164664

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Tourenplanungsprobleme bei der Fahrzeugdisposition


Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden