AbstractAutonomous vehicle storage and retrieval systems have greatly increased in popularity in the last decade. In such a system, at each tier multiple roaming vehicles transport totes between the storage locations and the lifts. However, this may lead to vehicle interference. We study in which order and by which vehicle the storage and retrieval requests should be executed to minimize the makespan, without vehicle interference. The optimal storage locations for incoming totes are also determined. A blocking mitigation protocol is proposed to address vehicle interference. We propose a two‐phase matheuristic, where in the first phase, the tier is divided into zones, with each zone assigned its own vehicle. The second phase focuses on reassigning requests between adjacent vehicles to obtain improved solutions. The models proposed in both phases are solved to optimality in polynomial time and pseudo‐polynomial time, respectively. Computational experiments show that the matheuristic produces high‐quality solutions within a few seconds, even for large‐sized instances, making it suitable for real‐time decisions. Compared to methods commonly used in practice, our matheuristic can reduce the makespan by up to 15%. Our results show that making integrated decisions that combine storage assignment and request scheduling, is more beneficial than sequential optimization in terms of throughput performance, space utilization and overall system cost. We also find that increasing the number of vehicles has a diminishing return effect on the makespan. Another finding is that the system with a large number of short storage aisles leads to higher throughput capacity than that with a small number of long storage aisles.