Cooperative parallel tabu search for capacitated network design

We present a cooperative parallel tabu search method for the fixed charge, capacitated, multicommodity network design problem. Several communication strategies are analyzed and compared. The resulting parallel procedure displays excellent performances in terms of solution quality and solution times. The experiments show that parallel implementations find better solutions than sequential ones. They also show that, when properly designed and implemented, cooperative search outperforms independent search strategies, at least on the class of problems of interest here.