Solving Vehicle-Sharing Problems Using Grover Algorithm

Abstract

Optimization is central to urban mobility, where ride-sharing platforms must continuously match passengers with vehicles under complex constraints such as destination compatibility, cost, route efficiency, and acceptable waiting time. Classical exact methods like integer programming scale poorly as the problem size grows and struggle with highly dynamic inputs such as fluctuating demand, travel times, and vehicle capacities. Quantum computing offers an alternative paradigm: by exploiting superposition and interference, quantum search algorithms can explore large combinatorial spaces more efficiently than classical brute-force search. This study presents a proof-of-concept quantum formulation of a foundational ride-sharing assignment problem and investigates the use of Grover’s search algorithm. The model considers five unique passengers (Mehmet, Aytuğ, Filiz, Alara, and Ayliz) and two vehicles. Each passenger must be assigned to one of the two vehicles, subject to a balanced distribution objective (either a 3–2 or 2–3 split) and individual feasibility constraints. The problem is encoded on a 5-qubit quantum register, where the state of each qubit (|0⟩ or |1⟩) denotes assignment to Vehicle A or Vehicle B, mapping the full 2⁵ = 32-state Hilbert space to all possible allocations. A Grover oracle is designed to “mark” all assignments that satisfy the balanced-split and feasibility conditions by applying a phase flip to those computational basis states. The algorithm is implemented and simulated using IBM’s Qiskit framework. The results show that, after two Grover iterations, the total probability of measuring one of the ten valid “balanced” states increases from 31.25% to over 95%, in line with the expected quadratic speed-up of Grover’s algorithm over classical exhaustive search, which requires O(N) evaluations for N = 32 states. Although intentionally simplified—excluding realistic factors such as travel times, traffic, capacities, and time windows—this work demonstrates that a vehicle-sharing assignment problem can be cast as a quantum search task. Future work will focus on scaling to larger instances, incorporating richer operational constraints, and exploring quantum-classical hybrid approaches for real-world logistics optimization.