The advantages of the increasing usage of mobile devices that operate under the multihoming scheme are changing the communications world drastically. Therefore, next generation networks operators have the challenging task to distribute connections of mobile devices efficiently over their access networks, creating a big heterogeneous wireless network for telecommunications. We present a mixed integerlinear programming (MILP) model to balance the load of multiple services over wireless networks taking into account three key indicators: connection loads of access networks, connection costs, and battery consumption of connections. To solve the multi-objective problem, we propose a multi-objective Tabu Search procedure that is capable to find non-supported solutions in the online efficient set. To test the performance of our multi-objective Tabu Search, we tested it over four instances of the literature. In the first instance, a small instance, our procedure finds the true efficient set of solutions. For the other three instances, large instances with over a thousand mobile devices, our procedure finds good online efficient sets of solutions in less than 30 seconds. Finally, using appropriate multi-objective metrics, we compare the results of our multi-objective Tabu Search against the results of a state of the art multi-objective genetic algorithm in the literature for the same problem, outperforming the genetic algorithm in every instance tested.