CODEWITHSUNDEEP
javaartificial-intelligencea-starheuristics
mistic
mistic

Reputation: 285

Heuristic For A* Algorithm

I have a problem to solve with A* but i'm having difficults to design a good heuristic.

My problem are:

Determine the best route to accomplish by a garbage collection truck in a city that moves on a map known seeking to maximize the load and minimize travel time.

I have 4 types of nodes: Geral Nodes, Dump Nodes, Garbage Nodes and Gas Nodes.

The garbage collection truck may run out of gas and have the chance to refill the vehicle. There may also be more than 1 garbage dumpster where to deliver.

Whats the best heuristic to solve this problem?

Regards

Upvotes: 1

Views: 4049

Answers (2)

Geoffrey De Smet
Geoffrey De Smet

Reputation: 27312

A* is great to find the fastest/shortest route between 2 points.

However, your garbage truck problem is probably a completely different problem: you need to find the fastest/shortest route by ordering a set of points. That's basically the Traveling Salesman Problem (TSP) or it's big brother the Vehicle Routing Problem (VRP), both of which are NP-complete.

A* cannot handle NP-complete problems, you need algorithms like metaheuristics etc. Look for solutions on the TSP and VRP problems, for example the TSP and VRP example in OptaPlanner (java, open source) (which is shown in this video).

Upvotes: 0

Zim-Zam O'Pootertoot
Zim-Zam O'Pootertoot

Reputation: 18148

A good first-pass search heuristic is to use a greedy algorithm. For example, in a general route-planning algorithm (find the shortest route between cities) a decent heuristic is to use a greedy algorithm where you always go to the next city that's closest to the destination as the crow flies; this is a linear-time heuristic and never overestimates the solution. In your case, maybe you can use a greedy algorithm in which a garbage truck always goes to the next-closest garbage node, or the garbage node with the most garbage; I can't get more specific without knowing the details of the four nodes you're using, but you get the idea. Any linear-time algorithm that doesn't overestimate the solution will do, and you can then tweak it in your next pass. (An nlog(n) heuristic is also acceptable in most cases; n^2 is getting awfully expensive.)

Upvotes: 2

Related Questions