Optimization of Shared Autonomous Vehicles Routing Problem: From the View of Parking

Shared autonomous vehicles (SAVs) have great potential for achieving beneficial changes to the society. Although recent studies have explored the traffic safety, economic benefits and environmental impact, parking decisions of SAVs is rarely considered. SAVs need to park to avoid cruising during the interval between services. Appropriate parking decisions can contribute to reduce the vehicle kilometers traveled (VKT). This study synergistically considers routing and parking of SAVs for system optimization. Since the problem is NP-hard, we develop a variable neighborhood search (VNS) heuristic to solve it. The heuristic aims to minimize the VKT, the number of SAVs and the parking cost by systematic changes of neighborhood. A series of experiments based on the Anaheim network prove the high solving efficiency and quality of the heuristic. Results also indicate that the marginal cost of the system decreases with the increase in travel demand and the VKT increases with the increase in parking fees.