If there are a total of X possible cities to travel to, but our salesman only has to visit a fixed number of them Y<X, how do we choose the Y cities to travel to and the order? Has this problem been studied and/or does it have a formal name? Appreciate any references or real-world applications of this problem.
Traveling Salesman Problem where not all cities need to be visited
data analysisdiscrete optimizationoperations researchoptimizationterminology
Related Solutions
So if I understood correctly:
- you have a graph with set of vertices V representing the locations
- The vertices are labelled with the 'types' of clients
- There is a set of undirected, weighted edges (u,v) in E where (u,v) exists in E
- exists if it is possible to travel from location u to location v
- is weighted with the cost or distance of getting from u to v.
You want to find a set of edges connecting a subset of the vertices such that each unique label is included at least once in the subset of vertices.
My suggestion is to recast the problem as follows:
- Make the edges directed and add reverse edges for all the location-location edges
- Add vertices to the graph for each unique label
- Add a zero-weighted edge from each location to the labels associated with it
Since the edges are directed, there is no path that passes trough the 'label' vertices.
Now, if I'm right, your problem is (or is very similar to) a minimum-spanning tree problem because you want to find the set of edges that connects all of the label nodes at minimum cost.
Let's look at an example. Suppose you have four cities, A, X, Y, and Z, and A is at distance $1$ from each of the others, while the distance between any two of X, Y, Z is $100$. Then of course a solution to TSP starting at A is given by A to X to A to Y to A to Z to A – let's write this as AXAYAZA, which has length $6$, and visits A multiple times.
Now let's carry out the construction in Rahul's comment. We form a new problem with the same cities but with the distance between cities replaced by the length of the shortest path between the two cities. So in the new problem, A is still at distance $1$ from each of the others, but the distance between any two of X, Y, Z is $2$. Now the tirangle inequality is satisfied (although the configuration is still unrealizable in any Euclidean space), and a solution is given by AXYZA, length $6$, no city visited twice (except for both starting and ending at A).
So we have taken a problem where the solution has multiple visits to a city, and replaced it with an equivalent problem which doesn't. I hope it's clear that you can carry out this construction for any (finite) set of cities and distances. So you can always replace a problem with an equivalent problem where the triangle inequality is satisfied and no city gets visited more than once. So, there is no loss of generality in assuming the triangle inequality holds and no city gets visited more than once. That's why we can restrict our attention to what looks like, but really isn't, a special case.
Best Answer
Yes, search for optimal subtour problem, orienteering problem, and prize-collecting TSP. This problem appears as a subproblem in column-generation approaches to the vehicle routing problem.