Dynamic vehicle dispatching for shared-and-autonomous-mobility services with adaptive request assignment

Abstract

This study investigates a real-time vehicle dispatching problem for shared-and-autonomous-mobility (SAM) services that allow multiple passengers to share a ride. The objective is to optimize the real-time decision-making of the operator, and develop an online efficient algorithm to maximize the profit while ensuring service quality. In particular, we formulate the dynamic system with a series of static subproblems and continually optimize the vehicle dispatching solutions at each decision time point. Each static subproblem is formulated as a mixed-integer programming (MIP) model considering the maximum number of ride-pooling strangers and passenger satisfaction constraints. To solve the subproblem, we develop a customized hybrid algorithm that integrates an adaptive request assignment (ARA) scheme into the large neighborhood search (LNS) heuristic framework. Particularly, this method decomposes the multi-vehicle problem into single-vehicle problems and LNS iteratively identifies the optimal routing solution for each SAV. If overall profit does not improve after a certain number of iterations, the ARA scheme is invoked to adaptively reassign passenger requests to different vehicles. Numerical experiments are conducted to demonstrate the effectiveness of the proposed solution method against the benchmark approach and to examine the benefits of the SAM service model and the effect of passengers’ flexibility time on system performance to derive management insights.