Fleet management for autonomous vehicles using multicommodity coupled flows in time-expanded networks

International audienceVIPAFLEET 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 On-line 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 and to apply the well-known meta-strategy Replan to the online situation. As it turned out that Re-plan requires too long computation times, we devise a heuristic approach h-Replan based on the flow formulation. Finally, we evaluate the performance of Replan and h-Replan in comparison with the optimal offline solutions, both in terms of competitive analysis and computational experiments , showing that h-Replan computes reasonable solutions, so that it suits for the online situation