How can I find a route through a partitioned weighted graph that visits as many of the partitions as possible, for a given maximum distance? Start and end anywhere.
A real-world example could be to find a route that visits as many European countries as possible in $2000$ miles.
EDIT: by partitioned graph here, I mean that each vertex belongs to exactly one set, and for any $2$ vertices in the same set there exists a path that connects them whose vertices all belong to that set. The partition is already provided in the problem. The edge weights could correspond to distances - a max distance constraint is given in the problem. Again, think about cities belonging to countries, connected by roads.
The solution should be efficient but not necessarily exact. A typical number of partitions would be $\sim 50$. The number of vertices could be in the order of millions.
The image below shows an example for a max distance of $10$ - the path in red visits $3$ partitions. Example solution
This is called the set orienteering problem. See, for example: https://www.sciencedirect.com/science/article/abs/pii/S0377221717310202