A Double-Adaptive General Variable Neighborhood Search algorithm for the solution of the...

This work addresses a novel General Variable Neighborhood Search (GVNS) solution method, which integrates intelligent adaptive mechanisms to re-order the search operators during the intensification and diversification phases, in an effort to enhance its overall efficiency. To evaluate the performance of the new GVNS scheme, asymmetric and symmetric instances of the classic Traveling Salesman Problem (TSP) from the TSPLib were solved. The obtained results of the Double-Adaptive GVNS were compared with those achieved by two single-adaptive GVNS, which use an adaptive mechanism either for the intensification or the diversification phase and with a conventional GVNS. For a fair comparison, all GVNS schemes were structured using the same local search and shaking operators. Moreover, the novel GVNS algorithm was compared with some recent solution methods for the TSP, found in the open literature. The comparative studies revealed the high efficiency of the novel VNS scheme and underlined the significant impact of intelligent mechanisms on the performance of classic metaheuristic frameworks. A novel double adaptive GVNS (DA-GVNS) is proposed for the solution of the TSP. The proposed algorithm efficiently solves both symmetric and asymmetric instances. The DA-GVNS outperforms other GVNS schemes.•Results show that the novel VNS scheme performs better than other metaheuristics.

Английский

Applied Soft Computing. – 2022. – Vol. 121. – Art. 108746.