{"action":"created","issue":{"url":"https://api.github.com/repos/igraph/igraph/issues/896","labels_url":"https://api.github.com/repos/igraph/igraph/issues/896/labels{/name}","comments_url":"https://api.github.com/repos/igraph/igraph/issues/896/comments","events_url":"https://api.github.com/repos/igraph/igraph/issues/896/events","html_url":"https://github.com/igraph/igraph/issues/896","id":116795635,"number":896,"title":"Smart generation of different shortest paths","user":{"login":"otsaw","id":1157847,"avatar_url":"https://avatars.githubusercontent.com/u/1157847?v=3","gravatar_id":"","url":"https://api.github.com/users/otsaw","html_url":"https://github.com/otsaw","followers_url":"https://api.github.com/users/otsaw/followers","following_url":"https://api.github.com/users/otsaw/following{/other_user}","gists_url":"https://api.github.com/users/otsaw/gists{/gist_id}","starred_url":"https://api.github.com/users/otsaw/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/otsaw/subscriptions","organizations_url":"https://api.github.com/users/otsaw/orgs","repos_url":"https://api.github.com/users/otsaw/repos","events_url":"https://api.github.com/users/otsaw/events{/privacy}","received_events_url":"https://api.github.com/users/otsaw/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":7,"created_at":"2015-11-13T15:54:15Z","updated_at":"2015-11-17T13:40:56Z","closed_at":null,"body":"For route choice between two points on an actual road network, it would be useful to be able to generate a couple different alternative routes. To actually get different alternatives instead of e.g. a one block detour, some kind of a heuristic is needed. One popular method \"link penalty\" first finds the shortest path using Dijkstra's algorithm, then multiplies link weights along that path by a factor greater than one and then finds the shortest path on the altered network and so on until the desired amount of alternatives have been found.\r\n\r\nI currently have and use an R implementation of the link penalty method and it works fine, except it's a bit slow, which is why I'd like to see it in igraph, implemented in C code.\r\n\r\nFor references, see e.g. the following.\r\n\r\nEvaluation of choice set generation algorithms for route choice models\r\nhttp://web.mit.edu/rama/Public/papers/paper7.pdf\r\n\r\nRoute choice modeling: past, present and future research directions\r\nhttp://www.sciencedirect.com/science/article/pii/S1755534513700058\r\n"},"comment":{"url":"https://api.github.com/repos/igraph/igraph/issues/comments/157372995","html_url":"https://github.com/igraph/igraph/issues/896#issuecomment-157372995","issue_url":"https://api.github.com/repos/igraph/igraph/issues/896","id":157372995,"user":{"login":"otsaw","id":1157847,"avatar_url":"https://avatars.githubusercontent.com/u/1157847?v=3","gravatar_id":"","url":"https://api.github.com/users/otsaw","html_url":"https://github.com/otsaw","followers_url":"https://api.github.com/users/otsaw/followers","following_url":"https://api.github.com/users/otsaw/following{/other_user}","gists_url":"https://api.github.com/users/otsaw/gists{/gist_id}","starred_url":"https://api.github.com/users/otsaw/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/otsaw/subscriptions","organizations_url":"https://api.github.com/users/otsaw/orgs","repos_url":"https://api.github.com/users/otsaw/repos","events_url":"https://api.github.com/users/otsaw/events{/privacy}","received_events_url":"https://api.github.com/users/otsaw/received_events","type":"User","site_admin":false},"created_at":"2015-11-17T13:40:56Z","updated_at":"2015-11-17T13:40:56Z","body":"> Also, parallelization might help if you have multiple CPU cores as igraph uses a single CPU core only for shortest path search. No idea how to do that in R, though - I'm not an R expert.\r\n\r\nI have 64 cores, so yes, I do already use parallelization -- `mclapply` in R.\r\n\r\n> Do you have exact coordinates for the intersections of the roads (assuming that the nodes represent intersections and not roads)? If so, it might be the case that the A* search would be faster than Dijkstra.\r\n\r\nCoordinates are known. A* does sound interesting, but hard to say how useful it would be considering how much speeds can vary, especially with something like public transport network, which means anything between walking speed and high speed train."}}