Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Algorithms

Combinatorial GVNS (General Variable Neighborhood Search) Optimization for Dynamic Garbage Collection

Christos Papalitsas, Panagiotis Karakostas, Theodore Andronikos, Spyros Sioutas, Konstantinos Giannakis

Published Mar 27, 2018• 14 citations
Publisher

Abstract

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.

DOI
10.3390/a11040038

Related papers

Quantum-Inspired Deep Reinforcement Learning for Solving the Traveling Salesman Problem

Qianqian Liu, Jiahong Rui, Yue Ruan

The Traveling Salesman Problem (TSP), a well-known NP-hard optimization problem, has been widely studied for decades due to its broad practical applicability. In recent years, deep learning methods have shown promise in solving TSP; however, existing approaches often struggle to extract informative edge features between cities, which limits solution quality. To address this, we propose a Quantum-Inspired Deep Learning (QIDL) model that enhances node representations through quantum-inspired embedding, integrates Euclidean distance into the Transformer to strengthen spatial reasoning, and employs a quantum-inspired pointer network to replace greedy decoding with global optimization search. Experimental results demonstrate that QIDL outperforms traditional pointer networks, achieving faster convergence, improved stability, and a 1.76% reduction in tour length, with strong performance on medium-scale TSP instances. These results highlight the potential of QIDL to open new avenues for quantum-inspired learning in combinatorial optimization.

Cross Strait Radio Science and Wireless Technology Conference (CSRSWTC)•Nov 14, 2025•0 citations

Efficient quantum algorithm for solving travelling salesman problem: An IBM quantum experience

Karthik Srinivasan, Saipriya Satyajit, Bikash K. Behera +1 more

The famous Travelling Salesman Problem (TSP) is an important category of optimization problems that is mostly encountered in various areas of science and engineering. Studying optimization problems motivates to develop advanced techniques more suited to contemporary practical problems. Among those, especially the NP hard problems provide an apt platform to demonstrate supremacy of quantum over classical technologies in terms of resources and time. TSP is one such NP hard problem in combinatorial optimization which takes exponential time order for solving by brute force method. Here we propose a quantum algorithm to solve the travelling salesman problem using phase estimation technique. We approach the problem by encoding the given distances between the cities as phases. We construct unitary operators whose eigenvectors are the computational basis states and eigenvalues are various combinations of these phases. Then we apply phase estimation algorithm to certain eigenstates which give us all the total distances possible for all the routes. After obtaining the distances we can search through this information using the quantum search algorithm for finding the minimum to find the least possible distance as well the route taken. This provides us a quadratic speedup over the classical brute force method for a large number of cities. In this paper, we illustrate an example of the travelling salesman problem by taking four cities and present the results by simulating the codes in the IBM's quantum simulator.

arXiv:1805.10928•May 28, 2018•113 citations

Quantum evolutionary algorithm for TSP combinatorial optimisation problem

Ma, Yijiang, Tan Chye Cheah

This paper implements a new way of solving a problem called the traveling salesman problem (TSP) using quantum genetic algorithm (QGA). We compared how well this new approach works to the traditional method known as a classical genetic algorithm (CGA). The TSP is a well-established challenge in combinatorial optimization where the objective is to find the most efficient path to visit a series of cities, minimizing the total distance, and returning to the starting point. We chose the TSP to test the performance of both algorithms because of its computational complexity and importance in practical applications. We choose the dataset from the international standard library TSPLIB for our experiments. By designing and implementing both algorithms and conducting experiments on various sizes and types of TSP instances, we provide an in-depth analysis of the accuracy of the optimal solution, the number of iterations, the execution time, and the stability of the algorithms for both. The empirical findings indicate that the CGA outperforms the QGA in terms of finding superior solutions more quickly in most of the test instances, especially when the problem size is large. This suggests that although the principle of quantum computing provides a new way to solve complex combinatorial optimisation problems, the implementation of quantum phenomena and the setting of parameters such as the optimal angle for a quantum revolving gate is challenging and need further optimisation to achieve the desired results. Additionally, it is important to note that the QGA has not been tested on real quantum hardware, so its true performance remains unverified. These limitations provide rich opportunities for further research in the future.

arXiv:2409.13788•Sep 20, 2024•0 citations

Quantum Computing for Optimizing Routes in Smart Cities

André Filipe de Soveral Torres Lopes dos Santos

