Smart Cities constitute the future of civil habitation. Internet of Things (IoT) enable innovative services exploiting sensor data from sensors embedded in the city. Waste collection is treated as a potential IoT service which exploits robustness and cost efficiency of a heterogeneous fleet. In this paper we propose a dynamic routing algorithm which is robust and copes when a truck is overloaded or damaged and need replacement. We also incorporate a system model which assumes two kinds of trucks for waste collection, the Low Capacity Trucks (LCTs) and the High Capacity Trucks (HCTs). By incorporating HCTs we achieve reduction of the waste collection operational costs because route trips to the dumps are reduced due to high waste storage capacity of these trucks. Finally, the proposed models are evaluated on synthetic and real data from the city municipality of St. Petersburg, Russia. The models demonstrate consistency and correctness.