Journal of Industrial and Systems Engineering

Journal of Industrial and Systems Engineering

A Novel Hybrid Quantum-Enhanced Approach to Solve the Complex Last-Mile Delivery Problem with Mobile Hubs, Roaming Delivery, and Crowd Shippers

Document Type : conference paper

Authors
Sadjad Khalesi
Mohammad Reza Akbari
Moslem Habibi
Industrial engineering department, Sharif university of technology, Tehran, Iran
Abstract
This paper presents the Hybrid Quantum-Enhanced Simulated Annealer (QSA), a novel quantum-classical algorithm for optimizing complex last-mile delivery problems. Unlike traditional search-based methods like Variable Neighborhood Search (VNS) and Adaptive Large Neighborhood Search (ALNS), QSA integrates quantum exploration with classical optimization to enhance solution quality and efficiency. Computational experiments using the Qiskit quantum simulator (up to 20 qubits) and IBM Quantum Platform (up to 50 qubits) show that QSA outperforms VNS and ALNS, achieving near-optimal solutions in just 3 iterations versus 500 for traditional methods. This highlights QSA’s potential for large-scale combinatorial optimization. While quantum hardware remains limited, the study demonstrates the transformative promise of quantum computing in logistics, paving the way for future advancements in hybrid methodologies.
Keywords
Complex Urban logistics
Quantum Simulated Annealing
Local Search Algorithm
IBM Quantum Platform
Qiskit Quantum Simulator
[1]        F. Arute et al., ‘Quantum supremacy using a programmable superconducting processor’, Nature, vol. 574, no. 7779, pp. 505–510, 2019.
[2]        M. Streif, S. Yarkoni, A. Skolik, F. Neukart, and M. Leib, ‘Beating classical heuristics for the binary paint shop problem with the quantum approximate optimization algorithm’, Phys Rev A  (Coll Park), vol. 104, no. 1, p. 012403, 2021.
[3]        S. Yarkoni, E. Raponi, T. Bäck, and S. Schmitt, ‘Quantum annealing for industry applications: Introduction and review’, Reports on Progress in Physics, vol. 85, no. 10, p. 104001, 2022.
[4]        R. Harikrishnakumar, S. Nannapaneni, N. H. Nguyen, J. E. Steck, and E. C. Behrman, ‘A quantum annealing approach for dynamic multi-depot capacitated vehicle routing problem’, arXiv preprint arXiv:2005.12478, 2020.
[5]        M. Borowski et al., ‘New hybrid quantum annealing algorithms for solving vehicle routing problem’, in International Conference on Computational Science, Springer, 2020, pp. 546–561.
[6]        E. Osaba, E. Villar-Rodriguez, and A. Asla, ‘Solving a real-world package delivery routing problem using quantum annealers’, Sci Rep, vol. 14, no. 1, p. 24791, 2024.
[7]        S. Feld et al., ‘A hybrid solution method for the capacitated vehicle routing problem using a quantum annealer’, Frontiers in ICT, vol. 6, p. 13, 2019.
[8]        S. J. Weinberg, F. Sanches, T. Ide, K. Kamiya, and R. Correll, ‘Supply chain logistics with quantum and classical annealing algorithms’, Sci Rep, vol. 13, no. 1, p. 4770, 2023.
[9]        K. Srinivasan, S. Satyajit, B. K. Behera, and P. K. Panigrahi, ‘Efficient quantum algorithm for solving travelling salesman problem: An IBM quantum experience’, arXiv preprint arXiv:1805.10928, 2018.
[10]      A. Abbas et al., ‘Challenges and opportunities in quantum optimization’, Nature Reviews Physics, pp. 1–18, 2024.
[11]      T. Peng, A. W. Harrow, M. Ozols, and X. Wu, ‘Simulating large quantum circuits on a small quantum computer’, Phys Rev Lett, vol. 125, no. 15, p. 150504, 2020.
[12]      A. Lowe et al., ‘Fast quantum circuit cutting with randomized measurements’, Quantum, vol. 7, p. 934, 2023.
[13]      S. Sinno et al., ‘Performance of Commercial Quantum Annealing Solvers for the Capacitated Vehicle Routing Problem’, arXiv preprint arXiv:2309.05564, 2023.
[14]      L. S. Herzog et al., ‘Improving Quantum and Classical Decomposition Methods for Vehicle Routing’, arXiv preprint arXiv:2404.05551, 2024.
[15]      F. Sanches, S. Weinberg, T. Ide, and K. Kamiya, ‘Short quantum circuits in reinforcement learning policies for the vehicle routing problem’, Phys Rev A  (Coll Park), vol. 105, no. 6, p. 062403, 2022.
[16]      V. V Dixit and C. Niu, ‘Quantum computing for transport network design problems’, Sci Rep, vol. 13, no. 1, p. 12267, 2023.
[17]      F. Neukart, G. Compostella, C. Seidel, D. Von Dollen, S. Yarkoni, and B. Parney, ‘Traffic flow optimization using a quantum annealer’, Frontiers in ICT, vol. 4, p. 29, 2017.
[18]      B. E. Gillett and L. R. Miller, ‘A heuristic algorithm for the vehicle-dispatch problem’, Oper Res, vol. 22, no. 2, pp. 340–349, 1974.
[19]      D. Reyes, M. Savelsbergh, and A. Toriello, ‘Vehicle routing with roaming delivery locations’, Transp Res Part C Emerg Technol, vol. 80, pp. 71–91, 2017.