Quantum computing approach in uncertain data optimization problem for vehicle routing problem
DOI:
https://doi.org/10.35335/emod.v15i3.52Keywords:
Logistics, Optimization, Quantum Computing, Uncertain Data, Vehicle Routing ProblemAbstract
This research addresses the Vehicle Routing Problem (VRP) with uncertain data and proposes a novel approach using quantum computing techniques. The problem involves optimizing vehicle routes considering uncertain customer demands, time windows, and vehicle capacities. We formulate the problem mathematically and develop an algorithmic framework to tackle it. The approach incorporates multiple scenarios based on the uncertainty distribution and selects the one with the minimum cost to optimize the vehicle routes. Through a numerical example, we demonstrate the effectiveness of the proposed approach in generating optimal routes that minimize the total distance traveled by the vehicles. The results highlight the solution quality, adaptability to uncertainty, and potential benefits in terms of cost reduction and resource utilization. While the computational efficiency of quantum computing approaches is a consideration, this research provides a promising direction for addressing uncertain optimization problems in logistics and transportation. Future research should focus on scalability and refinement of the algorithm to further enhance its applicability in real-world scenarios.
References
Abbott, A. A., Calude, C. S., Dinneen, M. J., & Hua, R. (2019). A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing. International Journal of Quantum Information, 17(05), 1950042.
Ajagekar, A. (2020). Quantum computing for process systems optimization and data analytics.
Ajagekar, A., Humble, T., & You, F. (2020). Quantum computing based hybrid solution strategies for large-scale discrete-continuous optimization problems. Computers & Chemical Engineering, 132, 106630.
Azad, T., & Hasin, M. A. A. (2019). Capacitated vehicle routing problem using genetic algorithm: a case of cement distribution. International Journal of Logistics Systems and Management, 32(1), 132–146.
Beheshtinia, M. A., Salmabadi, N., & Rahimi, S. (2021). A robust possibilistic programming model for production-routing problem in a three-echelon supply chain. Journal of Modelling in Management.
Bernardo, M., & Pannek, J. (2018). Robust solution approach for the dynamic and stochastic vehicle routing problem. Journal of Advanced Transportation, 2018.
Bickley, S. J., Chan, H. F., Schmidt, S. L., & Torgler, B. (2021). Quantum-sapiens: the quantum bases for human expertise, knowledge, and problem-solving. Technology Analysis & Strategic Management, 33(11), 1290–1302.
Braaten, S., Gjønnes, O., Hvattum, L. M., & Tirado, G. (2017). Heuristics for the robust vehicle routing problem with time windows. Expert Systems with Applications, 77, 136–147.
Cheng, C. (2020). Robust Optimization for Supply Chain Applications: Facility Location and Drone Delivery Problems. Ecole Polytechnique, Montreal (Canada).
Çimen, M., & Soysal, M. (2017). Time-dependent green vehicle routing problem with stochastic vehicle speeds: An approximate dynamic programming algorithm. Transportation Research Part D: Transport and Environment, 54, 82–98.
da Silveira, L. R., Tanscheit, R., & Vellasco, M. M. B. R. (2017). Quantum inspired evolutionary algorithm for ordering problems. Expert Systems with Applications, 67, 71–83.
Deodoro, J., Gorbanyov, M., Malaika, M., Sedik, T. S., & Peiris, S. J. (2021). Quantum Computing and the Financial System: Spooky Action at a Distance? IMF Working Papers, 2021(071).
Dogani, A., Dourandish, A., Ghorbani, M., & Shahbazbegian, M. R. (2020). A hybrid meta-heuristic for a bi-objective stochastic optimization of urban water supply system. IEEE Access, 8, 135829–135843.
Duan, J., He, Z., & Yen, G. G. (2021). Robust multiobjective optimization for vehicle routing problem with time windows. IEEE Transactions on Cybernetics, 52(8), 8300–8314.
Feng, L., Huang, Y., Zhou, L., Zhong, J., Gupta, A., Tang, K., & Tan, K. C. (2020). Explicit evolutionary multitasking for combinatorial optimization: A case study on capacitated vehicle routing problem. IEEE Transactions on Cybernetics, 51(6), 3143–3156.
Franca, L. S., Ribeiro, G. M., & Chaves, G. de L. D. (2019). The planning of selective collection in a real-life vehicle routing problem: A case in Rio de Janeiro. Sustainable Cities and Society, 47, 101488.
Goel, R., Maini, R., & Bansal, S. (2019). Vehicle routing problem with time windows having stochastic customers demands and stochastic service times: Modelling and solution. Journal of Computational Science, 34, 1–10.
Guzzetti, S., Alvarez, L. A. M., Blanco, P. J., Carlberg, K. T., & Veneziani, A. (2020). Propagating uncertainties in large-scale hemodynamics models via network uncertainty quantification and reduced-order modeling. Computer Methods in Applied Mechanics and Engineering, 358, 112626.
Hadfield, S. A. (2018). Quantum algorithms for scientific computing and approximate optimization. Columbia University.
Hannan, M. A., Lipu, M. S. H., Akhtar, M., Begum, R. A., Al Mamun, M. A., Hussain, A., Mia, M. S., & Basri, H. (2020). Solid waste collection optimization objectives, constraints, modeling approaches, and their challenges toward achieving sustainable development goals. Journal of Cleaner Production, 277, 123557.
Harikrishnakumar, R., Nannapaneni, S., Nguyen, N. H., Steck, J. E., & Behrman, E. C. (2020). A quantum annealing approach for dynamic multi-depot capacitated vehicle routing problem. ArXiv Preprint ArXiv:2005.12478.
Hu, C., Lu, J., Liu, X., & Zhang, G. (2018). Robust vehicle routing problem with hard time windows under demand and travel time uncertainty. Computers & Operations Research, 94, 139–153.
Jones, M. C. (2021). Simulation-Based Optimization Approach to Supply Chain Network Design Under Uncertainty Incorporating Tactical and Strategic Decisions. The George Washington University.
Konstantakopoulos, G. D., Gayialis, S. P., & Kechagias, E. P. (2020). Vehicle routing problem and related algorithms for logistics distribution: a literature review and classification. Operational Research, 1–30.
Koubaa, R., Bacha, S., & Smaoui, M. (2020). Robust optimization based energy management of a fuel cell/ultra-capacitor hybrid electric vehicle under uncertainty. Energy, 200, 117530.
Kuo, R. J., & Zulvia, F. E. (2017). Hybrid genetic ant colony optimization algorithm for capacitated vehicle routing problem with fuzzy demand—A case study on garbage collection system. 2017 4th International Conference on Industrial Engineering and Applications (ICIEA), 244–248.
Li, Y., Soleimani, H., & Zohal, M. (2019). An improved ant colony optimization algorithm for the multi-depot green vehicle routing problem with multiple objectives. Journal of Cleaner Production, 227, 1161–1172.
Liu, J., Tang, K., & Yao, X. (2021). Robust optimization in uncertain capacitated arc routing problems: Progresses and perspectives. IEEE Computational Intelligence Magazine, 16(1), 63–82.
Liu, Z., Li, S., & Ge, Y. (2021). A quantum computing-based numerical method of mixed-integer optimal control problems under uncertainty for alkali–surfactant–polymer flooding. Engineering Optimization, 53(3), 531–550.
Lordi, V., & Nichol, J. M. (2021). Advances and opportunities in materials science for scalable quantum computing. MRS Bulletin, 46, 589–595.
Loxton, M., Truskett, R., Scarf, B., Sindone, L., Baldry, G., & Zhao, Y. (2020). Consumer behaviour during crises: Preliminary research on how coronavirus has manifested consumer panic buying, herd mentality, changing discretionary spending and the role of the media in influencing behaviour. Journal of Risk and Financial Management, 13(8), 166.
Marsh, S., & Wang, J. B. (2020). Combinatorial optimization via highly efficient quantum walks. Physical Review Research, 2(2), 23302.
Meng, F., Ding, Y., Li, W., & Guo, R. (2019). Customer-oriented vehicle routing problem with environment consideration: two-phase optimization approach and heuristic solution. Mathematical Problems in Engineering, 2019.
Mohsin, S. A., Younes, A., & Darwish, S. M. (2021). Dynamic cost ant colony algorithm to optimize query for distributed database based on quantum-inspired approach. Symmetry, 13(1), 70.
Munari, P., Moreno, A., De La Vega, J., Alem, D., Gondzio, J., & Morabito, R. (2019). The robust vehicle routing problem with time windows: compact formulation and branch-price-and-cut method. Transportation Science, 53(4), 1043–1066.
Mungwattana, A., Soonpracha, K., & Janssens, G. K. (2019). A REAL-WORLD CASE STUDY OF A VEHICLE ROUTING PROBLEM UNDER UNCERTAIN DEMAND. International Journal for Traffic & Transport Engineering, 9(1).
Nembrini, R., Ferrari Dacrema, M., & Cremonesi, P. (2021). Feature selection for recommender systems with quantum computing. Entropy, 23(8), 970.
Osaba, E., Villar-Rodriguez, E., Oregi, I., & Moreno-Fernandez-de-Leceta, A. (2021). Hybrid quantum computing-tabu search algorithm for partitioning problems: preliminary study on the traveling salesman problem. 2021 IEEE Congress on Evolutionary Computation (CEC), 351–358.
Patti, T. L., Kossaifi, J., Anandkumar, A., & Yelin, S. F. (2021). Nonlinear quantum optimization algorithms via efficient ising model encodings. ArXiv.
Ram, P. K., Bhui, N., & Kuila, P. (2020). Gene selection from high dimensionality of data based on quantum inspired genetic algorithm. 2020 11th International Conference on Computing, Communication and Networking Technologies (ICCCNT), 1–5.
Shang, C., & You, F. (2019). A data-driven robust optimization approach to scenario-based stochastic model predictive control. Journal of Process Control, 75, 24–39.
Shaydulin, R., Ushijima-Mwesigwa, H., Negre, C. F. A., Safro, I., Mniszewski, S. M., & Alexeev, Y. (2019). A hybrid approach for solving optimization problems on small quantum computers. Computer, 52(6), 18–26.
Shi, Y., Zhou, Y., Ye, W., & Zhao, Q. Q. (2020). A relative robust optimization for a vehicle routing problem with time-window and synchronized visits considering greenhouse gas emissions. Journal of Cleaner Production, 275, 124112.
Shone, R., Glazebrook, K., & Zografos, K. G. (2021). Applications of stochastic modeling in air traffic management: Methods, challenges and opportunities for solving air traffic problems under uncertainty. European Journal of Operational Research, 292(1), 1–26.
Talouki, R. Z., Javadian, N., & Movahedi, M. M. (2021). Optimization and incorporating of green traffic for dynamic vehicle routing problem with perishable products. Environmental Science and Pollution Research, 28, 36415–36433.
Vyskočil, T., Pakin, S., & Djidjev, H. N. (2019). Embedding inequality constraints for quantum annealing optimization. Quantum Technology and Optimization Problems: First International Workshop, QTOP 2019, Munich, Germany, March 18, 2019, Proceedings 1, 11–22.
Wang, Y., Assogba, K., Fan, J., Xu, M., Liu, Y., & Wang, H. (2019). Multi-depot green vehicle routing problem with shared transportation resource: Integration of time-dependent speed and piecewise penalty cost. Journal of Cleaner Production, 232, 12–29.
Wu, X., & Wu, S. (2017). An elitist quantum-inspired evolutionary algorithm for the flexible job-shop scheduling problem. Journal of Intelligent Manufacturing, 28, 1441–1457.
Yang, F., Dai, Y., & Ma, Z.-J. (2020). A cooperative rich vehicle routing problem in the last-mile logistics industry in rural areas. Transportation Research Part E: Logistics and Transportation Review, 141, 102024.
Yang, Z.-C., Rahmani, A., Shabani, A., Neven, H., & Chamon, C. (2017). Optimizing variational quantum algorithms using pontryagin’s minimum principle. Physical Review X, 7(2), 21027.
Zhang, H., Zhang, Q., Ma, L., Zhang, Z., & Liu, Y. (2019). A hybrid ant colony optimization algorithm for a multi-objective vehicle routing problem with flexible time windows. Information Sciences, 490, 166–190.
Zhang, S., Mu, D., & Wang, C. (2020). A solution for the full-load collection vehicle routing problem with multiple trips and demands: an application in Beijing. IEEE Access, 8, 89381–89394.
Downloads
Published
How to Cite
Issue
Section
License
Copyright (c) 2021 Patrisia Teresa Marsoit, Liu Wang Zhang, Deodoro Lakonde, Firta Sari Panjaitan
This work is licensed under a Creative Commons Attribution 4.0 International License.
