In Location-Based Services (LBSs), the service is provided based on the users' locations through location determination and mobility anticipation. Most of the current location prediction research focuses on generalised location models, where the geographic extent is divided into regular shape cells. One such technique is the Mobility Prediction based on an Ant System (MPAS), which depends on the earlier Ant Colony Optimisation (ACO) that suffers from problems such as search stagnation and pheromone update. In this paper, a New Routing Area Displacement Prediction (NRADP) is introduced, which works on the routing-area level instead of the cell level. Experimental results show that the NRADP offers improved effectiveness, higher prediction rate, and a reduced search stagnation ratio in comparison with the MPAS.