License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.SEA.2018.25
URN: urn:nbn:de:0030-drops-89600
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/8960/
Go to the corresponding LIPIcs Volume Portal

Bsaybes, Sahar ; Quilliot, Alain ; Wagler, Annegret K.

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

pdf-format:
LIPIcs-SEA-2018-25.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{bsaybes_et_al:LIPIcs:2018:8960,
  author =	{Sahar Bsaybes and Alain Quilliot and Annegret K. Wagler},
  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 =	{Gianlorenzo D'Angelo},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/8960},
  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}
}

Keywords: fleet management, offline and online pickup and delivery problem, multicommodity flows
Collection: 17th International Symposium on Experimental Algorithms (SEA 2018)
Issue Date: 2018
Date of publication: 19.06.2018

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