Travel Salesman Problem find itinerary with highest visited sites attractiveness score

[Faroug Tifratene]

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. example: - 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.