We study the Mixed Capacitated General Routing Problem (MCGRP)in which a fleet of capacitated vehicles has to serve a set of requests by traversing a mixed weighted graph. The requests may be located on nodes, edges, and arcs. We propose a new Iterated Local Search metaheuristic for the problem. Computational experiments show that the proposed metaheuristic is highly effective on five published benchmarks for the MCGRP. The metaheuristic yields excellent results also on seven standard CARP datasets, and good results on four well-known CVRP benchmarks.