Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Limit graph search/crash when there is no connection #104

Closed
NopMap opened this issue Sep 4, 2013 · 1 comment
Closed

Limit graph search/crash when there is no connection #104

NopMap opened this issue Sep 4, 2013 · 1 comment
Assignees
Milestone

Comments

@NopMap
Copy link
Contributor

NopMap commented Sep 4, 2013

Implement an upper bound to the weight of partial solutions examined by the search algorithms. Solutions exceeding the upper bound are not expanded but discarded. Search is thus limited to a reasonable range.

The cutoff value is the longest acceptable detour for a vehicle multiplied with the worst possible weight assigned to an edge plus some tolerance.

@ghost ghost assigned NopMap Sep 4, 2013
@NopMap
Copy link
Contributor Author

NopMap commented Sep 5, 2013

Implementation complete locally for AStar and AStarBidirection. Cutoff will have to be adjusted according to use case. In my test case it is 100 times the direct distance between the points. This is a fairly safe value but in my test case reduces the calculation time from 38s to 4s.

I was unable to merge the EdgeExplorer changes from master to my branch, so I will make a pull request once I'm back on the master.

@karussell karussell added this to the 0.4 milestone May 9, 2014
@karussell karussell removed this from the 0.4 milestone Aug 18, 2014
@karussell karussell changed the title Avoid full graph search/crash when there is no connection Limit graph search/crash when there is no connection Jan 8, 2015
@karussell karussell added this to the 0.4 milestone Jan 20, 2015
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

2 participants