A Genetic Algorithm for Multi-Capacity Fixed-Charge Flow Network Design
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913575154483200 |
|---|---|
| author | Eardley, Caleb Gomez, Dalton Dupuis, Ryan Papadopoulos, Michael Yaw, Sean |
| author_facet | Eardley, Caleb Gomez, Dalton Dupuis, Ryan Papadopoulos, Michael Yaw, Sean |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_05798 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Genetic Algorithm for Multi-Capacity Fixed-Charge Flow Network Design Eardley, Caleb Gomez, Dalton Dupuis, Ryan Papadopoulos, Michael Yaw, Sean Neural and Evolutionary Computing Artificial Intelligence 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. |
| title | A Genetic Algorithm for Multi-Capacity Fixed-Charge Flow Network Design |
| topic | Neural and Evolutionary Computing Artificial Intelligence |
| url | https://arxiv.org/abs/2411.05798 |