Glossar Tourenoptimierung und
Tourenplanung
Was bedeutet eigentlich ...?
Simulation, Mandatenfähigkeit oder mathematische Optimierung? Hier erläutern wir Ihnen die wichtigsten Begriffe rund um die Tourneplanung und Tourenoptimierung.
Schnellsuche
A
Bei Abrufkunden sind Aufträge nicht fest beauftragt. Sie kommen aber so regelmäßig vor, dass sie vor vorne herein in Touren miteingeplant werden. Auch wenn es nicht immer zum Auftrag kommt, ist es wirtschaftlicher, diese Auftrage miteinzuplanen als sie spontan zu disponieren und die laufenden Touren zu ändern.
Die Arbeitszeitregelung für Lkw-Fahrer ist eine wichtige Restriktion bei der Tourenplanung.
Neben dem Arbeitszeitgesetz (ArbZG), das für abhängig beschäftigtes Fahrpersonal gilt, spielt vor allem für Lkw ab 3,5 t zulässigem Gesamtgewicht das Gesetz zur Regelung der Arbeitszeit von selbständigen Kraftfahrern (KrFArbZG) eine wichtige Rolle.
Allgemein fordert das ArbZG eine mindestens 30-minütige Arbeitszeitpause nach höchstens 6 Stunden Arbeit. Ebenso gilt, dass die tägliche Arbeitszeit auf höchstens 8 Stunden begrenzt ist, jedoch zweimal pro Woche auf maximal 10 Stunden erweitert werden kann.
Das KrFArbZG gilt auch für selbstständige Fahrer und fordert eine maximale wöchentliche Arbeitszeit von 48 Stunden, die kurzzeitig auf bis zu 60 Stunden pro Woche ausgedehnt werden kann.
Die Gesetze haben zahlreiche Ausnahmen und Sonderregelungen. Darüber hinaus gilt auch die Verordnung zu Lenk- und Ruhezeiten (europaweit), die wiederum zahlreiche Sonderfälle regelt. Dies hat dazu geführt, dass die Prüfung, ob die nächste Schicht eines Fahrers tatsächlich zulässig ist, zum Alptraum verkommen kann. Insbesondere muss man dazu die Einsatzzeiten eines Fahrers in den letzten Monaten genau kennen.
Arc-Routing-Probleme oder auch kantenorientierte Routingprobleme sind eine Klasse von Tourenplanungsproblemen, bei denen die Dienstleistung entlang einer Kante und nicht in einem Knoten erbracht werden. Kanten in Graphen entsprechen zumeist Straßenabschnitten in der Realität.
Typische Beispiele für Arc-Routing-Probleme sind die Müllabfuhr oder die Straßenreinigung.
Ob ein Problem knoten- oder kantenorientiert modelliert wird, hängt oft auch vom Betrachtungsstandpunkt des Modellierers ab. So kann man beispielsweise in der Entsorgung auch eine knotenorientierte Modellierung wählen, wenn man die Standorte der einzelnen Mülltonnen kennt.
Da z. B. die Zahl der Mülltonnen entlang eines Straßenabschnitts in der Regel viel größer als eins ist, wird das knotenorientierte Problem in der Regel viel größer als das kantenorientierte sein.
B
Branch-and-Bound-Verfahren sind Algorithmen, die ein Optimierungsproblem durch sukzessive Einschränkung bzw. Verzweigung (branching) von Entscheidungsvariablen lösen. Dabei wird ein sogenannter Entscheidungsbaum (decision tree) aufgebaut. Vor jeder neuen Verzweigung in einem Knoten wird geprüft, ob der Teilbaum, der unter diesem Knoten liegt, überhaupt in einer optimalen Lösung vorkommen kann. Dazu wird ein einfacher zu lösendes Optimierungsproblem gelöst (Relaxation), welches eine Schranke (bound) für die bestmögliche Lösung in diesem Teilbaum angibt.
Daher besteht ein Branch-and-Bound-Verfahren in einem abwechselnden Prozess der Verzweigung und Berechnung von Schranken. Ein gutes Branch-and-Bound-Verfahren ist dadurch gekennzeichnet, dass die Lösung der Relaxation schnell erfolgen kann, die Relaxation einen Wert nahe an der optimalen Lösung des ursprünglichen Problems liefert und im Mittel möglichst wenig Knoten im Entscheidungsbaum erzeugt werden müssen.
Branch-and-Bound-Verfahren sind sogenannte „exakte Algorithmen“. Das heißt, dass sie bei genügend langer Rechenzeit immer eine optimale Lösung liefern. Leider steigt die dafür notwendige Rechenzeit in der Regel exponentiell mit der Laufzeit, sodass in der Praxis nur wenige Klassen von Optimierungsproblemen mit diesen Verfahren gelöst werden können.
In der Tourenplanung kommen in einzelnen Fällen sog. Branch-and-Price-Verfahren oder Branch-and-Cut-Verfahren bzw. Kombinationen davon („Branch-and-Price-and-Cut“) zum Einsatz. Diese können bestimmte Typen von (großen) Problemen (z. B. Travelling-Salesman-Probleme) gut lösen.
C
Constraintprogrammierung / Constraint Programming (CP) bezeichnet ein Paradigma, bei dem der Anwender ein Modell durch Angabe von Variablen und deren Beziehungen durch Restriktionen / Constraints deklarativ formuliert. Anschließend versuchen Algorithmen, durch sukzessive Reduktion der möglichen Wertebereiche der Variablen eine gültige Lösung für das Modell zu finden.
Allgemein betrachtet ist Constraint Programming daher kein Optimierungsverfahren, sondern ein Verfahren zur Bestimmung einer Variablenbelegung, die alle Constraints erfüllt. Durch Angabe eines Mindest- oder Höchstwertes für eine Zielfunktion lassen sich aber damit auch Optimierungsprobleme lösen.
Constraint Programming funktioniert in der Optimierung immer dann gut, wenn es nur wenige mögliche Lösungen gibt und diese schwer aufzufinden sind. Bisher gibt es in der Tourenoptimierung nur wenige Constraint-Programming-Ansätze, die besser funktionieren als „klassische“ Optimierungsverfahren.
Unter einer Crew versteht man in der Regel eine Flugzeugbesatzung.
Sie besteht in der Regel aus einem Piloten, einem Co-Piloten und mehreren Flugbegleitern.
Bei der Umlauf- bzw. Schichtplanung von Crews gelten zahlreiche, in der Regel sehr komplexe, Restriktionen, die die Zuverlässigkeit der Schicht stark beeinflussen. So kann die maximale Schichtdauer davon abhängen, wie viele einzelne Flugstrecken in einer Schicht enthalten sind, wann die Schicht beginnt, welche Flughäfen besucht werden oder welche Tageszeiten die Schicht überdeckt.
D
Die Tourenplanung erfolgt oftmals in einem dynamischen Umfeld, d.h. es gibt ständig Veränderungen und Informationen, die sofort berücksichtigt werden müssen (neue Aufträge, Stornierungen, Störungen, Auftragsänderungen, Verspätungen, Fahrzeugausfall etc.). Eine Software mit dynamischer Tourenplanung kann in Echtzeit automatisch und flexibel auf Veränderungen während der Planung reagieren, da vorausschauend mögliche Ereignisse und Ungewissheiten in die Planung einbezogen werden. Dadurch sind erstellte und veränderte Tourenpläne hinsichtlich Veränderungen robust, d.h. es werden nur kleine Änderungen verursacht.
Ein Dreiecks-Flugmuster (triangle) ist ein Flugmuster, bei dem man ausgehend von einer Basis A zum Flughafen B, dann zum Flughafen C und schließlich zurück zur Basis A fliegt.
Es handelt sich um ein komplexes Flugmuster, weil man nicht nur von der Basis und zurück, sondern dazwischen zum Flughafen C fliegt. Das Besondere an diesem Flugmuster ist, dass es nicht symmetrisch ist. Das heißt, dass man jede Strecke (A, B), (B, C) und (C, A) nur einmal abdeckt. Da man bei Linienflügen jede Strecke in jede Richtung gleich oft abdecken möchte, benötigt man also weitere Flugmuster, die die Gegenrichtungen (B, A), (C, B) und (C, A) abdecken. Die einfachste Möglichkeit, dies zu erreichen, ist das Muster in der entgegengesetzten Richtung zu fliegen.
E
In der Optimierung ist ein exaktes Verfahren ein Algorithmus, der garantiert eine optimale Lösung eines Optimierungsproblems findet. Bekannte exakte Verfahren sind z. B. die ungarische Methode zur Lösung von Zuordnungsproblemen, der Dijkstra-Algorithmus zur Bestimmung kürzester Wege oder der Simplex-Algorithmus zur Lösung linearer Programme.
Beachten Sie, dass die meisten Optimierungsprobleme nicht nur eine, sondern viele optimale Lösungen haben können und dass ein exaktes Verfahren in der Regel nur eine dieser Lösungen ermittelt.
Da sich die meisten Optimierungsprobleme nicht exakt lösen lassen, verwendet man stattdessen oft Heuristiken und Metaheuristiken bzw. löst nur Teilprobleme exakt.
F
Filiallogistik (auch Handelslogistik oder Retaillogistik) ist ein Spezialgebiet der Distributionslogistik. Im Fokus steht die zeitgerechte und effiziente Versorgung von Verkaufsstellen mit den richtigen Gütern. Die Filiallogistik macht oft einen Anteil von bis zu über 50 Prozent an den gesamten Logistikkosten des Handels aus. Online-Handel und demografischer Wandel lassen die Bedeutung der Filiallogistik weiter steigen.
G
Bei der Gebietsplanung oder auch Revierplanung werden kleinste geografische Einheiten (z.B. Kunden, Gemeinden oder Postleitgebiete) zu übergeordneten Gebietseinheiten (z.B. Vertreterbezirke, Entsorgungsbezirke) nach individuellen Kriterien zusammengefasst. Ziel der Gebietsplanung ist es in der Regel, möglichst effiziente und homogene Gebiete zu erstellen. So möchte man z. B. dass die durchschnittliche Arbeitszeit in allen Gebieten etwa gleich ist und dass keine langen Fahrstrecken innerhalb eines Gebiets vorkommen.
Unter Geokodierung versteht man das Ermitteln einer Position auf dem Globus anhand einer Adresse. Die Position wird in der Regel mit Hilfe von Geokoordinaten (Längengrad, Breitengrad) angegeben. Von einem guten Algorithmus zur Geokodierung erwartet man, dass dieser auch fehlerhafte Adressen gut zuordnen kann.
Geokoordinaten geben den Standort auf der Erdkugel mit Hilfe von 2 Punkten an (Breiten- und Längengrad). Es gibt zahlreiche Referenzsysteme, um den Standort möglichst exakt anzugeben. Am häufigsten findet man World Geodetic System 1984 (WGS84). Die Geokoordinaten der gts sind: (50.82329, 6.07036).
Ein Greedy-Algorithmus ist ein Algorithmus, der eine Lösung eines Optimierungsproblems dadurch erzeugt, dass er in jedem Schritt die „beste“ zur Verfügung stehende Auswahl aus einer Menge von Entscheidungsoptionen wählt.
Ein sehr bekannter Greedy-Algorithmus ist der Nearest-Neighbour-Algorithmus zur Lösung von Tourenplanungsproblemen: Man baut die Touren auf, indem man im Depot startet und in jedem Schritt den nächstgelegenen Ort/Kunden besucht, der noch nicht besucht wurde, und dessen Hinzunahme zur Tour zulässig ist. Kann kein weiterer Ort hinzugefügt werden, fährt man zum Depot zurück, schließt die aktuelle Tour ab und beginnt mit einer neuen Tour. Der Algorithmus endet, wenn alle Orte/Kunden in Touren aufgenommen wurden.
Leider liefern Greedy-Algorithmen in der Regel sehr schlechte Ergebnisse, weil am Ende nur sehr ungünstige Entscheidungsmöglichkeiten zur Verfügung stehen. Eine Ausnahme ist die Bestimmung eines minimal spannenden Baums in einem Graphen. In diesem Sonderfall findet der Greedy-Algorithmus (sog. „Algorithmus von Kruskal“) tatsächlich eine garantiert optimale Lösung.
H
Heuristik ist die Wissenschaft von Methoden und Verfahren zur Problemlösung. In der Tourenplanung und Tourenoptimierung spricht man als Heuristik einen Algorithmus, der für ein (schwieriges) Optimierungsproblem versucht, in kurzer Zeit eine möglichst gute Lösung zu finden. Heuristiken unterscheiden sich von exakten Verfahren dadurch, dass sie nicht garantiert eine optimale Lösung finden. In Software für die Tourenplanung findet man in der Regel immer Heuristiken, da es nur wenige Spezialfälle von Tourenoptimierungsproblemen gibt, für die man in akzeptabler Zeit exakt optimale Lösungen bestimmen kann.
I
In der Tourenoptimierung unterscheidet man zwischen Problemen und Instanzen. Als Optimierungsproblem bezeichnet man eine allgemeine Beschreibung eines Problems (oft in Form eines Optimierungsmodells). Beispielsweise beschreibt das Travelling-Salesman-Problem das Problem, in einer Stadt zu starten, alle anderen Städte zu besuchen und zur Ursprungsstadt zurückzukehren, sodass die zurückgelegte Strecke minimiert wird.
Eine Instanz konkretisiert für ein gegebenes Problem die Daten, sodass man dieses auch lösen kann. Für das Travelling-Salesman-Problem besteht z. B. die Konkretisierung dadurch, dass man die Zahl der zu besuchenden Städte und eine Distanzmatrix (mit den Abständen zwischen den Städten) angibt. Dann kann man mit Hilfe eines geeigneten Algorithmus das Problem lösen.
K
Bei engen Zeitvorgaben werden Touren oft konsolidiert, da es ist nicht immer die effizienteste Lösung ist, wenn ein Fahrzeug nach einer Lieferung oder Abholung direkt zurückfährt. Deshalb werden Konsolidierungspunkte festgelegt, an denen Waren angeliefert und abgeholt werden. Die Fahrzeuge legen somit kürzere Strecken zurück und können somit effizienter eingesetzt werden.
Die Bestimmung von kürzesten oder schnellsten Wegen zwischen Punkten in einem Netzwerk ist ein schon lange bekanntes Problem in der Informatik bzw. dem Operations Research. Ziel ist es, die Länge und enthaltenen Kanten eines Weges zwischen 2 oder allen Punkten in einem Netzwerk zu bestimmen. Bereits in den fünfziger Jahren des vergangenen Jahrhunderts haben die Mathematiker Edsger W. Dijkstra und George Dantzig dafür ein Algorithmus entwickelt.
Heute müssen in vielen Anwendungsgebieten, wie z. B. der Tourenplanung, Strecken und Fahrzeiten zwischen hunderten, tausenden oder zehntausenden von Orten in riesigen Straßennetzen (z. B. alle Straßen in Europa) ermittelt werden. Dafür wurde der Dijkstra-Algorithmus in den letzten zehn Jahren erheblich weiterentwickelt, damit dies mit kurzen Laufzeiten ermöglicht wird.
Mit den aktuellen Algorithmen ist es möglich, große Distanzmatrizen in sehr kurzer Zeit zu berechnen. Darüber hinaus bieten Tourenplanungssysteme wie TransIT, die Möglichkeit, Straßensperren zu berücksichtigen und das Wenden von Lkw möglichst zu verhindern, was noch umfangreichere Anpassungen der Algorithmen erfordert.
Kurier-, Express- und Paket-Dienstleister transportieren vor allem Briefe, Dokumente, Päckchen und Kleinstückgüter. Durch standardisierte Abläufe und einen hohen Automatisierungsgrad sind Zustellungen in kurzer Zeit (24-Stunden-, 48-Stundenservice, Same-Day- bzw. Over-Night-Delivery) bei hoher Wirtschaftlichkeit möglich.
L
Die Lenk- und Ruhezeitregelungen für Kraftfahrer sind in der EG-Verordnung 561/2006 geregelt. Sie gelten damit praktisch europaweit für Kraftfahrzeuge ab 3,5 t zulässigem Gesamtgewicht bzw. in Deutschland bereits ab 2,8 t zulässigem Gesamtgewicht.
Die wichtigsten Regelungen betreffen die notwendigen Pausen und maximalen Lenkzeiten.
So müssen z. B. nach maximal 4,5 Stunden eine oder mehrere Pausen von insgesamt mindestens 45 Minuten genommen werden. Die Pausen dürfen gesplittet werden, jedoch nur nach einem speziellen Muster.
Die Tageslenkzeit ist auf 9 Stunden begrenzt, wobei sie zweimal pro Woche auf 10 Stunden ausgedehnt werden darf. Beträgt die Lenkzeit mehr als 9 Stunden, so gilt wiederum die Pausenregelung für die Lenkzeit über 4,5 Stunden ein zweites Mal: Man benötigt also in den letzten 4,5 Stunden Lenkzeit wieder eine oder mehrere Pausen von insgesamt mindestens 45 Minuten.
Die Wochenlenkzeit ist auf 56 Stunden begrenzt, wobei innerhalb von 2 Wochen nur 90 Stunden zulässig sind.
Die Regelung enthält auch noch zahlreiche weitere Teil- und Sonderregelungen, die dazu geführt haben, dass es zahlreiche Bücher zu diesem Thema gibt, die ausführlich auf Sonderfälle eingehen.
Fährt man wiederum mit 2 Fahrern, die sich abwechseln, so kann das ununterbrochene Fahren erheblich ausgedehnt werden.
Als letzte Meile (last mile) wird das letzte Wegstück beim Transport von Waren und Paketen zur Haustür des Kunden bezeichnet. Es ist also das letzte Glied in der Supply Chain. Die letzte Meile stellt für Dienstleister, Logistiker und vor allem für Kurier-Express-Paket-Dienstleister (KEP) eine große Herausforderung dar – insbesondere durch das wachsende Sendungsaufkommen aufgrund des Onlinehandels. Typischerweise beträgt der Anteil der Kosten für die letzte Meile etwa 2/3 der Gesamtkosten von Paketdiensten.
In der Tourenplanung gilt es, die Fahrten für die Zustellung so zu bündeln, dass der Aufwand möglichst gering ist. Ein großes Problem für effiziente Touren bei der Zustellung an Endverbraucher ist das Nicht-Antreffen von Empfängern und die damit verbundene wiederholte Zustellung. Um dieses Problem zu entschärfen, gibt es als Alternative die Zustellung an Paketshops, Packstationen und Paketschließfächer. Ebenso müssen Paketdienste mit teilweise extremen saisonalen Einflüssen umgehen. Den meisten bekannt ist hier vor allem das Weihnachtsgeschäft, bei dem die Mengen sich zum Teil gegenüber dem Normalbetrieb mehr als verdoppeln.
Ein Zukunftsszenario für die Warenzustellung sind Logistikdrohnen. Mit dem steigenden Paketvolumen nimmt auch das Verkehrsaufkommen, insbesondere in den Städten zu. Durch eine gezielte Tourenoptimierung können die Fahrten in regelmäßigen Abständen an neue oder wechselnde Verkehrsströme angepasst werden.
Die Lineare Programmierung (LP) ist ein Teilgebiet der Optimierung, welches sich mit der Lösung von Optimierungsproblemen mit linearen Restriktionen und einer linearen Zielfunktion beschäftigt.
Der bekannteste Algorithmus zur Lösung von LP ist der Simplex-Algorithmus. Dieser liefert für die meisten praktisch relevanten Probleme exakte Lösungen in kurzer Rechenzeit. Theoretisch hat der Simplex-Algorithmus jedoch den Nachteil, dass die Laufzeit exponentiell mit der Problemgröße wachsen kann. Von daher wurden in den achtziger Jahren einige Algorithmen entwickelt, deren Laufzeit polynomial beschränkt ist. Diese haben sich jedoch in der Praxis nicht durchgesetzt, während einige Barrier-Methoden sich auch als praktisch effizient herausgestellt haben.
M
Eine Software ist mandantenfähig, wenn sie die gleichzeitige Verwaltung mehrerer Mandanten (z.B. Kunden oder Regionen) über einen Nutzer erlaubt. Dies ist zum Beispiel bei der Belieferung von Filialen oder Niederlassungen wichtig. So sind in der Tourenplanung alle Objekte mit geografischem Bezug einem Mandanten zugeordnet, so dass die Planung nach Niederlassungen getrennt erfolgen kann. Für Auswertungen oder bei einer notwendigen Zusammenarbeit mehrerer Niederlassungen können mehrere Mandanten gemeinsam aktiviert werden.
Manuelle Tourenplanung bedeutet die Planung einer Tour durch einen Menschen. Wir verstehen darunter in der Regel, dass eine Tour nicht oder nur teilweise durch einen Optimierungsalgorithmus erstellt wurde. In der Software TransIT können Sie z. B. Touren manuell erstellen oder Touren, die durch einen Algorithmus geplant wurden, manuell verändern.
Die mathematische Optimierung bzw. Programmierung beschäftigt sich mit der Bestimmung einer optimalen Lösung aus einer Menge von zulässigen Lösungen. Die Menge der zulässigen Lösungen wird im Allgemeinen durch sog. Restriktionen über den Entscheidungsvariablen definiert. Die „Optimalität“ wird durch Angabe einer sog. „Zielfunktion“ über den Entscheidungsvariablen definiert, die es zu maximieren oder minimieren gilt. Typische Beispiele sind die Kostenminimierung oder die Deckungsbeitragsmaximierung.
Eine Metaheuristik ist ein übergeordneter Algorithmus, der die Lösungssuche eines oder mehrerer abhängiger Algorithmen steuert.
Sie beruht auf einer Sammlung von (Meta-)Strategien, die unabhängig vom zugrundeliegenden Optimierungsproblem und den abhängig gesteuerten Algorithmen sind.
Bekannte Metaheuristiken sind Simulated Annealing, Tabu Search, Ameisenalgorithmen, GRASP, Variable Neighbourhood Search, Evolutionäre und Genetische Algorithmen.
Bei der Modellierung erstellt man ein (mathematisches) Modell der Realität, um damit Berechnungen durchzuführen. Das Ziel der Berechnung kann es z. B. sein, ein System zu simulieren oder zu optimieren. Ein Optimierungsmodell wird dazu genutzt, Entscheidungsvorschläge für das reale System zu ermitteln.
N
In der Netzwerkoptimierung werden auf Basis von Modellierung und Simulation die Beziehungen aller Objekte eines (Logistik-)Netzwerks (z. B. Mitarbeiter, Kunden, Lieferanten, Lager, Standorte und Strukturen) in ihrer Gesamtheit optimiert.
Beim Netzwerkdesign bestimmt man in der Regel die grundlegenden Flüsse innerhalb eines Logistik-Netzwerks bzw. einer Supply-Chain. Typische Beispiele sind die Flüsse von Lieferanten in Läger, von Lägern zu Kunden usw.
O
Unter Optimierung versteht man das Ermitteln einer besten Lösung aus einer Menge von zulässigen Lösungen. In der mathematischen Optimierung werden dazu mathematische Optimierungsmodelle eingesetzt. Beispiele hierfür sind lineare und gemischt-ganzzahlige Optimierungsmodelle.
Der OptimierungsCheck ist ein kostenloses Angebot von gts, bei dem auf Grundlage von Kundendaten eine erste Analyse des Optimierungspotenzials erfolgt. Durch den OptimierungsCheck gibt es eine realistische Vorstellung, wie die Tourenplanung und Optimierung erfolgt.
OpenStreetMap ist ein CrowdSourcing-Projekt zum Sammeln und Verarbeiten von Geodaten auf der ganzen Welt. Ähnlich wie Wikipedia erstellen und Ergänzen die Nutzer Karten zur Nutzung durch die Allgemeinheit. In zahlreichen Ländern ist die Qualität dieser Karten mindestens gleich gut, wenn nicht sogar besser als diejenigen der kommerziellen Karten. Das Tourenplanungssystem TransIT verwendet teilweise OpenStreetMap-Daten zur Ermittlung von Routen, Distanzen und Fahrzeiten zwischen Orten.
P
Das Pickup-and-Delivery-Problem (PDP) beschreibt im Operations Research eine Klasse von Problemen, bei denen ein Transport von einem Pickup-Punkt zu einem Delivery-Punkt durchgeführt werden muss. Im Unterschied zum Vehicle-Routing-Problem muss man 2 Punkte oder Knoten betrachten, nämlich den Pickup- und den Delivery-Punkt.
In der Praxis gibt es zahlreiche Varianten des PDP, z. B. mit Zeitfenstern für die Abholung und Auslieferung (Pickup and Delivery Problem with Time Windows, PDPTW).
Bei Paket- und Expressdiensten bezeichnet das Pickup-and-Delivery hingegen die lokale Abholung und Zustellung von Sendungen. Aus Sicht des Operations Research handelt es sich dabei allerdings in der Regel um Varianten des VRP. Dies kann durchaus zu Verwirrungen führen.
Unter Planung versteht man die geistige Vorwegnahme zukünftigen Handelns. In der Regel geschieht Planung zielgerichtet, z. B. mit dem Ziel die Auslastung zu steigern, Kosten zu minmieren oder Erlöse zu steigern.
Die Software TransIT ist speziell für die Tourenplanung und -optimierung entwickelt worden. Sie wird in zahlreichen Branchen eingesetzt und beinhaltet Module zur strategischen, taktischen und operativen Planung. Darüber hinaus erlaubt sie auch das Steuern der Tourendurchführung.
Q
Quantitative mathematische Modelle dienen der Berechnung von Ergebnissen mit Hilfe von quantitativen Daten. Beispiele für quantitative Daten sind Adressen, Geokoordinaten, Fahrzeugkapazitäten, Anzahl Stopps in einer Tour usw.
R
Eine Rahmentour ist eine Zusammenfassung von Kunden, Standorten, Straßenabschnitten oder Ähnlichem, die regelmäßig zusammen in einer Tour bedient werden sollen.
Im Gegensatz zu operativen (echten) Touren sind die konkreten Kunden, Standorte usw. in der Regel nicht in eine Reihenfolge gebracht, weil zum Zeitpunkt der Planung nicht bekannt ist, welche wann zusammen bedient werden sollen.
Beispielsweise bedienen viele Großhändler ihre Kunden mit Hilfe von Rahmentouren. Dies erlaubt es, anhand der Rahmentour-Kennzeichnung der Kunden, die Ware im Lager zu kommissionieren und an der Rampe bereitzustellen, bevor die konkrete Tourenplanung über die Bedienreihenfolge entscheidet. Ähnlich arbeiten auch Paket- und Expressdienste, die auf Basis von Rahmentouren täglich ihre Sendungen mit automatisierten Anlagen auf Adressbasis sortieren.
Revierplanung bezeichnet die Aufgabe, einzelne Kunden, Aufträge, Straßenabschnitte oder Ähnliches zu gruppieren. In der Regel wird die Gruppierung so vorgenommen, dass daraus einzelne Gebiete entstehen, die in einer Tourenplanung von einem Fahrzeug bedient werden (Rahmentouren).
Revierplanung ist vor allem im Bereich der Abfallwirtschaft ein gängiger Begriff.
Ein Tourenplan ist robust, wenn kleine Änderungen in den Input-Daten nur kleine Änderungen im Tourenplan bewirken. Robuste Tourenpläne können z. B. das Ergebnis einer Gebietsplanung sein.
Routenplanung oder Routenberechnung („routing“) bezeichnet einen Dienst oder eine Software zur Navigation. Während in der Tourenplanung viele Fahrzeuge simultan betrachtet werden, betrachtet man in der Routenplanung nur ein Fortbewegungsmittel (Auto, Öffentliche Verkehrsmittel, Fahrrad, zu Fuß.)
S
Unsere Tourenplanungssoftware kann mit allen gängigen sowie von uns erstellten individuellen Schnittstellen verbunden werden.
Simulation wird im Bereich der Tourenplanung häufig verwendet, um strategische oder taktische Optimierungsergebnisse auf operativer Ebene zu verifizieren. Durch die Simulation wird untersucht, wie Touren in der Vergangenheit abgelaufen wären, wenn eine optimierte Taktik oder Strategie zum Einsatz gekommen wäre. Durch den Vergleich der Ergebnisse mit den echten operativen Ergebnissen lassen sich Rückschlüsse auf die Qualität der neuen Taktiken bzw. Strategien ziehen. Die Simulationen werden entweder mit historischen Daten durchgeführt, häufig aber auch mit angepassten historischen Daten (z.B. veränderten Mengen oder Veränderung der zeitlichen Grundlagen.)
Moderne Software zur Tourenplanung zeichnet sich durch eine geschickte Kombination von Funktionen zur automatischen Optimierung, manuellen Eingriffsmöglichkeiten, Echtzeitinformation (in der Regel aus Telematiksystemen), digitalen Landkarten und Methoden zur Geokodierung aus.
Zielsetzung dieser Softwaresysteme ist es, schneller zu planen (durch automatische Optimierung und Unterstützung der manuellen Planung) und besser zu planen.
Unsere Tourenplanungssoftware bildet auch spezielle Anforderungen, wie Wendeverbote, Straßensperren und Fahrverbote, ab und bietet Alternativrouten an. TransIT kann in Echtzeit automatisch und flexibel auf Veränderungen während der Planung und während der Tour reagieren, da vorausschauend mögliche Ereignisse und Ungewissheiten in die Planung einbezogen werden. Auf Basis des geografischen Informationssystems für die Kartendarstellung, Geokodierung und Entfernungsberechnung erreicht TransIT eine höchstmögliche Aktualität der Kartendaten.
Stochastische Tourenplanung berücksichtigt Auftragswahrscheinlichkeiten, also die Wahrscheinlichkeit dafür, dass Aufträge tatsächlich durchgeführt werden müssen. Dies ist in der Regel bei der Optimierung von Regeltourenplänen relevant, also Plänen, die regelmäßig gefahren werden (z.B. in medizinischen Laboren oder bei der Tourenplanung in der Abfallwirtschaft) und Aufträge enthalten (z.B. Abrufkunden), die nicht bei jeder Tourdurchführung angefahren müssen.
Die strategische Tourenplanung bezieht sich auf regelmäßige Touren mit festen, unveränderlichen, langfristig planbaren Fahrplänen. Ziele sind u.a. die Reduzierung des täglichen Planungsaufwandes, die Zusage von festen Lieferzeiten, das Outsourcing von festen Touren, die Gebietsplanung oder die Standortoptimierung.
Die Supply-Chain-Optimierung zielt auf die Verbesserung und Effizienzsteigerung aller Prozesse einer Supply Chain (Versorgungskette) unter Berücksichtigung des Kosten-Nutzen-Verhältnisses, der Kundenzufriedenheit und aller die Supply Chain beeinflussenden internen und externen Faktoren.
T
Bei der taktischen/operativen Tourenplanung oder Tourenoptimierung versucht man, einen Tourenplan zu erstellen, der für einen längeren Zeitraum gültig ist. Dieser ist oft als eine Art „Rahmen“ anzusehen, der für einen speziellen Zeitraum (z. B. einen Tag) konkretisiert werden muss.
Telematik ist die Verknüpfung von Telekommunikation und Informatik und wird insbesondere im Verkehrsmanagement verwendet. Tourenplanung und Telematik gehen idealerweise Hand in Hand: So können optimierte Touren an Navigationsgeräte oder mobile Endgeräte übertragen werden. Umgekehrt kann z. B. der Mitarbeiter den Status von Aufträgen ändern, was wiederum im Tourenplanungssystem sichtbar wird und ggf. auch zu einer Umplanung führen kann (z. B. bei Verspätungen).
Tourenplanung ist das Gruppieren (Clustern) von Aufträgen oder Transportaufträgen zu Touren und die Bestimmung der Reihenfolge der Anfahrtspunkte (Routing) innerhalb dieser Touren. Dabei sind zahlreiche Restriktionen einzuhalten, wie z. B. eingeschränkte Anfahrtszeiten, Kapazitäten, Vorrangbeziehungen etc.
Innerhalb der Tourenplanung werden die strategische (langfristige), die taktische (operative), die robuste/dynamische und manuelle Tourenplanung unterschieden. Die strategische Tourenplanung bezieht sich auf regelmäßige Touren mit festen, unveränderlichen, langfristig planbaren Fahrplänen. Ziele sind u.a. die Reduzierung des täglichen Planungsaufwandes, die Zusage von festen Lieferzeiten, das Outsourcing von festen Touren, die Gebietsplanung oder die Standortoptimierung.
Bei der taktischen Tourenplanung wird versucht, eine Art Tourengerüst für einen längeren Zeitraum zu bestimmen, während bei der operativen Tourenplanung bzw. Tourenoptimierung ein konkreter Auftragsbestand vorliegt.
Um die Qualität und Effizienz von bestehende Touren zu steigern, werden diese auf ungenutzte Optimierungspotenziale hin untersucht. In der Regel erfolgt die Tourenoptimierung mit einem Tourenplanungs- oder Tourenoptimierungssystem wie TransIT. Dieses setzt dann Optimierungsalgorithmen ein, um die Tourenpläne schneller und in besserer Qualität zu erstellen, als dies ein Anwender tun kann.
Die Software TransIT ist speziell für die Tourenplanung und -optimierung entwickelt worden. Durch zahlreiche Anwendungen und Module kann TransIT für jedes Unternehmen spezifisch angepasst werden. Das System wird bei mehr als 120 Kunden in vielen Ländern eingesezt und dient als Basis für die Planung von tausenden Touren jeden Tag.
Die Software TransIT kann für verschiedenste Planungsaufgaben eingesetzt werden. In Abhängigkeit der vorliegenden Planungsaufgabe und Planungsebene (strategisch, taktisch, operativ) kann das System durch den Einsatz der zugehörigen Module optimal an die Bedürfnisse der Kunden angepasst werden. Beispiele für TransIT-Module sind:
- Gebietsoptimierung
- Tourenoptimierung
- Telematik
- Web-Anwendungen
U
Umweltzonen sind Bereiche, in die zur Reduzierung der Feinstaubbelastung nur Fahrzeuge einfahren dürfen, die bestimmte Abgasstandards einhalten. Die Kennzeichnung erfolgt mit roter, gelber und grüner Feinstaubplakette. Diese gelten unabhängig von Kraftstoffart und zulässigem Gesamtgewicht für alle PKW, Busse und LKW. Zurzeit gibt es Umweltzonen in 57 deutschen Städten. Umweltzonen gibt es in ganz Europa. Die Tourenplanungssoftware TransIT kann spezielle Anforderungen, wie die Kennzeichnung von Umweltzonen und Fahrverbote, dynamisch abbilden. Es werden Alternativrouten angeboten. TransIT kann in Echtzeit automatisch und flexibel auf Veränderungen während der Planung und während der Tour reagieren, da vorausschauende mögliche Ereignisse und Ungewissheiten in die Planung einbezogen werden. Auf Basis des geografischen Informationssystems für die Kartendarstellung, Geokodierung und Entfernungsberechnung erreicht TransIT eine höchstmögliche Aktualität der Kartendaten.
Weitere Informationen erhalten Sie hier: www.umwelt-plakette.de
Ein U-Turn bzw. eine Kehrtwendung bezeichnet einen Wendevorgang, bei dem das Fahrzeug die Richtung umkehrt. In vielen Fällen versucht man bei der Tourenplanung U-Turns zu vermeiden, weil diese das Unfallrisiko erheblich erhöhen bzw. mit großen Fahrzeugen zum Teil nahezu unmöglich sind. Das Tourenplanungssystem TransIT erlaubt es, Wendevorgänge zu bestrafen, sodass diese soweit praktisch oder wirtschaftlich möglich, vermieden werden.
V
Das Gebiet des Vehicle Routing (dt.: Tourenplanung) ist ein wichtiger Teilbereich des Operations Research, der sich mit der Tourenoptimierung beschäftigt. Die Wissenschaftler, die in diesem Bereich tätig sind, beschäftigen sich mit der Entwicklung von Modellen und Algorithmen zur Lösung von Tourenoptimierungsproblemen.
Die untersuchten Tourenoptimierungsprobleme lassen sich hierbei anhand der Modelle klassifizieren, wobei ein Modell definiert, welche Aspekte ein Problem kennzeichnen. Genauer kann man die Probleme anhand ihrer Entscheidungsvariablen (oder einfach: Variablen) und der damit formulierten Constraints (dt.: Restriktionen) unterscheiden.
So definieren z. B. die Variablen, ob räumliche oder zeitliche Aspekte eine Rolle spielen, welche Art von Kosten berücksichtigt werden oder z. B. ein deterministisches oder stochastisches Modell eingesetzt wird.
Über die Restriktionen legt man fest, welche einschränkenden Aspekte eines Problems berücksichtigt werden. Beispiele sind Zeitfenster, Kapazitäten, getrennte Abholungen und Zustellungen und Vieles mehr.
Das Vehicle-Routing-Problem beschreibt in gewisser Weise das einfachste relevante Tourenplanungsproblem: Eine Flotte gleicher Fahrzeuge befindet sich in einem Depot und soll bei verschiedenen Kunden Ware abholen (oder einsammeln, wobei gleichzeitige Abholung und Einsammlung im Standardproblem nicht berücksichtigt ist). Die Warenmenge kann als eindimensionale Größe beschrieben werden, die angibt, wie viele Einheiten der Fahrzeugkapazität durch diese Waren belegt werden. Ziel ist es nun, die Fahrzeuge den Kunden zuzuordnen (Clustering) und gleichzeitig die Besuchsreihenfolge (Routing) so zu ermitteln, dass die zurückgelegte Strecke minimiert wird.
In manchen Fällen wird dabei auch eine maximale Strecke pro Fahrzeug berücksichtigt oder als Zielfunktion die Minimierung der Anzahl der eingesetzten Fahrzeuge formuliert.
W
Ein W-Flugmuster ist ein Flugmuster, das in einer Flugzeugbasis A startet, zum Flughafen B fliegt, dann von B nach C und zurückfliegt, um schließlich zur Basis A zurückzukehren. Es handelt sich um ein sogenanntes „komplexes Muster“, da man nicht direkt von der Basis und zurückfliegt.
Der Name kommt daher, dass man das Muster wie ein „W“ darstellen kann.
Y
Mit Yield Management oder Revenue Management bezeichnet man Verfahren, die ein Produkt oder eine Dienstleistung dynamisch in Abhängigkeit der Nachfrage bepreisen. Bekannt sind solche Verfahren seit langem vor allem in der Reise- und Touristikbranche. So kosten beispielsweise Hotelübernachtungen in der Hochsaison oder zu Messezeiten das Vier- oder Fünffache dessen, was in der Normalsaison verlangt wird. Ähnliches kennt man auch von Flügen, Fähren usw.
Heute verwenden viele Unternehmen Algorithmen zur Steuerung des Yield-Managements. Das ist besonders in großen Unternehmen unvermeidlich, weil bereits die immense Anzahl, z. B. von Hotelübernachtungen oder Flugtickets, eine vollständig manuelle Anpassung der Preise unmöglich macht.
Z
Ein Zeitfenster beschreibt innerhalb eines Tourenplanungsproblems ein Zeitintervall, in dem vor Ort eine Dienstleistung (z. B. Kundenbesuch, Mülltonnen-Entleerung, Paketauslieferung, Möbelaufbau) stattfinden soll. Zeitfenster schränken dabei die Zahl der zulässigen Touren in der Regel stark ein und führen zu oftmals zu Lösungen, die geografisch betrachtet nicht sinnvoll sind. Um möglichst kundenorientiert zu handeln, nehmen Dienstleister in der Regel diese wirtschaftlichen Nachteile in Kauf.
Von mehrfachen Zeitfenstern (engl.: multiple time windows) spricht man, wenn mehrere disjunkte Zeitintervalle zulässig sind. Beispiele sind Kunden, die nur morgens oder abends angetroffen werden können, jedoch mittags nicht oder dass eine Dienstleistung an jedem Wochentag zwischen 2 Uhrzeiten erbracht werden kann (z. B. zwischen 08:00 und 15:00 Uhr).
Eine Zielfunktion ist eine mathematische Formulierung, die mit Hilfe von Variablen beschreibt, welches Ziel bei einer Optimierung erreicht werden soll. Eine Zielfunktion soll dann minimiert oder maximiert werden.
In vielen Fällen werden eindimensionale Zielfunktionen formuliert, die z. B. über Kosten, Erlöse, Umsätze, Auslastungen definiert sind. In der Tourenplanung kann eine Zielfunktion z. B. die Minimierung der zurückgelegten Strecke, der Summe der Fahrzeiten, der maximalen Fahrzeit oder der Zahl der eingesetzten Fahrzeuge verlangen. Diese sind zum Teil konkurrierende Ziele: So konkurriert die Minimierung der zurückgelegten Strecke oft mit dem Ziel, die Zahl der eingesetzten Fahrzeuge zu minimieren. Genauso ist es z. B. bei Problemen mit Zeitfenstern der Fall, dass die kürzeste Strecke nicht erreicht wird, wenn man die Tourdauer minimieren möchte (statt zu warten können Sie z. B. Umwege in Kauf nehmen, um Zeit zu sparen).
Verfolgt man gleichzeitig mehrere Ziele, so spricht man von einer multikriteriellen Optimierung. Ein Beispiel hierfür ist, dass man z. B. erreichen möchte, dass alle Vertriebsmitarbeiter etwa gleich lange arbeiten müssen und gleichzeitig der potentielle Umsatz je Mitarbeiter ebenfalls gleich ist.
