Top

Published in:

2021 | OriginalPaper | Chapter

Multimodal Container Planning: A QUBO Formulation and Implementation on a Quantum Annealer

Authors : F. Phillipson, I. Chiscop

Published in: Computational Science – ICCS 2021

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Quantum computing is developing fast. Real world applications are within reach in the coming years. One of the most promising areas is combinatorial optimisation, where the Quadratic Unconstrained Binary Optimisation (QUBO) problem formulation is used to get good approximate solutions. Both the universal quantum computer as well as the quantum annealer can handle this kind of problems well. In this paper, we present an application on multimodal container planning. We show how to map this problem to a QUBO problem formulation and how the practical implementation can be done on the quantum annealer produced by D-Wave Systems.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter OnCall Operator Scheduling for Satellites with Grover’s Algorithm

next chapter Portfolio Optimisation Using the D-Wave Quantum Annealer

https://www.dwavesys.com/news/d-wave-systems-sells-its-first-quantum-computing-system-lockheed-martin-corporation.

https://www.dwavesys.com/press-releases/d-wave%C2%A0announces%C2%A0d-wave-2000q-quantum-computer-and-first-system-order.

https://www.dwavesys.com/press-releases/d-wave-previews-next-generation-quantum-computing-platform.

https://support.dwavesys.com/hc/en-us/community/posts/360034852633-High-Chain-Break-Fractions.

We used the D-Wave 2000 system. Only recently, D-Wave presented the 5000 qubit version.

Andersen, J., Crainic, T.G., Christiansen, M.: Service network design with management and coordination of multiple fleets. Eur. J. Oper. Res. 193(2), 377–389 (2009)MathSciNetCrossRef

Arute, F., et al.: Quantum supremacy using a programmable superconducting processor. Nature 574(7779), 505–510 (2019)CrossRef

Booth, M., Reinhardt, S.P., Roy, A.: Partitioning optimization problems for hybrid classical/quantum execution. Technical report, D-Wave Systems (September 2017)

Cao, Y., Jiang, S., Perouli, D., Kais, S.: Solving set cover with pairs problem using quantum annealing. Sci. Rep. 6(1), 33957 (2016)CrossRef

Chapuis, G., Djidjev, H., Hahn, G., Rizk, G.: Finding maximum cliques on the d-wave quantum annealer. J. Sig. Process. Syst. 91(3–4), 363–377 (2018)

Chiscop, I., Nauta, J., Veerman, B., Phillipson, F.: A hybrid solution method for the multi-service location set covering problem. In: International Conference On Computational Science (ICCS) (2020)

Coffrin, C.J.: Challenges with chains: Testing the limits of a d-wave quantum annealer for discrete optimization. Technical report, Los Alamos National Laboratory, U.S. (2019)

De Juncker, M.A.M., Huizing, D., del Vecchyo, M.R.O., Phillipson, F., Sangers, A.: Framework of synchromodal transportation problems. ICCL 2017. LNCS, vol. 10572, pp. 383–403. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-68496-3_26CrossRef

Ding, B., Yu, J.X., Qin, L.: Finding time-dependent shortest paths over large graphs. In: Proceedings of the 11th International Conference on Extending Database Technology: Advances in Database Technology, pp. 205–216. ACM (2008)

10.

Even, S., Itai, A., Shamir, A.: On the complexity of time table and multi-commodity flow problems. In: 16th Annual Symposium on Foundations of Computer Science, SFCS 1975, pp. 184–193. IEEE (1975)

11.

Farhi, E., Goldstone, J., Gutmann, S.: A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028 (2014)

12.

Farhi, E., Goldstone, J., Gutmann, S., Sipser, M.: Quantum computation by adiabatic evolution. arXiv:quant-ph/0001106v1 (2000)

13.

Feld, S., et al.: A hybrid solution method for the capacitated vehicle routing problem using a quantum annealer. Front. ICT 6, 13 (2019)CrossRef

