Cargando…

Supply chain logistics with quantum and classical annealing algorithms

Noisy intermediate-scale quantum (NISQ) hardware is almost universally incompatible with full-scale optimization problems of practical importance which can have many variables and unwieldy objective functions. As a consequence, there is a growing body of literature that tests quantum algorithms on m...

Descripción completa

Detalles Bibliográficos
Autores principales: Weinberg, Sean J., Sanches, Fabio, Ide, Takanori, Kamiya, Kazumitzu, Correll, Randall
Formato: Online Artículo Texto
Lenguaje:English
Publicado: Nature Publishing Group UK 2023
Materias:
Acceso en línea:https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10036469/
https://www.ncbi.nlm.nih.gov/pubmed/36959248
http://dx.doi.org/10.1038/s41598-023-31765-8
_version_ 1784911661531922432
author Weinberg, Sean J.
Sanches, Fabio
Ide, Takanori
Kamiya, Kazumitzu
Correll, Randall
author_facet Weinberg, Sean J.
Sanches, Fabio
Ide, Takanori
Kamiya, Kazumitzu
Correll, Randall
author_sort Weinberg, Sean J.
collection PubMed
description Noisy intermediate-scale quantum (NISQ) hardware is almost universally incompatible with full-scale optimization problems of practical importance which can have many variables and unwieldy objective functions. As a consequence, there is a growing body of literature that tests quantum algorithms on miniaturized versions of problems that arise in an operations research setting. Rather than taking this approach, we investigate a problem of substantial commercial value, multi-truck vehicle routing for supply chain logistics, at the scale used by a corporation in their operations. Such a problem is too complex to be fully embedded on any near-term quantum hardware or simulator; we avoid confronting this challenge by taking a hybrid workflow approach: we iteratively assign routes for trucks by generating a new binary optimization problem instance one truck at a time. Each instance has [Formula: see text] quadratic binary variables, putting it in a range that is feasible for NISQ quantum computing, especially quantum annealing hardware. We test our methods using simulated annealing and the D-Wave Hybrid solver as a place-holder in wait of quantum hardware developments. After feeding the vehicle routes suggested by these runs into a highly realistic classical supply chain simulation, we find excellent performance for the full supply chain. Our work gives a set of techniques that can be adopted in contexts beyond vehicle routing to apply NISQ devices in a hybrid fashion to large-scale problems of commercial interest.
format Online
Article
Text
id pubmed-10036469
institution National Center for Biotechnology Information
language English
publishDate 2023
publisher Nature Publishing Group UK
record_format MEDLINE/PubMed
spelling pubmed-100364692023-03-25 Supply chain logistics with quantum and classical annealing algorithms Weinberg, Sean J. Sanches, Fabio Ide, Takanori Kamiya, Kazumitzu Correll, Randall Sci Rep Article Noisy intermediate-scale quantum (NISQ) hardware is almost universally incompatible with full-scale optimization problems of practical importance which can have many variables and unwieldy objective functions. As a consequence, there is a growing body of literature that tests quantum algorithms on miniaturized versions of problems that arise in an operations research setting. Rather than taking this approach, we investigate a problem of substantial commercial value, multi-truck vehicle routing for supply chain logistics, at the scale used by a corporation in their operations. Such a problem is too complex to be fully embedded on any near-term quantum hardware or simulator; we avoid confronting this challenge by taking a hybrid workflow approach: we iteratively assign routes for trucks by generating a new binary optimization problem instance one truck at a time. Each instance has [Formula: see text] quadratic binary variables, putting it in a range that is feasible for NISQ quantum computing, especially quantum annealing hardware. We test our methods using simulated annealing and the D-Wave Hybrid solver as a place-holder in wait of quantum hardware developments. After feeding the vehicle routes suggested by these runs into a highly realistic classical supply chain simulation, we find excellent performance for the full supply chain. Our work gives a set of techniques that can be adopted in contexts beyond vehicle routing to apply NISQ devices in a hybrid fashion to large-scale problems of commercial interest. Nature Publishing Group UK 2023-03-23 /pmc/articles/PMC10036469/ /pubmed/36959248 http://dx.doi.org/10.1038/s41598-023-31765-8 Text en © The Author(s) 2023 https://creativecommons.org/licenses/by/4.0/Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/ (https://creativecommons.org/licenses/by/4.0/) .
spellingShingle Article
Weinberg, Sean J.
Sanches, Fabio
Ide, Takanori
Kamiya, Kazumitzu
Correll, Randall
Supply chain logistics with quantum and classical annealing algorithms
title Supply chain logistics with quantum and classical annealing algorithms
title_full Supply chain logistics with quantum and classical annealing algorithms
title_fullStr Supply chain logistics with quantum and classical annealing algorithms
title_full_unstemmed Supply chain logistics with quantum and classical annealing algorithms
title_short Supply chain logistics with quantum and classical annealing algorithms
title_sort supply chain logistics with quantum and classical annealing algorithms
topic Article
url https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10036469/
https://www.ncbi.nlm.nih.gov/pubmed/36959248
http://dx.doi.org/10.1038/s41598-023-31765-8
work_keys_str_mv AT weinbergseanj supplychainlogisticswithquantumandclassicalannealingalgorithms
AT sanchesfabio supplychainlogisticswithquantumandclassicalannealingalgorithms
AT idetakanori supplychainlogisticswithquantumandclassicalannealingalgorithms
AT kamiyakazumitzu supplychainlogisticswithquantumandclassicalannealingalgorithms
AT correllrandall supplychainlogisticswithquantumandclassicalannealingalgorithms