A Genetic Algorithm for Multi-Capacity Fixed-Charge Flow Network Design
This incremental method addresses network design problems in infrastructure, transportation, and supply chains, offering a practical solution for large-scale instances.
The paper tackles the NP-hard Multi-Capacity Fixed-Charge Network Flow problem by developing a genetic algorithm that uses a novel representation to avoid invalid solutions, achieving efficient performance on real-world CO2 capture and storage data.
The Multi-Capacity Fixed-Charge Network Flow (MC-FCNF) problem, a generalization of the Fixed-Charge Network Flow problem, aims to assign capacities to edges in a flow network such that a target amount of flow can be hosted at minimum cost. The cost model for both problems dictates that the fixed cost of an edge is incurred for any non-zero amount of flow hosted by that edge. This problem naturally arises in many areas including infrastructure design, transportation, telecommunications, and supply chain management. The MC-FCNF problem is NP-Hard, so solving large instances using exact techniques is impractical. This paper presents a genetic algorithm designed to quickly find high-quality flow solutions to the MC-FCNF problem. The genetic algorithm uses a novel solution representation scheme that eliminates the need to repair invalid flow solutions, which is an issue common to many other genetic algorithms for the MC-FCNF problem. The genetic algorithm's efficiency is displayed with an evaluation using real-world CO2 capture and storage infrastructure design data. The evaluation results highlight the genetic algorithm's potential for solving large-scale network design problems.