Multiple Participant Routing


Carpooling is an appropriate solution to address traffic congestion and to reduce the ecological footprint of the car use. MuPaRo addresses an essential problem for providing dynamic carpooling: how to compute the shortest driver’s and passenger’s paths. Indeed, those two paths are synchronized in the sense that they have a common subpath between two points: the location where the passenger is picked up and the one where he is dropped off the car. The passenger path may include time-dependent public transportation parts before or after the common subpath. This defines the 2 Synchronization Points Shortest Path Problem (2SPSPP) and focuses explicitly on the computation of optimal itineraries for the 2SPSPP, i.e. determining the (optimal) pick- up and drop-off points and the two synchronized paths that minimize the total traveling time. We also define restrictions areas for reasonable pick-up and drop-off points and use them to guide the algorithms using heuristics based on landmarks.

The ATMOS 2013 paper presents this work.

The software git is available here : (but for now you have to request us to grant you access)

Carpooling : the 2 Synchronization Points Shortest Paths Problem