Ho familiarità con il problema del venditore ambulante e molti dei vari approcci per risolverlo.
Ma c'è un nome per il seguente problema:
Given an existing (solved) tour and a new city, insert the new city into the tour (at the start, between any two existing cities, or at the end), such that the total increase in distance is minimized.
La soluzione a forza bruta è semplice: passa attraverso l'intero percorso per trovare il più piccolo aumento di distanza. Questo non è diverso dal metodo di inserimento per risolvere il TSP. Ma ho problemi a trovare una soluzione ottimizzata per questo nuovo problema, o capire come applicare una euristica esistente al problema.
C'è un nome per questo particolare problema? Tutto quello che posso trovare per il TSP ha a che fare con la risoluzione del tour originale, ma non copre una soluzione per aggiungere una città a un tour stabilito. Per il tour risolto di cui sopra, può o non può essere ottimizzato, ma in entrambi i casi non può essere modificato. Potrebbe essere perfetto, o essere un nido di topi confuso. L'unico cambiamento è aggiungere la nuova città, ovunque soddisfi la dichiarazione del problema.
EDIT # 1
Sembra esserci un malinteso con la domanda originale. L'unica risposta fino ad ora presuppone un percorso iniziale "ottimizzato", che potenzialmente non sarà il caso (quasi certamente non lo sarà).
Usando la stessa affermazione di problemi di prima: si supponga che la rotta indicata sia non ottimizzata. Invece, i nodi nella rotta sono stati impostati su una pianificazione, dove devono essere visitati in momenti particolari o in un ordine particolare. Il percorso specificato non può essere modificato, salvo per l'inserimento del nuovo nodo nella posizione ottimale (o quasi ottimale).
Un'estensione del problema potrebbe essere:
Given multiple routes and a new node, insert the new node into one of the routes (at the start, between any two existing nodes, at the end), such that the total increase in distance is minimized.
Guardando questa presentazione più recente, non riesco a vedere come avere 100 percorsi con 50 nodi sia diverso da quello di avere una rotta con 5000 nodi. Allo stesso modo, il ridimensionamento dovrebbe essere identico tra i due (aggiungendo una nuova rotta di 50 nodi o aggiungendo 50 nodi alla stessa rotta).
In ogni caso, mi è stato detto che questo può avere un ridimensionamento sub-lineare, con l'appropriata euristica applicata.