EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Quantum Heuristic Approach to Vehicle Routing Problem

Jun Suk Kim, Donghyeon Lee, Chang Wook Ahn

Mathematics · 18.03.2026 · 14 (6) · 1026

DOI: 10.3390/math14061026 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Mathematics, online erschienen am 18.03.2026. Verfasst von Jun Suk Kim und 2 weiteren Autor:innen. Die Arbeit nennt 42 Literaturangaben. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0). Gefördert von: Hyundai Motor Company, KIA Corporation, National Research Foundation of Korea.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

Quantum optimization has recently drawn considerable attention as one of the possible applications of noisy intermediate-scale quantum computation, yet the problem of qubit requirement remains a major bottleneck when combinatorial optimization problems are converted into quantum circuits. This issue becomes especially critical in solving the capacitated vehicle routing problem (CVRP) with the quantum approximate optimization algorithm (QAOA), since the number of required qubits increases polynomially with respect to the number of nodes. This study investigates whether a heuristic divide-and-conquer strategy can be adapted to the quantum setting so as to improve qubit efficiency while preserving the optimization capability to a reasonable extent. The proposed method decomposes a single CVRP into multiple traveling salesman problems (TSPs) by the sweeping-based clustering method, searches for the sector configuration with the smallest angle sum by Grover’s search algorithm, and then solves each sector-wise TSP with the QAOA aided by the gravitational search algorithm. Experiments on five benchmark datasets show that the proposed approach attains feasible solutions within 3.4 to 12.7% of the reinforcement-learning baseline on the main test set. These results suggest that the proposed approach serves as a plausible quantum heuristic framework for constrained routing optimization, with the advantage of reducing the qubit burden by decomposing the original problem into smaller subproblems.

Förderung

  • Hyundai Motor Company
  • KIA Corporation
  • National Research Foundation of Korea
  • Republic of Korea government
  • GIST

Zitieren

APA

Kim, J. S., Lee, D., & Ahn, C. W. (2026). Quantum Heuristic Approach to Vehicle Routing Problem. Mathematics, 14(6), 1026. https://doi.org/10.3390/math14061026

Vancouver

Kim JS, Lee D, Ahn CW. Quantum Heuristic Approach to Vehicle Routing Problem. Mathematics. 2026;14(6):1026. doi:10.3390/math14061026

BibTeX
@article{Kim2026,
  author = {Kim, Jun Suk and Lee, Donghyeon and Ahn, Chang Wook},
  title = {Quantum Heuristic Approach to Vehicle Routing Problem},
  journal = {Mathematics},
  year = {2026},
  volume = {14},
  number = {6},
  pages = {1026},
  doi = {10.3390/math14061026}
}
Kostenlos starten →