Mobile networks have faced rapid increase in the number of mobile users and the solution for supporting the growing population is to reduce the cell sizes and to increase the bandwidth reuse. This will cause the number of location management operations and call deliveries to increase significantly, and result in high signaling overhead. We focus on minimizing this overhead, by efficient Location Area Planning (LAP). In this paper we seek to determine the location areas to achieve the minimization of the registration cost, constrained by the paging cost. For that we propose a simulated annealing algorithm, which is applied on a basic Location Area partition of cells formed by a greedy algorithm. We used our realistic mobile environment simulator to generate input (cell changing and incoming call statistics) for our algorithm, and by comparing the values of the registration cost function we recognized that significant reduction was achieved in the amount of the signaling traffic.