4 ms·
> eliminating left turns wherever possible after it found that drivers have to sit idly in the trucks while waiting to take the left turn to pass through traffi
by leereeves 10y ago
> eliminating left turns wherever possible after it found that drivers have to sit idly in the trucks while waiting to take the left turn to pass through traffic. So, it created an algorithm that eliminated left turns from drivers’ routes even if meant a longer journey.
Sounds reasonable.
> In 2005 ... the total distance covered by its 96,000 trucks was reduced by 747,000km. In 2011, ... the company had reduced distance travelled by trucks by 20.4 million miles. A recent report by The Independent says that the total reduction in distance travelled by UPS trucks now stands at 45.8 million miles.
But how does eliminating left turns even it means a longer journey reduce the total distance travelled?
Edit:
The Independent article referenced here explains:
> The efficiency of planning routes with its navigation software this way has even helped the firm cut the number of trucks it uses by 1,100, bringing down the company’s total distance travelled by 28.5m miles – despite the longer routes.
- pc86 10y agoIt won't always be longer, it just wasn't a deal breaker if it was.
- gjem97 10y agoI 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 :)
- snrplfth 10y agoIt also tends to reduce distance travelled because left turns are often done to get onto faster roads - if you right-turn it all the way, you're often on slower roads, so you're not going as fast, but you're saving actual travel distance.
- deleted 10y ago[deleted]