Nowadays, urban solid waste management is one of the most crucial activities in municipalities and their affiliated organizations. It includes the processes of collection, transportation and disposal. These major operations require a large amount of resources and investments, which will always be subject to limitations. In this paper, a chance-constrained programming model based on fuzzy credibility theory is proposed for the multi-trip capacitated arc routing problem to cope with the uncertain nature of waste amount generated in urban areas with the aim of total cost minimization. To deal with the complexity of the problem and solve it efficiently, a hybrid augmented ant colony optimization algorithm is developed based on an improved max-min ant system with an innovative probability function and a simulated annealing algorithm. The performance of hybrid augmented ant colony optimization is enhanced by using the Taguchi parameter design method to adjust the parameters' values optimally. The overall efficiency of the algorithm is evaluated against other similar algorithms using well-known benchmarks. Finally, the applicability of the suggested methodology is tested on a real case study with a sensitivity analysis to evolve the managerial insights and decision aids.