The telco operators face up to challenges related to the need of ensuring a quality of service to the user in a planning, maintenance and resource allocation in their complex networks. These challenges are directly related with the need to ensure an user’s service with a good level of quality in a highly dynamic environment in terms of changes in the radio access technologies, growth in the number of mobile users, technical requirements of the new services and applications, and the possibility to connect to different networks at the same time, among others. In this paper, we address the problem of the user’s service allocation into the different feasible networks in order to reduce the network overloading. We present a multihoming load balancing scheme that allows the re-allocation of services according to their QoS requirements and the availability of network resources. We propose a multi-objective optimization model of this problem together with an evolutionary algorithm to solve it. Through simulation in different scenarios, we show that our algorithm is efficient, sensitive, scalable and provides optimal solutions.