用遗传算法优化多容量网络流设计，降低基础设施建设成本。
A Genetic Algorithm for Multi-Capacity Fixed-Charge Flow Network Design
- 创新编码方式避免无效解修复，提升求解效率
- 基于真实碳捕集项目数据验证，可处理大规模问题
- 适合需要快速求解的工程网络规划场景
多容量固定费用网络流（MC-FCNF）问题是固定费用网络流问题的推广，目标是在网络边分配容量，使指定流量能以最低成本传输。该问题中，只要边上有非零流量，就需支付固定成本。此问题在基础设施、交通、电信和供应链管理中广泛应用。由于MC-FCNF问题是NP难的，使用精确方法求解大规模实例不切实际。本文提出一种遗传算法，旨在快速获得高质量的流解决方案。该算法采用新颖的解表示方法，避免了其他遗传算法中常见的无效解修复问题。通过使用真实的二氧化碳捕集与封存（CCS）基础设施设计数据进行评估，结果表明该算法在求解大规模网络设计问题方面具有潜力。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。