Scalable routing in Multi-Modal transportation networks – MultiMod

The scientific and technical activities of MultiMod are organized around 4 complementary scientific work-packages, WP1-4.

WP1: Design of scalable algorithms for the multimodal engine.
Address the scalability of algorithms for computing itineraries in road or PT networks. These algorithms shall offer good tradeoff between conflicting objectives: offer short query-time (usually needing long pre-computation), handle real-time events and take user preferences into account. Consider the computation of robust and alternative itineraries to ease rerouting. Investigate the management of walking connections to speed up multimodal itinerary computation.

WP2: Solutions for combining carpooling with PT network.
Address the computation of mix itineraries combining carpooling with PT by designing faster algorithms and providing more accurate solutions. Provide tradeoff solutions maximizing the satisfaction of users (drivers and travelers). To this end, consider various car-path solutions from short detour to meeting-point, to optimal routes passing by specified meeting-points (constrained shortest path). Propose methods for efficiently filtering carpooling offers of interest for a traveller to scale with the growth of the system. Investigate how to optimize the filling of vehicles without penalizing the driver with excessive detours or delays. A difficult question here is how to cope with the volatility of solutions over time.

WP3: Mobility companion. Implement the algorithms designed in WP1-2 in a platform integrating carpooling and PT network.

WP4: Assessments. Construct realistic benchmark instances enabling to evaluate the algorithms in a large variety of situations and to reproduce experiments. Define appropriate metrics to measure the performances of algorithms with respect query time, memory footprint, quality of solutions, etc. Provide feedback to other WPs.

The results at T+18 concern:
1) Integration of new connectivity constraints to speed up the resolution of the traveling salesman problem (TSP). This problem is central in many variants of vehicle routing problems.
2) Design of a real-time simulator for on-demand transport (TAD) of persons. The aim is to optimize the vehicle journey while maximizing user satisfaction.
3) Optimization of the Connexion Scan algorithm (CSA) for fast route calculation in PT networks. Work on a better handling of real time in the algorithm.
4) Study of the complexity of algorithms for computing alternate paths and k shortests dissimilar paths. We are now working on the design of new algorithms to solve these problems while including specific constraints (e.g., electric bike versus standard bike).
5) Design of methods based on «Embarassingly Parallel Search« for multi-criteria optimization. Preliminary results on TSP.
6) Construction of an instance benchmark to test the algorithms.

In the next period, we will continue the ongoing work on algorithm design, and intensify algorithm integration and experimentation. We will also increase our efforts on WP2.

Nicolas Isoart, Jean-Charles Régin. Introduction de contraintes structurelles pour la résolution du problème du voyageur de commerce. JFPC, Jun 2019, Albi, France hal.archives-ouvertes.fr/hal-02160046

Duc-Minh Phan, Laurent Viennot. Fast Public Transit Routing with Unrestricted Walking through Hub Labeling. Special Event on Analysis of Experimental Algorithms (SEA2), Jun 2019, Kalamata, Greece
hal.inria.fr/hal-02161283

Nicolas Isoart, Jean-Charles Régin. An adaptive CP method for TSP solving. [Research Report] Université Côte d’Azur. 2019
hal.archives-ouvertes.fr/hal-02165374

The MultiMod project aims at enhancing the mobility of citizens in urban areas by providing them, through a unique interface enabling to express their preferences, the most convenient transportation means to reach their destinations. Indeed, the increasing involvement of actors and authorities in the deployment of more responsible and cost-effective logistics and the progress made in the field of digital technology have made possible to create synergies in the creation of innovative services for improving the mobility in cities. However, users are faced with a number of solutions that coexist at different scales, providing complementary information for the mobility of users, but that make very complex to find the most convenient itinerary at a given time for a specific user. In this context, MultiMod aims at improving the mobility of citizens in urban areas by proposing contextualized services, linking users, to facilitate multimodal transport by combining, with flexibility, all available modes (planned/dynamic carpooling, public transport (PT), car-sharing, bicycle, etc.).

We consider the use of carpooling in metropolitan areas, and so for short journeys. Such usage enables itineraries that are not possible with PT, allows for opening up areas with low PT coverage by bringing users near PT (last miles), and for faster travel-time when existing PT itineraries are too complex or with too low frequency (e.g., one bus per hour). In this context, the application must help the driver and the passenger as much as possible. In particular, the application must propose the meeting-point, indicate the driver the detour duration, and indicate the passenger how to reach this meeting-point using PT. Here, the time taken by drivers and passengers to agree becomes a critical issue and so the application must provide all needed information to quickly take a decision (i.e., in one click).

In addition, the era of Smart City gathers many emerging concepts, driven by innovative technological players, which enables the exploitation of real-time data (e.g., delay of a bus, traffic jam) made available by the various actors (e.g., communities in the framework of Open Data projects, users via their mobile terminals, traffic supervision authorities). In the MultiMod project, we will use these rich sources of data to propose itineraries that are feasible at query-time. Our findings will enable the design of a mobility companion able not only to guide the user along her journey, including when and how to change of transportation mean, but also to propose itinerary changes when the current one exceeds a threshold delay. The main originality of this project is thus to address the problem of computing itineraries in large-scale networks combining PT, carpooling and real-time data, and to satisfy the preferences of users. We envision that the outcome of this project will significantly improve the daily life of citizens.

The targeted metropolitan area for validating our solutions is Ile-de-France. Indeed, Instant-System is currently developing the new application “Vianavigo lab” which will replace the current “Vianavigo” application for the PT network of Ile-de-France. Our findings will therefore be tested at scale and eventually be integrated and deployed in production servers and mobile applications. The smaller networks of Bordeaux and Nice will be used to perform preliminary evaluations since Instant System already operates applications in these cities (Boogi Nice, Boogi Bordeaux).
An important remark is that new features and algorithms can contractually be deployed in production every 4 months, thus enabling Instant System to measure and challenge the results of the MultiMod project in continue. This is a chance for the project to maximize its impact.