6
$\begingroup$

Our beloved Travelling Salesman just bought the Manual of the Planes and wants to make some use of it. He is not a great adventurer though, so he will restrain his travels in the Parallel and Fundamental Planes, which are tightly coupled with the Material Plane (and try not to spend so much time in the Quasi-elemental Plane of Minerals and all the gold that lies there!). Let's say therefore that we have M-1 Parallel Planes and our salesman can visit each city in any of them. Travel from Material Neverwinter to Astral Luskan is of course different than travel from Material Neverwinter to Material Luskan and not always in a trivial manner (might cost more, might cost less). To make matters worse, the Salesman can visit each city in only one Plane and cannot therefore benefit from a portal connecting Shadow Waterdeep with Faerie Baldur's Gate if he initially arrived in Material Waterdeep (assume Dimensional Anchors covering the cities). So the Salesman has to complete his path using these new restrictions.

A 4th Level Wizard exclaimed instantly that this Plane Travelling Salesman has a problem that is not easier than those of his normal colleagues (just assume that the travel between two cities costs the same regardless of the Planes used and you have a classic TSP). The question is: How can he convert the problem into another that has already been researched by the scholars?


Less nerdy description:

Replace each of the N nodes in the original TSP with M subnodes. Distances are given for every pair of subnodes between different nodes. For each node, a single subnode must be used in the solution. Give an algorithm for the new problem.


Edit:

It turns out that it is indeed a well-researched problem so I am adding all the aliases I found for it.

  • Generalized TSP
  • Group TSP
  • TSP with Neighbourhoods
  • Set TSP
  • One-of-a-Set TSP
  • Multiple Choice TSP
  • Covering Salesman Problem
$\endgroup$
  • $\begingroup$ I've been calling this the World Tour Problem: I want to visit every country in the world, but I don't care which airports I visit. (I think it is equivalent) $\endgroup$ – Lyndon White Jan 22 '16 at 5:31
9
$\begingroup$

If the tour is required to visit one node in each group, then the problem is called Group-TSP, or TSP-with-neighborhoods. There's a ton of work on this in the plane (just google it), and in general it's as hard as HITTING SET (the case in which your metric is all 1s). There's a paper by Safra and Schwartz that shows that Geometric group TSP (in the plane) is hard to any constant factor.

$\endgroup$
3
$\begingroup$

Thanks to Suresh's "naming" of the problem I have also found this paper: A New Efficient Transformation of Generalized Traveling Salesman Problem into Traveling Salesman Problem which might also help Salesmen Travelling the Planes!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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