Using algorithms to improve car-sharing systems
For his PhD thesis at EPFL, Martin Repoux examined solutions for improving how car-sharing systems manage their fleets and parking places. The models he created, particularly for a car-sharing provider in Grenoble, France, helped boost the service levels and increase profitability.
Over the past two decades, car-sharing has become a popular alternative to individual car ownership in both France and Switzerland. Many city dwellers are reconsidering the benefits of owning a car due to a heightened awareness of environmental issues, the difficulty of driving and parking in cities, and improved public transportation. As a result, car-sharing services are gaining in popularity in large cities.
However, car-sharing has yet to become a permanent part of the urban transportation landscape. This is something that the failed Autolib' electric car-sharing program, which ran for eight years in the Greater Paris area, made clear. Autolib' never generated decent profits and was finally scrapped in 2018. To be appealing, a car-sharing system must make vehicles easily available, which requires a dense network of parking locations. It also needs to be flexible, since users value easy booking processes and vehicles that are ready-to-go. In the case of free-floating rentals – i.e., where drivers are not required to return a car to the point of departure – the issue also arises of whether a parking place will be available at the destination.
Car manufacturers and car-sharing providers are aware of such requirements and the need for shared systems, and are searching for efficient, cost-effective responses. Repoux, who completed his thesis at EPFL's Urban Transport Systems Laboratory, teamed up with several of these providers. “My thesis was structured around two major projects, both of which involved on-demand car-sharing systems that were closely linked to manufacturers seeking to attract users and make such systems sustainable,” says Repoux, whose public thesis defense was held on 11 February.
Simulating and predicting demand
A large part of Repoux's work was focused on the city of Grenoble, where he was approached by a car-sharing provider that was trying to increase its base of regular users. “We wanted to see what we could do with our system’s operational design, which lets users book a vehicle's point of departure as well as its destination. The idea was to use historical data on car-sharing usage proactively – rather than reactively, which is the usual practice – and thus predict vehicles' positions and whether they needed to be repositioned.”
Using historical data, I generated diagrams of the expected number of empty parking places and vehicles at charging stations
The goal was to ensure that vehicles and parking places would be available at all times in order to meet user demand. Repoux developed a Markovian representation for the state of a charging station: “Using historical data, I generated diagrams of the expected number of empty parking places and vehicles at charging stations at given points in the future. That let me determine the likelihood that a problematic state – or a state in which demand cannot be met – will occur. We tested our hypotheses both in the field and using simulations in order to calculate improvements in service rates and determine whether vehicle redistribution is worthwhile or whether the random nature of demand is a limiting factor.” As part of his research, Repoux used a simulator that he had developed for his Master's degree in civil engineering at EPFL, and updated it to compare various redistribution scenarios.
Repoux’s algorithmic models for optimizing redistribution indicate that, by charging the right fees, a car-sharing company can increase its revenue – even if it has to hire an employee to proactively move vehicles from one location to another. In his best-case scenario, 30% of the requests unmet by a purely reactive redistribution policy could be met by a proactive one. "Ideally, you would have all information about demand in advance, though this is impossible. Therefore, since you can't immediately fill all requests by teleporting vehicles, a 100% match rate is unattainable," Repoux wryly notes.
In the second part of his thesis, Repoux explores an idea for an innovative public transportation system called a Multi-Layered Personal Transit System. Such a system would enable users to travel in self-contained, driverless cabins from departure to destination, without having to change vehicles. The cabins would be arranged in convoys led by vehicles driven by transportation-system employees. “It would be somewhat like an urban, road-based railway, where cars can be detached at purpose-built stations and attached to other human-driven vehicles,” explains Repoux.
The advantage of this system, which is similar to the ULTra (Urban Light TRAnsit) self-driving pods at London's Heathrow Airport, is that it would already be compliant with urban traffic regulations, which do not yet cover driverless vehicles. In Repoux’s system, only the stations would require special infrastructure and safety features adapted to the cabins. Like car-sharing systems, his invention would offer an innovative alternative for improving public transportation in cities and reducing vehicle use, without requiring a complete overhaul of urban infrastructure.