Vehicle Routing for Shared Autonomous Electric Vehicles Considering Passengers’ Uncertain Waiting Time Tolerance and Acceptable Stopover

The ridesharing system effectively allocates limited vehicle resources by organizingpassengers with similar itineraries to share seats of the same vehicle, thereby reducingvehicle miles traveled and the number of required vehicles. Shared autonomouselectric vehicles (SAEVs), which apply autonomous electric vehicles to ridesharingsystems, have attracted rising attention from both academia and industry, thanks totheir high fleet efficiency, flexible mobility, and low energy consumption. This studyinvestigates the vehicle routing problem of SAEVs considering passengers’ uncertainwaiting time tolerance (WTT) and acceptable stopovers. Specifically, a passenger isassumed to have an uncertain WTT for vehicle pick-up delays and a pre-specifiednumber of acceptable stopovers during the entire trip. The vehicle routes of SAEVs areoptimized to serve a set of pre-known passengers so that the profit of SAEV operatorsare 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 allpossible realizations of passengers’ uncertain WTT. The intractable constraintsassociated with the uncertain WTT in RMIP are then addressed using robustoptimization techniques. Since the resultant model cannot be easily solved by availablesolvers, we thus further develop a formulation-based two-layer heuristic algorithm byexploiting decomposable model structures to efficiently find good-quality solutions. Acase study using real-life ridesharing data of Chengdu, China demonstrates theefficacy of the proposed model and the heuristic algorithm. We also analyze the impactof stopovers and fleet size on profits and the optimal solution and report practicalmanagerial insights.