We consider a waste collection routing and fleet composition problem for a collection network with multiple types of waste. While each container (i.e., each waste type in each node) has assigned a weekly collection frequency, the collection schedule is to be optimized. The fleet composition decision is made over a set of heterogeneous single-compartment vehicles. The problem is formulated as a multi-trip multi-commodity heterogeneous fleet composition periodic vehicle routing problem with an overall aim to minimize the total operational costs. A general mathematical model of the problem is presented and a solution algorithm is proposed. Computational results are presented on an illustrative data sample (with regards of a future usage of the proposed approach on a real case study in the Czech Republic). The probem is solved by the developed heuristic method as well as by exact methods in order to test the suggested waste collection approach (i.e., model as well as proposed algorithm).