Überblick

Das „Traveling Salesman Problem“ (TSP) oder „Handlungsreisenden-Problem“ lässt sich der Kategorie der Reihenfolgeprobleme hinsichtlich der Planung von Lieferrouten und des optimalen Einsatzes von Transportmitteln zuordnen. Häufig wird es auch mit dem Terminus „Lieferanten-Problem“ umschrieben. Die Geburtsstunde des TSP für entsprechende unternehmensbezogene Planungsmodelle kann nicht eindeutig bestimmt werden. So wurde es in den 1920er und 1930er beispielsweise durch den österreichischen Mathematiker Karl Menger publiziert und vertreten. Im Nachgang wurden wurden von einer Reihe von Wissenschaftlern die unterschiedlichsten mathematischen Modelle bzw. Algorithmen entwickelt, um Routenplanungen unter ökonomischen Gesichtspunkten rechnerisch zu optimieren.

In seiner klassischen Ausprägung zielt das TSP darauf ab, dass ein Handlungsreisender von einem Startpunkt aus (Stadt, Depot etc.) auf seiner Route mehrere Kunden an unterschiedlichen Standorten genau einmal besuchen muss und nach erfolgter Belieferung des letzten Kunden wieder an seinen Ausgangsort zurückkehrt. Betriebswirtschaftlich entscheidend ist dabei die Beantwortung der Frage, wie die Route konkret gewählt werden muss, d.h. in welcher Reihenfolge die Kunden zu besuchen sind, damit die entstehenden Fahrtkosten minimiert werden.

Im Vergleich zum klassischen TSP erhöht sich die Planungskomplexität dann, wenn nicht lediglich ein Handlungsreisender, sondern mehrere parallel auf Reisen geschickt werden. Hier muss nicht nur festgelegt werden, in welcher Reihenfolge welche Kunden beliefert werden. Zusätzlich muss auch geplant werden, welche Handlungsreisenden (oder Fahrzeuge) auf welcher Route eingesetzt werden. Auch hier muss insgesamt die kürzeste und kostengünstigste Fahrtstrecke ermittelt werden.

Konzept

Die Kernzielsetzung kombinatorischer Optimierungsprobleme im Rahmen des TSP besteht regelmäßig darin, die kostengünstigste Route hinsichtlich der Belieferung einer vorgegebenen Anzahl von Kunden zu bestimmen. Die Reisekosten zwischen den relevanten Kunden-Standorten bzw. Lieferzielen lassen sich dabei grundsätzlich anhand der jeweiligen Entfernungen, der üblichen Kosten pro Kilometer. sowie der Reise- bzw. Arbeitszeiten paarweise ermitteln. Sie bilden die Grundlage für die Lösung des jeweils einschlägigen Planungsproblems. In Abhängigkeit von der Komplexität des Planungsproblems kann dabei zudem die Anzahl der einzusetzenden Fahrzeuge relevant sein, welche tendenziell so gering wie möglich ausfallen sollte. Die Realisierung der vorgegebenen Ziele ist dabei abhängig von unterschiedlichen Struktur- (z.B. Depot- und Routenanzahl, Art der eingesetzten Verkehrsmittel) und Kontextvariablen (z.B. Lage der Depots, Art, Menge und Umfang der Transportwaren, Anzahl der theoretisch einsetzbaren Fahrzeuge).

Die konkrete Konzipierung der Routenplanung ist demnach äußerst voraussetzungsvoll und mit steigender Komplexität jenseits des klassischen TSP (mehr Kunden, mehr Fahrzeuge etc.) umso rechen-, zeit- und kostenintensiver. Hier einschlägige Probleme sind jedoch grundsätzlich mathematisch eindeutig und exakt lösbar. Betriebswirtschaftlich sinnvoll ist die Bestimmung optimaler Routenlösungen dagegen regelmäßig ausschließlich für die Lösung von Planungsfragen in der Größenordnung des klassischen TSP. Hier kommt in Kenntnis und auf der Basis der relevanten Fahrtkosten und einer dem Rechenaufwand gerecht werdenden Kundengröße (bis etwa 100) die Anwendung standartmäßiger Branch-and-Bound-Algorithmen zur Identifizierung der optimalen Route in Betracht. Bei entsprechender Komplexität eignen sich derartig Verfahren auch für die Lösung von TSP mit mehreren Fahrzeugen.

In der Realität national und international operierender Logistik-Unternehmen dürfte ein Rückgriff auf Methoden zur Berechnung der optimalen Route regelmäßig ausscheiden, da der entsprechende Rechenaufwand und die damit verbundenen Kosten betriebswirtschaftlich nicht zu rechtfertigen sind. Vielmehr bietet sich hier der Rückgriff heuristische Verfahren der Problemlösung an, mit denen optimale Routen durch die Anwendung entsprechender Algorithmen zumindest näherungsweise mathematisch definiert werden können. Die diesbezüglichen Verfahren und Algorithmen sind dabei – auch hinsichtlich ihrer Anzahl bzw. Bandbreite – mindestens so komplex wie die mit ihnen zu bearbeitenden Problemlagen.

So existieren entsprechende Heuristiken sowohl für das klassische TSP als auch für Problematiken, bei denen mehrere Fahrzeuge einzusetzen sind. Gemeinsam ist diesen Verfahren, dass ihnen eine Problemstellung zugrunde liegt, nach der alle Kunden aus demselben Depot beliefert werden sollen. Sie unterscheiden sich jedoch hinsichtlich ihrer Zuordnungsmodalitäten. So lassen sich mit einigen Verfahren die einzelnen Kunden und Routen den verfügbaren Fahrzeugen in einem Schritt zuordnen. Andere Verfahren wiederum gehen hier – unabhängig von der Reihenfolge – schrittweise vor, indem sie in dem einen Schritt den Kundenstandorten die Fahrzeuge und in dem anderen den Fahrzeugen die Routen zuordnen. Auch für die Bedingung, dass es bei der Routenplanung unter Umständen mehrere Depots zu berücksichtigen gilt, existieren einschlägige Heuristiken.

Mehrwert

Traveling Salesman Probleme sind nicht allgemeingültig zu definieren und zu lösen. Hiervon zeugen alleine schon die vielfältigen mathematischen Konzepte, welche jeweils unterschiedliche Parameter berücksichtigen. Doch jenseits der Komplexität des im Einzelfall einschlägigen Problems und des damit zu wählenden Lösungsweges ergeben sich durch eine mathematische Optimierung von Logistikrouten jeweils signifikante Einsparungspotentiale für das betroffene Unternehmen. Diese sollten dabei in einem betriebswirtschaftlich sinnvollen Verhältnis zu den Berechnungskosten des jeweils gewählten Verfahrens liegen.