2026-07-25T01:58:04Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24766 2026-02-09T07:37:58Z ddc:004 open_access

A Genetic Algorithm for Multi-Capacity Fixed-Charge Flow Network Design Eardley, Caleb Gomez, Dalton Dupuis, Ryan Papadopoulos, Michael Yaw, Sean Fixed-Charge Network Flow Genetic Algorithm Matheuristic Infrastructure Design 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 utility is demonstrated with an evaluation using real-world CO₂ capture, transportation, and storage infrastructure design data. The evaluation results highlight the genetic algorithm’s potential for solving large-scale network design problems. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Caleb Eardley and Dalton Gomez and Ryan Dupuis and Michael Papadopoulos and Sean Yaw 2025 Is Part Of OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.ATMOS.2025.10 urn:nbn:de:0030-drops-247661 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.10 eng https://creativecommons.org/licenses/by/4.0/legalcode