Routing optimization of shared autonomous electric vehicles under uncertain travel time and uncertain service time

The emerging autonomous electric vehicles have facilitated the implementation of the shared autonomous electric vehicle (SAEV) service. In real-life applications, the operations of SAEVs may be affected by various uncertain factors, such as uncertain travel time caused by traffic congestion and uncertain service time caused by unpredictable customer delay. It is essential to consider uncertain factors to design conservative and robust routes for SAEVs. In this paper, we study a routing optimization problem of SAEVs, where the charging schedules, uncertain travel time, and uncertain service time are considered. The objective of the problem is to minimize the total operational cost that consists of fixed cost and travel cost of SAEVs. A branch-and-price algorithm is developed to solve the problem. Specifically, a tailored label setting algorithm is introduced to identify the robust feasible routes with accessible charging schedules for the pricing subproblem. The proposed algorithm is tested on a set of generated instances. The computational results indicate that the proposed algorithm outperforms the commercial solver CPLEX in terms of both solution quality and computational time. Besides, based on the sensitivity analyses, we show the impact of the budgets of uncertainty, maximum deviations of uncertain parameters, battery capacity, fixed cost, and charging speed on the SAEV service. This work can also provide inspirations of both models and algorithms for many other application areas, such as urban logistics.