1

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.

Improve this question
1
  • 1
    To whoever voted to close this as opinion-based: huh?
    – Jules
    Apr 24, 2017 at 10:40

1 Answer 1

Reset to default
7

Adding another city to an optimal route is essentially no different from solving the TSP in the first place. If it were simple, then the TSP would be simple; you could simply reduce a 100-city tour to a 99-city tour and so on. The fact that adding another node might invalidate the entire reasoning that proved the current optimal solution to be optimal is precisely what makes the problem NP-complete. I suppose that's why no one has found it worthwhile to invent a separate name for the incremental case.

Improve this answer
2
  • I have added an edit to the original question, hopefully clarifying what I am asking. It is almost certain that the original route is not optimal, but nonetheless cannot be changes, save for the addition of the new node. I agree that it is similar to the TSP, which is why I reference it, but it's a slight twist, or a variation. Since the route is not optimized, the only thing that can be improved upon is the manner in which I add a new node.
    – Birrel
    Apr 24, 2017 at 16:36
  • @Birrel Alright, the twist is slight in itself, but it completely changes the outcome. Adding a new link anywhere to an unchangeable circuit without the optimality condition simply requires a linear search, and so it's trivial compared to the real TSP.
    – Kilian Foth
    May 2, 2017 at 11:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.