Ant Colony Optimization for Solving Large-Scale Bi-Level Network Design Problems

Abstract

In this study, we consider a bi-level hierarchical network design problem that encompasses both gradual and cooperative coverage. The lower-level facility serves as the primary point of contact for customers, while the upper-level facility acts as a supplier for the lower-level facilities. We first present a mathematical formulation of the problem, followed by an Ant Colony Optimization (ACO) approach to solve it. We then compare the performance of our method with commercial exact solvers. Our experiments, conducted on instances of various sizes, show that while exact methods may succeed in the long run, our heuristic provides a fast and reliable option for operational decisions that need to be made in a short period of time. In nine out of twelve instances, the exact solver failed to find a feasible solution within three hours for the high-budget case and two hours for the low-budget case. In contrast, our heuristic had run times between 0.1 and 0.4 h for 50 iterations. We also compare the performance of ACO with that of a Genetic Algorithm (GA) to evaluate its effectiveness among heuristics. Our numerical results demonstrate that ACO outperforms GA. This study contributes to the literature by offering a solid theoretical framework for the problem and implementing ACO to solve a bi-level facility location problem. Our results demonstrate that ACO can deliver good solutions in a reasonable time and serves as a promising alternative.