# A Genetic Algorithm for Multi-Capacity Fixed-Charge Flow Network Design

arXiv: https://arxiv.org/abs/2411.05798 · HTML: https://mlsanity.com/paper/2411.05798/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 29 references that are in the map.
- First posted on arXiv 26 Oct 2024.

## Builds on (most cited first, 2 of 2)

- [Online Buy-at-Bulk Network Design](https://mlsanity.com/paper/1509.03212/) (2015)
- [Planning For Edge Failure in Fixed-Charge Flow Networks](https://mlsanity.com/paper/2407.20036/) (2024)

## Abstract (arXiv)

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.