An on-demand bus is like a shared taxi that operates only when riders want to travel between the origin and destination locations. It offers many advantages over fixed-route buses, but the riders are bothered by the need to tediously enter such data as origins, destinations, and deadlines. A location recommendation system that predicts such data would help riders during the reservation process and help target potential riders when buses are idle. In this paper, a general and scalable framework for such location recommendation algorithms is presented. It is based on users' location histories and spatio-temporal correlations among the locations by combining prediction methods of the collaborative filtering algorithms, which are widely used in e-commerce, with a popular method in data mining called link propagation. Experiments on real-world data demonstrate that the accuracy of recommendations with the spatio-temporal information is better than those without. © 2011 Authors.