Online Trip Planning for Public Bike Systems

Public Bike System (PBS) not only provides convenient travel service but also alleviates the last-mile problem. With the increasing awareness of environmental protection and green commuting, people prefer to use the public bike as transportation for short-distance travel. However, the explosion of users in PBS leads to new congestion problems. To relieve the pressure of PBS, there are many types of research on system prediction, operation, and trip planning. However, there is few work focusing on the online trip planning problem. To study the case, we propose an Online Matching Trip Planning algorithm (OMTP), and we prove the theoretical lower bound of OMTP is 1 - 1/e. And then, we consider the short-term conflicts among users and design an Online Group Trip Planning algorithm (OGTP). We design two kinds of experiments- Generated Data Based and Real Data Based. In the generated data based experiment, we reveal the impact of different parameters with the generated trip data. In the real data based experiment, we validate our proposed algorithms with the real trip data set in New York City. The results show that OMTP and OGTP save time per trip on average.