Vehicle routing for shared autonomous electric vehicles considering passengers’ uncertain waiting time tolerance and acceptable stopover

Abstract

The ridesharing system effectively allocates limited vehicle resources by organizing passengers with similar itineraries to share seats of the same vehicle, thereby reducing vehicle miles traveled and the number of required vehicles. Shared autonomous electric vehicles (SAEVs), which apply autonomous electric vehicles to ridesharing systems, have attracted rising attention from both academia and industry, thanks to their high fleet efficiency, flexible mobility, and low energy consumption. This study investigates the vehicle routing problem of SAEVs considering passengers’ uncertain waiting time tolerance (WTT) and acceptable stopovers. Specifically, a passenger is assumed to have an uncertain WTT for vehicle pick-up delays and a pre-specified number of acceptable stopovers during the entire trip. The vehicle routes of SAEVs are optimized to serve a set of pre-known passengers so that the profit of SAEV operators are maximized. To solve this problem, we first develop a robust mixed-integer program (RMIP) that explicitly formulates the number of stopovers during passenger trips and all possible realizations of passengers’ uncertain WTT. The intractable constraints associated with the uncertain WTT in RMIP are then addressed using robust optimization techniques. Since the resultant model cannot be easily solved by available solvers, we thus further develop a formulation-based two-layer heuristic algorithm by exploiting decomposable model structures to efficiently find good-quality solutions. A case study using real-life ridesharing data of Chengdu, China demonstrates the efficacy of the proposed model and the heuristic algorithm. We also analyze the impact of stopovers and fleet size on profits and the optimal solution and report practical managerial insights.