A friend and I are trying to publish a version of the Travelling Salesman Problem known as the "Travelling Santa Problem": If Santa has to visit each county in the United States, and wants to deliver presents to people as rapidly as possible, then the quandary is not just which route across the 3,100-some continental counties is optimal--that has been solved--but also how to account for the fact that there are different numbers of households in each of those counties (data that we have.)
I've read quite a bit of discussion on how to solve the TSP when the edges are not equally weighted--say, not all airline prices are the same--but I can't seem to find any discussion that accounts for the priority of each node. It's possible is this not really a TSP problem, but it may be. While one could easily just order Santa to visit each county in descending order of population, that would involve so much zigzagging that he would still be delivering presents on Dec. 27. But if one gives him the standard TSP solution for US counties, he's saving time but not prioritizing nearby counties in the order that they ought to be visited to maximize the percent of houses visited.
One could argue that the TSP solution is still optimal because it's the quickest way to reach 100%. But if the "score" for this problem is the median number of hours each child waited (assuming none are obediently asleep!) then finishing as fast as possible isn't effective if the deliveries were backloaded to the end of the route. For example, a TSP-generated route that has Santa end up in Los Angeles County would be foolish, since it's the most populous county in the country.
Obviously we don't know what Santa's velocity is, but so long as we assume it's finite and some small fraction of c, there should be an optimal solution that still tries to minimize total travel distance in order to deliver presents faster, but allows for a longer-than-minimal distance if that means hitting more populous nearby locations first.
This may be an old problem, but it's the kind that is difficult to communicate to Google. Thank you!