Page tree
Skip to end of metadata
Go to start of metadata

Verfahren des nächsten Nachfolgers, engl.: iterative procedure

Die Touren werden bei dieser, auch Sukzessivverfahren genannten, Methode konstruiert, indem jeweils von einem Kunden derjenige als der zunächst zu beliefernde Kunde gewählt wird, der dem vorherigen Kunden am nächsten liegt. Aufbauend auf der Idee, dass ein Tourenproblem eine Kombination eines Reihenfolge- und Zuordnungsproblems darstellt, versuchen diese zweistufigen Verfahren diese beiden Probleme unabhängig voneinander zu lösen. Es gibt prinzipiell zwei unterschiedliche Vorgehensweisen, die Cluster first - Route second, deren Hauptaugenmerk auf der Zuordnung der Kundenorte liegt, und das Route first - Cluster second, welches zuerst das Reihenfolgeproblem der Routenzuordnung löst.

Sämtliche Sukzessivverfahren sind als Hill-Climbing Verfahren konstruiert. Sie benutzen Heuristiken zur Unterstützung der Suche nach einer guten Lösung. Die Sukzessivverfahren sind jedoch nicht optimierend, d.h. eine e- Umgebung der Abweichung der gefundenen Lösungen vom Optimum kann bei diesen Verfahren nicht angegeben werden.



Abb. 1: Verfahren des nächsten Nachfolgers

  • No labels
Write a comment…