Journal of Industrial and Systems Engineering

Journal of Industrial and Systems Engineering

Quantum Modeling of the Dynamic Ride-sharing Problem

Document Type : conference paper

Authors
Erfan Amani Bani
Kourosh Eshghi
Department of Industrial Engineering, Sharif University of Technology, Tehran, Iran
Abstract
Mathematical modeling and the subsequent development of optimization algorithms for problems have been the core focus of operations research scientists. However, the challenges of solving complex models within an acceptable time frame have consistently fostered creativity in this field. Quantum computing has been proposed as an alternative to binary computing for several decades. In recent years, scientists and researchers in operations research have paid significant attention to utilizing and integrating this logic with optimization. Specifically, quantum variants of many optimization algorithms have been developed; however, more focus needs to be placed on modeling optimization problems using quantum variables. In this paper, a practical problem, the dynamic ride-sharing problem, is redefined and subsequently modeled using quantum variables. The resulting model, defined based on quantum variables, is fully compatible with quantum algorithms.
Keywords
Dynamic ride-sharing problem
quantum computing
quantum optimization
[1] R. S. Sutor. Dancing with Qubits: How quantum computing works and how it can change the world. Packt Publishing Ltd, 2019.
[2] A. Di Febbraro, E. Gattorna, and N. Sacco. Optimization of dynamic ridesharing systems. Transportation research record, 2359(1):44–50, 2013.
[3] H. N. Psaraftis. A dynamic programming solution to the single vehicle many-to-many immediate request dial-a-ride problem. Transportation
        Science, 1980.
[4] W. B. Powell. A stochastic formulation of the dynamic assignment problem, with an application to truckload motor carriers. Transportation
        Science, 1996.
[5] M. Z. Spivey and W. B. Powell. The dynamic assignment problem. Transportation Science, 2004.
[6] G. Berbeglia, J. Cordeau, and G. Laporte. Dynamic pickup and delivery problems. European Journal of Operational Research, 2010.
[7] M. Schilde, K. F. Doerner, and R. F. Hartl. Metaheuristics for the dynamic stochastic dial-a-ride problem with expected return transports.
        Computers Operations Research, 2011.
[8] A. Tafreshian and N. Masoud. Trip-based graph partitioning in dynamic ridesharing. Transportation Research Part C-emerging Technologies,
        2020.
[9] A. G. H. Kek, Q. Meng, R. L. Cheu, and C. H. Fung. A decision support system for vehicle relocation operations in carsharing systems.
        Transportation Research Part E-logistics and Transportation Review, 2009.
[10] A. Najmi, D. Rey, and T. H. Rashidi. Novel dynamic formulations for real-time ride-sharing systems. Transportation Research Part E-logistics
        and Transportation Review, 2017.
[11] N. Masoud and R. Jayakrishnan. A decomposition algorithm to solve the multi-hop peer-to-peer ride-matching problem. Transportation
        Research Part B-methodological, 2017.
[12] N. Masoud, R. Lloret-Batlle, and R. Jayakrishnan. Using bilateral trading to increase ridership and user permanence in ridesharing systems.
        Transportation Research Part E-logistics and Transportation Review, 2017.
[13] N. Masoud and R. Jayakrishnan. A real-time algorithm to solve the peer-to-peer ride-matching problem in a flexible ridesharing system.
        Transportation Research Part B-methodological, 2017.
[14] M. Tamannaei and I. Irandoost. Carpooling problem: A new mathematical model, branch-and-bound, and heuristic beam search algorithm.
        Journal of Intelligent Transportation Systems, 2019.
[15] A. Lee and M. W. P. Savelsbergh. Dynamic ridesharing: Is there a role for dedicated drivers? Transportation Research Part B-methodological,
        2015.
[16] M. Stiglic, N. Agatz, M. W. P. Savelsbergh, and M. Gradišar. Making dynamic ride-sharing work: The impact of driver and rider flexibility.
        Transportation Research Part E-logistics and Transportation Review, 2016.
[17] D. Wang, Q. Wang, Y. Yin, and T. Cheng. Optimization of ride-sharing with passenger transfer via deep reinforcement learning.
        Transportation Research Part E: Logistics and Transportation Review, 2023.
