In this paper we deal with the solution of the sequential ordering problem (SOP) in parallel environments. In particular, we present a parallel version of the rollout algorithm, an innovative heuristic method for solving NP-Hard combinatorial optimization problems, recently proposed by Bertsekas et al. The proposed parallel algorithm has been designed by considering a cooperative multi-thread parallelization strategy, where several threads visit different portions of the solution space independently and periodically exchange information about the solutions found during the search. Such an approach allows not only to speed up the convergence to the best solution, but to find also better solutions, taking roughly the same computation time. The performance of the proposed parallel RH has been evaluated on a cluster of PCs, by considering a set of test problems taken from the TSPLIB.
