|i am trying develop an algorithm to solve a Travelling Salesman Problem similar case where the goal is to find the best route with the highest attractiveness score (sum of scores for all visited sites/nodes) within a fixed time frame.
to illustrate this more:
a tourist wants to visit N attraction sites in a city and he only has 8 hours to visit as many attraction sites as possible. every site has an attractiveness score and the time spent to visit it.
- site A with ID 0 has an attractiveness score of 90 and requires 10 minutes to visit it ([0, 90, 10])
- site B with ID 1 has an attractiveness score of 69 and requires 7 minutes to visit it ([1, 69, 7])
- site C with ID 2 has an attractiveness score of 72 and requires 7 minutes to visit it ([2, 72, 11])
- site D with ID 3 has an attractiveness score of 116 and requires 16 minutes to visit it ([3, 116, 16])
and so on.
Now we have a time matrix T where T[i][j] represents the necessary time to go from site i to site j. finally we consider site 0 as both the start site and the end site, i.e. the tourist starts his journey at site 0 and returns to site 0 (a hotel for instance).
so the task is to find an itinerary for the tourist to visit as many attractions as possible with a maximum sum score of attractiveness.
example of T matrix for sites A,B,C and D (it could be 50 sites):
T = [0, 40, 35, 90]
[30, 0, 25, 130]
[67, 83, 0, 75]
[45, 79, 130, 0]
The TSP has been solved using different algorithms or methods but i am stuck with this one as it's a little bit different in the sense that the goal is to find the maximum attractiveness score for an itinerary within a time frame, and not the shortest route.
your help is much appreciated
I thought of methods like greedy algorithm, dynamic programming used in TSP but couldn't find a way to solve this particular problem.