This letter considers routing in delay tolerant networks whereby nodes have semi-predictable mobility patterns within a time period. We propose a mobility-based routing protocol (MBRP) where nodes construct a space-time graph dynamically. As the space-time graph may be incomplete, MBRP presents a heuristic that evaluates encountered nodes based on their recorded mobility patterns in order to disseminate a finite number of bundle replicas. Simulation results, over a service quality metric comprising of delivery, delay and overhead, show that MBRP achieves up to 105 % improvement as compared to four well-known routing protocols. Finally, MBRP is capable of achieving 50 % of the performance attained by the optimal algorithm, whereby all nodes are preloaded with a space-time graph.