Die vorliegende Arbeit ist so konzipiert, dass praktische Aspekte von Tourenplanungsproblemen in den Vordergrund gestellt werden. Anhand eines realitätsnahen Beispiels werden ausgewählte Verfahren vorgestellt und auch angewendet. Das theoretische Hintergrundwissen wird natürlich auch entsprechend behandelt und vorgestellt. Ohne eine fundierte theoretische Basis ist die systematische Lösung von komplexen Problemstellungen, zu denen Tourenplanungprobleme zweifelsohne gehören, nahezu unmöglich. Bei der Vorstellung der einzelnen Verfahren wird der theoretische Aspekt jedoch zugunsten einer umfangreicheren Darstellung praktischer Anwendungsmöglichkeiten so weit wie möglich reduziert. Daher war es auch nie mein Ziel, so viele Verfahren wie möglich in dieser Arbeit vorzustellen. Es wurden solche Verfahren ausgewählt, anhand derer besonders wichtige Aspekte hinsichtlich einer Umsetzung auf in der Realität vorkommende Probleme aufgezeigt werden konnten. Hauptsächlich ging es mir bei dieser Arbeit darum, zu verdeutlichen, dass es bei konkret vorliegenden Problemen nicht darum gehen kann, ein einzelnes Verfahren auszuwählen und anzuwenden. Vielmehr geht es darum, durch geeignete Modifikationen bestehender Verfahren eine zum konkreten Problem passende Optimierungsroutine zu entwickeln. Gerade bei sehr realitätsnahen Problemstellungen, zu denen auch die dynamische Tourenplanung mit Zeitfenstern zählt, können einzelne Standardverfahren nur den Ausgangspunkt der Problembewältigung darstellen. [...]
Inhaltsverzeichnis
Vorwort
Abbildungsverzeichnis
Tabellenverzeichnis
Algorithmenverzeichnis
Abkürzungsverzeichnis
Symbolverzeichnis
1. Grundlagen zur Tourenplanung
1.1 Die Tourenplanung im betriebswirtschaftlichen Kontext
1.2 Tourenplanung als Disziplin des Operations Research
1.3 Gang der Problemanalyse und der Problemlösung
2. Zur Vielfältigkeit von Tourenplanungsproblemen
2.1 Kriterienkatalog zur Problemidentifizierung
2.1.1 Die Ausgestaltung des Netzwerks
2.1.2 Die Beschaffenheit des Fuhrparks
2.1.3 Die Zeit als wichtiger Einflussfaktor
2.1.4 Verschiedene Zielsetzungen
2.2 Grundmodelle der Tourenplanung
2.2.1 Das Handlungsreisendenproblem
2.2.2 Das Standardproblem der Tourenplanung
2.2.3 Kombinations- und Erweiterungsmöglichkeiten der Modelle
2.3 Berücksichtigung dynamischer Aspekte
2.4 Zusammenfassung und Problempräzisierung
3. Lösungsmöglichkeiten und Szenariokonstruktion
3.1 Konzepte zur Lösung des
3.1.1 Heuristische Verfahren für Tourenplanungsprobleme
3.1.2 Spezielle Lösungsansätze für dynamische Problemstellungen
3.1.3 Tourenoptimierung mit Hilfe von Metaheuristiken
3.2 Konstruktion eines DTRP - Szenarios
4. Konstruktions- und Verbesserungsverfahren
4.1 Konstruktionsverfahren
4.1.1 Das Savingsverfahren
4.1.2 Anwendungsmöglichkeiten von Einfügeheuristiken
4.1.3 Anwendung einer „nächster Nachbar“ Heuristik
4.1.4 Anwendungsmöglichkeiten zweistufiger Verfahren
4.2 Verbesserungsverfahren
4.2.1 Intraroutenverbesserung
4.2.2 Interroutenverbesserung
4.2.2.1 Das 2-opt* Kantentauschverfahren
4.2.2.2 Verbesserung anhand multipler Kriterien
4.2.3 Verfahrensvergleich und Ergebnisdetails
4.3 Anmerkungen zur Optimalität
5. Einbeziehung veränderlicher Informationen
5.1 Klassifizierung von Änderungsmöglichkeiten
5.2 Update eines bestehenden Tourenplans
5.3 Integration statischer Algorithmen in die Updateroutine
5.4 Betrachtung von Änderungen im Beispielproblem
6. Vorstellung weiterer Lösungsmöglichkeiten
7. Eine kritische Rekapitulation mit Ausblick
Anhang
Literaturverzeichnis
Eidesstattliche Erklärung
Vorwort
Die vorliegende Arbeit ist so konzipiert, dass praktische Aspekte von Tourenplanungs-problemen in den Vordergrund gestellt werden. Anhand eines realitätsnahen Beispiels werden ausgewählte Verfahren vorgestellt und auch angewendet. Das theoretische Hintergrundwissen wird natürlich auch entsprechend behandelt und vorgestellt. Ohne eine fundierte theoretische Basis ist die systematische Lösung von komplexen Problemstellungen, zu denen Touren-planungprobleme zweifelsohne gehören, nahezu unmöglich. Bei der Vorstellung der einzelnen Verfahren wird der theoretische Aspekt jedoch zugunsten einer umfangreicheren Darstellung praktischer Anwendungsmöglichkeiten so weit wie möglich reduziert.
Daher war es auch nie mein Ziel, so viele Verfahren wie möglich in dieser Arbeit vorzustellen. Es wurden solche Verfahren ausgewählt, anhand derer besonders wichtige Aspekte hinsichtlich einer Umsetzung auf in der Realität vorkommende Probleme aufgezeigt werden konnten. Hauptsächlich ging es mir bei dieser Arbeit darum, zu verdeutlichen, dass es bei konkret vorliegenden Problemen nicht darum gehen kann, ein einzelnes Verfahren auszuwählen und anzuwenden. Vielmehr geht es darum, durch geeignete Modifikationen bestehender Verfahren eine zum konkreten Problem passende Optimierungsroutine zu entwickeln. Gerade bei sehr realitätsnahen Problemstellungen, zu denen auch die dynamische Tourenplanung mit Zeitfenstern zählt, können einzelne Standardverfahren nur den Ausgangs-punkt der Problembewältigung darstellen.
Vor dem Abschluss dieser einleitenden Worte möchte ich die Gelegenheit nutzen, mich für die entgegengebrachte Unterstützung zu bedanken. Zunächst bedanke ich mich bei Herrn Dr. Kulmann, der mir durch zahlreiche e-Mails immer wieder interessante Denkanstöße gegeben hat und mich auch in kritischen Situationen immer unterstützt hat. Des Weiteren bedanke ich mich bei meiner langjährigen Freundin und ehemaligen Schulkameradin Frau Mansfeld für ihre wertvollen Anregungen und Kritiken. Ein besonderer Dank gilt meiner Lebensgefährtin Frau Krybus, die mich während der Fertigstellung dieser Arbeit nach allen Kräften und in jeglicher Hinsicht unterstützt hat.
Lars Laboch
Kapitel 1 Grundlagen zur Tourenplanung
Bei Tourenplanungsproblemen geht es im Allgemeinen darum, Fahrzeugtouren hinsichtlich einer im Vorfeld zu benennenden Zielsetzung optimal einzuplanen. Die Fahrzeuge können dabei einer bereits existierenden Fahrzeugflotte angehören und somit als feste Größe betrachtet werden, oder die Planung der Fahrzeugflotte kann Bestandteil des Optimierungsprozesses sein. Die Aufgabe der Fahrzeuge und deren Fahrer besteht darin, an geographisch unterschiedlichen Punkten einen, wie auch immer gearteten, Service zu leisten.[1]
Ein häufig verwendetes Zielkriterium ist die Minimierung der für den Tourenplan insgesamt benötigten Fahrtzeit.[2] Darüber hinaus können aber je nach konkreter Problemausprägung auch andere Zielsetzungen, wie zum Beispiel die Minimierung der Gesamtkosten des Tourenplans, die Minimierung nicht besuchter Kunden in einer Planperiode, oder eine möglichst gleichmäßige Auslastung der Touren relevant sein.[3]
Als Restriktionen werden häufig die Fahrzeugkapazität und die Routenlänge bzw. -zeit betrachtet.[4] Eine weitere wichtige Restriktion stellen Zeitfenster dar. Zeitfenster besagen, dass es nur bestimmte Zeiten oder Zeitintervalle gibt, innerhalb derer der Service stattfinden kann.[5]
Die bisher genannten Kriterien können sowohl Bestandteil einer statischen als auch einer dynamischen Problemstellung sein. Ein statisches Tourenplanungsproblem liegt dann vor, wenn alle problemrelevanten Daten bekannt sind und sich diese im Zeitablauf auch nicht mehr ändern. Bei einem dynamischen Tourenplanungsproblem können sich aber wichtige Daten im Zeitablauf ändern, so dass ein bereits optimaler Tourenplan gegebenenfalls modifiziert werden muss, damit die Erfüllung der Zielsetzung unter Einhaltung aller Restriktionen gewährleistet bleibt.[6]
Die Anwendungsgebiete der Tourenplanung sind sehr vielfältig. In der Praxis werden Touren von Spediteuren und Paketdiensten, von Taxi Unternehmen, von Kurier- und Rettungsdiensten sowie von öffentlichen Verkehrsbetrieben geplant.[7] Die Liste ist damit keinesfalls vollständig und soll nur einen ersten Eindruck über die Relevanz der Tourenplanung für praktische Problemstellungen liefern.
Der Fokus dieser Arbeit ist auf die Tourenplanung eines Reparaturdienstes gerichtet. Ein solches Dienstleistungsunternehmen wird von den Kunden beauftragt defekte Geräte oder Anlagen zu reparieren, wobei es sich bei solchen Unternehmen um Installationsfirmen für sanitäre Anlagen oder auch um Reparaturdienste für elektronische Haushaltsgroßgeräte handeln kann. Um eine solche Reparatur durchführen zu können, muss ein Mitarbeiter der Firma den Kunden aufsuchen und das Gerät vor Ort instand setzen. Da der Kunde oftmals nicht den ganzen Tag über anwesend ist, sind Zeitfenster hier von besonderer Bedeutung. Zudem sind dynamische Aspekte zu berücksichtigen, d.h. es sind nicht unbedingt alle problemrelevanten Daten zu Beginn einer Planungsperiode bekannt. Es können neue Aufträge eingehen deren Erfüllung unter Beibehaltung des bestehenden Tourenplans nicht möglich ist, aber durch eine Planumstellung möglich wäre. In solchen Fällen ist eine Modifizierung des bestehenden Tourenplans unerlässlich.
Bevor die Problemstellungen im Folgenden detaillierter beschrieben und behandelt wird, soll zunächst eine Einordnung der Tourenplanung in den betriebswirtschaftlichen Kontext und in das Forschungsgebiet des Operations Research erfolgen. Im Anschluss daran wird der weitere Verlauf der Untersuchung skizziert.
1.1 Die Tourenplanung im betriebswirtschaftlichen Kontext
Die Tourenplanung lässt sich in das Aufgabengebiet der betriebs-wirtschaftlichen Logistik einordnen. In diesem Kontext besteht die Kernaufgabe darin, ein nachgefragtes Gut oder Produkt zum richtigen Zeitpunkt in der richtigen Menge am vereinbarten Übergabeort zu minimalen Kosten bereitzustellen.[8] Der Güterfluss lässt sich in diesem Zusammenhang idealtypisch in die Phasen der Beschaffung, Produktion, Absatz und Entsorgung einteilen. Die Tourenplanung ist dabei als ein Teilproblem der Distributionslogistik zu sehen. Hinsichtlich des Güter-flusses ist die Distributionslogistik ihrerseits dem Absatz von Gütern oder Produkten zugeordnet. Das Aufgabenfeld der Distributionslogistik umfasst dabei die strategische Planung, wie zum Beispiel die Standortwahl, taktische Aufgabenstellungen, worunter beispielsweise die Festlegung des Lieferbereiches und der Fuhrparkgröße fallen, und eben auch operative Entscheidungen wie die konkrete Planung der Touren.[9] Zu beachten ist hierbei, dass die einzelnen Teilaufgaben nicht isoliert voneinander betrachtet werden können, da zum Beispiel die Festlegung eines Liefergebietes die Größe des Fuhrparks, und somit die Tourenanzahl und Tourenlänge, beeinflusst. Umgekehrt können aber die hieraus resultierenden Touren bei zu hohen Kosten Einfluss auf strategische Entscheidungen, wie beispielsweise die Standortwahl, nehmen.
Auch wenn in der betriebswirtschaftlichen Logistik primär von Gütern ausgegangen wird, so ist ein enger Zusammenhang mit der hier behandelten Problemstellung gegeben. Ein Reparaturdienst bietet zwar kein Gut im eigentlichen Sinne an, aber der zu erbringende Service ist quasi sein Produkt und dieses muss ebenfalls nach den besagten Kriterien abgesetzt werden.
1.2 Tourenplanung als Disziplin des Operations Research
Im Hinblick auf das Forschungsfeld des Operations Research lässt sich die Tourenplanung eindeutig der Graphentheorie zuordnen.[10] Ein Graph bildet real vorhandene Netzwerke, wie zum Beispiel Straßennetze, in einfacher und anschaulicher Weise ab und ist so in der Lage, einen ersten Überblick über komplexe Zusammenhänge zu liefern.
Grundsätzlich besteht ein Graph aus einer nichtleeren Menge von Knoten V, einer Menge von Kanten E mit V ∩ E = Â und einer Inzidenzabbildung, die jedem Element e c E genau zwei Elemente i,j c V zuordnet.[11] Im weiteren Verlauf wird für einen solchen Graphen die übliche Notation G = [V, E] verwendet. Des Weiteren lassen sich Tourenplanungsprobleme dem Bereich der kombinatorischen Optimierung zuordnen. Ein kombinatorisches Optimierungsproblem liegt dann vor, wenn die Menge der möglichen Alternativen begrenzt ist bzw. der zulässige Lösungsbereich endlich ist.[12] Es geht mit anderen Worten darum, durch verschiedene Anordnungen der zu betrachtenden Objekte eine Menge zulässiger Lösungen zu generieren und aus dieser Menge dann diejenige Lösung zu ermitteln, die gemäß den Zielkriterien als optimal angesehen werden kann.
Eine weitere wichtige Unterteilung von Tourenplanungsproblemen ist die Einteilung in kantenorientierte und knotenorientierte Probleme.[13] Da ein Graph aus Kanten und Knoten besteht, müssen bei kantenorientierten Problemen demnach alle oder zumindest ein Teil der Kanten durchlaufen werden. Bei knotenorientierten Problemen stehen hingegen die einzelnen Knoten im Vordergrund. Ein praktisches Beispiel für ein kantenorientiertes Problem ist unter anderem das Briefträgerproblem, bei dem alle Straßen eines Zustellbezirkes mit der Zielsetzung, die unproduktiven Strecken zu minimieren, durchlaufen werden müssen.[14]
Die Kunden eines Reparaturdienstes sind jedoch als Knoten in einem Straßennetzwerk zu interpretieren; es werden somit keine kompletten Straßen bedient und dementsprechend handelt es sich bei der hier zugrunde liegenden Problemstellung um ein knotenorientiertes Optimierungsproblem.
1.3 Gang der Problemanalyse und der Problemlösung
Im weiteren Verlauf werden in Kapitel 2 Grundprobleme der Tourenplanung vorgestellt und Möglichkeiten der Klassifizierung eines konkreten Problems aufgezeigt. Kapitel 3 gibt einen Überblick über prinzipielle Möglichkeiten zur Problemlösung. Anschließend werden in Kapitel 4 Konstruktions- und Verbesserungsverfahren vorgestellt. Die Anwendung dieser Verfahren beschränkt sich hierbei zunächst auf eine statische Problemausprägung. In Kapitel 5 werden Übertragungsmöglich-keiten der vorgestellten Methoden in ein dynamisches Umfeld erörtert. Zur Anwendung weiterer Lösungsmethoden und deren Eignung zur Problembewältigung liefert Kapitel 6 einige Anhaltspunkte. Im Anschluss hieran wird in Kapitel 7 abschließend ein Resümee der Arbeit und unter Berücksichtigung praktischer Aspekte noch ein kurzer Ausblick angegeben.
Kapitel 2 Zur Vielfältigkeit von Tourenplanungsproblemen
In der Realität existieren sehr viele unterschiedliche Bereiche und Aufgaben bei deren Bewältigung die Tourenplanung eine bedeutende Stellung einnimmt. Da all diesen Bereichen und Aufgabenstellungen unterschiedliche Problemausprägungen zugrunde liegen, stellen sich Tourenplanungsprobleme als sehr facettenreich dar. Die Planung einer Busroute oder -linie bringt andere Anforderungen mit sich als beispielsweise die Planung des Einsatzes von Rettungsfahrzeugen oder die Routen- und Einsatzplanung eines Fahrradkuriers. Entsprechend der mannigfaltigen konkreten Problemausprägungen ist es nicht verwunderlich, dass es in der wissenschaftlichen Theorie viele unterschiedliche Modelle und Lösungsansätze für Tourenplanungsprobleme gibt.
Vor diesem Hintergrund ist es zweckmäßig, zunächst Ansatzpunkte und Möglichkeiten zur Klassifizierung eines konkret vorliegenden Problems anzugeben, bevor entsprechende Lösungsverfahren behandelt werden.
In den Abschnitten 2.1 bis 2.3 werden solche Klassifizierungsansätze vorgestellt. Darauf aufbauend wird in Abschnitt 2.4 das dieser Arbeit zugrunde liegende Problem näher spezifiziert.
2.1 Kriterienkatalog zur Problemidentifizierung
In diesem Abschnitt wird ein Kriterienkatalog als Hilfestellung zur genauen Identifizierung des vorliegenden Problemtyps vorgestellt. Der Katalog erhebt nicht den Anspruch der Vollständigkeit sondern ist vielmehr auf das in dieser Arbeit fokussierte Problem eines Reparaturservices zugeschnitten.
2.1.1 Die Ausgestaltung des Netzwerks
Das dem Problem zugrunde liegende Netzwerk bzw. der Graph kann unterschiedlicher Natur sein.[15] Sind die Knoten und deren Positionen in Form von Koordinaten, also (xi, yi) und (xj, yj), angegeben, so handelt es sich um ein Koordinatennetz. Als Kantenlänge bzw. Distanz zwischen den Knoten gilt dann der euklidische Abstand. Dies entspricht formal dem Ausdruck .
Wird hingegen von einem Straßennetz ausgegangen, so entfallen diese luftlinienartigen Verbindungen. Vor einer Optimierung in einem solchen Netzwerk muss zunächst eine Matrix mit kürzesten Wegen zwischen den Knoten erstellt werden. Nur so ist es möglich, die zurückgelegte Entfernung entsprechend zu bewerten. Das Straßennetz kann dabei symmetrisch, das bedeutet ohne Einbahnstraßen, asymmetrisch oder gemischt sein.[16] Zudem kann der Ort der Nachfrage als Knoten oder als Kante vorliegen. Auch ein Mix ist in diesem Zusammenhang möglich.[17] Des Weiteren ist die Anzahl der Depots, welche der Position an der die Fahrt eines Fahrzeuges beginnt und eventuell auch endet entsprechen, zu berücksichtigen. Im Hinblick auf dynamische Aspekte, auf welche in Abschnitt 2.3 näher eingegangen wird, ist es zudem von Bedeutung, festzustellen, ob es sich bei der Problem-stellung und dem zugehörigen Netzwerk um ein eher lokales Gebiet oder um ein eher globales Gebiet handelt. Bei kleineren Gebieten haben die Zeitrestriktionen eine höhere Priorität und eine kleine Veränderung kann zu einer kompletten Revidierung des bisherigen Plans führen. Bei globalen Gebieten existieren jedoch oftmals ausreichende Zeitpuffer.[18]
2.1.2 Die Beschaffenheit des Fuhrparks
Hinsichtlich des Fuhrparks ist es zunächst einmal interessant zu wissen, ob es sich um mehrere Fahrzeuge oder nur um ein einziges Fahrzeug handelt. Ist nur ein Fahrzeug gegeben, so ist das Problem leichter zu lösen, da eine Zuordnung von Fahrzeug zu Kunde entfällt.[19] Sind mehrere Fahrzeuge vorhanden, so ist zu klären, ob es sich bei diesen um homogene oder heterogene Vehikel handelt. Dies ist besonders dann von Interesse, wenn Kapazitätsrestriktionen berücksichtigt werden müssen.[20] Sollte ein Fahrzeug auf einer Auslieferungstour eingesetzt sein und die Fahrzeugkapazität nicht für alle Kunden der Tour ausreichen, so stellt sich die Frage, ob ein anderes Fahrzeug eingesetzt werden kann oder ob ein oder mehrere Aufträge dieser Tour teilbar sind, die Kunden also von mehreren Fahrzeugen beliefert werden können.[21] Zudem kann zwischen geschlossenen und offenen Touren unterschieden werden. Geschlossene Touren liegen vor, wenn das Fahrzeug nach Beendigung der Tour wieder zum Depot zurückkehrt.[22] Bei Paketdiensten, die zwischen Zustell- und Abholtouren unterscheiden und zudem verstärkt mit Subunternehmern zusammenarbeiten, ist eine Rückkehr der Zustellfahrzeuge zum Depot nicht unbedingt erforderlich.
2.1.3 Die Zeit als wichtiger Einflussfaktor
Tourenplanungsprobleme unterliegen in vielerlei Hinsicht zeitlichen Einflüssen und Restriktionen. Bei der Einhaltung von Fahrplänen, wie sie bei Bus- und Bahnverkehren vorliegen, ist dem zeitlichen Aspekt oberste Priorität zugeordnet.[23] Sind dagegen Zeiträume in Form von Zeitfenstern relevant, so stellt sich die Frage, ob diese Termine harte Bedingungen darstellen, sie also unter keinen Umständen verletzt werden dürfen, oder ob Verletzungen der Zeitfenster in Form von Verspätungen zulässig sind.[24] Die maximal zulässige Zeit pro Tour ist bei den meisten Tourenplanungs-problemen ebenfalls ein Kriterium das berücksichtigt werden muss.[25] Des Weiteren kann die Zeit mit der Art der Nachfrage in Verbindung gebracht werden. Die Nachfrage kann bereits vor dem Prozess der Tourenplanung bekannt oder zumindest stochastisch vorhersehbar sein. In einem dynamischen Umfeld kann sich die Nachfragesituation aber zu jedem möglichen Zeitpunkt ändern. Es ist denkbar, dass Kunden keinen Service mehr benötigen oder das Kunden hinzukommen und schnell bedient werden möchten. Ebenfalls von Bedeutung ist der der Planung zugrunde liegende Zeitraum. Es kann sich um nur eine Periode, zum Beispiel einen Arbeitstag, oder um mehrere Perioden handeln. Werden mehrere Perioden betrachtet, so bietet sich die Möglichkeit, Aufträge gegebenenfalls in eine Folgeperiode zu verschieben.
2.1.4 Verschiedene Zielsetzungen
Die oben skizzierten Restriktionsmöglichkeiten beziehen sich auf sehr unterschiedliche Aspekte. Hinsichtlich der Zielsetzung einer Touren-optimierung sind jedoch ebenfalls verschiedene Kriterien möglich.[26] Die Minimierung der Kosten oder der zurückgelegten Distanz ist sicherlich ein wichtiges Ziel der Tourenplanung, aber gerade unter Berücksichtigung von Zeitfenstern und einem dynamischen Umfeld können weitere Ziele hinzu-kommen.[27] Wenn ein Unternehmen besonders kundenorientiert am Markt agiert, wird es versuchen, Verspätungen so weit wie möglich zu reduzieren oder sie gar nicht entstehen zu lassen. Andererseits werden Unternehmen, die primär kostenorientiert handeln, einen Kunden mit einem nicht lohnenswert erscheinenden Auftrag eher abweisen. Kommt es in einem dynamischen Umfeld zu einem Totalausfall eines Fahrzeugs, so stellt sich die Frage, ob die verbleibenden Fahrzeuge die Kunden der ausgefallenen Tour unter Vernachlässigung des Kostenoptimums anfahren, oder ob die auf der Tour noch offenen Aufträge auf spätere Perioden verschoben werden.
Die folgende Tabelle stellt die genannten Aspekte nochmals in übersichtlicher, stichpunktartiger Form zusammen, wobei die besonders hervorgehobenen Ausprägungsformen dem in dieser Arbeit fokussierten Problemtyp entsprechen.
Abbildung in dieser Leseprobe nicht enthalten
2.2 Grundmodelle der Tourenplanung
Eine weitere Hilfestellung zur Klassifizierung eines konkret vorliegenden Optimierungsproblems aus dem Bereich der Tourenplanung geben die im Folgenden dargestellten Grundmodelle. Solche Grundmodelle gehen zumeist von sehr speziellen Annahmen aus, können aber bei Bedarf oftmals verallgemeinert werden.
2.2.1 Das Handlungsreisendenproblem
Bei diesem Problem, welches auch als Travelling Salesman Problem bzw. TSP bekannt ist, geht es darum, eine optimale Reiseroute von einem Standort über eine Anzahl vorgegebener Orte zurück zum Ausgangsort zu finden.[28] Das typische Optimierungsziel besteht in der Minimierung der insgesamt zurückgelegten Distanz bzw. der insgesamt entstandenen Kosten. Da der variable Kostenanteil einer solchen Rundreise im Wesentlichen von der zurückgelegten Distanz abhängt, können beide Begriffe hier synonym verwendet werden.
Betrachtet wird ein symmetrisches TSP, d.h. es liegt ein bewerteter Graph G = [V, E; d] vor und die Distanz zwischen Knoten i und Knoten j entspricht derjenigen von Knoten j nach Knoten i, es gilt demnach dij = dji. Des Weiteren seien alle Entfernungen bekannt und in einer Distanzmatrix D erfasst. Für den Fall i = j soll dij = dji = ºgelten. Gesucht ist ein Hamiltonscher Kreis in G, also eine Kantenfolge die jeden Knoten von G genau einmal enthält.[29] Formal lässt sich das TSP als binäres Optimierungsproblem wie folgt darstellen:[30]
Abbildung in dieser Leseprobe nicht enthalten
Die Gleichungen (2) und (3) besagen, dass jeder Knoten auf der Rundreise besucht und wieder verlassen wird. Durch die Bedingung (4) wird erreicht, dass keine Untertour, welche sich durch eine Rundreise über weniger als n Knoten ausdrückt, Teil einer zulässigen Lösung des TSP sein kann.[31]
Bezüglich der Komplexität des TSP ist noch anzumerken, dass es sich um ein NP - schweres Problem handelt. Das bedeutet, dass es keinen Algorithmus nach heutigem Wissensstand gibt, der das Problem mit polynomialen Rechenaufwand zu lösen vermag.[32]
2.2.2 Das Standardproblem der Tourenplanung
Das Standardproblem ist auch als Vehicle Routing Problem, kurz VRP, bekannt. Es sollen n Kunden mit den zur Verfügung stehenden Fahrzeugen genau einmal besucht werden. Jeder Kunde i, mit i = 1,…,n, hat dabei einen bekannten und als sicher geltenden Bedarf hi. Der Fuhrpark setzt sich aus k, mit k = 1,…,m, Fahrzeugen zusammen. Die Vehikel sind alle identisch und haben eine Kapazität von Qk. Durch die Kapazitätsrestriktion ist es in der Regel nicht mehr möglich, dass alle Kunde von einem Fahrzeug bedient werden können. Alle Fahrzeuge starten von einem Depot, für welches hier die Notation i = 0 verwendet wird, und beenden ihre Tour auch dort. Bevor eine Route festgelegt wird, müssen zunächst die Fahrzeuge und Kunden zueinander in Beziehung gebracht werden. Eine Tour entsteht durch die Zuordnung von Fahrzeug zu Kunden, also der Festlegung, welches Fahrzeug welche Kunden besucht. Die Route eines Fahrzeugs ist durch die Reihenfolge, in welcher es die Kunden anfährt, bestimmt. Der Tourenplan wird durch die Gesamtheit aller Touren definiert. Ein zulässiger Tourenplan liegt dann vor, wenn alle Restriktionen eingehalten werden.[33]
Wie beim bereits vorgestellten Handlungsreisendenproblem soll auch hier von einem ungerichteten Graphen mit symmetrischer Entfernungsmatrix D ausgegangen werden. Die Bestimmung einer solchen Matrix ist für alle Tourenplanungsprobleme unerlässlich. Wie eine solche Distanzmatrix konkret ermittelt wird soll an dieser Stelle nicht näher behandelt werden. Im Rahmen der Szenariokonstruktion[34] wird hierauf noch näher eingegangen. Das Zielkriterium besteht auch hier in einem kostenminimalen Tourenplan. Das Problem kann, wie das TSP, als Optimierungsproblem mit binären Variablen aufgefasst werden.[35]
Abbildung in dieser Leseprobe nicht enthalten
Gleichung (6) stellt bei diesem Modell sicher, dass jeder Kunde einem Fahrzeug zugeordnet ist. Das Depot wird hiervon ausgenommen, da es von allen Fahrzeugen angefahren wird. Die Kapazitätsrestriktion wird durch die Formulierung (7) berücksichtigt. Die Gleichungen (8a) und (8b) stellen sicher, dass ein besuchter Knoten auch wieder verlassen wird und die Bedingung (9) entspricht der bereits vorgestellten Bedingung (4) für das Travelling Salesman Problem.
Auch das Vehicle Routing Problem kann bezüglich der Komplexität in die Klasse der NP - schweren Optimierungsprobleme eingeordnet werden.[36]
2.2.3 Kombinations- und Erweiterungsmöglichkeiten der Modelle
Die genaue Analyse der beiden vorgestellten Basismodelle liefert wichtige Erkenntnisse über die Problemstruktur und ermöglicht so einen Modellentwurf für ein konkret vorliegendes Tourenplanungsproblem. Für das dieser Arbeit zugrunde liegende Optimierungsproblem eines Reparaturdienstes lassen sich beide Grundmodelle kombinieren. Ein reines TSP liegt nicht vor, da mehrere Fahrzeuge zum Einsatz kommen. Beim klassischen VRP werden mehrere Vehikel betrachtet, diese unterliegen aber Kapazitätsrestriktionen. Die Fahrzeuge eines Reparaturdienstes unterliegen in diesem Sinne keinen Kapazitätsrestriktionen, da dem Kunden keine Waren im eigentlichen Sinne geliefert werden. Die Fahrzeuge solcher Firmen sind in der Regel so gewählt, dass die notwendigen Werkzeuge und eventuell einige Ersatzteile transportiert werden können und so die Nachfrage des Kunden nach Service befriedigt werden kann. Da der Kunde nicht immer am Ort der Nachfrage erreichbar ist, werden zudem Zeitfenster der Form (fi, li) benötigt. Die Variable fi steht für den frühestmöglichen Zeitpunkt des Servicebeginns beim Kunden i und li entsprechend für den spätestmöglichen Zeitpunkt des Servicebeginns beim Kunden i. Innerhalb dieser Zeitfenster ist dann der Kunde erreichbar und eine Reparatur an dem defekten Gerät möglich. Die beiden bereits erwähnten Grundmodelle müssen demnach kombiniert und um Zeitrestriktionen in Form von Zeitfenstern erweitert werden.
Abbildung in dieser Leseprobe nicht enthalten
Obwohl das so konstruierte Modell kein typisches Grundmodell der Tourenplanung darstellt, ist die als m-TSPTW bezeichnete Problemstellung innerhalb der Modelle zur Tourenoptimierung wohlbekannt. Auch das m-TSPTW lässt sich als Modell mit Binärvariablen darstellen.[37]
Statt der bisherigen Verwendung von Distanzen werden in der Zielfunktion (10) nun Kosten c verwendet, wobei cij die Kosten des Weges von i nach j darstellen. Wie bereits erwähnt lassen sich die Kosten als eine Funktion der zurückgelegten Distanz dij ausdrücken. Da aber bei eventuell gegebenen Wartezeiten wi, die immer dann auftreten, wenn das den Kunden i anfahrende Fahrzeug k vor dem frühestmöglichen Servicestartpunkt fi beim Kunden eintrifft, Kosten der Form Abbildung in dieser Leseprobe nicht enthaltenentstehen können, erscheint die Darstellung von Kosten statt Distanzen zweckmäßiger. Zusätzliche Kosten für Wartezeiten entstehen insbesondere dann, wenn die Mitarbeiter Stundenlöhne erhalten. Durch die Gleichung (11) wird sichergestellt, dass ein Fahrzeug k die maximal zulässige Routenzeit Zk nicht überschreitet. Der Ausdruck (12) ist lediglich eine andere Darstellungsform der Gleichungen (8a) und (8b), während Bedingung (13) den Bedingungen (4) und (9) entspricht. Die Restriktion (14) dient der Sicherstellung der Kompatibilität zwischen den Ankunftszeiten zweier Kunden. Durch die Bedingungen (15) und (16) wird sichergestellt, dass der Servicebeginn Kunden i innerhalb seines Zeitfensters (fi, li) liegt.
Da das obige Modell eine Verallgemeinerung des TSP darstellt, ist es ebenfalls der Klasse NP - schwerer Probleme zuzuordnen.
Bevor im nächsten Abschnitt auf die dynamischen Aspekte bei Touren-planungsproblemen näher eingegangen wird, soll das erstellte Modell anhand der folgenden Graphik verdeutlicht werden.
Dem Depot wurde in Abbildung 1 ebenfalls ein Zeitfenster zugeordnet. Die maximale Tourenlänge je Fahrzeug wird dadurch auf neun Stunden begrenzt. Der abgebildete Tourenplan ist zulässig, es werden alle geforderten Bedingungen erfüllt. Da bereits in dieser beispielhaften Skizze eine Fülle von Angaben enthalten ist, sind die wesentlichen Informationen in der folgenden Tabelle zusammengefasst.
Abbildung in dieser Leseprobe nicht enthalten
2.3 Berücksichtigung dynamischer Aspekte
Die bislang getroffenen Annahmen und die darauf aufbauenden Modelle haben prinzipiell einen statischen Charakter. Um ein vorliegendes Problem als statisch oder dynamisch charakterisieren zu können ist es zwingend notwendig zu wissen, wann dem Planer bzw. Disponenten die benötigten Informationen zur Verfügung stehen.[38] Sind alle nötigen Informationen bereits zu Beginn des Planungs- bzw. Optimierungsprozesses bekannt und als feste Größe gegeben, liegt ein statisches Problem vor. Können sich aber die dem Problem zugehörigen Daten im Zeitablauf ändern, ist das Problem als dynamisch einzustufen.
Durch die explizite Berücksichtigung veränderlicher Informationen ist es quasi nicht mehr möglich das Problem durch einen einzigen Optimierungsprozess zu lösen. Eine zufrieden stellende Lösung ist nur durch Etappenlösungen zu erreichen, d.h. das ein Problem immer bloß aufgrund der aktuell verfügbaren Informationsgrundlage gelöst wird und bei neuen Informationen diese entsprechend in die Problemstellung integriert werden müssen.[39] Unter Umständen kann zum Beispiel ein anfragender Kunde, der zuvor nicht in der Tour eines Fahrzeugs eingeplant war, die bisherige Tourenplanung für das Fahrzeug grundlegend ändern oder sogar zur Revidierung des gesamten Tourenplans führen.
Bevor einige Kriterien, die für die Unterscheidung von dynamischen und statischen Tourenplanungsproblemen besonders relevant erscheinen, vorgestellt werden, sind zunächst die bereits erwähnten „Informationen“ in den Fokus der Analyse zu setzen. Neben den essentiellen Angaben, wie zum Beispiel die Anzahl der Fahrzeuge, Größe des Servicegebietes oder die zu berücksichtigende Anzahl der bereits zu Beginn des Optimierungsprozesses vorhandenen Kunden, benötigt der Entscheidungsträger in einem dynamischen Umfeld noch weitere Informationen. Die folgenden Aspekte stellen lediglich eine Auswahl der wichtigsten Faktoren dar.[40]
a) Der Disponent muss zu jedem Zeitpunkt Kenntnis über die aktuelle Position der Fahrzeuge haben.
b) Die bereits geplante Tour muss für jedes Fahrzeug bekannt sein.
c) Der Ort der neuen Nachfrage muss genau bestimmt werden können.
d) Ebenfalls müssen die Entfernungen und Fahrtzeiten zwischen den jeweiligen Servicepunkten bzw. Kunden bekannt sein.
e) Die Eigenschaften des zugrunde liegenden Netzwerks müssen bei der Planung ebenfalls berücksichtigt werden.
Hinsichtlich dieser Faktoren ist es natürlich zwingend erforderlich, dass die Informationen auch entsprechend kommuniziert werden können. Ein Kunde muss die Möglichkeit haben, seinen Wunsch gegenüber der Firma zu äußern. Der Disponent oder Entscheidungsträger muss seinerseits die Möglichkeit haben, den Fahrern bei Bedarf eine Änderung des Plans mitzuteilen.[41]
Eine Hilfestellung hinsichtlich der Klassifizierung in statische und dynamische Tourenplanungsprobleme leistet der im Folgenden skizzierte Kriterienkatalog.[42]
a) Der Faktor Zeit
Bei dynamischen Problemstellungen ist die Dimension Zeit von größter Bedeutung. Um zum Beispiel neue Aufträge optimal zuordnen zu können, muss der Disponent zu dem Zeitpunkt, zu welchem er die Information über eine geänderte Auftragslage erhält, den genauen Standort der zur Auftragserledigung in Frage kommenden Fahrzeuge kennen. Die bloße Berücksichtigung von Zeitfenstern ist ebenfalls noch kein Indiz für ein dynamisches Optimierungsproblem, da das Problem solange als statisch anzusehen ist, wie sich die Zeitfensterrestriktionen im Zeitablauf nicht ändern.
b) Unsicherheiten aufgrund der Informationsgrundlage
Zu Beginn der Planung sind möglicherweise nicht alle relevanten Informationen bekannt. Im Zeitablauf können neue Informationen hinzukommen und müssen in den Plan integriert werden. Hinsichtlich der Güte zukünftiger Informationen lassen sich diese in ungenaue und gänzlich unbekannte Informationen einteilen. Ungenaue Informationen liegen dann vor, wenn beispielsweise das Auftreten neuer Servicepunkte mit einer gewissen Wahrscheinlichkeit vorhergesagt werden kann. Wenn ein Fahrzeug während einer Tour komplett ausfällt, dann handelt es sich um eine Information von höchster Bedeutung für die weitere Planung, aber der Zeitpunkt eines solchen Totalausfalls kann in der Regel weder hinreichend präzise geschätzt noch vorhergesagt werden.
c) Konzentration auf unmittelbare Ereignisse
Der Disponent muss sich in dynamischen Szenarien auf unmittelbar bevorstehende Ereignisse konzentrieren. Ein Kunde, der erst ist den nächsten Tagen um eine Reparatur gebeten hat, ist in der Situation des aktuellen Tourenplans nicht interessant. Zudem ist die Information, dass dieser Kunde in einigen Tagen eine Reparatur wünscht, mit Unsicherheiten behaftet. Es ist denkbar, dass er sich anders entscheidet und den Service nicht mehr in Anspruch nehmen möchte, da er sich zum Beispiel ein neues Gerät angeschafft hat. Informationen und Ereignisse im aktuellen Zeitrahmen weisen eine höhere Dringlichkeit auf und benötigen die volle Aufmerksamkeit des Entscheidungsträgers.
d) Aktualisierungsbedarf aufgrund neuer Informationen
Wenn dem Disponenten neue Informationen bekannt werden, muss er diese berücksichtigen. Ein Lösungsmechanismus muss daher ebenfalls in der Lage sein, diese neuen Informationen zu verarbeiten. Da eine Lösung zeitnah ermittelt werden muss, sind schnelle Lösungsverfahren und eine entsprechend hohe Rechenleistung unabdingbar. Zudem kann eine veränderte Informationsgrundlage zur Korrektur bereits getroffener Entscheidungen führen; sofern dies noch möglich ist.
e) Zielsetzung und Restriktionen der Optimierungsaufgabe
Die typische Zielsetzung statischer Tourenplanungsprobleme, wie zum Beispiel die Minimierung der zurückgelegten Wegstrecke, kann in einem dynamischen Umfeld oftmals nicht sinnvoll umgesetzt werden. Wenn erst gegen Ende eines Arbeitstages ein Auftrag eingeht, der am Anfang einer Route liegt, so ist es offensichtlich, dass das Ziel der minimalen Wegstrecke für die entsprechende Tour nicht mehr erreicht werden kann. Je nach Situation müssen somit andere Ziele in Betracht gezogen werden. Diese können sich beispielsweise in der Maximierung der Servicequalität oder der Maximierung der Produktivität eines Mitarbeiters ausdrücken. Bezüglich der Zeitfensterrestriktionen wird bei statischen Problemstellungen oftmals von festen, unumstößlichen Zeitfenstern ausgegangen. In einem dynamischen Szenario wäre dies aufgrund der unvollständigen Informationslage kaum praktikabel. Wenn keine Verspätungen zugelassen würden, dann hätte dies oftmals zur Folge, dass neu anfragende Kunden auf die nächste Periode verlegt werden müssten, da die Einplanung eines neu hinzukommenden Kunden oftmals eine Verletzung von Terminsetzungen bereits eingeplanter Kunden bedeutet.
Die Bedeutung der einzelnen Faktoren hinsichtlich der Problemstellung hängt nicht zuletzt vom Grad der Dynamik ab. Der Dynamikgrad resultiert vor allem aus der Frequenz und der Amplitude der Veränderung.[43] Unter Frequenz der Veränderung ist hier die Häufigkeit, in welcher neue Informationen im Zeitablauf bekannt werden, zu verstehen. Die Amplitude der Veränderung gibt Anhaltspunkte über die Stärke der Veränderungsaus-prägung. Wird ein Parameter des Problems geändert, so kann sich eine geringfügige Änderung oder aber ein komplett andere Problemstellung ergeben. Wird zum Beispiel ein neuer Kunde einem Fahrzeug zugeordnet und liegt dieser Kunde nahe an der ursprünglichen Route, dann ergeben sich, wenn auch alle anderen Kunden mit ihren entsprechenden Servicezeiten und Zeitfenstern noch bedient werden können, nur geringfügige Änderungen. Der Mitarbeiter wird aller Voraussicht nach nur etwas später als ursprünglich geplant zum Depot zurückkehren. Fällt aber gleich ein Fahrzeug aufgrund eines Unfalls oder einer Panne zu Beginn der Tour komplett aus, dann bedeutet dies eine wesentliche Änderung für den Tagesplan. Es muss nun überlegt werden, ob eventuell ein Ersatzwagen beschafft wird, oder ob allen Kunden die diesem Fahrzeug zugeordnet waren eine Absage erteilt wird, oder ob zumindest ein Teil dieser Kunden durch andere Fahrzeuge angesteuert werden kann.
Aufgrund der bisher entstandenen hohen Informationsdichte wird im nächsten Abschnitt eine kurze Zusammenfassung der bislang aufgeführten Annahmen und Aspekte erfolgen. Zudem wird die dieser Arbeit zugrunde liegende Problemstellung vor dem Hintergrund der bislang vorgestellten Faktoren und Kriterien näher erläutert.
[...]
[1] Siehe DOMSCHKE (1982, S. 131).
[2] Vgl. NEUMANN/MORLOCK (2002, S. 468).
[3] Vgl. CHRISTOFIDES (1985, S. 435).
[4] Siehe DOMSCHKE (1982, S. 132).
[5] Siehe SOLOMON (1987, S. 254).
[6] Vgl. SAVELSBERGH/SOL (1998, S. 475).
[7] Vgl. GENDREAU/POTVIN (1998, S. 2).
[8] Siehe hierzu LACKNER (2004, S. 6ff.).
[9] Vgl. LACKNER (2004, S. 8).
[10] Siehe NEUMANN/MORLOCK (2002, S. 176ff.).
[11] Ebenda (2002, S. 177).
[12] Vgl. NEUMANN/MORLOCK (2002, S. 380).
[13] Vgl. DOMSCHKE (1982, S. 133).
[14] Ebenda (1982, S. 108).
[15] Vgl. LACKNER (2004, S. 12).
[16] Siehe BODIN/GOLDEN (1981, S. 98).
[17] Ebenda (1981, S. 98).
[18] Vgl. GENDREAU/POTVIN (1998, S. 2ff.).
[19] Vgl. LACKNER (2004, S. 12).
[20] Siehe BODIN/GOLDEN (1981, S. 98f.).
[21] Siehe LACKNER (2004, S. 13).
[22] Vgl. LACKNER (2004, S. 13).
[23] Ebenda (2004, S. 14).
[24] Vgl. GENDREAU/POTVIN (1998, S. 3).
[25] Vgl. BODIN/GOLDEN (1981, S. 99).
[26] Ebenda (1981, S. 99).
[27] Vgl. LACKNER (2004, S. 15).
[28] Vgl. NEUMANN/MORLOCK (2002, S. 438).
[29] Ebenda (2002, S. 439).
[30] Vgl. ORLOFF (1974, S. 38).
[31] Siehe ORLOFF (1974, S. 38).
[32] Siehe NEUMANN/MORLOCK (2002, S. 190f.).
[33] Siehe LACKNER (2004, S. 10).
[34] Siehe Abschnitt 3.2 (S. 24ff.).
[35] Vgl. CHRISTOFIDES (1985, S. 435f.).
[36] Vgl. DESROSIERS et al. (1995, S. 82).
[37] In Anlehnung an THANGIAH (1995, S. 4).
[38] Vgl. PSARAFTIS (1995, S. 153).
[39] Vgl. LACKNER (2004, S. 21).
[40] Vgl. SHEN et al. (1995, S. 190).
[41] Siehe LACKNER (2004, S. 23f.).
[42] Siehe hierzu PSARAFTIS (1988, S. 225ff.).
[43] Siehe LACKNER (2004, S. 27f.).
- Citar trabajo
- Lars Laboch (Autor), 2005, Dynamische Tourenplanung mit Zeitfenstern, Múnich, GRIN Verlag, https://www.grin.com/document/49534
-
-
-
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X. -
-
¡Carge sus propios textos! Gane dinero y un iPhone X.