Lineare Optimierung beim TSP

[Cyf]

Ich bin irgendwie auf die dumme Idee gekommen, mich mal mit etwas komplexeren Problemstellungen beschäftigen zu wollen.
Also habe ich mir das für Optimierungsprobleme typische TSP mal angesehen und mir verschiedene Lösungsansätze mal angesehen, leider ist mir derzeit die Funktionsweise von exakten Lösungsverfahren (außer praktisch laufzeitmäßig sinnlose Permutation) wie Branch-and-Cut noch nicht wirklich klar, laut Wiki besteht das ganze ja aus einer Kombination von Schnittebenenverfahren und Branch-and-Bound.
Daher mal ein paar Fragen in der Hoffnung jemand kann mir weiterhelfen
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. Leider habe ich in der Richtung überhaupt noch keine Erfahrung (aber durchaus den Willen mich mit ein wenig Mathe zu beschäftigen), mit welchem Verfahren beginne ich am besten?
Funktioniert sowas auch prinzipiell, wenn man das Problem verschärft z.B. wenn sich der Wert der Kanten mit jedem Zug ändern würden z.B. der Handlungsreisende wird müde pro Zug verlängern sich die Kanten um 1, oder die Städte können nur zu einer bestimmten Zeit betreten werden, weil sie zum Beispiel nachts absperren, und ggf. müsste der Reisende warten (es geht hier jetzt nicht darum, ob das realistisch ist), also sprich, wenn die Kantenlänge von einer sich ändernden Variable abhängt?