In recent years, Quantum Computing has been gaining increasing importance as more and more examples of Quantum Supremacy (demonstrating that a programmable quantum device can solve a problem that no classical computer can solve in any feasible amount of time) has been demonstrated by Google, Honeywell and other places where quantum computing research is underway.The potential of Quantum Computing is explored to address computational issues within the smart cities domain.Focusing in its application on the routing of garbage trucks.The garbage truck routing issue was studied and a simplified model of route planning was considered.A modified "Travelling Salesman Problem" (TSP) algorithm was applied, with added restrictions concerning the start and the end of the route.A few graphs from a TSP database were used.With each graph, the problem was formulated as a QUBO, and using a solver (Qbsolv), it was solved both by a classical computer (Laptop) and a Quantum Computer (Dwave Advantage System).Due to the limitation on time with the Dwave Quantum Computer, there was a limit to how many experiments that were possible to run on it.The samples show that as the complexity of the problem increases, so does its deviation from the "optimal result", but nonetheless the results obtained show that it is possible to obtain a "good enough" result that has practical real world applications.

•Jul 21, 2021•1 citation

Adiabatic quantum computing impact on transport optimization in the last-mile scenario

Juan Francisco Ariño Sales, Raúl Andrés Palacios Araos

In the ever-evolving landscape of global trade and supply chain management, logistics optimization stands as a critical challenge. This study takes on the Vehicle Routing Problem (VRP), a variant of the Traveling Salesman Problem (TSP), by proposing a novel hybrid solution that seamlessly combines classical and quantum computing methodologies. Through a comprehensive analysis of our approach, including algorithm selection, data collection, and computational processes, we provide in-depth insights into the efficiency, and effectiveness of our hybrid solution compared to traditional methods. The results after analysis of 14 datasets highlight the advantages and limitations of this approach, demonstrating its potential to address NP-hard problems and contribute significantly to the field of optimization algorithms in logistics. This research offers promising contributions to the advancement of logistics optimization techniques and their potential implications for enhancing supply chain efficiency.

arXiv:2301.07691•Frontiers in Computer Science•Nov 15, 2023•24 citations

Genetic Quantum Algorithm and Its Application to Combinatorial Optimization Problems

This paper presents a comprehensive review of recent advancements in Genetic Quantum Algorithms (GQAs) and their application to combinatorial optimization problems.As quantum computing gains momentum, researchers are increasingly integrating quantum principles with classical metaheuristics like genetic algorithms to address NP-hard challenges such as the traveling salesman problem (TSP), job-shop scheduling, and graph coloring.This review synthesizes peer-reviewed studies published between 2023 and 2025.It highlights key innovations, performance outcomes, convergence behavior, scalability, and hardware constraints.The analysis reveals that GQAs offer significant improvements in solution accuracy, search efficiency, and robustness over classical techniques, though issues such as decoherence, quantum noise, and circuit depth remain open areas of exploration.

