Waste collection and management presents a major challenge for municipalities wanting to achieve cleaner urban environments. Smart city infrastructure incorporating the Internet of Things (IoT) paradigm offers substantial advantages in terms of real-time waste monitoring capability. Basic sensory monitoring by itself, however, falls short of achieving optimal waste management without comprehensive data analytics. To this end, the present work proposes an off-the-shelf IoT-based waste monitoring solution, combined with back-end data analytics for efficient waste collection. The work employs Raspberry Pi and ultrasonic sensors, mounted on waste-bins in a specific area of a cooperating municipality for waste capacity monitoring. Realtime bin status and machine learning analytics are used to identify present as well as predict future waste collection scheduling. Dynamic collection servicing routes are accordingly mapped for utilization by waste collection vehicles. During a tenday trial and validation period, it was observed that the proposed design increases fuel efficiency by up to 46% and a reduction in collection times by up to 18%. In addition to the noted quantitative improvements, the proposed scheme can also aid in optimizing long-term waste policies in smart city environments using the recorded statistics.