The simulated annealing algorithm (SAA) is a well-established approach to the approximate solution of combinatorial optimisation problems. SAA allows for occasional uphill moves in an attempt to reduce the probability of becoming stuck in a poor but locally optimal solution. Previous work showed that SAA can find better solutions, but it takes much longer time. In this paper, in order to harness the power of the very recent hybrid Many Integrated Core Architecture (MIC), we propose a new parallel simulated annealing algorithm customised for MIC. Our experiments with the Travelling Salesman Problem (TSP) show that our parallel SAA gains significant speedup.