The collection and treatment of waste poses a major challenge to modern urban planning, particularly to smart cities. To cope with this problem, a cost-effective alternative to conventional methods is the use of Automated Vacuum Waste Collection (AVWC) systems, using air suction on a closed network of underground pipes to transport waste from the drop off points scattered throughout the city to a central collection point. This paper describes and empirically evaluates a novel approach to defining daily operation plans for AVWC systems to improve quality of service, and reduce energy consumption, which represents about 60% of the total operation cost. We model a daily AVWC operation as a Markov decision process, and use Approximate Dynamic Programming techniques (ADP) to obtain optimal operation plans. The experiments, comparing our approach with the current approach implemented in some real-world AVWC systems, show that ADP techniques significantly improve the quality of AVWC operation plans.