Many cities around the world are making investments in innovative public transportation infrastructure. Bike-sharing systems (BSS) are one example of this. One key recurring BSS operation problem is the rebalancing of bikes at regular intervals. This redistribution of bikes from full stations to empty stations is required to meet expected demand patterns. Rebalancing entails finding the shortest Hamiltonian cycle in a graph that has the minimal residual. This is an NP-hard problem, and there are a number of algorithms that can be used to find optimal tours, but none are feasible for large instances, since they all grow exponentially. In this paper, we propose a new rebalancing algorithm based on the deferred acceptance algorithm, a well-known game theory algorithm consisting of two phases: tour construction and tour improvement. The proposed algorithm models the rebalancing problem as two disjoint sets of players. Each player in these sets has their own objective function, which is used to build the preference list for players on the other side. Experimental results for the proposed algorithm are promising.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A heuristic for rebalancing bike sharing systems based on a deferred acceptance algorithm


    Contributors:


    Publication date :

    2017-06-01


    Size :

    355965 byte




    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Smart Rebalancing for Bike Sharing Systems using Quantum Approximate Optimization Algorithm

    Harikrishnakumar, Ramkumar / Nannapaneni, Saideep | IEEE | 2021


    Dockless Bike-Sharing Rebalancing Problem with Simultaneous Faulty Bike Recycling

    Usama, Muhammad / Zahoor, Onaira / Bao, Qiong et al. | ASCE | 2019


    Study on Bike Sharing Rebalancing: Evidence from Kunming

    Yin, Anteng / Ning, Bojin / Wang, Yeqin | ASCE | 2020


    Study on Bike Sharing Rebalancing: Evidence from Kunming

    Yin, Anteng / Ning, Bojin / Wang, Yeqin | TIBKAT | 2021


    Rebalancing Bike Sharing Systems under Uncertainty using Quantum Bayesian Networks

    Harikrishnakumar, Ramkumar / Borujeni, Sima E. / Ahmad, Syed Farhan et al. | IEEE | 2021