Many optimization problems belong to the class of NP-hard problems. These are problems related to the optimal use of resources and, in particular, might include financial management, transportation, finding the optimal routes, production scheduling, etc. Due to the size of real-world practical examples, metaheuristics are mainly used to solve them. The best approaches are based on the local search method. Generally, the larger the sample is, the better the results are. The ability to perform calculations on quantum computers gives the chance of exploring very large neighborhoods with an exponential number of elements. Given the current limitations in the number of qubits available in quantum computers nowadays, the most promising approach is hybrid quantum-classical methods. In this paper, we introduce a new approach and an algorithm designed to explore the problem space on a quantum computer. The results of the conducted computational experiments confirm that even with a limited number of qubits, hybrid algorithms can, even today, be a real competitor for classical methods.