This study investigates the potential of employing autonomous vehicles (AVs) for catering waste collection, aiming to enhance customer satisfaction and facilitate route learning for AVs. We formulate the problem as a coherent multi-trip vehicle routing problem, accounting for both arrival time consistency and route consistency. We develop an advanced column generation algorithm tailored for consistency and multi-trip routing constraints. The effectiveness of algorithm is validated across diverse instances, demonstrating superior computational efficiency compared to GUROBI. Moreover, sensitivity analysis of the two consistency types reveals that a marginal cost increase of up to 1.5% can significantly improve both arrival time and route consistency. Furthermore, our findings indicate a mutually reinforcing relationship between time consistency and route consistency, offering valuable management insights for waste collection companies. This study highlights AVs’ potential to efficiently manage catering waste collection, ensuring reliability and customer satisfaction with minimal cost impact.