D-Wave Implementation of Quantum Annealing for Optimal Resource Allocation in Disaster Response Operation of Marikina City

Main Article Content

Allyza Ruth Cadeliña
Moris Assanty Cuevas
Marselean Kallos
Morris John Montemayor
Ronald Jay Uy
Joshua Benjamin Rodriguez
Orland Tubola

Abstract

Quantum computing shows a positive approach for addressing optimization challenges in NP-hard problems such as the vehicle routing problem (VRP). This study focuses on improving the efficiency of disaster response operations by localizing the application of D-wave quantum annealing in Marikina City. This study uses the Solution Partitioning Solver (SPS) and the Quadratic Unconstrained Binary Optimization (QUBO) formulation to convert the VRP into an equation that can be solved using quantum annealing. The study demonstrates that quantum computing effectively distributes resources during emergency response operations and improves overall operational efficiency. In determining the most effective route for each vehicle, the D-wave Leap API and QUBO representation compute the distances traveled by each vehicle. These findings contribute to the practical applications of quantum computing to revolutionize various fields, including disaster management. Implementing D-wave quantum annealing in Marikina City shows relevance for future advancements in optimizing resource allocation and improving disaster response operations.

Article Details

How to Cite
[1]
A. R. Cadeliña, “D-Wave Implementation of Quantum Annealing for Optimal Resource Allocation in Disaster Response Operation of Marikina City”, ECTI-CIT Transactions, vol. 18, no. 1, pp. 24–33, Jan. 2024.
Section
Research Article

References

F. Andrei, “Quantum Computing for Optimization Problems — Solving the Knapsack Problem,” Medium, Jan. 16, 2023. [Online]. Available: https://towardsdatascience.com

E. Alampay, C. Cabotaje, L. Angeles, M. Loriza, Odulio and J. Quebral, “Local GovernmentVolunteer Collaboration for Disaster Risk Management in the Philippines,” Philippine Journal of Public Administration, vol. 63, no. 2, 2019.

H. Xu, S. Dasgupta, A. Pothen and A. Banerjee, “Dynamic Asset Allocation with Expected Shortfall via Quantum Annealing,”Entropy, vol. 25, no. 3, pp. 541, 2023.

J. Dargan, “D-Wave Quantum Annealer Practical Usage in 2023,” The Quantum Insider, May 05, 2023. [Online]. Available: https://thequantuminsider.com

T. Huang, Y. Zhu, R. S. M. Goh and T. Luo, “When quantum annealing meets multitasking: Potentials, challenges and opportunities,” Array, vol. 17, pp. 100282, Mar. 2023.

P. Date, R. Patton, C. Schuman and T. Potok, “Efficiently embedding QUBO problems on adiabatic quantum computers,” Quantum Information Processing, vol. 18, no. 4, Mar. 2019.

D. Venturelli, S. Mandr`a, S. Knysh, B. O’Gorman, R. Biswas and V. Smelyanskiy, “Quantum Optimization of Fully Connected Spin Glasses,” Physical Review X, vol. 5, no. 3, Sep. 2015.

S. Harwood, C. Gambella, D. Trenev, A. Simonetto, D. Bernal and D. Greenberg, “Formulating and Solving Routing Problems on Quantum Computers,” in IEEE Transactions on Quantum Engineering, vol. 2, pp. 1-17, 2021.

M. Alzaqebah, S. Abdullah and S. Jawarneh, “Modified artificial bee colony for the vehicle routing problems with time windows,” SpringerPlus, vol. 5, no. 1, Aug. 2016.

B. Kallehauge, N. Boland and O. B. G. Madsen, “Path inequalities for the vehicle routing problem with time windows,” Networks, vol. 49, no. 4, pp. 273–293, 2007.

C. Truden, K. Maier and P. Armbrust, “Decomposition of the vehicle routing problem with time windows on the time dimension,” Transportation Research Procedia, vol. 62, pp. 131–138, 2022.

J. Pelik ́an, “A Modification of the Vehicle Routing Problem,” Hradec Economic Days (HED), Mar. 2021.

S.-C. Lo and Y.-L. Chuang, “Vehicle Routing Optimization with Cross-Docking Based on an Artificial Immune System in Logistics Management,” Mathematics, vol. 11, no. 4, p. 811, Feb. 2023.

“Solving Problems with Quantum Samplers — D-Wave System Documentation documentation,” docs.dwavesys.com. [Online]. Available: https://docs.dwavesys.com

M. Borowski et al., “New Hybrid Quantum Annealing Algorithms for Solving Vehicle Routing Problem,” International Conference on Computational Science Computational Science – ICCS 2020, Springer, vol. 12142 pp. 546–561, Jun. 2020,

P. Gora, “Solving Vehicle Routing Problems using Quantum Computing,” 2022. Accessed: Jun. 03, 2023. [Online]. Available: https://www. informatyka.agh.edu.pl/

D-wave hybrid — dwave-system 1.10.0 documentation, https://docs.ocean.dwavesys.com/en/latest/docs_hybrid/intro/overview. html.