Abstract
Obtaining optimal solutions of combinatorial optimization problems is computationally intractable. These problems are known as NP-hard and cannot be solved optimally within a reasonable amount of time. Satisfying with good solution obtained by heuristic search methods within an acceptable execution time is the efficient way in practice. Even using heuristic search, obtaining a good quality solution within a reasonable computing time for large scale and evaluating the quality of the obtained solutions have still difficulties. The hybridization and parallelism of heuristics search offer the possibility for enhancing the efficiency of the search. In first place, a case study of heuristic search techniques for solving a real-world combinatorial optimization problem is discussed in this study. Two straightforward and efficient approaches based on simulated annealing and tabu search are implemented to solve the integer nonlinear programming model which proposed in the case study. In second place, we aim the hybridization of different methods by parallel computing. We present a parallel hybrid heuristic search that combines branch-and-bound method and tabu search algorithm by cooperative multi-search scheme to integrate the benefits of exact methods and metaheuristics. These two algorithms perform searches in parallel and cooperate by asynchronously exchanging information. We use a master-slave model to reduce the complexity of communication and enhance the performance of data exchange. A branch-and-bound process is used as the master process to control the exchange of information and the termination of computation. Several tabu search processes are executed simultaneously as the slave processes, and are cooperative by asynchronously exchanging information of the best solutions found and new initial solutions with the master process of branch-and-bound. According to the computation experiments of solving traveling salesman problems, the proposed heterogeneous parallel search algorithm outperforms a conventional parallel branch-and-bound method and a conventional parallel tabu search. The results also show the proposed heterogeneous parallel search algorithm achieves linear accelerations when we use more processors to accelerate searching time.