Which algorithm to choose for solving the problem?

Question

Algorithms

There is a problem:
The set of cities served by company X is represented by a graph, the vertices of which correspond to the cities, and the edges correspond to the routes connecting them, while the length of the edge determines the distance between the cities. Each city corresponds to an integer - the number of contracts that can be concluded in this city. Determine the route that the salesman should take in such a way as to conclude the maximum possible number of contracts. It is assumed that the fuel supply in the traveling salesman's car is only enough for a limited route. The solution must be visualized.
Question: what algorithm should be applied here?

Answer 1

So it seems like a classic traveling salesman problem. Wikipedia describes algorithms for solving this problem. Analyze everything and choose the best one.

Answer 2

If there is a memory N * 2 ^ N, where N is the number of cities, then we can use the dynamics of the set of cities passed plus the last city where the traveling salesman ended up. For each such combination, we remember the minimum amount of fuel that was required to get to this situation and the city from which we came to the last city. Then, for all situations, we pass from the last city along all edges, and we get into situations where there are 1 more cities visited. Again, for each we find the optimal (in terms of fuel) path by which we got there ... and so on, until the fuel runs out. After that, we go through the entire list, and look where more prizes are collected.
Up to 20-25 cities should work reasonable hours. Next, you have to look for heuristics.