0

Does the pgr_astar heuristic function of postgreSQL verify that the proposed path is optimal on time and length despite what mesure we choose as cost on the query?

Example: When asking this query

SELECT a.seq, a.id1 AS node, a.id2 AS edge, b.source, b.target, b.cost, b.reverse_cost, b.geom_way 
 FROM pgr_astar 
('SELECT id, source, target, fuel as cost, x1, y1, x2, y2, reverse_cost FROM San_francisco', 8,895, true, true)as a LEFT JOIN San_francisco as b  
ON a.id2 = b.id 
order by seq

Does pgr_astar verify that the result is optimal on length and time in addition of the cost(fuel)?

3

I'm not exactly sure I understand exactly what you're asking but I'll try to provide an explanation of what A* does.

Dijkstra and A* algorithms should theoretically return the same result because they are almost the same algorithm. What A* does is provide an optimization to the order in which nodes are searched. Generally speaking, in a spatial/geographical context, when a choice for the next node is encountered, the first one to be tested will be much more likely to be the one which puts you geographically closer to the end end goal. This is why the pg_aStar requires input of the (x,y) coordinates of the nodes.

The heuristic parameter refers to the equation used to calculate the amount to add to the cost of travelling to a node, based on the distance between the node's (x,y) location and the final end goal's (x,y) location. In pgRouting, it is an integer representing possible mathematical equations:

  • 0: h(v) = 0 (Use this value to compare with pgr_dijkstra)
  • 1: h(v) abs(max(dx, dy))
  • 2: h(v) abs(min(dx, dy))
  • 3: h(v) = dx * dx + dy * dy
  • 4: h(v) = sqrt(dx * dx + dy * dy)
  • 5: h(v) = abs(dx) + abs(dy)

Source

I feel like your question is asking if it is optimal on length (which I assume means the cost) and on time (which I assume means computation time). Optimal on length? Yes. Optimal on time? Probably - it depends on the chosen heuristic and the graph. If the graph is large but its complexity is fairly trivial and the heuristic makes sense then it should be solved faster than by Dijkstra.

However, on small graphs, the overhead of the additional calculation of the heuristic may dwarf the performance gains from the algorithm, in which case Dijkstra might actually be more performant.

This video is my go-to when explaining A* and the heuristic

2
  • Thank you for answering. Well I have a dataset of San Francisco in which I have the cost of each segment in time ( the estimated time needed to each segement) the length of each segement and the cost on fuel consumption of each segement (the fuel consumed by each segemnt). I'm asking if I mention that I want to find the optimal path using the fuel as cost, does the heuristic function take into account the length and the time of each segement implicitly? – Ben Aug 12 '18 at 14:38
  • No, it ultimately just considers the cost, which is in your case, fuel. The "length" component of A* is the length between any node to be explored and the final destination. This heuristic simply adjusts the order in which nodes are explored under the assumption that going to a node that is closer to the end goal will in most cases be part of the optimal solution. – wfgeo Aug 13 '18 at 11:46
1

I'm asking if I mention that I want to find the optimal path using the fuel as cost, does the heuristic function take into account the length and the time of each segment implicitly?

No. Both algorithms find the shortest path based on 'cost'. But you have complete control of what cost is.

As @1saac points out, A* prioritises moving towards the target, but both will give the same result. The A* makes an assumption, though, that moving closer to the target will speed things up. This is generally true if the cost is something like distance, but may not be for other costs.

Cost is typically something like length, time (=length/speed) but it can be any positive number - e.g. fuel consumption, toll road fees etc. that you want to minimise.

You could mix two costs by using a weighted formula e.g.

cost = (1*length)+(3*fuel_consumption)

If you normalize your length and fuel consumption values to a consistent range e.g. [0,1], that will give a weight of 3/4 to the fuel consumption and 1/4 to the length. That will prioritise saving fuel, but also add a small component of length (for example, to account for wear on tires).

I would recommend trying both - the A* optimisation may not be as effective as it would be if you were using length as a cost, but it really depends on your network.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.