Graph Coarsening Approach to the Vehicle Routing Problem: An Approximation Strategy
In the Noisy Intermediate-Scale Quantum (NISQ) era of quantum computing, solving complex optimization problems such as the Vehicle Routing Problem (VRP) remains a formidable challenge. To overcome this obstacle, we introduce a novel method in this paper that focuses on reducing the number of edges i...
Saved in:
| Main Authors: | , , , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2025-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10854442/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1825207053323337728 |
|---|---|
| author | Katarzyna Nalecz-Charkiewicz Arnav Das Turbasu Chatterjee Joshua Keene Pawel Gora Carlos C. N. Kuhn |
| author_facet | Katarzyna Nalecz-Charkiewicz Arnav Das Turbasu Chatterjee Joshua Keene Pawel Gora Carlos C. N. Kuhn |
| author_sort | Katarzyna Nalecz-Charkiewicz |
| collection | DOAJ |
| description | In the Noisy Intermediate-Scale Quantum (NISQ) era of quantum computing, solving complex optimization problems such as the Vehicle Routing Problem (VRP) remains a formidable challenge. To overcome this obstacle, we introduce a novel method in this paper that focuses on reducing the number of edges in a graph based on Euclidean distances between vertices while preserving the crucial characteristics needed for solving the VRP. Our graph coarsening approach combined with the inflation method enables the reduced graph to be processed efficiently by classical, quantum or hybrid (quantum-classical) solvers, resulting in a faster computation time. When using the proposed method with hybrid algorithms, we have demonstrated an improvement of approximately 50% in the solution found by the hybrid solver. The practicality of our method on quantum hardware highlights its potential to contribute to the advancement of quantum and hybrid algorithms and applications during the NISQ era. |
| format | Article |
| id | doaj-art-ce676cdb9ecd40e5a3797be2bbc2cf3c |
| institution | Kabale University |
| issn | 2169-3536 |
| language | English |
| publishDate | 2025-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj-art-ce676cdb9ecd40e5a3797be2bbc2cf3c2025-02-07T00:00:56ZengIEEEIEEE Access2169-35362025-01-0113224592247210.1109/ACCESS.2025.353467710854442Graph Coarsening Approach to the Vehicle Routing Problem: An Approximation StrategyKatarzyna Nalecz-Charkiewicz0https://orcid.org/0000-0002-8534-9898Arnav Das1https://orcid.org/0000-0003-3751-3056Turbasu Chatterjee2Joshua Keene3Pawel Gora4https://orcid.org/0000-0002-8037-5704Carlos C. N. Kuhn5https://orcid.org/0000-0001-8733-6962Faculty of Electronics and Information Technology, Warsaw University of Technology, Warsaw, PolandDepartment of Computer Science, St. Xavier’s University, Kolkata, IndiaDepartment of Computer Science, Virginia Tech, Blacksburg, VA, USA12thLevel Pty Ltd., Barton, AustraliaFundacja Quantum AI, Warsaw, Poland12thLevel Pty Ltd., Barton, AustraliaIn the Noisy Intermediate-Scale Quantum (NISQ) era of quantum computing, solving complex optimization problems such as the Vehicle Routing Problem (VRP) remains a formidable challenge. To overcome this obstacle, we introduce a novel method in this paper that focuses on reducing the number of edges in a graph based on Euclidean distances between vertices while preserving the crucial characteristics needed for solving the VRP. Our graph coarsening approach combined with the inflation method enables the reduced graph to be processed efficiently by classical, quantum or hybrid (quantum-classical) solvers, resulting in a faster computation time. When using the proposed method with hybrid algorithms, we have demonstrated an improvement of approximately 50% in the solution found by the hybrid solver. The practicality of our method on quantum hardware highlights its potential to contribute to the advancement of quantum and hybrid algorithms and applications during the NISQ era.https://ieeexplore.ieee.org/document/10854442/Combinatorial optimizationgraph reductionvehicle routingquantum computing |
| spellingShingle | Katarzyna Nalecz-Charkiewicz Arnav Das Turbasu Chatterjee Joshua Keene Pawel Gora Carlos C. N. Kuhn Graph Coarsening Approach to the Vehicle Routing Problem: An Approximation Strategy IEEE Access Combinatorial optimization graph reduction vehicle routing quantum computing |
| title | Graph Coarsening Approach to the Vehicle Routing Problem: An Approximation Strategy |
| title_full | Graph Coarsening Approach to the Vehicle Routing Problem: An Approximation Strategy |
| title_fullStr | Graph Coarsening Approach to the Vehicle Routing Problem: An Approximation Strategy |
| title_full_unstemmed | Graph Coarsening Approach to the Vehicle Routing Problem: An Approximation Strategy |
| title_short | Graph Coarsening Approach to the Vehicle Routing Problem: An Approximation Strategy |
| title_sort | graph coarsening approach to the vehicle routing problem an approximation strategy |
| topic | Combinatorial optimization graph reduction vehicle routing quantum computing |
| url | https://ieeexplore.ieee.org/document/10854442/ |
| work_keys_str_mv | AT katarzynanaleczcharkiewicz graphcoarseningapproachtothevehicleroutingproblemanapproximationstrategy AT arnavdas graphcoarseningapproachtothevehicleroutingproblemanapproximationstrategy AT turbasuchatterjee graphcoarseningapproachtothevehicleroutingproblemanapproximationstrategy AT joshuakeene graphcoarseningapproachtothevehicleroutingproblemanapproximationstrategy AT pawelgora graphcoarseningapproachtothevehicleroutingproblemanapproximationstrategy AT carloscnkuhn graphcoarseningapproachtothevehicleroutingproblemanapproximationstrategy |