3 ms·
I think "created an algorithm" is probably overselling it a bit. Clearly they already had a route planner, didn't they just modify it to add extra cost to a le
by gjem97 10y ago
I think "created an algorithm" is probably overselling it a bit. Clearly they already had a route planner, didn't they just modify it to add extra cost to a left turn?
- deleted 10y ago[deleted]
- lorenzhs 10y agoIncorporating turn costs into route planning is actually not that easy! For one it increases the amount of data you need (street layout, type of intersection, etc) and a lookup to add the appropriate penalty. But more importantly, it doesn't play well with many speed-up techniques. Two papers on the subject, applying turn costs to the two most popular speed-up techniques (I don't know if UPS uses either of these, though): https://algo2.iti.kit.edu/download/turn_ch.pdf https://algo2.iti.kit.edu/download/turn_ch.pdf http://i11www.iti.uni-karlsruhe.de/extra/publications/dgpw-crp-11.pdf http://i11www.iti.uni-karlsruhe.de/extra/publications/dgpw-c... The first author of the first paper now works at Google, and the authors of the second paper used to work at Microsoft Research and now are at Apple and Amazon. Make of that what you will :)