DROPS

Document

DOI: 10.4230/OASIcs.ATMOS.2025.10

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

Authors: Caleb Eardley, Dalton Gomez, Ryan Dupuis, Michael Papadopoulos, and Sean Yaw

Published in: OASIcs, Volume 137, 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)

Abstract

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.

Cite as

Caleb Eardley, Dalton Gomez, Ryan Dupuis, Michael Papadopoulos, and Sean Yaw. A Genetic Algorithm for Multi-Capacity Fixed-Charge Flow Network Design. In 25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025). Open Access Series in Informatics (OASIcs), Volume 137, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{eardley_et_al:OASIcs.ATMOS.2025.10,
  author =	{Eardley, Caleb and Gomez, Dalton and Dupuis, Ryan and Papadopoulos, Michael and Yaw, Sean},
  title =	{{A Genetic Algorithm for Multi-Capacity Fixed-Charge Flow Network Design}},
  booktitle =	{25th Symposium on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2025)},
  pages =	{10:1--10:14},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-404-8},
  ISSN =	{2190-6807},
  year =	{2025},
  volume =	{137},
  editor =	{Sauer, Jonas and Schmidt, Marie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.10},
  URN =		{urn:nbn:de:0030-drops-247661},
  doi =		{10.4230/OASIcs.ATMOS.2025.10},
  annote =	{Keywords: Fixed-Charge Network Flow, Genetic Algorithm, Matheuristic, Infrastructure Design}
}

Search Results

Documents authored by Dupuis, Ryan

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

Abstract

Cite as

Thanks for your feedback!

Could not send message