The harmony search algorithm has been proven to be an effective optimization method for solving diverse optimization problems. However, due to its slow convergence, the performance of HSA over constrained optimization problems is not very competitive. Therefore, many researchers have hybridized HSA with local search algorithms. However, it’s very difficult to known in advance which local search should be hybridized with HSA as it depends heavily on the problem characteristics. The question is how to design an effective selection mechanism to adaptively select a suitable local search to be combined with HSA during the search process. Therefore, this work proposes an adaptive HSA that embeds an adaptive selection mechanism to adaptively select a suitable local search algorithm to be applied. This work hybridizes HSA with five local search algorithms: hill climbing, simulated annealing, record to record, reactive tabu search and great deluge. We use the Solomon’s vehicle routing problem with time windows benchmark to examine the effectiveness of the proposed algorithm. The obtained results are compared with basic HSA, the local search algorithms and existing methods. The results demonstrate that the proposed adaptive HSA achieves very good results compared other methods. This demonstrates that the selection mechanism can effectively assist HSA to adaptively select a suitable local search during the problem solving process.