Inventory rebalancing and vehicle routing in bike sharing systems

Bike sharing systems have been installed in many cities around the world and are increasing in popularity. A major operational cost driver in these systems is rebalancing the bikes over time such that the appropriate number of bikes and open docks are available to users. The authors combine two aspects that have previously been handled separately in the literature: determining service level requirements at each bike sharing station, and designing (near-)optimal vehicle routes to rebalance the inventory. Since finding provably optimal solutions is practically intractable, the authors propose a new cluster-first route-second heuristic, in which a polynomial-size Clustering Problem simultaneously considers the service level feasibility and approximate routing costs. Extensive computational results on real-world data from Hubway (Boston, MA) and Capital Bikeshare (Washington, DC) are provided, which show that the heuristic outperforms a pure mixed-integer programming formulation and a constraint programming approach.

Language

  • English

Media Info

Subject/Index Terms

Filing Info

  • Accession Number: 01655895
  • Record Type: Publication
  • Files: TRIS
  • Created Date: Feb 28 2017 11:50AM