D-Wave Implementation of Quantum Annealing for Optimal Resource Allocation in Disaster Response Operation of Marikina City
Main Article Content
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
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
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.