The aim of this paper is to computationally compare several algorithms for the Minimum Cost Perfect Matching Problem on an undirected graph. Our work is motivated by the need to solve large instances of the Capacitated Arc Routing Problem (CARP) arising in the optimization of garbage collection in Denmark. Common heuristics for the CARP involve the computation of matchings of the odd-degree nodes of a graph. The algorithms used in the comparison include the CPLEX solution of an exact formulation, a recent implementation of the Blossom algorithm, as well as six constructive heuristics. The Blossom algorithm works well on graphs containing fewer than 4000 nodes and outperforms CPLEX in terms of computing time. For larger instances, we found that one of the constructive heuristics consistently exhibits the best behavior compared with the other five.