CoChat

Travel time optimization on multi-AGV routing by reverse annealing

Open access
Haba, Renichiro, Ohzeki, Masayuki, Tanaka, Kazuyuki · 2022 · Scientific Reports

The DOI matches its Crossref record; 46 of the 46 references it cites were found in a registry or an index.

Abstract

Quantum annealing has been actively researched since D-Wave Systems produced the first commercial machine in 2011. Controlling a large fleet of automated guided vehicles is one of the real-world applications utilizing quantum annealing. In this study, we propose a formulation to control the traveling routes to minimize the travel time. We validate our formulation through simulation in a virtual plant and authenticate the effectiveness for faster distribution compared to a greedy algorithm that does not consider the overall detour distance. Furthermore, we utilize reverse annealing to maximize the advantage of the D-Wave’s quantum annealer. Starting from relatively good solutions obtained by a fast greedy algorithm, reverse annealing searches for better solutions around them. Our reverse annealing method improves the performance compared to standard quantum annealing alone and performs up to 10 times faster than a commercial classical solver, Gurobi. This study extends a use of optimization with general problem solvers in the application of multi-AGV systems and reveals the potential of reverse annealing as an optimizer.

Overview

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

Crossref · 10.1038/s41598-022-22704-0

Cites

46 of 46 references verified0 citation errors · 0 not checkable

Statistics

Figures

Figure 1 Calibration of reversal distance. We performed reverse annealing on 10 random nontrivial QUBO problems that appeared while running the algorithm with 20 AGVs and analyzed the energies of each of the 1000 samples. For a given reversal distance, the height of the red, green, and gray areas represents the mean probability of attaining the same state, the ground state, and the other state, respectively.
Figure 1 Calibration of reversal distance. We performed reverse annealing on 10 random nontrivial QUBO problems that appeared while running the algorithm with 20 AGVs and analyzed the energies of each of the 1000 samples. For a given reversal distance, the height of the red, green, and gray areas represents the mean probability of attaining the same state, the ground state, and the other state, respectively.CC BY · PubMed Central
Figure 2 Annealing schedule of forward and reverse annealing. The red and blue lines indicate the chronological changes in annealing parameter s in forward and reverse annealing, respectively.
Figure 2 Annealing schedule of forward and reverse annealing. The red and blue lines indicate the chronological changes in annealing parameter s in forward and reverse annealing, respectively.CC BY · PubMed Central
Figure 3 Virtual plant we used in this study. The network shows the roads on which AGVs can move. Each circle represents a node, which is an intersection or a mid-point. Each arrow represents the directed connection between two nodes. The length of each arrow is one meter. The square nodes indicate the pick-up or drop-off points that can be the source and destination of AGVs. In the plant, 20 AGVs are active on their task.
Figure 3 Virtual plant we used in this study. The network shows the roads on which AGVs can move. Each circle represents a node, which is an intersection or a mid-point. Each arrow represents the directed connection between two nodes. The length of each arrow is one meter. The square nodes indicate the pick-up or drop-off points that can be the source and destination of AGVs. In the plant, 20 AGVs are active on their task.CC BY · PubMed Central
Figure 4 Comparison of TTS performance. The orange circle and purple triangle show mean value of TTS(0.99) of Gurobi and reverse annealing, respectively. The error bars indicate the standard error.
Figure 4 Comparison of TTS performance. The orange circle and purple triangle show mean value of TTS(0.99) of Gurobi and reverse annealing, respectively. The error bars indicate the standard error.CC BY · PubMed Central
Figure 5 Comparison of residual energy. The purple triangle, red cross, and green circle show mean residual energy of samples on 10 problems solved by reverse annealing, forward annealing, and the greedy algorithm, respectively. The error bars indicate the standard error.
Figure 5 Comparison of residual energy. The purple triangle, red cross, and green circle show mean residual energy of samples on 10 problems solved by reverse annealing, forward annealing, and the greedy algorithm, respectively. The error bars indicate the standard error.CC BY · PubMed Central

Verification

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Citations

Cites

Show all 46 references

Research works printed but not linked: 2

  1. Ide, N., Asayama, T., Ueno, H. & Ohzeki, M. Maximum likelihood channel decoding with quantum annealing machine, in 2020 International Symposium on Information Theory and Its Applications (ISITA), 91–95 (2020).
  2. Maruyama, N., Ohzeki, M. & Tanaka, K. Graph minor embedding of degenerate systems in quantum annealing. arXiv:2110.10930 [quant-ph] (2021). · arXiv

Cited by

See all 56

Metadata

Authors
Haba, R., Ohzeki, M., & Tanaka, K.
Affiliations
  • Tohoku University (JP)
  • Tokyo Institute of Technology (JP)
Corresponding author
Haba, Renichiro
Venue
Scientific Reports
Published
2022-10-22
Volume
12
Issue
1
Pages
17753-17753
ISSN
2045-2322 (ISSN-L)
OpenAlex
W4307137897
Cited by
43
References
43
Citations by year
2026: 9 · 2025: 21 · 2024: 8 · 2023: 5
FWCI
3.90
Type
journal article
Language
en
Open access
Licence
Locations
  • Scientific Reports (publishedVersion, cc-by)
  • PubMed Central (publishedVersion, cc-by)
  • PubMed (publishedVersion)
  • arXiv (Cornell University) (submittedVersion)
  • DOAJ (DOAJ: Directory of Open Access Journals) (submittedVersion, cc-by-sa)
  • arXiv (Cornell University)
Funders
  • JSPS KAKENHI (20H02168, 18H03303)
  • JST-CREST (JPMJCR1402)
  • MEXT-Quantum Leap Flagship Program (JPMXS0120352009)
Topics
  • Physical Sciences › Engineering › Industrial and Manufacturing Engineering › Vehicle Routing Optimization Methods
  • Physical Sciences › Computer Science › Artificial Intelligence › Quantum Computing Algorithms and Architecture
  • Physical Sciences › Engineering › Industrial and Manufacturing Engineering › Advanced Manufacturing and Logistics Optimization
Keywords
automated guided vehicles, travel time minimization, reverse annealing, quantum annealing, D-Wave quantum annealer, hybrid quantum-classical optimization, greedy algorithm, detour distance

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review

How to cite

Cite CoChat for the checks on this page, and the paper for its own findings.

This page
CoChat. (2026). Citation check: Travel time optimization on multi-AGV routing by reverse annealing. https://app.cochat.ai/papers/10.1038/s41598-022-22704-0
The paper
Haba, R., Ohzeki, M., & Tanaka, K. (2022). Travel time optimization on multi-AGV routing by reverse annealing. Scientific Reports. https://doi.org/10.1038/s41598-022-22704-0

Data sources

Bibliographic data: Semantic Scholar, OpenAlex, Crossref.

Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).

Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.