New algorithm finds best routes for one-way car sharing

June 24, 2013 by Jennifer Chu

Need a car, but don't want the hassle of owning one? Today, there are many services to help you get around this jam, including traditional car-rental companies, taxis, and car-sharing programs such as Zipcar and Greenwheels. But what if you want to drive a car without the inconvenience of having to return it to your starting point?

That's where a concept called "mobility on demand" comes in. Essentially a one-way vehicle-sharing system, mobility on demand typically consists of a fleet of vehicles, parked in a network of stations, and available for short-term rentals. A driver can pick up a vehicle, and drop it off later at a station closest to his or her destination. Mobility on demand has gained traction in recent years as a convenient and sustainable form of transportation, primarily with bicycle-sharing programs like Hubway in Boston.

But adapting the concept to has been more of a challenge. While there are a few one-way programs on the road today—notably, Daimler's Car2Go and BMW's DriveNow—such programs bring significant logistical issues.

Chief among these, says Emilio Frazzoli, an associate professor of aeronautics and astronautics at MIT, is the issue of imbalance: During a typical day, the number of cars throughout a network shifts toward certain destinations. (Think of drivers commuting each morning from the suburbs to downtown offices.) As a result, these locations see a glut of cars, in turn depleting fleets at other stations.

Programs like Car2Go address this issue by employing drivers to rebalance the fleet, moving cars to high-demand locations. But as Frazzoli has found, the rebalancing drivers themselves then become unbalanced. What's more, such rebalancing trips do not generate revenue, yet are an expense to the operator.

To rebalance the system, Frazzoli and his colleagues have developed a vehicle-routing algorithm that adds another component to the scenario: a driver who shuttles a car back to a station, but with a customer, much like a taxi service. The group's algorithm determines the most efficient means of balancing taxi trips and shuttle trips while minimizing wasted trips.

Finally, to maintain stability within the system, and ensure that every customer has access to a car with minimal wait time, the researchers determined the most efficient number of vehicles and rebalancing drivers for a mobility-on-demand system. Their simulations indicate that at least one shuttling driver is necessary for every three vehicles in the fleet to ensure vehicle availability for the customers.

"What you need is some way to make the system self-balance," says Frazzoli, who is a lead investigator in the Singapore-MIT Alliance for Research and Technology (SMART). "You need a car to be taken back to a place where customers are waiting. Car-sharing companies that are not ensuring high availability of vehicles may be using too few human drivers, or not rebalancing the vehicles efficiently."

The group, which includes Daniela Rus, professor of computer science and engineering and director of MIT's Computer Science and Artificial Intelligence Laboratory, as well as researchers from the University of Waterloo, Stanford University and Boston University, has co-authored a paper, which was presented this month at the annual conference of the American Automatic Control Council, in Washington.

Driving with others

In working out a rebalancing strategy, the researchers simulated an idealized mobility-on-demand system. They randomly placed 10 to 200 stations throughout a grid, and assumed that the paths between stations were straight.

To develop the vehicle-routing algorithm, the group factored in a range of variables: the number of customers, drivers and vehicles at a given station; the rate at which customers arrive at and depart from a station; travel time between stations; and the rate of shuttling vehicles and drivers between stations. The group determined the fraction of customers who prefer to drive themselves, versus those willing to use a taxi service—an alternative that would allow a shuttling driver to drive a car back to a given station while earning a fare from a customer.

Taking into account all these variables, the researchers devised an algorithm that determines how the number of vehicles, customers and drivers evolve at each station. The group then ran simulations with the algorithm, programming in random arrival rates for each station, and random destination probabilities. They ran simulations of networks and observed the resulting flow of traffic.

From the simulations, Frazzoli and his team found that the minimum number of rebalancing drivers needed to keep a system balanced is equal to one-third the number of vehicles in the system. That fraction is reduced to one-fifth if several drivers are allowed to ride back to a station with a customer.

The issue of rebalancing in a transportation system is an old one, says Alexandre Bayen, associate professor of systems engineering at the University of California at Berkeley.

"Fleets have always had problems—for example, planes fly back empty sometimes, and off-service buses often drive without passengers to rebalance. But there is a new aspect to it, which is car sharing, which will take off at very large scale," says Bayen, who was not involved in the research. "The biggest contribution of this paper is to deal with the new aspects of this problem: the system is distributed, demand is unknown and dynamic, and vehicle-to-passenger ratios are different than for other fleets. I think it's really ingenious, because it's a complex problem."

'A tangible benefit to people'

Frazzoli sees such a system—a combination of a car-share, shuttle and taxi service—as a promising, sustainable transportation alternative.

"The idea we're pursuing is, 'What if we had a system where there are fewer cars that are actually used most of the time?' Instead of everybody having one car and using it 5 percent of the time, what if everybody used shared cars, and these shared cars are used 95 percent of the time?" Frazzoli posits. "That would have all the benefits of having your own car, and all the sustainability of public transportation."

In the future, Frazzoli says mobility-on-demand systems may be even more efficient with the development of autonomous vehicles: Cars may one day be able to drive themselves back to where they're needed. Issues of safety aside, the challenge, he points out, is cost: Is the price of a self-driving car less than what it would cost to hire human drivers? According to the group's results, an autonomous car would have to cost less than it would cost to employ three drivers over the lifetime of the vehicle—essentially the minimum cost to keep a system in balance.

Going forward, Frazzoli is working on two fronts: exploring more scenarios with the current algorithm, including simulations in which popular destinations change throughout the day, and finding ways to reduce the cost of self-driving cars.

"For me, autonomous cars go hand in hand with car-sharing," Frazzoli says. "It would save money and it would decrease the cost of using a vehicle, and allow you to reduce congestion. So this can have a tangible benefit to people, especially those living in large cities."

Explore further: French electric car share program sets sights on Indy

Related Stories

Networked cars make traffic safer and more efficient

June 20, 2013

Vehicles and infrastructures exchanging information with one another and notifying drivers about dangers and traffic situations make traffic safer and more efficient. This has been proven by one of the biggest field tests ...

Explosive growth predicted for automotive electronics

May 31, 2013

The global market for advanced automotive electronics - everything from driver assistance programs to new kinds of visual displays - will jump to $240 billion by 2020, up more than 50 percent from 2010, according to a recent ...

Recommended for you

Making it easier to collaborate on code

October 26, 2016

Git is an open-source system with a polarizing reputation among programmers. It's a powerful tool to help developers track changes to code, but many view it as prohibitively difficult to use.

Dutch unveil giant vacuum to clean outside air

October 25, 2016

Dutch inventors Tuesday unveiled what they called the world's first giant outside air vacuum cleaner—a large purifying system intended to filter out toxic tiny particles from the atmosphere surrounding the machine.


Please sign in to add a comment. Registration is free, and takes less than a minute. Read more

Click here to reset your password.
Sign in to get notified via email when new comments are made.