A* - Graph Traversal Heuristic

Question

I have a graph that represents a city. I know the location of places of interest (nodes, which have a Importance value), the location of the hotel I'm staying in, how the nodes are connected, the traversal time between them and have acess to latitude and longitude. There are no issues converting from time to distance and vice-versa.

The objective is to tour the city, maximizing the importance per day but limiting one day of travel to 10 hours. A day begins and ends at the hotel. I have a working A* algorithm that chooses the lowest value but with no heuristic yet, which I guess makes it a BB for now. With that in mind:

• Since I have access to Lat/Long, my first stab at an heuristic, while only dealing with times, would be the distance as the crow flies between a node and the hotel. Would this be an admissible heuristic? It gives me the shortest possible distance and time, so it wouldn't overestimate.

Now let's say the Importance of a node is between 1-4. In order to factor it in, one idea could be g(neighbor) = g(current) + (edge_cost / Importance^2). Assuming this would be valid (if not, why?):

• But now the heuristic values would be in a different unit. Could a solution to this simply be give the Hotel Importance = 1? If the value is the same, will it still be admissible? EDIT: I think this will end up giving me problems because of the difference in scale.
• I still have to restrict the total amount of time. Should each node keep track of the total time spent, in order to compare to the limit, plus the g() and h() values, because of the different units?

And finally:

• Since I have to start and end in the same node, what comes to mind is to explore a node and should I find the hotel see if I still have time to explore the neighbors instead of going back. However, if I still have time to expand to one more node, but time runs out and I can't get to the hotel from there, I'm assuming I'll have to backtrack to the parent.
• I can't help but see similarities to the knapsack problem. Even though I have to use A*, is there any lesson I can take from it?
• Must my heuristic be consistent in this case? If so, why?

By the way, the purpose here is pathfinding first, optimizations second.

Answer 1

This actually looks like a combination of the travelling salesman problem (TSP) and knapsack problem (KP). It's KP in this respect: the knapsack capacity is 10 (for total hours available in a day) and the locations are the items. The item value equals the location value. The item weight is equal to the time it takes to travel to the location (plus the location's portion of the trip back to the hotel). The challenge arises from the fact that an item's weight is unknown until you solve the optimal tour through the selected locations--enter the TSP and Pathfinding.

One approach might be to use a pathfinding algorithm (e.g. A*, Bellman–Ford, or Dijkstra's algorithm) primarily to compute a distance matrix between each node. The distance matrix can then be leveraged while solving the TSP portion of the problem: finding a tour through the locations and using the total time as the weight.

The next step is up to you. If you are looking for an approximate solution, many heuristics exist for both TSP and KP: See Christofides TSP Heuristic, or the Minimum TSP and Maximum Knapsack entries at the Compendium of NP Optimization problems.

If on the other hand you seek an optimal solution, you may be out of luck. Still I recommend you find a copy of Graph Theory. An Algorithmic Approach by Nicos Christofides (ISBN-13: 978-0121743505). It provides heuristics for early backtracking in a Depth-First-Search that expedite the search for optimal solutions to several NP-Complete problems.