{"action":"created","issue":{"url":"https://api.github.com/repos/pgRouting/pgrouting/issues/349","labels_url":"https://api.github.com/repos/pgRouting/pgrouting/issues/349/labels{/name}","comments_url":"https://api.github.com/repos/pgRouting/pgrouting/issues/349/comments","events_url":"https://api.github.com/repos/pgRouting/pgrouting/issues/349/events","html_url":"https://github.com/pgRouting/pgrouting/issues/349","id":91826832,"number":349,"title":"One-to-Many Astar","user":{"login":"boerngen-schmidt","id":245062,"avatar_url":"https://avatars.githubusercontent.com/u/245062?v=3","gravatar_id":"","url":"https://api.github.com/users/boerngen-schmidt","html_url":"https://github.com/boerngen-schmidt","followers_url":"https://api.github.com/users/boerngen-schmidt/followers","following_url":"https://api.github.com/users/boerngen-schmidt/following{/other_user}","gists_url":"https://api.github.com/users/boerngen-schmidt/gists{/gist_id}","starred_url":"https://api.github.com/users/boerngen-schmidt/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/boerngen-schmidt/subscriptions","organizations_url":"https://api.github.com/users/boerngen-schmidt/orgs","repos_url":"https://api.github.com/users/boerngen-schmidt/repos","events_url":"https://api.github.com/users/boerngen-schmidt/events{/privacy}","received_events_url":"https://api.github.com/users/boerngen-schmidt/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":1,"created_at":"2015-06-29T14:50:59Z","updated_at":"2015-06-29T15:27:28Z","closed_at":null,"body":"Hello everyone,\r\n\r\nthis is a feature request of a one-to-many routing algorithm using astar. First off, if it does not make sense feel free to close the issue and discard it.\r\n\r\nCurrently I'm writing my master thesis, where I do simulate gasoline refilling strategies for commuters in germany. Everytime a commuter generates a refill event I have to find the cheapest reachable refill station. Currently I use kdijkstra for this problem, but while writing my thesis I read, that the performance of Astar is much better than the one of dijkstra, so wouldn't it make sense to also have a pgr_kastar function?\r\n\r\n- benjamin"},"comment":{"url":"https://api.github.com/repos/pgRouting/pgrouting/issues/comments/116731881","html_url":"https://github.com/pgRouting/pgrouting/issues/349#issuecomment-116731881","issue_url":"https://api.github.com/repos/pgRouting/pgrouting/issues/349","id":116731881,"user":{"login":"woodbri","id":805250,"avatar_url":"https://avatars.githubusercontent.com/u/805250?v=3","gravatar_id":"","url":"https://api.github.com/users/woodbri","html_url":"https://github.com/woodbri","followers_url":"https://api.github.com/users/woodbri/followers","following_url":"https://api.github.com/users/woodbri/following{/other_user}","gists_url":"https://api.github.com/users/woodbri/gists{/gist_id}","starred_url":"https://api.github.com/users/woodbri/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/woodbri/subscriptions","organizations_url":"https://api.github.com/users/woodbri/orgs","repos_url":"https://api.github.com/users/woodbri/repos","events_url":"https://api.github.com/users/woodbri/events{/privacy}","received_events_url":"https://api.github.com/users/woodbri/received_events","type":"User","site_admin":false},"created_at":"2015-06-29T15:27:28Z","updated_at":"2015-06-29T15:27:28Z","body":"Well your statement is only partially correct. AStar is faster than Dijkstra for doing a one to one route. AStar is in fact Dijkstra with a heuristic that allows it to search only a subset of the graph moving toward the destination node, whereas Dijkstra solve the whole graph. But if you have many target destinations then using Dijkstra will solve off the solutions at once, and a kastar would need to sole the graph k-times which will like take longer than one dijkstra solution that gives you all your answers at once. So pgr_kdijkstra is the way to go.\r\n\r\nThere are some caveats to the above. I'm sure we can construct cases where the above would not be true, like your k target nodes are very far away and spread out geographically. Or where all the target nodes are clustered very close together such that the Astar solution would find all the nodes in a single pass, but as a general solution I think pgr_kdijkstra() is probably the better solution."}}