Lösungsverfahren für das periodische Tourenplanungsproblem

Die Basis jeder Tourenplanung liegt in dem Problem des Handlungsreisenden. Der Ursprung dieses Konzeptes ist ungewiss, eines der ersten Werke ist ein deutsches Handbuch. „Der Handlungsreisende, wie er sein soll und was er zu thun hat, um Aufträge zu erhalten, und eines glücklichen Erfolges in seinen Geschäften gewiss zu seyn“ von einem „alten Commis Voyageur“ beschreibt neben der erfolgreichen Pferdehaltung auch seinen Ansatz der Tourenplanung. Das Ziel des TSP ist es, eine gegebene Anzahl an Orten zu besuchen und dabei die Kosten für die Stecke zu minimieren. Für jede mögliche Verbindung zwischen den Knoten ist eine Kante mit entsprechender Gewichtung gegeben. Aufbauend auf dem TSP haben Dantzig und Ramser 1959 unter dem Titel „The Truck Dispatching Problem“ die Tourenplanung entwickelt. Der Unterschied dabei liegt in der Anzahl der ausliefernden Personen. Beim TSP wird die Routenführung für eine Person, beispielsweise einen Postboten, der seine Strecke zum Austragen der Briefe optimiert, beschrieben. Das VRP hingegen optimiert die Tourenplanung gleichzeitig für mehrere Auslieferer.