A hybrid algorithm for a two-objective traffic engineering problem

We consider an Internet traffic routing problem. The paths for requests are assigned implicitly by setting link weights. The loads of links are generated by a simulator. If the load of a link is greater than its capacity, then the link is called congested. Our goal is to minimize two objective functions: the number of congested links and the distance between the initial and current weight vectors. The problem also includes two constraints: the total link flow in the network has an upper bound and new congested links are unwanted. We propose a new two-stage evolutionary scheme. The scheme employs a local search algorithm with a large neighbourhood to find an initial approximation of the Pareto set. The algorithm utilizes an integer linear programming model to determine the best solution in the neighbourhood. We compare the proposed scheme with well-known evolutionary algorithms using instances with 628 links and 1324 requests. According to the experiments, the proposed scheme constructs solutions statistically better at 15–49% for many performance indicators (9 out of 10). Tab. 3, illustr. 6, bibliogr. 42.