14.

Foster, R.C., Weaver, B., Gattiker, J.: Applications of quantum annealing in statistics. arXiv preprint arXiv:1904.06819 (2019)

15.

Glover, F., Kochenberger, G., Du, Y.: A tutorial on formulating and using QUBO models. arXiv preprint arXiv:1811.11538 (2018)

16.

Huizing, D.: General methods for synchromodal planning of freight containers and transports. Master’s thesis, Delft University of Technology, The Netherlands (2017)

17.

Jiang, S., Britt, K.A., McCaskey, A.J., Humble, T.S., Kais, S.: Quantum annealing for prime factorization. Sci. Rep. 8(1), 17667 (2018)CrossRef

18.

Johnson, M.W., et al.: Quantum annealing with manufactured spins. Nature 473(7346), 194–198 (2011)CrossRef

19.

Kalicharan, K., Phillipson, F., Sangers, A., De Juncker, M.: Reduction of variables for solving logistic flow problems. In: 2019 6th International Physical Internet Conference (IPIC) (2019)

20.

Lucas, A.: Ising formulations of many NP problems. Front. Phys. 2, 5 (2014)CrossRef

21.

McGeoch, C.C.: Adiabatic Quantum Computation and Quantum Annealing: Theory and Practice. Synthesis Lectures on Quantum Computing, vol. 5, no. 2, pp. 1–93 (2014)

22.

Mes, M.R.K., Iacob, M.E.: Synchromodal transport planning at a logistics service provider. In: Zijm, H., Klumpp, M., Clausen, U., Hompel, M. (eds.) Logistics and Supply Chain Innovation. Lecture Notes in Logistics. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-22288-2_2

23.

Neukart, F., Compostella, G., Seidel, C., Dollen, D.V., Yarkoni, S., Parney, B.: Traffic flow optimization using a quantum annealer. Front. ICT 4, 29 (2017)CrossRef

24.

Pelofske, E., Hahn, G., Djidjev, H.: Solving large minimum vertex cover problems on a quantum annealer. In: Proceedings of the 16th ACM International Conference on Computing Frontiers, CF 2019, pp. 76–84. ACM, New York (2019)

25.

Piattini, M., et al.: The Talavera manifesto for quantum software engineering and programming. In: Proceedings of the 1st QANSWER Workshop (2020)

26.

Rieffel, E.G., Venturelli, D., O’Gorman, B., Do, M.B., Prystay, E.M., Smelyanskiy, V.N.: A case study in programming a quantum annealer for hard operational planning problems. Quantum Inf. Process. 14(1), 1–36 (2014). https://doi.org/10.1007/s11128-014-0892-xCrossRefMATH

27.

van Riessen, B., Negenborn, R.R., Dekker, R.: Synchromodal container transportation: an overview of current topics and research opportunities. In: Corman, F., Voß, S., Negenborn, R.R. (eds.) ICCL 2015. LNCS, vol. 9335, pp. 386–397. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-24264-4_27CrossRef

28.

SteadieSeifi, M., Dellaert, N.P., Nuijten, W., Van Woensel, T., Raoufi, R.: Multimodal freight transportation planning: a literature review. Eur. J. Oper. Res. 233(1), 1–15 (2014)CrossRef

29.

Zweers, B.G., Bhulai, S., van der Mei, R.D.: Optimizing barge utilization in hinterland container transportation. Nav. Res. Logistics (NRL) 66(3), 253–271 (2019)MathSciNetCrossRef

Title: Multimodal Container Planning: A QUBO Formulation and Implementation on a Quantum Annealer
Authors: F. Phillipson
I. Chiscop
Publisher: Springer International Publishing
Book: Computational Science – ICCS 2021
Print ISBN: 978-3-030-77979-5

Electronic ISBN: 978-3-030-77980-1

Copyright Year: 2021
DOI: https://doi.org/10.1007/978-3-030-77980-1_3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner