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. [J. Heuristics 3 (1997) 245]. 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 independentlyand periodically exchange information about the solutions found during the search. Such an approach allows not onlyto 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, byconsidering a set of test problems taken from the TSPLIB [Orsa J. Comput. 3 (1991) 376].
Scheda prodotto non validato
Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo
|Titolo:||A Cooperative Parallel Rollout Algorithm for the Sequential Ordering Problem|
|Data di pubblicazione:||2003|
|Citazione:||A Cooperative Parallel Rollout Algorithm for the Sequential Ordering Problem / Guerriero, Francesca; Mancini, M.. - In: PARALLEL COMPUTING. - ISSN 0167-8191. - 29(2003), pp. 663-677.|
|Appare nelle tipologie:||1.1 Articolo in rivista|