Centralized Routing for Bike-sharing Systems

Bike-sharing systems, where people rent bikes typically for last-mile commuting, has gained great popularity in recent years due to the rapid development of mobile networks. Station-based bike-sharing systems have been widely studied in both academia and industry, where problems like bike rental demand prediction and bike redistribution have been discussed. In contrast, not much attention has been paid to the routing algorithms for shared-bike riders. A routing solution consists of two stations, suggesting where to rent and return a bike. Existing routing works generally target a single rider. However, during the rush hours, there often exist routing requests from multiple riders simultaneously, which has not been carefully investigated before. In this paper, we study the routing problem for multiple shared-bike riders with hardness analyses and approximation algorithms. The challenge lies in how to allocate the limited resources (bikes/docks at the stations) among the competing riders. We show that this problem is NP-hard, and thus propose two heuristics. We also propose an optimization technique on routing plan generations, to improve the efficiency of the algorithms. Extensive experiments have been carried out to verify the performance of the proposed algorithms. It turns out that the greedy-based routing algorithm, which has an approximation factor of 1/3, is both effective and efficient.