Internet of Things (IoT) enables Smart Cities with novel services. Waste collection in Smart Cities becomes a dynamic process with the proliferation of sensors and actuators embedded on real waste bins. Heterogeneous fleets of trucks are used for efficient waste collection exploiting the diverse road network. In this paper we propose a novel approach by incorporating Low Capacity Trucks (LCTs) and High Capacity Trucks (HCTs). However, HCTs are serving as Mobile Depots (MDs) which are cost efficient and decongest traffic in Smart Cities. A detailed system overview illustrates the architecture of the proposed approach. We also propose novel algorithms which support dynamic waste collection with MDs. Scheduling and routing are transformed to dynamic models. Specifically, we propose a novel scheduling algorithm while we customize an existing routing algorithm. The models where experimentally evaluated with real and synthetic data from the city of St. Petersburg, Russia. The results were promising and proved that the incorporation of MDs is efficient for waste collection in IoT-enabled Smart Cities. Finally, we perform an economic analysis in order to define the economic impact of the proposed solution to the municipality budget for an ownership cost for a period of five years; in which the proposed solution proved to be cost efficient.