Over the last decades, the rapid growth of e-commerce has increased the scale and operational intensity of warehouse systems. Consequently, sustainability in warehouse operations has become increasingly important due to rising energy consumption and environmental concerns. As an answer to this growth, Automated Guided Vehicles (AGVs) are utilized more, directly affecting energy usage and operational efficiency. This study develops a sustainability-oriented optimization framework for AGV-assisted order picking in warehouses with random storage and multiple products per location. The framework includes five mathematical models prioritizing one or more environmental (distance minimization), economic (AGV utilization), and social (workload balancing) sustainability perspectives. A generalized recursive matheuristic algorithm based on iterative cut generation is developed for the first model. A real-life dataset is used to evaluate the proposed approaches. Results reveal substantially different outcomes from different sustainability perspectives. The “Compact Clustering Model” achieved the best environmental performance, reducing total travel distance and normalized energy consumption by approximately 27–29% compared with the baseline formulation. From an economic sustainability perspective, several formulations achieved 92–100% AGV utilization, while social sustainability indicators showed load variability ranging from approximately 5.1 to 13.1. Overall, the findings demonstrate that different formulations provide distinct sustainability advantages in AGV-assisted warehouse systems.