International Research Journal of Modernization in Engineering Technology and Science•Sep 23, 2025•0 citations
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 Traveling Salesman Problem (TSP), a well-known NP-hard optimization problem, has been widely studied for decades due to its broad practical applicability. In recent years, deep learning methods have shown promise in solving TSP; however, existing approaches often struggle to extract informative edge features between cities, which limits solution quality. To address this, we propose a Quantum-Inspired Deep Learning (QIDL) model that enhances node representations through quantum-inspired embedding, integrates Euclidean distance into the Transformer to strengthen spatial reasoning, and employs a quantum-inspired pointer network to replace greedy decoding with global optimization search. Experimental results demonstrate that QIDL outperforms traditional pointer networks, achieving faster convergence, improved stability, and a 1.76% reduction in tour length, with strong performance on medium-scale TSP instances. These results highlight the potential of QIDL to open new avenues for quantum-inspired learning in combinatorial optimization.
The famous Travelling Salesman Problem (TSP) is an important category of optimization problems that is mostly encountered in various areas of science and engineering. Studying optimization problems motivates to develop advanced techniques more suited to contemporary practical problems. Among those, especially the NP hard problems provide an apt platform to demonstrate supremacy of quantum over classical technologies in terms of resources and time. TSP is one such NP hard problem in combinatorial optimization which takes exponential time order for solving by brute force method. Here we propose a quantum algorithm to solve the travelling salesman problem using phase estimation technique. We approach the problem by encoding the given distances between the cities as phases. We construct unitary operators whose eigenvectors are the computational basis states and eigenvalues are various combinations of these phases. Then we apply phase estimation algorithm to certain eigenstates which give us all the total distances possible for all the routes. After obtaining the distances we can search through this information using the quantum search algorithm for finding the minimum to find the least possible distance as well the route taken. This provides us a quadratic speedup over the classical brute force method for a large number of cities. In this paper, we illustrate an example of the travelling salesman problem by taking four cities and present the results by simulating the codes in the IBM's quantum simulator.
This paper implements a new way of solving a problem called the traveling salesman problem (TSP) using quantum genetic algorithm (QGA). We compared how well this new approach works to the traditional method known as a classical genetic algorithm (CGA). The TSP is a well-established challenge in combinatorial optimization where the objective is to find the most efficient path to visit a series of cities, minimizing the total distance, and returning to the starting point. We chose the TSP to test the performance of both algorithms because of its computational complexity and importance in practical applications. We choose the dataset from the international standard library TSPLIB for our experiments. By designing and implementing both algorithms and conducting experiments on various sizes and types of TSP instances, we provide an in-depth analysis of the accuracy of the optimal solution, the number of iterations, the execution time, and the stability of the algorithms for both. The empirical findings indicate that the CGA outperforms the QGA in terms of finding superior solutions more quickly in most of the test instances, especially when the problem size is large. This suggests that although the principle of quantum computing provides a new way to solve complex combinatorial optimisation problems, the implementation of quantum phenomena and the setting of parameters such as the optimal angle for a quantum revolving gate is challenging and need further optimisation to achieve the desired results. Additionally, it is important to note that the QGA has not been tested on real quantum hardware, so its true performance remains unverified. These limitations provide rich opportunities for further research in the future.
In recent years, Quantum Computing has been gaining increasing importance as more and more examples of Quantum Supremacy (demonstrating that a programmable quantum device can solve a problem that no classical computer can solve in any feasible amount of time) has been demonstrated by Google, Honeywell and other places where quantum computing research is underway.The potential of Quantum Computing is explored to address computational issues within the smart cities domain.Focusing in its application on the routing of garbage trucks.The garbage truck routing issue was studied and a simplified model of route planning was considered.A modified "Travelling Salesman Problem" (TSP) algorithm was applied, with added restrictions concerning the start and the end of the route.A few graphs from a TSP database were used.With each graph, the problem was formulated as a QUBO, and using a solver (Qbsolv), it was solved both by a classical computer (Laptop) and a Quantum Computer (Dwave Advantage System).Due to the limitation on time with the Dwave Quantum Computer, there was a limit to how many experiments that were possible to run on it.The samples show that as the complexity of the problem increases, so does its deviation from the "optimal result", but nonetheless the results obtained show that it is possible to obtain a "good enough" result that has practical real world applications.
In the ever-evolving landscape of global trade and supply chain management, logistics optimization stands as a critical challenge. This study takes on the Vehicle Routing Problem (VRP), a variant of the Traveling Salesman Problem (TSP), by proposing a novel hybrid solution that seamlessly combines classical and quantum computing methodologies. Through a comprehensive analysis of our approach, including algorithm selection, data collection, and computational processes, we provide in-depth insights into the efficiency, and effectiveness of our hybrid solution compared to traditional methods. The results after analysis of 14 datasets highlight the advantages and limitations of this approach, demonstrating its potential to address NP-hard problems and contribute significantly to the field of optimization algorithms in logistics. This research offers promising contributions to the advancement of logistics optimization techniques and their potential implications for enhancing supply chain efficiency.
This paper presents a comprehensive review of recent advancements in Genetic Quantum Algorithms (GQAs) and their application to combinatorial optimization problems.As quantum computing gains momentum, researchers are increasingly integrating quantum principles with classical metaheuristics like genetic algorithms to address NP-hard challenges such as the traveling salesman problem (TSP), job-shop scheduling, and graph coloring.This review synthesizes peer-reviewed studies published between 2023 and 2025.It highlights key innovations, performance outcomes, convergence behavior, scalability, and hardware constraints.The analysis reveals that GQAs offer significant improvements in solution accuracy, search efficiency, and robustness over classical techniques, though issues such as decoherence, quantum noise, and circuit depth remain open areas of exploration.