Improving the tracking areas (TA) configuration over time to reduce signaling overhead is vital for location management of Long Term Evolution networks. The user location and mobility patterns have the tendency to change over time, and consequently the TA layout needs to be revised. A TA reconfiguration would cause service interruption and "cost". Hence there will always be a tradeoff between the total signaling overhead and the reconfiguration cost. In this paper a genetic algorithm together with local search are applied to this bi-objective problem. Unlike previous methods, our approach does not need to weight together the two objective functions. Instead, the algorithm is designed to deliver various pareto-optimal solutions in a single run. Computational experiments are presented for a realistic TA planning scenario of Lisbon city. The results illustrate the ability of the approach to address the primary concern in decision making of an operator - benefit versus cost, by means of providing multiple reconfiguration choices with various levels of trade-off between the two factors.