Ant Colony Optimization (ACO) is a new population oriented search metaphor that has been successfully applied to NP-hard combinatorial optimization problems. In this paper we discuss parallelization strategies for Ant Colony Optimization algorithms. We empirically test the most simple strategy, that of executing parallel independent runs of an algorithm. The empirical tests are performed applying MAX-MIN Ant System, one of the most efficient ACO algorithms, to the Traveling Salesman Problem and show that using parallel independent runs is very effective.