Rundreiseplanung

Rundreiseprobleme bestimmen eine optimale Rundreise ausgehend von einem Startort entweder über gewisse vorgeschriebene Strecken oder über eine Anzahl vorgegebener Orte zurück zum Startort. Während im ersten Fall ein kanten- oder pfeilorientiertes Problem vorliegt, handelt es sich im zweiten Fall um ein knotenorientiertes Problem. Kanten- oder pfeilorientierte Rundreiseprobleme treten beispielsweise bei der Leerung von Briefkästen oder Containern für Altpapier bzw. Altglas oder bei der Straßenreinigung auf. Knotenorientierte Problemstellungen liegen z. B. bei Kundenbesuchen von Außendienstmitarbeitern, bei der Auslieferung oder beim Einsammeln von Gütern oder bei der Bestimmung der Bearbeitungsreihenfolge von Aufträgen auf einer Maschine vor.