General variable neighborhood search (GVNS) is a well known and widely used metaheuristic for efficiently solving many NP-hard combinatorial optimization problems. We propose a novel extension of the conventional GVNS. Our approach incorporates ideas and techniques from the field of quantum computation during the shaking phase. The travelling salesman problem (TSP) is a well known NP-hard problem which has broadly been used for modelling many real life routing cases. As a consequence, TSP can be used as a basis for modelling and finding routes via the Global Positioning System (GPS). In this paper, we examine the potential use of this method for the GPS system of garbage trucks. Specifically, we provide a thorough presentation of our method accompanied with extensive computational results. The experimental data accumulated on a plethora of TSP instances, which are shown in a series of figures and tables, allow us to conclude that the novel GVNS algorithm can provide an efficient solution for this type of geographical problem.

The purpose of this paper is to assess how three shaking procedures affect the performance of a metaheuristic GVNS algorithm. The first shaking procedure is generally known in the literature as intensified shaking method. The second is a quantum-inspired perturbation method, and the third is a shuffle method. The GVNS schemes are evaluated using a search strategy for both First and Best improvement and a time limit of one and two minutes. The formed GVNS schemes were applied on Traveling Salesman Problem (sTSP, nTSP) benchmark instances from the well-known TSPLib. To examine the potential advantage of any of the three metaheuristic schemes, extensive statistical analysis was performed on the reported results. The experimental data shows that for aTSP instances the first two methods perform roughly equivalently and, in any case, much better than the shuffle approach. In addition, the first method performs better than the other two when using the First Improvement strategy, while the second method gives results quite similar to the third. However, no significant deviations were observed when different methods of perturbation were used for Symmetric TSP instances (sTSP, nTSP).