Lexikon der Mathematik: subtour elimination constraints
Techniken, um in auf der Assignment-Relaxation beruhenden Branchand-Bound Algorithmen für das Travelling-Salesman-Problem disjunkte Teilprobleme zu erhalten, in denen mindestens eine Rundreise auf einer Teilmenge der Orte, die bei der Lö-sung der Assignment-Relaxation berechnet wurde, eliminiert wird.
Bei einer Rundreise auf i Orten können z. B. i Teilprobleme gebildet werden, indem im j-ten Teilproblem die ersten j − 1 Teilstrecken der Rundreise erzwungen und die j-te Teilstrecke verboten werden.
Copyright Springer Verlag GmbH Deutschland 2017
Schreiben Sie uns!