[18] P. He, J. G. Jin, and F. Schulte. The flexible airport bus and last-mile ride-sharing problem: Math-heuristic and metaheuristic approaches.
        Transportation Research Part E: Logistics and Transportation Review, 2024.
[19] A. Narayanan and M. Moore. Quantum-inspired genetic algorithms. Proceedings of IEEE International Conference on Evolutionary
        Computation, 1996.
[20] K. Han, K.-H. Han, and J.-H. Kim. Genetic quantum algorithm and its application to combinatorial optimization problem. Proceedings of the
        2000 Congress on Evolutionary Computation. CEC00 (Cat. No.00TH8512), 2000.
[21] H. Teng, B. Yang, and B. Zhao. A new mutative scale chaos optimization quantum genetic algorithm. Chinese Control and Decision
        Conference, 2008.
[22] S. Zhao, G. Xu, T. Tao, and L. Liang. Real-coded chaotic quantum-inspired genetic algorithm for training of fuzzy neural networks. Computers
        Mathematics With Applications, 2009.
[23] J. Sun, B. Feng, and W. Xu. Particle swarm optimization with particles having quantum behavior. Proceedings of the 2004 Congress on
        Evolutionary Computation (IEEE Cat. No.04TH8753), 2004.
[24] J. Liu, W. Xu, and J. Sun. Quantum-behaved particle swarm optimization with mutation operator. IEEE International Conference on Tools with
        Artificial Intelligence, 2005.
[25] G. Nannicini. Fast quantum subroutines for the simplex method. Operations Research, 72(2):763–780, 2024.
[26] Z. Zhao, L. Fan, and Z. Han. Hybrid quantum benders’ decomposition for mixed-integer linear programming. In 2022 IEEE Wireless
        Communications and Networking Conference (WCNC), pages 2536–2540. IEEE, 2022.
[27] W. da Silva Coelho, L. Henriet, and L.-P. Henry. Quantum pricing-based column-generation framework for hard combinatorial problems.
        Physical Review A, 107(3):032426, 2023.
[28] I. Kerenidis and A. Prakash. A quantum interior point method for lps and sdps. ACM Transactions on Quantum Computing, 2020.
[29] A. Syrichas and A. Crispin. Large-scale vehicle routing problems: Quantum annealing, tunings and results. Computers Operations Research,
        2017.
[30] Z. Wang and J. Dai. Separated vehicle scheduling optimisation for container trucking transportation based on hybrid quantum evolutionary
        algorithm. International Journal of Computing Science and Mathematics, 2017.
[31] H. Irie, G. Wongpaisarnsin, M. Terabe, A. Miki, and S. Taguchi. Quantum annealing of vehicle routing problem with time, state and capacity.
        QTOP@NetSys, 2019.
[32] S. M. Harwood, C. Gambella, D. Trenev, A. Simonetto, D. E. Bernal, and D. Greenberg. Formulating and solving routing problems on
        quantum computers. IEEE Transactions on Quantum Engineering, 2021.
[33] D. Fitzek, T. Ghandriz, L. Laine, M. Granath, and A. F. Kockum. Applying quantum approximate optimization to the heterogeneous vehicle
        routing problem. Scientific Reports, 2021.
[34] S. Chiew, K. Poirier, R. Mishra, U. Bornheimer, E. Munro, S. H. Foon, C. W. Chen, W. Lim, and C. Nga. Multiobjective optimization and
        network routing with near-term quantum computers. IEEE Transactions on Quantum Engineering, 2023.
[35] P. W. Shor. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review, 41(2):303–332,
        1999.
[36] R. M. Karp. Reducibility among combinatorial problems. Springer, 2010.
[37] J. A. De Loera, R. Hemmecke, S. Onn, U. Rothblum, and R. Weismantel. Convex integer maximization via graver bases. Journal of Pure and
        Applied Algebra, 213(8):1569–1577, 2009.
[38] H. Alghassi, R. Dridi, and S. Tayur. Graver bases via quantum annealing with application to non-linear integer programs. arXiv preprint
        arXiv:1902.04215, 2019.
[39] A. Karahalios, S. Tayur, A. Tenneti, A. Pashapour, F. S. Salman, and B. Yıldız. A quantum-inspired bilevel optimization algorithm for the first
        responder network design problem. INFORMS Journal on Computing, 37(1):172–188, 2025.