I am familiar with the Traveling Salesman Problem, and many of the various approaches to solving it.

But is there a name for the following problem:

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.

The brute-force solution is simple - looping through the entire route to find the smallest increase in distance. This is not unlike the insertion method for solving the TSP. But I'm having trouble coming up with an optimized solution for this new problem, or figuring out how I might apply an existing heuristic to the problem.

Is there a name for this particular problem? Everything I can find for the TSP has to do with solving the original tour, but doesn't cover a solution for adding a city to an established tour. For the aforementioned solved tour, it may or may not be optimized, but in either case it cannot be changed. It might be perfect, or be a jumbled rats' nest. The only change is adding the new city, wherever it satisfies the problem statement.

EDIT #1

There seems to be a misunderstanding with the original question. The only answer so far assumes an "optimized" initial route, which potentially will not be the case (it almost certainly will not be).

Using the same problem statement as before: Assume the given route is not optimized. Instead, the nodes in the route have been set to a schedule, where they need to be visited at particular times, or in a particular order. The given route cannot be changed, save for the insertion of the new node at the optimal (or near-optimal) location.

An extension of the problem could be:

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.

Looking at this newest presentation, I cannot see how having 100 routes with 50 nodes would be any different than having one route with 5000 nodes. Similarly, scaling should be identical between the two (adding a new route of 50 nodes, or adding 50 nodes to the one route).

At any rate, I've been told this can have sub-linear scaling, with the appropriate heuristics applied to it.

• To whoever voted to close this as opinion-based: huh? – Jules Apr 24 '17 at 10:40