License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/OASIcs.ATMOS.2013.150
URN: urn:nbn:de:0030-drops-42517
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2013/4251/
Go to the corresponding OASIcs Volume Portal

Bit-Monnot, Arthur ; Artigues, Christian ; Huguet, Marie-José ; Killijian, Marc-Olivier

Carpooling: the 2 Synchronization Points Shortest Paths Problem

pdf-format:
13.pdf (0.5 MB)

Abstract

Carpooling is an appropriate solution to address traffic congestion and to reduce the ecological footprint of the car use. In this paper, we address 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). We show that the 2SPSPP has a polynomial worst-case complexity. However, despite this polynomial complexity, one needs efficient algorithms to solve it in realistic transportation networks.
We focus on efficient computation of optimal itineraries for solving 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 restriction areas for reasonable pick-up and drop-off points and use them to guide the algorithms using heuristics based on landmarks. Experiments are conducted on real transportation networks. The results show the efficiency of the proposed algorithms and the interest of restriction areas for pick-up or drop-off points in terms of CPU time, in addition to its application interest.

BibTeX - Entry

@InProceedings{bitmonnot_et_al:OASIcs:2013:4251,
  author =	{Arthur Bit-Monnot and Christian Artigues and Marie-Jos{\'e} Huguet and Marc-Olivier Killijian},
  title =	{{Carpooling: the 2 Synchronization Points Shortest Paths Problem}},
  booktitle =	{13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems},
  pages =	{150--163},
  series =	{OpenAccess Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-58-3},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{33},
  editor =	{Daniele Frigioni and Sebastian Stiller},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2013/4251},
  URN =		{urn:nbn:de:0030-drops-42517},
  doi =		{10.4230/OASIcs.ATMOS.2013.150},
  annote =	{Keywords: Dynamic Carpooling, Shortest Path Problem, Synchronized Paths}
}

Keywords: Dynamic Carpooling, Shortest Path Problem, Synchronized Paths
Collection: 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems
Issue Date: 2013
Date of publication: 05.09.2013

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI