Algorithm Finds Best Routes for One-Way Car Sharing

Courtesy of Christine Daniloff/MIT

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 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.

Read more . . .