Algorithm does real-time, city-wide ridesharing
Anyone who's ever been stuck in stop-and-go
traffic would be happy to tell you that congestion is a waste of time.
But the true scale of the waste is difficult to comprehend. It's
estimated that congestion costs the US one percent of its annual GDP, as
people waste otherwise productive hours and fuel sitting in their
vehicles, and that doesn't even consider all the pollution this traffic
creates.
Despite those numbers, most people wouldn't
choose to use options that cut congestion, like public transit or ride
sharing. In many cases, that's because these alternatives require giving
up some autonomy, as you can't necessarily go where you want whenever
you want.
A paper in this week's PNAS
suggests that doesn't have to be the case. Using a real-world database
of fully autonomous travel—a week's worth of New York City taxi
rides—the authors demonstrate an algorithm that can service travel needs
in real time with minimal waits for a ride. The result would be far
fewer cars on the road. Even with standard cabs, only a quarter of
today's taxi fleet would be required to service all the ride requests.
The work was done by a joint MIT/Cornell team,
who decided to take on what's essentially a massive computational
challenge. Figuring out how to ride share is more than just matching
passengers with vehicles. You want to match them with a vehicle that's
already nearby, meaning the wait for the ride is minimal. Then, other
passengers have to be added in a way that doesn't result in a
significant diversion from the first passenger's trip. Once a ride is
shared, there needs to be a smooth addition and subtraction of
passengers, such that the vehicle ends up empty as infrequently as
possible.
As the paper puts it, "A major challenge when
addressing this problem is the need to explore a very large decision
space, while computing solutions fast enough to provide users with the
experience of real-time booking and service."
The biggest part of that challenge is finding
the optimal solution within that entire decision space; algorithms often
get hung up on a local optimum or can't explore the entire space within
a reasonable amount of time. Fortunately, the authors recognized that
they don't need the global optimum. A reasonably good local optimum may
not be the most efficient, but it's good enough to get people in cars
quickly. A first round of trip assignments is done using what's called a
greedy algorithm, which simply starts with the longest trips first and
tries to minimize travel delays.
From there, the algorithm attempts
optimizations, but it's capable of producing an answer at any time if a
decision has to be made. In addition, it's possible to make some
optimizations like limiting the cars that are considered for servicing a
trip (to ones that start off within a set distance of the passenger,
for example). That saves considerable computational time.
In addition to the optimizations, the authors'
approach allows them to set limits on things like the waiting time and
the amount of additional time a given rider experiences in the car due
to other passenger's needs. It can also be adjusted to perform
optimizations for different vehicle sizes.
The authors find that, for low capacity
vehicles like existing taxis, it's possible to perform a full
optimization; larger vehicles (like small vans) force the use of
algorithms that are only likely to produce a fully optimized trip
schedule. In either case, if the total travel delay per passenger is
capped at five minutes, the algorithms can always produce a result in
less than 30 seconds.
And now for reality...
With the software in hand, the team then
turned to their real-world data: every single taxi trip taken during a
week in May of 2013. That's the time and location of every pick-up and
drop-off for each of the city's 13,586 taxis.
The authors suggest that using their system
can get a lot of these cabs off the roads. With a fleet similar to
today's four-seat vehicles, only 3,000 would be needed to serve 98
percent of the ride requests. Riders would experience a mean wait of 2.7
minutes (generally quicker than hailing a cab) and an in-ride delay of
2.3 minutes due to handling other passengers. Switching to vans with a
capacity of 10 passengers, similar numbers could be generated with just
2,000 vehicles.
As the capacity goes up, more passengers will
typically mean more travel delays. But these delays stay below 100
seconds, and they're partly offset by the fact that people tend to get
picked up faster. Each vehicle ends up traveling fewer miles than a
typical cab, which should cut down on maintenance to boot. Jamming into a
crowded van isn't anyone's idea of fun, but in most cases, these
vehicles aren't that crowded. Even if you cut the number of vans down to
1,000 and checked during the periods of peak demand, only 40 percent
would be more than half full.
Of course, cabs are only one of the sources of
congestion in a typical city, so this wouldn't be a cure-all for
traffic—assuming most riders were even interested in using it. The same
system would probably work for on-demand car pooling, which would add
significantly to the decreased number of cabs. And it's hard not to
notice the overlap between a system like this and Elon Musk's vision for the future of Tesla vehicles, which sees them autonomously serving passengers when not in use by their owners.
No comments