This paper presents an efficient parallel and vectorized implementation of three different selection functions (Roulette Wheel, I-Roulette and DS-Roulette) for tour construction (the most time-consuming part of the Ant Colony Optimization bio-inspired metaheuristic) targeting two Intel multi-core processors and the Knights Corner Intel Xeon Phi coprocessor. The results show that our best implementation (with I-Roulette as selection function) on Xeon Phi 7120P runs up to 78.98 x faster compared to its sequential counterpart on a Xeon v2 CPU.