A Dispatching Algorithm with Application to Fleets of Shared Autonomous Vehicles

Abstract

Fleets of shared autonomous vehicles have been predicted to dominate the transport sector within a near future. For this to work efficiently—including the handling of spontaneous requests—the associated routing problems need to be modelled dynamically and solved efficiently. We formulate and model the problem of routing a fleet of shared autonomous vehicles over a period of time. For each vehicle and each moment in time, it must be decided which customers to serve and which routes to take. The resulting model is solved using a rolling horizon optimisation methodology together with an insertion heuristic for new requests. The optimisation problems resulting from the rolling horizon methodology are solved using column generation, where the subproblems, being elementary shortest path problems with side constraints, are solved using both a local-search heuristic and a dynamic programming algorithm. Our computational experiments show that real-world sized problem instances can be solved to near-optimality within a reasonable computing time.