Heuristische Verfahren

Wie im vorherigen Abschnitt gezeigt, liefern exakte Verfahren wie die begrenzte Enumeration zwar das optimale Ergebnis, sind aber sehr rechen- und zeitaufwendig. Bei einer bestimmten Anzahl an Knoten kann nicht mal mehr mit EDV-Analage eine optimale Lösung ermittelt werden, weil die Anzahl an Kombinationen so groß ist, dass die Zeit bis eine optimale Lösung gefunden wird selbst für Rechenprogramme einfach zu groß ist.

Deswegen wird auf heuristische Verfahren zurückgegeriffen. Hierbei handelt es sich um Näherungsverfahren zur Bestimmung einer Lösung, die dann aber nicht unbedingt optimal sein muss, aber zumindest näherungsweise eine gute Lösung ermitteln. Das Problem ist allerdings, dass man bei den heuristischen Verfahren nicht einschätzen kann, wie gut die ermittelte Lösung ist, da aufgrund der Nichtkenntnis des Optimalwerts auch keine Abweichung vom Optimalwert ermittelt werden kann. 

In den folgenden Abschnitten sollen zwei heuristische Eröffungsverfahren zur Lösung von Traveling-Salesman-Problemen aufgezeigt werden. Hierzu zählen das Verfahren des besten Nachfolgers und das Verfahren der sukzessiven Einbeziehung von Stationen.

Es wird hierfür auf das im Abschnitt Vollständige Enumeration aufgeführte Beispiel zurückgergriffen, da hier die optimale Lösung ermittelt werden konnte und damit ein Vergleich zu den Lösungen der heuristischen Verfahren möglich ist.