Crew Scheduling Problems (CSPs) are frequently found in the transportation industry. They are often formulated as Set Partitioning Problems (SPPs) in which additional industrial constraints can be added, and solved by linear programming methods. As they are highly constrained, metaheuristics often struggle in finding feasible and good solutions to these problems. In fact, either as standalone methods or coupled with linear programming, the design of efficient metaheuristics to solve CSPs is still a challenge. The purpose of this paper is to propose and experimentally compare three adaptations of popular metaheuristics to solve the SPP. The proposed methods, based on Genetic Algorithms, Ant Colony Optimization and Iterated Local Search, are tested on the 55 SPP benchmarks of the OR-Library in a common computing environment. They are meant to serve as a guideline in a greater project aimed as solving real-world CSPs on HPC architectures.