: Waste collection is a highly visible municipal service that involves large expenditures and difficult operational problems, plus that waste collection and disposal has high expenses in terms of investment costs (i.e. vehicles fleet) and operational costs (i.e. fuel, maintenances). In this research, The Capacitated Arc Routing Problem which is one of the most important routing problems with ample of usage in real word (e.g. waste collection),will be described. Due to the uncertain nature of demands and difficulties of its real amount determination, we use two approaches to deal with uncertainty of the problem: 1) A chance constrained programming model based on the fuzzy credibility theory in which demands are triangular fuzzy variable, and 2) Robust optimization method based on Bertsimas and Sym’s robust model. As the problem NP-complete complexity class, hence a simulated annealing algorithm and an improved max-min ant colony algorithm have been applied in order to solve the problem.To generate appropriate initial solutions a proposed heuristic algorithm is used in the simulated annealing algorithm. Improved max-min ant colony algorithm is also uses in order to evaluate performance of the simulated annealing in large-sized problems. To improve the performance of the proposed algorithms, Taguchi method is used in order to design experiments of parameters adjustment. In following, a number of sample problems were generated randomly in small, medium and large dimensions to evaluate features of the proposed model and its various solving approaches. Finally, the experimental results have shown that simulated annealing algorithm and the proposed improved max-min ant colony algorithm has appropriate performance in a reasonable time. Then, at the end of the research, we implemented a case study in Sepahanshahr, Isfahan and its obtained results and suggestions have been demonstrated.