A variable fixing heuristic with Local Branching for the fixed charge uncapacitated network design problem with user-optimal flow

• We propose an Iterated Local Search based heuristic for the Fixed Charge Uncapacitated Network Design Problem with User-optimal Flow.
• The developed algorithm relies on very few parameters.
• A novel perturbation mechanism based on cycle-based moves is proposed.
• Extensive computational experiments illustrate the robustness of our algorithm in terms of solution quality.
• First Hybrid Method for this problem.

This paper presents an iterated local search for the fixed-charge uncapacitated network design problem with user-optimal flow (FCNDP-UOF), which concerns routing multiple commodities from its origin to its destination by designing a network through selecting arcs, with an objective of minimizing the sum of the fixed costs of the selected arcs plus the sum of variable costs associated with the flows on each arc. Besides that, since the FCNDP-UOF is a bilevel problem, each commodity has to be transported through a shortest path, concerning the edges length, in the built network. The proposed algorithm generates an initial solution using a variable fixing heuristic. Then a local branching strategy is applied to improve the quality of the solution. At last, an efficient perturbation strategy is presented to perform cycle-based moves to explore different parts of the solution space. Computational experiments show that the proposed solution method consistently produces high-quality solutions in reasonable computational times.