Zitat:
Ich würde gerne mit Verfahren beginnen, die zumindest ermöglichen eine gefundene Lösung abzuschätzen, also eine untere Schranke für die Zeit die für die benötigt wird zu finden.
Was verstehst du unter einer "unteren Schranke"? Ich denke dabei an die kürzeste Strecke und du wirst keinen Algorithmus finden, der dir diese Information schnell geben wird, da das ja die Lösung von TSP wäre.
Wenn du dich bisher noch nicht mit solchen Problemen befasst hast, wird es keine gute Idee sein, von Anfang an mit zusätzlichen Problemen zu arbeiten, TSP ist schon (NP-)schwer genug.