2026-08-17T14:18:34Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8960 2024-03-06T10:42:57Z ddc:004 open_access

Fleet Management for Autonomous Vehicles Using Multicommodity Coupled Flows in Time-Expanded Networks Bsaybes, Sahar Quilliot, Alain Wagler, Annegret K. fleet management offline and online pickup and delivery problem multicommodity flows 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sahar Bsaybes and Alain Quilliot and Annegret K. Wagler 2018 Is Part Of LIPIcs, Volume 103, 17th International Symposium on Experimental Algorithms (SEA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2018.25 urn:nbn:de:0030-drops-89600 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2018.25 eng https://creativecommons.org/licenses/by/3.0/legalcode