A Heuristic Algorithm for Rebalancing Large-scale Bike Sharing Systems using Multiple Trucks

City bikes and bike sharing systems (BSSs) are one solution to reducing traffic-related CO₂ emissions. These systems feature a multitude of bike stations scattered around a city where users can borrow bikes from one station and return them to the same or a different station. However, this action may create an unbalanced system, namely, some stations will have excess bikes and other with a low number. In this paper, the authors propose a solution to address this issue and satisfy expected demand patterns. They unveil an algorithm that provides a delivery truck with a road to follow. The truck will go from one station to another and satisfy individual station demands. Achieving this objective in an optimal manner (i.e., finding the shortest Hamiltonian cycle) is an NP-hard problem. However, for small instances, an exact solution can be obtained. The heuristic algorithm presented can deliver optimal and/or near optimal solutions at substantially lower computational costs, eventhough the algorithm is not parallel and the different subtours are solved in a sequential manner. It has three steps. The first step consists of dividing a large BSS network into “p” subnetworks, where p is also the number of available trucks. Each truck will serve a subnetwork. Then the redistribution within each subnetwork is modeled as a cooperative game and the deferred acceptance algorithm is used to construct a good initial tours. Finally, an improvement to the tours is performed using the 2-opt algorithm. The proposed algorithm was tested using large benchmark instances. The results show promising performance in terms of solution quality and computational time. The proposed algorithm can be used for real-time BSS re-balancing given its computational efficiency.

  • Supplemental Notes:
    • This paper was sponsored by TRB committee ANF20 Standing Committee on Bicycle Transportation.
  • Corporate Authors:

    Transportation Research Board

  • Authors:
    • Elhenawy, Mohammed
    • Bichiou, Youssef
    • Rakha, Hesham
  • Conference:
  • Date: 2019


  • English

Media Info

  • Media Type: Digital/other
  • Features: Figures; References; Tables;
  • Pagination: 16p

Subject/Index Terms

Filing Info

  • Accession Number: 01697835
  • Record Type: Publication
  • Report/Paper Numbers: 19-00239
  • Files: TRIS, TRB, ATRI
  • Created Date: Dec 7 2018 9:39AM