In this paper, a comparative analysis of the metaheuristic maintenance optimization of refuse collection vehicles (RCV) using the Taguchi experimental design is presented based on a RCV model as a multi-state degradation system with two dependent subsystems. The model which is based on a probabilistic approach includes two stochastic degradation processes, a random failure process and a set of maintenance actions and their effects. The optimal values of the mean time to preventive maintenance are determined by maximizing the availability of the complete system and by minimizing total costs. In order to solve the real life problem of the multi-objective optimization of RCV maintenance, three different metaheuristic optimization algorithms were used: a real coded genetic algorithm, an improved harmony search algorithm and simulated annealing. Each algorithm has parameters that need to be accurately calibrated to ensure the best performance. For this purpose, calibration was applied to the parameters by means of the Taguchi method. Finally, the optimal values of the mean time to minimal preventive maintenance of RCVs are obtained and computational results of the three optimization algorithms are compared.