Title: Vehicle Sharing Systems: Analysis, modeling, simulation, optimization.

The number of cities equipped with Vehicle Sharing Systems (VSS, BSS, VLS) is increasing rapidly. VSS are viewed as a promising way to reduce the usage of personal car and improve the quality of life by reducing traffic, noise and air pollution. Despite the growing number of VSS, they are still poorly understood and often suffer from congestion problems (absence of a vehicle or of a parking spot at the destination).

The goal of the internship will be to contribute to the understanding of VSS by developing computer and mathematical methods. For completeness, we describe four research directions bellow. According to his preferences and skill, the student will choose one of the them during the internship. The others can serve as a basis for a subsequent PhD proposal.

1. Benchmark the historical data of various real VSS, and develop visualization tools, to help humans deal directly with such data.
2. Data mining, in order to estimate the underlying intensity of user flow depending on the stations, time, day, season, weather.
3. Modelling and simulating so as to have a solid basis for investigating the behavior of future systems and optimizing them.
4. Mathematical analysis of models of VSS, so as to have an analytic understanding of how VSS behave and help optimizing them.

1/ Data gathering and visualization.

Thanks to open-data trends, many operators of bike sharing systems make available huge quantity of data regarding the operation of their systems. Depending on the operator and the city, this files contain historical data of the state of the stations, the trips performed by users, or some maintenance or regulation operations. However, there is no uniformity regarding the type of the information and their format. The goal of this part would be to:

• contribute to an inventory of existing databases and to the collection of data that are available only in real time.
• define a detailed universal data format that can contain all these information.
• define compressed (with or without loss) formats.
• develop open-source tools that can convert various existing data sets, detect and correct their incoherence and translate them into the universal formats.
• develop an open source tool to infer some missing information from the available ones.
• develop an open-source tool that outputs performance indicators and visualizations from data.

Keywords: Format standardization, error correction, compression, spacio-temporal visualization.

2/ Data mining and analysis of existing systems.

Vehicle sharing systems are hard to visualize. They are ruled by spacio-temporal patterns, but external factors creates a high degree of randomness in the systems; and they have a very large scale (more than 1000 stations and 20000 bikes for Velib' in Paris). If one counts the transit for each pair of stations, depending on the time period in the day, most of the average values will be zeros, and almost all of them will be tiny integers. The relative variance of such average values is far too high. Moreover, we also would like to find hidden structure in the historical data, so as to shed light on the (universal ?) joint impact of distance, altitude variation or weather conditions on the transit. Hence, there is a need of aggregation methods, like clustering techniques, in order to analyze such systems. The goal of this part would be to adapt "continuous clustering" techniques, such as non-negative matrix factorization (NMF) or latent Dirichlet Allocation (LDA), so as to help factoring out the temporal, spatial and environmental (weather) dependencies of such system. More generally, a key issue is to develop statistical methods to deal with the sparsity of data that are assumed to be statistically ruled by known parameters, but in an unknown way.

Keywords: Temporal series, dynamic graphs, clustering, statistics.

3/ Modeling and simulation

Visualization of existing data-set can be used to understand how bad or good a system works. However, they are not sufficient to qualitatively evaluate the change in performance when a parameter of the system (such as the number of vehicles or a reservation policy) is modified. A natural way to do so is to build a model and a simulator that implements this model. The goal of this part is to contribute to the development of a generic discrete-event simulator: VSS-SimulatorG. It is modular, so as to represent the behavior of a user, reservation rules, re-balancing strategies. It has an interface to feed the simulator with data from a real city. The simulator outputs basic performance indicators and also produces a trace of computation in a format compatible with the one of first research direction 1, and can hence be visualized with a generic tool designed for real historical data.

Keywords: Modular modelling, discrete-event simulation, performance indicators.

4/ Stochastic models, approximations and optimization

Vehicles sharing systems are naturally represented as stochastic systems, more specifically, queuing networks. Large-scale stochastic systems of these types are a challenge to evaluate without simulation. The goal of this part is to study which approximation techniques are most useful for studying vehicles sharing systems represented by queuing networks. Mathematically, we seek proofs of the validity of such approximations under certain assumptions, as well as bounds on their errors in general. Numerically, we also use such approximations to design heuristic rules for operational optimization problems, such as fleet sizing, station location, pricing and incentives or truck regulation. The efficiency of such heuristics is usually evaluated using simulations (see section on modeling and simulation). We also try to design simple intuitive heuristics to compare them with those derived by mathematical approximations, since it is not suitable to increase to complexity of a system without improving slightly its performances.

Keywords: Queuing networks, fluid and mean field approximations, linear and convex programming, simple heuristics.

Location and supervisor

The intern will be hosted at Inria Grenoble or GSCOP and supervised by Nicolas Gast and Vincent Jost (CNRS)

References:

• Data visualization and analysis of existing systems
• Vehicle Sharing System Pricing Regulation: A Fluid Approximation. Ariel Waserhole and Vincent Jost.
• Incentives and Redistribution in Homogeneous Bike-Sharing Systems with Stations of Finite Capacity. Christine Fricker and Nicolas Gast
• A class of mean field interaction models for computer and communication systems. M. Benaïm, J.-Y. Le Boudec.