1 Search Results for "Killijian, Marc-Olivier"

Document
DOI: 10.4230/OASIcs.ATMOS.2013.150
Carpooling: the 2 Synchronization Points Shortest Paths Problem

Authors: Arthur Bit-Monnot, Christian Artigues, Marie-José Huguet, and Marc-Olivier Killijian

Published in: OASIcs, Volume 33, 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2013)

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.
Cite as

Arthur Bit-Monnot, Christian Artigues, Marie-José Huguet, and Marc-Olivier Killijian. Carpooling: the 2 Synchronization Points Shortest Paths Problem. In 13th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 33, pp. 150-163, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{bitmonnot_et_al:OASIcs.ATMOS.2013.150,
  author =	{Bit-Monnot, Arthur and Artigues, Christian and Huguet, Marie-Jos\'{e} and Killijian, Marc-Olivier},
  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 =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-939897-58-3},
  ISSN =	{2190-6807},
  year =	{2013},
  volume =	{33},
  editor =	{Frigioni, Daniele and Stiller, Sebastian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2013.150},
  URN =		{urn:nbn:de:0030-drops-42517},
  doi =		{10.4230/OASIcs.ATMOS.2013.150},
  annote =	{Keywords: Dynamic Carpooling, Shortest Path Problem, Synchronized Paths}
}
  • Refine by Author
  • 1 Artigues, Christian
  • 1 Bit-Monnot, Arthur
  • 1 Huguet, Marie-José
  • 1 Killijian, Marc-Olivier

  • Refine by Classification

  • Refine by Keyword
  • 1 Dynamic Carpooling
  • 1 Shortest Path Problem
  • 1 Synchronized Paths

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2013

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact