Glossar Optimierung und Tourenplanung

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.

Typsiche 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.

Die Arbeitszeitrgelung 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 30minütige Arbeitszeitpause nach höchstens sechs Stunden Arbeit. Ebenso gilt, dass die tägliche Arbeitszeit auf höchstens acht 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 (leider) 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.

Branch-and-Bound-Verfahren sind Algorithmen, die ein Optimierungsproblem durch sukzessive Einschränkung bzw. Verzweigung (engl.: "Branching") von Entscheidungsvariablen lösen. Dabei wird ein sog. "Entscheidungsbaum" (engl.: "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 (sog. "Relaxation"), welches eine Schranke (engl.: "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 urpsrünglichen Problems liefert und im Mittel möglichst wenig Knoten im Entscheidungsbaum erzeugt werden müssen.

Branch-and-Bound-Verfahren sind sog. "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.

Constraint Programming (CP) bezeichnet ein Paradigma, bei dem der Anwender ein Modell durch Angabe von Variablen und deren Beziehungen (durch Restriktionen (engl.: "Constraints" formuliert) deklarativ formuliert und Algorithmen anschließend versuchen, durch sukzessive Reduktion der möglichen Wertebereiche der Variablen eine gültige Lösung für das Modell zu finden.

Allgemein betrachtet ist CP 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.

CP 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 CP-Ansätze, die besser funktionieren als "klassiche" 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 Zulässigkeit der Schicht stark beeinflussen. So kann die maximale Schichtdauer davon abhängen, wieviele einzelne Flugstrecken in einer Schicht enthalten sind, wann die Schicht beginnt, welche Flughäfen besucht werden oder welche Tageszeiten die Schicht überdeckt.

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 und während der Tour reagieren, da vorausschauende 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 (engl.: 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 symmatrisch 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.

In der Optimerung 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 Optimerungsprobleme nicht exakt lösen lassen, verwendet man stattdessen oft Heuristiken und Metaheuristiken bzw. löst nur Teilprobleme exakt.

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.

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 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 zwei Punkten an (Breiten- und Längengrad). Da die Erde keine echte Kugel ist, gibt es zahlreiche Referenzsysteme, um den Standort möglicht exakt anzugeben. Am häufigsten findet man World Geodetic System 1984 (WGS84). Die Geokoordinaten der GTS Systems and Consulting GmbH sind: (50.836905, 6.080616).

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.

Eine Heuristik ist ein 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.

In der Optimierung unterscheidet man zwischen Problemen und Instanzen. Als Optimierungsproblem bezeichnet man eine allgemeine Beschreibung eines Problems (oft in Form eines Optimierugnsmodells). 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.

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 zwei oder allen Punkten in einem Netzwerk zu bestimmen. Bereits in den fünfziger Jahren des vergangenen Jahrhunderts wurden von Dijkstra und Dantzig dafür ein Algorithmus entwickelt, der auch heute noch sehr bekannt ist.

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 (bedenken sie, dass eine 1000 x 1000 Matrix eine Million Distanzen enthalten muss). 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 setzen und das Wenden von Lkw möglichst zu verhindern, was noch umfangreichere Anpassungen der Algorithmen erfordert.

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.

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 zwei 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 zwei Fahrern, die sich abwechseln, so kann das ununterbrochene Fahren erheblich ausgedehnt werden. Auf die entsprechenden Sonderfälle gehen wir hier nicht ein.

Eine Software ist mandantenfähig, wenn sie die gleichzeitige Verwaltung mehrerer Mandanten (z.B. Kunden oder Regionen) über einen Nutzer erlaubt.

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 Optimierungsagorithmus erstellt wurde. In der Software TransIT können Sie z. B. Touren manuelle 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 order mehrerer abhängiger Algorithmen steuert.

Sie beruht auf einer Sammlung von 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.

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 Netzwerk-Design 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.

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 OpenStreetMsp-Daten zur Ermittlung von Routen, Distanzen und Fahrzeiten zwischen Orten.

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 zwei 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.

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.

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. Dies bezeichnen wir auch als Planung von 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. Robustheit erhält man nicht zum Nulltarif, denn eine rein kostengesteuerte Optimierung ist in der Regel wenig robust, weil sie alle Restriktionen bis zum Limit ausnutzt. Robuste Tourenpläne können z. B. das Ergebnis einer ausgeklügelten Gebietsplanung sein.

Eine Route ist eine Abfolge von Punkten, die ein Fahrer oder Fahrzeug in einem Straßennetzwerk besucht. Während in der Tourenplanung viele Fahrzeuge simultan betrachtet werden, betrachtet man in der Routenplanung nur ein Fahrzeug.

Eine Schnittstelle (Interface) ist ein Übergang zwischen Datenübertragungseinrichtungen, Hardwarekomponenten, logischen Softwareeinheiten oder zwischen Menschen und Computern.

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 (die Kosten der Tourenpläne sinken und die Qualität steigt).

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.

Bei der taktischen 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 Handhelds ü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 die 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.

Derzeit setzt sich mehr und mehr Tourenplanungssoftware bzw. Tourenoptimierungssoftware durch. Gute Systeme zur Tourenplanung zeichnen sich dadurch aus, dass sie automatisch mit Hilfe von Optimierungsalgorithmen Tourenpläne erzeugen können. Ein Planer kann diese dann anschließend, falls gewünscht, manuell verändern. Wenn ein Anwender mit oder ohne Tourenplanungssystem einen Tourenplan von Hand erstellt, spricht man von maueller Tourenplanung.

Die Tourenoptimierung zielt auf die Steigerung der Qualität der Tourenpläne. In der Regel erfolgt die Tourenoptimierung mit einem Tourenplanungs- oder -optimierungssystem 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

Ein U-Turn bzw. eine Kehrtwendung bezeichnet einen Wendevorgang, bei dem das Fahrzeug die Richtung umkehrt. In vielen Fällen verscuht 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 pönalisieren, sodass diese soweit praktisch oder wirtschaftlich möglich, vermieden werden.

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 (VRP) oder dt.: Standardproblem der Tourenplanung beschreibt in gewisser Weise das einfachste relevante Tourenplanungsproblem: Ein 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, wieviele Einheiten der Fahrzeugkapazität durch diese Waren belegt werden. Ziel ist es nun, die Fahrzeuge den Kunden zuzuordnen (sog.: "Clustering") und gleichzeitig die Besuchsreihenfolge (sog.: "Routing") so zu ermitteln, dass die zurückgelegte Strecke minimiert wird.

In manchen Fällen werden dabei auch eine maximale Strecke pro Fahrzeug berücksichtigt oder als Zielfunktion die Minimierung der Anzahl der eingesetzten Fahrzeuge formuliert.

Ein W-Flugmuster ist ein Flugmuster, das in einer Flugzeugbasis A startet, zum Flughafen B fliegt, dann von B nach C und zurück fliegt, um schließlich zur Basis A zurückzukehren. Es handelt sich um ein sog. "komplexes Muster", da man nicht direkt von der Basis und zurück fliegt.

Der Name kommt daher, dass man das Muster wie ein "W" darstellen kann:

Mit Yield 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 durchaus 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 schiere Zahl (z. B. von Hotelübernachtungen oder Flugtickets) eine vollständig manuelle Anpassung der Preise unmöglich macht.

Dass das Yield-Management in vielen Fällen prinzipiell gut funktioniert, konnte man nach der Air-Berlin-Pleite gut erkennen. Danach war Lufthansa auf vielen Strecken monopolist und die Preise stiegen deutlich, was laut Lufthansa auf die automatische Preisanpassung durch ihre Algorithmen zurückzuführen sei.

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.

Ein Zeitfenster beschreibt innerhalb eines Tourenplanungsproblems ein Zeitintervall, indem 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 wenig Sinn machen. Aus unserer kundenorientierten Zeit sind Zeitfenster jedoch kaum wegzudenken, sodass Dienstleister in der Regel diese wirtschaftlichen Nachteile in Kauf nehmen, um ihren Kunden den bestmöglichen Service zu bieten.

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 zwei Uhrzeiten erbracht werden kann (z. B. zwischen 08:00 und 15:00 Uhr).