DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2018.25

Fleet Management for Autonomous Vehicles Using Multicommodity Coupled Flows in Time-Expanded Networks

Authors: Sahar Bsaybes, Alain Quilliot, and Annegret K. Wagler

Published in: LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018)

Abstract

VIPAFLEET is a framework to develop models and algorithms for managing a fleet of Individual Public Autonomous Vehicles (VIPA). We consider a homogeneous fleet of such vehicles distributed at specified stations in a closed site to supply internal transportation, where the vehicles can be used in different modes of circulation (tram mode, elevator mode, taxi mode). We treat in this paper a variant of the Online Pickup-and-Delivery Problem related to the taxi mode by means of multicommodity coupled flows in a time-expanded network and propose a corresponding integer linear programming formulation. This enables us to compute optimal offline solutions. However, to apply the well-known meta-strategy Replan to the online situation by solving a sequence of offline subproblems, the computation times turned out to be too long, so that we devise a heuristic approach h-Replan based on the flow formulation. Finally, we evaluate the performance of h-Replan in comparison with the optimal offline solution, both in terms of competitive analysis and computational experiments, showing that h-Replan computes reasonable solutions, so that it suits for the online situation.

Cite as

Sahar Bsaybes, Alain Quilliot, and Annegret K. Wagler. Fleet Management for Autonomous Vehicles Using Multicommodity Coupled Flows in Time-Expanded Networks. In 17th International Symposium on Experimental Algorithms (SEA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 103, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bsaybes_et_al:LIPIcs.SEA.2018.25,
  author =	{Bsaybes, Sahar and Quilliot, Alain and Wagler, Annegret K.},
  title =	{{Fleet Management for Autonomous Vehicles Using Multicommodity Coupled Flows in Time-Expanded Networks}},
  booktitle =	{17th International Symposium on Experimental Algorithms (SEA 2018)},
  pages =	{25:1--25:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-070-5},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{103},
  editor =	{D'Angelo, Gianlorenzo},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.25},
  URN =		{urn:nbn:de:0030-drops-89600},
  doi =		{10.4230/LIPIcs.SEA.2018.25},
  annote =	{Keywords: fleet management, offline and online pickup and delivery problem, multicommodity flows}
}

Search Results

Documents authored by Bsaybes, Sahar

Fleet Management for Autonomous Vehicles Using Multicommodity Coupled Flows in Time-Expanded Networks

Abstract

Cite as

Thanks for your feedback!

Could not send message