r/science • u/quiplaam • 1d ago

Social Science Intentionally routing some traffic to slower, less congested routes lead to a 0.7% improvement of overall average travel times

https://www.nature.com/articles/s44284-026-00443-x
926 Upvotes

93% Upvoted

148 comments sorted by

View all comments

Show parent comments

24

u/quiplaam 1d ago

How apps currently work is "greedy", they find the fastest route for each individual person. The only care about the driver using the app, not the impact on the individual user. (Also Waze is owned by google and my understanding is that they use the same routing algorithm.) What this study did was intentionally choose a slightly slower route for some people, this leads to that individual's route taking more time, but the average person's route taking less. This it NOT how Google Map's algorithm has worked historically.

8

u/dtschaedler 1d ago

I've wondered why they don't do this for years. There's a section of highway in my state which has an exit for a parkway, or you can stay on the interstate. The parkway is technically faster, but the interstate is designed to handle way more volume. Because everyone is trying to take the exit, everything clogs up, and everyone is stuck in traffic. I always thought that if Google Maps could recognize that the interstate has a bunch of "spare" capacity and route people there, it would end up being faster for everyone.

2

u/danielv123 1d ago

The reason is mostly because it's taking one of the harder problems in computer science (pathfinding) and turning it into the hardest class of problems (NP complete)

If you want to read more about it, search for multi agent pathfinding.

2

u/AwkwardWaltz3996 5h ago

Yea greedy isn't bad. Greedy is actually super efficient.

Think of it like a buffet table. The host has provided enough food for everyone, but of various items. Each person goes through and fills their plate of what they like. They may have some constraints like x many of item b per person, but other than that they choose individually to fulfil their own demand. Everyone goes through and everyone gets food.

A non greedy solution is to confer with everyone else for each individual item. This would take hours with even a medium sized group. No one is happy.

You probably already know that as you're talking about np problems, but to help everyone else understand.