Effective and Efficient Fleet Dispatching Strategies for Dynamically Matching AVs to Travelers in Large-scale Transportation Systems

This paper addresses the problem of dynamically matching automated vehicles (AVs) to open traveler requests in a large-scale automated-mobility-on-demand (AMOD) simulation framework. While optimization-based matching strategies based on the linear assignment problem formulation significantly outperform simple heuristic strategies (e.g. nearest neighbor), the scalability of the assignment problem limits its applicability to large problem instances. This study proposes a fleet dispatching strategy to dynamically assign AVs to travelers that involves the assignment problem formulation but restricts the decision space to reduce computational time. First, we significantly trim the decision space via only considering the k-closest open requests around each idle vehicle or k-closest idle vehicles around each open request. Second, we only calculate point-to-point shortest paths for vehicles and travelers that are close in spatial proximity. For vehicles and travelers that are not close in proximity, we use zone-to-zone travel time estimates. This study embeds the proposed AV fleet dispatching strategy within Polaris-an agent-based transportation simulation modeling framework. Within Polaris, the restricted fleet dispatching strategy proposed in this significantly outperforms (i) existing large-scale strategies in terms of fleet performance and (ii) the unrestricted assignment problem strategy in terms of computational performance.