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

View

Eardley, Caleb , Gomez, Dalton , Dupuis, Ryan , Papadopoulos, Michael , Yaw, Sean ·

YOU? · · 2025 · Open Access · · DOI: https://doi.org/10.4230/oasics.atmos.2025.10

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.

Related Topics

Enhanced Data Rates For Gsm Evolution

Network Model

Algorithm

Supply Chain

Concepts

Genetic algorithm Minimum-cost flow problem Flow network Computer science Mathematical optimization Flow (mathematics) Generalization Representation (politics) Scheme (mathematics) Network planning and design Supply chain network Enhanced Data Rates for GSM Evolution Network model Algorithm Distributed computing Multi-commodity flow problem Supply chain

Metadata

Type: article
Language: en
Landing Page: https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.10
OA Status: green
OpenAlex ID: https://openalex.org/W7110058799

All OpenAlex metadata

Raw OpenAlex JSON

OpenAlex ID: https://openalex.org/W7110058799

Canonical identifier for this work in OpenAlex
DOI: https://doi.org/10.4230/oasics.atmos.2025.10

Digital Object Identifier
Title: A Genetic Algorithm for Multi-Capacity Fixed-Charge Flow Network Design

Work title
Type: article

OpenAlex work type
Language: en

Primary language
Publication year: 2025

Year of publication
Publication date: 2025-01-01

Full publication date if available
Authors: Eardley, Caleb, Gomez, Dalton, Dupuis, Ryan, Papadopoulos, Michael, Yaw, Sean

List of authors in order
Landing page: https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.10

Publisher landing page
Open access: Yes

Whether a free full text is available
OA status: green

Open access status per OpenAlex
OA URL: https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.10

Direct OA link when available
Concepts: Genetic algorithm, Minimum-cost flow problem, Flow network, Computer science, Mathematical optimization, Flow (mathematics), Generalization, Representation (politics), Scheme (mathematics), Network planning and design, Supply chain network, Enhanced Data Rates for GSM Evolution, Network model, Algorithm, Distributed computing, Multi-commodity flow problem, Supply chain

Top concepts (fields/topics) attached by OpenAlex
Cited by: 0

Total citation count in OpenAlex

Full payload

