2

I have an optimization(optimisation) problem, I think it is travelling salesman, where I want to find an answer to the question:

"What is the best coffee shop for person x within a 50km radius?"

The variables for this question are dependent on:

  • the persons self-assessed palate level (1, 2, 3);
  • the rating of the coffee shop (1 - 10);
  • and the distance of the coffee shop.

The need for a higher rated coffee shop increases with a higher palate level, however it also decreases the further away the coffee shop. So the minima needs to be determined based on all those variables.

My question is, is this a travelling salesman type problem? if yes, how do I frame it as so (or just a pointer in the direction of how to frame it would be helpful)?

Seth
  • 53
  • 1
    No, this is not a travelling salesmen problem (TSP). A TSP would be to make a coffee shop tour with the smallest travelled way. – The Pheromone Kid Sep 11 '14 at 06:33
  • I didn't think TSP always had to be about distance. I thought the TSP is an example that uses distance as the edges between all the graph nodes however if you could frame the problem such that the edges could mean something else and then find the minima in the graph? – Seth Sep 11 '14 at 22:29
  • 1
    It's easy to find the shortest distance between two points on a graph (which I think your problem is about). The TSP involves finding the shortest path through all the points on a graph. – TonyK Sep 19 '14 at 12:32

2 Answers2

4

Assume there are $N$ coffee shops $\leq 50$ km away from your hometown $H$. When you have visited all of them each has obtained a certain number of points according to your criteria (including distance from $H$), and the shop with the largest number of points is the best one. There is only a comparison of $N$ values involved here.

In order to find out about the quality of each of the $N$ shops it might be necessary to envisage a grand tour visiting all of them, starting and ending at $H$. This then would be a TSP, but it has nothing to do with the final rating of the shops.

Christian Blatter
  • 226,825
0

If i understand the question, the coffee shop graph is complete, and the edges are weighted by the distances between them. The coffee shops ratings are also normalized by the palate level of the individual, and he is represented as a node with edges connecting to all shops, with weights in distance. And the coffee shop rating also gets normalized by distance. You can then just sort in descending order to find the nearest and best shop. the trick is in the normalization of shop rate by palate level and distance. It will impact the sorting order. So the problem does not have a reduction to TSP, as formulated, but if you want to visit all of them, in minimum time, then yes.

panday
  • 17