Quantum-Inspired Vehicle Routing Scheme for Rebalancing in Bike Sharing Systems
Chia‐Ho Ou, Chih-Yu Chen, Chu‐Fu Wang, Ching‐Ray Chang · SPIN · 2023
Bike sharing systems (BSSs) are gaining popularity worldwide, and with the rise of global warming, they have become even more critical for reducing greenhouse gas emissions in cities. One of the key operations of a BSS is rebalancing, which involves maintaining the number of bikes at each station to a target value by arranging vehicle loading and unloading operations. This paper proposes a quantum-inspired vehicle routing scheme to solve the rebalancing problem in BSSs. The problem is modeled as a variant of the Traveling Salesman Problem (TSP), which is an NP-hard problem that is computationally difficult to solve. The proposed approach formulates the problem as a Quadratic Unconstrained Binary Optimization (QUBO) model, which can be solved using a digital annealer. The proposed scheme’s performance is evaluated on the Fujitsu digital annealer and compared with the proposed greedy algorithm. The experimental results show that the proposed approach outperforms the greedy algorithm in finding a better feasible solution.