The automated valet parking problem for parking garage service provision

Abstract Automated valet parking is a use case for autonomous driving. It allows customers to leave their vehicles at the entrance of a parking garage. The vehicles then independently steer to a parking space. Besides increasing comfort, automated valet parking also enables parking garage operators to provide additional services, such as charging an electric vehicle, to which the vehicle can be autonomously routed. We formulate automated valet parking service provision as a scheduling problem and propose solution methods that focus on runtime and quality of results. The results show that the proposed optimization approach is capable of slightly outperforming heuristic benchmarks in many scenarios. However, we also find that the First-Come-First-Served and Earliest-Due-Date-First heuristics are often satisfying scheduling approaches. In addition, the potential of optimizing automated valet parking service provision is compared to traditional parking garages, showing at least a 46.4% increase in charging and other services scheduled.