Tourenplanung

Aufgabe der Tourenplanung ist es, gegebene Aufträge mit einem vorhandenen Fuhrpark so auszuführen, dass z. B. die variablen Kosten, die gesamte Fahrstrecke bzw. Fahrzeit bzw. die Anzahl der einzusetzenden Fahrzeuge minimiert werden. Für jedes einzusetzende Fahrzeug ist eine Tour festzulegen, die durch die Anzahl der auszuführenden Aufträge und deren Reihenfolge definiert ist. Die Bestimmung der Reihenfolge der Aufträge innerhalb jeder Tour stellt ein knoten- oder kantenorientiertes Rundreiseproblem dar. Bei der Tourenplanung kann es sich um den Transport von Gütern oder Personen handeln. Tourenplanungsprobleme treten beispielsweise bei der täglichen Auslieferung von Gütern in den Handel, bei Kundenbesuchen von Außendienstmitarbeitern, beim Einsammeln von Gütern (z. B. der Leerung von Müllcontainern oder Briefkästen) oder beim Schulbusverkehr auf. Im Folgenden erfolgt eine Beschränkung auf knotenorientierte Tourenplanungsprobleme85.