id	https://openalex.org/W7110058799
doi	https://doi.org/10.4230/oasics.atmos.2025.10
ids.openalex	https://openalex.org/W7110058799
fwci	0.0
type	article
title	A Genetic Algorithm for Multi-Capacity Fixed-Charge Flow Network Design
biblio.issue
biblio.volume
biblio.last_page
biblio.first_page
topics[0].id	https://openalex.org/T10567
topics[0].field.id	https://openalex.org/fields/22
topics[0].field.display_name	Engineering
topics[0].score	0.23730197548866272
topics[0].domain.id	https://openalex.org/domains/3
topics[0].domain.display_name	Physical Sciences
topics[0].subfield.id	https://openalex.org/subfields/2209
topics[0].subfield.display_name	Industrial and Manufacturing Engineering
topics[0].display_name	Vehicle Routing Optimization Methods
topics[1].id	https://openalex.org/T11053
topics[1].field.id	https://openalex.org/fields/22
topics[1].field.display_name	Engineering
topics[1].score	0.18205526471138
topics[1].domain.id	https://openalex.org/domains/3
topics[1].domain.display_name	Physical Sciences
topics[1].subfield.id	https://openalex.org/subfields/2207
topics[1].subfield.display_name	Control and Systems Engineering
topics[1].display_name	Process Optimization and Integration
topics[2].id	https://openalex.org/T10847
topics[2].field.id	https://openalex.org/fields/22
topics[2].field.display_name	Engineering
topics[2].score	0.06086258590221405
topics[2].domain.id	https://openalex.org/domains/3
topics[2].domain.display_name	Physical Sciences
topics[2].subfield.id	https://openalex.org/subfields/2208
topics[2].subfield.display_name	Electrical and Electronic Engineering
topics[2].display_name	Advanced Optical Network Technologies
is_xpac	False
apc_list
apc_paid
concepts[0].id	https://openalex.org/C8880873
concepts[0].level	2
concepts[0].score	0.721118152141571
concepts[0].wikidata	https://www.wikidata.org/wiki/Q187787
concepts[0].display_name	Genetic algorithm
concepts[1].id	https://openalex.org/C99545648
concepts[1].level	3
concepts[1].score	0.7168238162994385
concepts[1].wikidata	https://www.wikidata.org/wiki/Q2897180
concepts[1].display_name	Minimum-cost flow problem
concepts[2].id	https://openalex.org/C114809511
concepts[2].level	2
concepts[2].score	0.7104414105415344
concepts[2].wikidata	https://www.wikidata.org/wiki/Q1412924
concepts[2].display_name	Flow network
concepts[3].id	https://openalex.org/C41008148
concepts[3].level	0
concepts[3].score	0.6200994849205017
concepts[3].wikidata	https://www.wikidata.org/wiki/Q21198
concepts[3].display_name	Computer science
concepts[4].id	https://openalex.org/C126255220
concepts[4].level	1
concepts[4].score	0.5664634108543396
concepts[4].wikidata	https://www.wikidata.org/wiki/Q141495
concepts[4].display_name	Mathematical optimization
concepts[5].id	https://openalex.org/C38349280
concepts[5].level	2
concepts[5].score	0.5640950798988342
concepts[5].wikidata	https://www.wikidata.org/wiki/Q1434290
concepts[5].display_name	Flow (mathematics)
concepts[6].id	https://openalex.org/C177148314
concepts[6].level	2
concepts[6].score	0.5597034692764282
concepts[6].wikidata	https://www.wikidata.org/wiki/Q170084
concepts[6].display_name	Generalization
concepts[7].id	https://openalex.org/C2776359362
concepts[7].level	3
concepts[7].score	0.5265651345252991
concepts[7].wikidata	https://www.wikidata.org/wiki/Q2145286
concepts[7].display_name	Representation (politics)
concepts[8].id	https://openalex.org/C77618280
concepts[8].level	2
concepts[8].score	0.5045521855354309
concepts[8].wikidata	https://www.wikidata.org/wiki/Q1155772
concepts[8].display_name	Scheme (mathematics)
concepts[9].id	https://openalex.org/C114563136
concepts[9].level	2
concepts[9].score	0.45303380489349365
concepts[9].wikidata	https://www.wikidata.org/wiki/Q19725982
concepts[9].display_name	Network planning and design
concepts[10].id	https://openalex.org/C2778397037
concepts[10].level	4
concepts[10].score	0.44199931621551514
concepts[10].wikidata	https://www.wikidata.org/wiki/Q17083947
concepts[10].display_name	Supply chain network
concepts[11].id	https://openalex.org/C162307627
concepts[11].level	2
concepts[11].score	0.39245977997779846
concepts[11].wikidata	https://www.wikidata.org/wiki/Q204833
concepts[11].display_name	Enhanced Data Rates for GSM Evolution
concepts[12].id	https://openalex.org/C104122410
concepts[12].level	2
concepts[12].score	0.337817907333374
concepts[12].wikidata	https://www.wikidata.org/wiki/Q1416406
concepts[12].display_name	Network model
concepts[13].id	https://openalex.org/C11413529
concepts[13].level	1
concepts[13].score	0.33237338066101074
concepts[13].wikidata	https://www.wikidata.org/wiki/Q8366
concepts[13].display_name	Algorithm
concepts[14].id	https://openalex.org/C120314980
concepts[14].level	1
concepts[14].score	0.2978360652923584
concepts[14].wikidata	https://www.wikidata.org/wiki/Q180634
concepts[14].display_name	Distributed computing
concepts[15].id	https://openalex.org/C170334043
concepts[15].level	3
concepts[15].score	0.29294952750205994
concepts[15].wikidata	https://www.wikidata.org/wiki/Q6934437
concepts[15].display_name	Multi-commodity flow problem
concepts[16].id	https://openalex.org/C108713360
concepts[16].level	2
concepts[16].score	0.2898947596549988
concepts[16].wikidata	https://www.wikidata.org/wiki/Q1824206
concepts[16].display_name	Supply chain
keywords[0].id	https://openalex.org/keywords/genetic-algorithm
keywords[0].score	0.721118152141571
keywords[0].display_name	Genetic algorithm
keywords[1].id	https://openalex.org/keywords/minimum-cost-flow-problem
keywords[1].score	0.7168238162994385
keywords[1].display_name	Minimum-cost flow problem
keywords[2].id	https://openalex.org/keywords/flow-network
keywords[2].score	0.7104414105415344
keywords[2].display_name	Flow network
keywords[3].id	https://openalex.org/keywords/flow
keywords[3].score	0.5640950798988342
keywords[3].display_name	Flow (mathematics)
keywords[4].id	https://openalex.org/keywords/generalization
keywords[4].score	0.5597034692764282
keywords[4].display_name	Generalization
keywords[5].id	https://openalex.org/keywords/representation
keywords[5].score	0.5265651345252991
keywords[5].display_name	Representation (politics)
keywords[6].id	https://openalex.org/keywords/scheme
keywords[6].score	0.5045521855354309
keywords[6].display_name	Scheme (mathematics)
language	en
locations[0].id	pmh:oai:drops-oai.dagstuhl.de:24766
locations[0].is_oa	True
locations[0].source.id	https://openalex.org/S4306402524
locations[0].source.issn
locations[0].source.type	repository
locations[0].source.is_oa	False
locations[0].source.issn_l
locations[0].source.is_core	False
locations[0].source.is_in_doaj	False
locations[0].source.display_name	Leibniz-Zentrum für Informatik (Schloss Dagstuhl)
locations[0].source.host_organization	https://openalex.org/I2799853480
locations[0].source.host_organization_name	Schloss Dagstuhl – Leibniz Center for Informatics
locations[0].source.host_organization_lineage	https://openalex.org/I2799853480
locations[0].license	cc-by
locations[0].pdf_url
locations[0].version	publishedVersion
locations[0].raw_type	publishedVersion
locations[0].license_id	https://openalex.org/licenses/cc-by
locations[0].is_accepted	True
locations[0].is_published	True
locations[0].raw_source_name
locations[0].landing_page_url	https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.10
authorships[0].author.id
authorships[0].author.orcid
authorships[0].author.display_name	Eardley, Caleb
authorships[0].author_position	first
authorships[0].raw_author_name	Eardley, Caleb
authorships[0].is_corresponding	True
authorships[1].author.id
authorships[1].author.orcid
authorships[1].author.display_name	Gomez, Dalton
authorships[1].author_position	middle
authorships[1].raw_author_name	Gomez, Dalton
authorships[1].is_corresponding	False
authorships[2].author.id
authorships[2].author.orcid
authorships[2].author.display_name	Dupuis, Ryan
authorships[2].author_position	middle
authorships[2].raw_author_name	Dupuis, Ryan
authorships[2].is_corresponding	False
authorships[3].author.id
authorships[3].author.orcid
authorships[3].author.display_name	Papadopoulos, Michael
authorships[3].author_position	middle
authorships[3].raw_author_name	Papadopoulos, Michael
authorships[3].is_corresponding	False
authorships[4].author.id	https://openalex.org/A4223032119
authorships[4].author.orcid
authorships[4].author.display_name	Yaw, Sean
authorships[4].author_position	last
authorships[4].raw_author_name	Yaw, Sean
authorships[4].is_corresponding	False
has_content.pdf	False
has_content.grobid_xml	False
is_paratext	False
open_access.is_oa	True
open_access.oa_url	https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.10
open_access.oa_status	green
open_access.any_repository_has_fulltext	False
created_date	2025-12-08T00:00:00
display_name	A Genetic Algorithm for Multi-Capacity Fixed-Charge Flow Network Design
has_fulltext	False
is_retracted	False
updated_date	2025-12-08T23:26:33.048892
primary_topic.id	https://openalex.org/T10567
primary_topic.field.id	https://openalex.org/fields/22
primary_topic.field.display_name	Engineering
primary_topic.score	0.23730197548866272
primary_topic.domain.id	https://openalex.org/domains/3
primary_topic.domain.display_name	Physical Sciences
primary_topic.subfield.id	https://openalex.org/subfields/2209
primary_topic.subfield.display_name	Industrial and Manufacturing Engineering
primary_topic.display_name	Vehicle Routing Optimization Methods
cited_by_count	0
locations_count	1
best_oa_location.id	pmh:oai:drops-oai.dagstuhl.de:24766
best_oa_location.is_oa	True
best_oa_location.source.id	https://openalex.org/S4306402524
best_oa_location.source.issn
best_oa_location.source.type	repository
best_oa_location.source.is_oa	False
best_oa_location.source.issn_l
best_oa_location.source.is_core	False
best_oa_location.source.is_in_doaj	False
best_oa_location.source.display_name	Leibniz-Zentrum für Informatik (Schloss Dagstuhl)
best_oa_location.source.host_organization	https://openalex.org/I2799853480
best_oa_location.source.host_organization_name	Schloss Dagstuhl – Leibniz Center for Informatics
best_oa_location.source.host_organization_lineage	https://openalex.org/I2799853480
best_oa_location.license	cc-by
best_oa_location.pdf_url
best_oa_location.version	publishedVersion
best_oa_location.raw_type	publishedVersion
best_oa_location.license_id	https://openalex.org/licenses/cc-by
best_oa_location.is_accepted	True
best_oa_location.is_published	True
best_oa_location.raw_source_name
best_oa_location.landing_page_url	https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.10
primary_location.id	pmh:oai:drops-oai.dagstuhl.de:24766
primary_location.is_oa	True
primary_location.source.id	https://openalex.org/S4306402524
primary_location.source.issn
primary_location.source.type	repository
primary_location.source.is_oa	False
primary_location.source.issn_l
primary_location.source.is_core	False
primary_location.source.is_in_doaj	False
primary_location.source.display_name	Leibniz-Zentrum für Informatik (Schloss Dagstuhl)
primary_location.source.host_organization	https://openalex.org/I2799853480
primary_location.source.host_organization_name	Schloss Dagstuhl – Leibniz Center for Informatics
primary_location.source.host_organization_lineage	https://openalex.org/I2799853480
primary_location.license	cc-by
primary_location.pdf_url
primary_location.version	publishedVersion
primary_location.raw_type	publishedVersion
primary_location.license_id	https://openalex.org/licenses/cc-by
primary_location.is_accepted	True
primary_location.is_published	True
primary_location.raw_source_name
primary_location.landing_page_url	https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2025.10
publication_date	2025-01-01
publication_year	2025
referenced_works_count	0
abstract_inverted_index.a	7, 22, 27, 97, 115
abstract_inverted_index.an	50, 131, 150
abstract_inverted_index.at	35
abstract_inverted_index.be	33
abstract_inverted_index.by	61
abstract_inverted_index.in	21, 68
abstract_inverted_index.is	52, 83, 92, 130, 147
abstract_inverted_index.of	9, 30, 49, 58
abstract_inverted_index.so	85
abstract_inverted_index.to	16, 19, 101, 107, 124, 134
abstract_inverted_index.The	0, 38, 80, 111, 143, 162
abstract_inverted_index.and	76, 157
abstract_inverted_index.any	55
abstract_inverted_index.can	32
abstract_inverted_index.for	41, 54, 139, 170
abstract_inverted_index.the	10, 46, 108, 122, 140, 166
abstract_inverted_index.Flow	4, 13
abstract_inverted_index.This	64, 94
abstract_inverted_index.aims	15
abstract_inverted_index.both	42
abstract_inverted_index.cost	39, 48
abstract_inverted_index.edge	51
abstract_inverted_index.find	103
abstract_inverted_index.flow	23, 31, 59, 105, 127
abstract_inverted_index.many	69, 135
abstract_inverted_index.need	123
abstract_inverted_index.such	25
abstract_inverted_index.that	26, 45, 62, 120
abstract_inverted_index.uses	114
abstract_inverted_index.with	149
abstract_inverted_index.CO₂	154
abstract_inverted_index.areas	70
abstract_inverted_index.chain	78
abstract_inverted_index.cost.	37
abstract_inverted_index.data.	161
abstract_inverted_index.edge.	63
abstract_inverted_index.edges	20
abstract_inverted_index.exact	90
abstract_inverted_index.fixed	47
abstract_inverted_index.issue	132
abstract_inverted_index.large	87
abstract_inverted_index.model	40
abstract_inverted_index.novel	116
abstract_inverted_index.other	136
abstract_inverted_index.paper	95
abstract_inverted_index.using	89, 152
abstract_inverted_index.which	129
abstract_inverted_index.amount	29, 57
abstract_inverted_index.arises	67
abstract_inverted_index.assign	17
abstract_inverted_index.common	133
abstract_inverted_index.design	160, 174
abstract_inverted_index.hosted	34, 60
abstract_inverted_index.repair	125
abstract_inverted_index.scheme	119
abstract_inverted_index.supply	77
abstract_inverted_index.target	28
abstract_inverted_index.MC-FCNF	81, 109, 141
abstract_inverted_index.Network	3, 12
abstract_inverted_index.design,	73
abstract_inverted_index.genetic	98, 112, 137, 144, 167
abstract_inverted_index.invalid	126
abstract_inverted_index.minimum	36
abstract_inverted_index.network	24, 173
abstract_inverted_index.problem	65, 82
abstract_inverted_index.quickly	102
abstract_inverted_index.results	164
abstract_inverted_index.solving	86, 171
abstract_inverted_index.storage	158
abstract_inverted_index.utility	146
abstract_inverted_index.NP-Hard,	84
abstract_inverted_index.capture,	155
abstract_inverted_index.designed	100
abstract_inverted_index.dictates	44
abstract_inverted_index.incurred	53
abstract_inverted_index.non-zero	56
abstract_inverted_index.presents	96
abstract_inverted_index.problem,	6, 14
abstract_inverted_index.problem.	110, 142
abstract_inverted_index.problems	43
abstract_inverted_index.solution	117
abstract_inverted_index.(MC-FCNF)	5
abstract_inverted_index.algorithm	99, 113
abstract_inverted_index.highlight	165
abstract_inverted_index.including	71
abstract_inverted_index.instances	88
abstract_inverted_index.naturally	66
abstract_inverted_index.potential	169
abstract_inverted_index.problems.	175
abstract_inverted_index.solutions	106
abstract_inverted_index.algorithms	138
abstract_inverted_index.capacities	18
abstract_inverted_index.eliminates	121
abstract_inverted_index.evaluation	151, 163
abstract_inverted_index.real-world	153
abstract_inverted_index.solutions,	128
abstract_inverted_index.techniques	91
abstract_inverted_index.large-scale	172
abstract_inverted_index.management.	79
abstract_inverted_index.Fixed-Charge	2, 11
abstract_inverted_index.demonstrated	148
abstract_inverted_index.high-quality	104
abstract_inverted_index.impractical.	93
abstract_inverted_index.algorithm’s	145, 168
abstract_inverted_index.Multi-Capacity	1
abstract_inverted_index.generalization	8
abstract_inverted_index.infrastructure	72, 159
abstract_inverted_index.representation	118
abstract_inverted_index.transportation,	74, 156
abstract_inverted_index.telecommunications,	75
cited_by_percentile_year
countries_distinct_count	0
institutions_distinct_count	5
citation_normalized_percentile.value	0.81444174
citation_normalized_percentile.is_in_top_1_percent	False
citation_normalized_percentile.is_in_top_10_percent	False