Communications of the ACM
Algorithm Finds Best Routes For One-Way Car Sharing
Credit: El blog de Moises Gonzalez
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, that are 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 passenger cars has been more of a challenge. While there are a few one-way car-sharing 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."
Sustainable System
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."
This research was supported by funding from Singapore's National Research Foundation and by the Office of Naval Research.
No entries found