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

The Multi-Capacity Fixed-Charge Network Flow (MC-FCNF) problem is a well-studied optimization problem encountered in many domains including infrastructure design, transportation, telecommunications, and supply chain management [16, 26, 27]. In the MC-FCNF problem, each edge in the network has multiple capacities available to it, with each capacity having its own fixed construction and variable utilization costs. The objective of the MC-FCNF problem is to assign capacities to edges in the network such that a target flow amount can be hosted at minimal cost. The MC-FCNF problem is a generalization of the Fixed-Charge Network Flow (FCNF) problem, which has a single capacity (and fixed and variable costs) available per edge. The MC-FCNF problem is NP-Hard to approximate within the natural logarithm of the number of vertices in the graph [27]. As such, finding optimal solutions to large instances is often computationally infeasible.

Significant work has already been done on solving the MC-FCNF and FCNF problems using many techniques including mathematical programming, branch and bound, and exact optimization approaches [14, 15, 21, 10, 8]. Multi-capacity edge networks are often referred to as buy-at-bulk network design problems, and are often framed as facility location problems, which is similar to the MC-FCNF problem but with added demand constraints on sinks [13, 4, 1]. Genetic algorithms have also been introduced for variants of the MCNF problem [9, 2, 28, 25, 12, 30, 29, 19].

In this paper, we introduce a novel genetic algorithm to solve the MC-FCNF problem. The novel contribution of our genetic algorithm is the representation of a flow solution by an array of parameters that scale the fixed-costs for each edge in the network. This representation ensures that each array corresponds to a valid flow, thereby eliminating the need for computationally expensive repair functions that are required by other genetic algorithms for the MC-FCNF problem [9, 2, 25, 17, 30, 29, 19]. By avoiding costly repair functions, the proposed algorithm is able to efficiently find high-quality solutions to very large MC-FCNF problem instances. The proposed genetic algorithm is inspired by slope scaling techniques previously employed for the FCNF problem [14, 7]. It is a matheuristic, as it employs mathematical programming to calculate a flow solution from a linear program parameterized with the fixed-cost scaling arrays [11]. Our genetic algorithm is similar to an algorithm proposed by [6], though ours takes a different two-stage approach to handle multi-capacity edges. Additionally, we provide more insight into the existence of the optimal solution in the search space.

An evaluation is presented that designs ${\text{CO}}_2$ capture and storage (CCS) infrastructure deployments using real-world data composed of thousands of vertices and tens of thousands of edges. In the evaluation, the genetic algorithm is compared to the solution of an optimal integer linear program formulation of the MC-FCNF problem. Results from the evaluation demonstrate the utility of the genetic algorithm for very large networks, even if the solution is very small compared to the full network.

The rest of this paper is organized as follows: Section 2 formally introduces the MC-FCNF program and formulates it as an integer linear program. Section 3 presents a linear programming modification to the integer linear program that serves as the core to the genetic algorithm. Sections 4 and 5 introduce the genetic algorithm and discuss the existence of the optimal solution in the search space. Section 6 presents an evaluation of the genetic algorithm on real-world CCS data and the paper is concluded in Section 7.

MC-FCNF is formulated as follows: Given a directed graph with vertices $V$, edges $E$, a source $s\in V$ with no incoming edges, and a sink $t\in V$ with no outgoing edges, flow must be assigned to the edges such that the target amount of flow $T$ is sent from the source vertex to the sink vertex. There is a set $K$ of the possible capacities for each edge. Each capacity option $k\in K$ for an edge $e\in E$ has a fixed cost $a_{ek}$, and a variable cost $b_{ek}$. Assignment of flow to an edge incurs the total fixed cost, as well as the variable cost per unit of flow. The assigned flow must preserve the conservation of flow, meet the target flow amount, and minimize the overall cost.

This problem can also be formulated as an integer linear program (ILP), as shown below:

Instance Input Parameters:
     $V$ Vertex set      $E$ Directed edge set      $K$ Set of possible capacities for each edge      $s\in V$ Source vertex with no incoming edges      $t\in V$ Sink vertex with no outgoing edges      $c_k$ Capacity of $k$      $a_{ek}$ Fixed construction cost of edge $e$ with capacity $k$      $b_{ek}$ Variable utilization cost of edge $e$ with capacity $k$      $T$ Target flow amount

Decision Variables:
     $y_{ek}\in \{0,1\}$ Use indicator for edge $e$ with capacity $k$      $f_{ek}\in {ℝ}^{\ge 0}$ Amount of flow on edge $e$ with capacity $k$

Objective Function:

Subject to the following constraints:

Where constraint (2) enforces the capacity of each edge and forces $y_{ek}$ to be set to one if $f_{ek}$ is non-zero. Constraint (3) allows at most one capacity to be deployed on each edge. Constraint (4) enforces conservation of flow at each internal vertex. Constraint (5) ensures that the total flow amount meets the target.

Since the MC-FCNF problem is NP-Hard, solving this ILP is intractable for large instances [27]. The objective of this paper is to introduce a novel algorithm that efficiently finds high-quality solutions to this ILP without directly solving it.

In this section, we introduce a linear program (LP) that is a modification of the ILP presented in Section 2. Since it is an LP, this new formulation can be solved optimally in polynomial time. This LP forms the foundation of the genetic algorithm discussed in Section 4. Two components of the ILP change to turn it into an appropriate LP:

1. 1.

   The binary decision variables $y_{ek}$ are removed, thereby turning the model into an LP. Since the $y_{ek}$ variables are removed, the fixed costs are then scaled and combined with the variable costs.

2. 2.

   A new scaling parameter, $d_{ek}$, is introduced for each capacity on each edge that will scale the fixed cost of the edge. These parameters form the representation of a flow solution in the genetic algorithm.

Let $g_{ek}$ be the decision variable representing the amount of flow on edge $e$ with capacity $k$ in the LP, analogous to the $f_{ek}$ decision variable in the ILP. Then, the objective function of the LP is:

The constraints in the LP mirror the constraints in the ILP:

Where constraint (7) enforces the capacity of each edge. Constraint (8) enforces conservation of flow at each internal vertex. Constraint (9) ensures that the total flow amount meets the target.

The output of this LP is a flow value for each $g_{ek}$. Of course, the optimal flow found by the LP is likely not an optimal solution for the ILP. The true cost of the LP’s solution can be determined by calculating its value when input into the ILP’s objective function in Equation (1). This is first done by defining an edge-use indicator function $z_{ek}$ and assigning it values as follows:

This makes the true cost of the LP’s solution equal to:

The genetic algorithm in Section 4 works by varying the $d_{ek}$ scaling parameters and scoring the resulting optimal $g_{ek}$ values found by the LP using Equation (11).

Genetic algorithms are a common evolutionary heuristic method used for searching and optimization. Genetic algorithms manage a population of organisms that each correspond to a solution to the problem. The population evolves over iterations of the algorithm using evolutionary processes observed in nature including selection, crossover, and mutation operations. Selection is the process of deciding which organisms of the population continue into the next iteration (i.e., next generation). This is the mechanism that allows the algorithm to prioritize organisms that correspond to better solutions to the problem and control the size of the population. Crossover is the generation of a new organism from two existing organisms, analogous to biological reproduction. Similarly, mutation is the slight modification of an organism into a new one corresponding to a different solution. Crossover and mutation operations are the mechanisms that allow the algorithm to search for new, and possibly better, solutions.

A number of genetic algorithms have been developed to solve various versions of the FCNF problem. In these algorithms, organisms are broadly represented as either individual edges, or predefined routes through the network. Representing organisms as individual edges typically involves a binary variable for each edge indicating its availability for use [9, 29]. Alternatively, representing organisms as predefined routes involves a binary variable for each route in a set of predefined routes through the network [2, 25, 19]. In the case of the individual edge representation, generating the initial population, crossover operations, and mutation operations often requires repairing the organism, as random sets of edges are unlikely to result in valid flows. Using predefined routes simplifies repairing operations, but may still require repair in the event of capacity constraint violations, and is likely to result in sub-optimal solutions due to the limited set of routing options. The genetic algorithms that use these representations address the issue by employing computationally expensive repair functions to make organisms correspond to valid flows. Instead of representing an organism in this fashion, we represent it as an array of the fixed-cost scaling parameters $d_{ek}$ introduced in Section 3. Then, the solution corresponding to this organism is the set of flow values $g_{ek}$ found by the LP from Section 3. The result of this representation is that we can guarantee the solution corresponding to any organism is a valid flow, since the LP enforces that. This avoids costly repair functions and is the key to the efficiency of our approach.

The motivation for using the fixed-cost scaling parameters as the organism representation is that it allows control over the amount of fixed-costs incurred, while also removing the integer variables from the optimal ILP. As the scaling parameter decreases to zero, the scaled fixed-cost increases to infinity, thereby dissuading selection of that edge by the LP. Conversely, as the scaling parameter increases to infinity, the scaled fixed-cost approaches zero, thereby encouraging selection of that edge by the LP. The genetic algorithm is tasked with searching for an organism of scaling parameters whose corresponding flow solution is as close to optimal for the ILP as possible. Given that the genetic algorithm is using the fixed-cost scaling parameters as a proxy for a solution instead of using a solution directly, an important question is whether or not there exists a set of scaling parameters that yields an optimal flow solution. A proof that such a set of scaling parameters is guaranteed to exist is presented in Section 5. The key components and workflow of the genetic algorithm are described below:

The purpose of this section is to show that the genetic algorithm is capable of finding the optimal solution of the ILP. This claim is not trivial, as the search space of the genetic algorithm is the set of possible $d_{ek}$ arrays, which are merely a proxy for flow values, the property we are actually optimizing for.

The original motivation for formulating the LP in Section 3 and representing the organisms in the genetic algorithm as $d_{ek}$ arrays follows from the following false claim:

The rationale for this claim is that if each $d_{ek}$ and $g_{ek}$ both equal the optimal ILP flow values, then the cost of the LP’s objective function from Equation (6) will equal the optimal cost of the ILP’s objective function from Equation (1). Claim 1 is also the stated motivation behind other similar genetic algorithms for the FCNF problem [6]. This claim is shown to be false in Figure 1 with the displayed fixed costs ($a_e$), variable costs ($b_e$), capacities ($c_e$), and a capture target of three. In this instance, the optimal ILP solution is to set the amount of flow on $e_1$ and $e_3$ to two and the amount of flow on $e_2$ and $e_4$ to one for a total cost of $20$. Setting $d_{e_1}$ and $d_{e_3}$ to two and $d_{e_2}$ and $d_{e_4}$ to one yields the LP objective of minimizing $7g_{e_1}+6g_{e_2}$. The optimal solution to this is to set the amount of flow on $e_1$ and $e_3$ to one and the amount of flow on $e_2$ and $e_4$ to two for a total cost of $21$, thereby contradicting Claim 1.

Since Claim 1 is false, along with the fact that the $d_{ek}$ arrays are only proxies for the flow value solutions we seek, it remains to be shown that there actually exists a set of $d_{ek}$ values that will result in the genetic algorithm finding optimal flow values for the ILP.

To demonstrate the efficiency and effectiveness of the genetic algorithm presented in Section 4, an evaluation was conducted using ${\text{CO}}_2$ capture and storage (CCS) infrastructure design data. CCS is a climate change mitigation strategy that involves capturing ${\text{CO}}_2$ from industrial sources, notably power generation, transporting the ${\text{CO}}_2$ in a pipeline network, and injecting it into geological reservoirs for long-term sequestration. Large-scale CCS adoption will require the optimization of infrastructure for hundreds of sources and sinks and thousands of kilometers of pipelines. The CCS infrastructure design problem aims to answer the question: What sources and sinks should be opened, and where should pipelines be deployed (and at what capacity) to process a defined amount of ${\text{CO}}_2$ at minimum cost. CCS sources and sinks both have fixed construction (or retrofit) costs, variable utilization costs, and capacities (or emission limits). Pipelines have multiple capacities available, depending on the diameter of the pipeline installed. Pipelines also have fixed construction costs and variable transportation costs that are dependent on the capacity selected. Unlike the MC-FCNF problem, the CCS infrastructure design problem has multiple sources and sinks, as well as node-specific costs and capacities. However, CCS infrastructure design instances can be reduced into MC-FCNF instances by introducing a super source and super sink, and by translating node costs and capacities onto edges [24, 27].

The genetic algorithm was implemented and integrated into $SimCCS$, the Java-based CCS infrastructure optimization software, which uses CPLEX as its optimization model solver [20]. Initial performance simulations guided the parameterization of the genetic algorithm to have a population size of $10$, and mutation and crossover probability of both $50$%. A mutation probability of $50$% means that each organism has a $50$% chance of mutation, and a crossover probability of $50$% means that $50$% of the population (without organism repetition) is crossed over with a random other organism in each iteration of the genetic algorithm. All reported genetic algorithm values are the average of three runs. The optimal ILP from Section 2 was implemented in $SimCCS$ using CPLEX as well. $SimCCS$ was used as a standardized way to represent CCS data and for problem and solution visualization. Timing was coded directly into $SimCCS$ to ensure only the algorithm of interest was being timed during simulation. Simulations were run on a machine with Ubuntu 20.04.5, an Intel Xeon W-2255 processor running at 3.7 GHz, and 64 GB of RAM. $SimCCS$ on this machine used IBM’s CPLEX optimization tool, version 22.1.1.0.

The genetic algorithm was tested on two CCS infrastructure design datasets. The first dataset covers the United State’s state of California and consists of $190$ sources with a total annual emission rate of $88.39$ Mt${\text{CO}}_2$/yr, $102$ sinks with a total lifetime storage capacity of $37.18$ Gt${\text{CO}}_2$, and $1188$ possible pipeline components (i.e., edges in the graph) with a total length of $17940.88$ km and $11$ possible capacities on each edge. This data was collected as part of the US Department of Energy’s (DOE) Carbon Utilization and Storage Partnership project, one of the DOE’s Regional Initiatives to Accelerate CCS Deployment. A map of this dataset is presented in Figure 2.

The second dataset covers the contiguous United States and consists of $2746$ sources with a total annual emission rate of $532.61$ Mt${\text{CO}}_2$/yr, $1202$ sinks with a total lifetime storage capacity of $2691.86$ Gt${\text{CO}}_2$, and $22597$ possible pipeline components with a total length of $424674.41$ km and $11$ possible capacities on each edge. This data was collected by Carbon Solutions, LLC as part of a study conducted by the Clean Air Task Force [3, 5]. Storage data was generated using the $SC{O}_{2}T$ geologic sequestration tool [23]. A map of this dataset is presented in Figure 3.

Candidate pipeline routes were generated in $SimCCS$ using its candidate network generation algorithms [31]. The National Energy Technology Laboratory’s ${\text{CO}}_2$ Transport Cost Model was used by $SimCCS$ to determine fixed construction and variable utilization costs for the $11$ discrete pipeline capacity options [22].

To assess the efficiency of the genetic algorithm, its solution cost was compared to the solution cost found by CPLEX solving the optimal ILP, with both methods being allowed to run for set running time periods. For the California dataset, those running time periods were $0.5$, $1$, $2$, $4$, and $8$ hours. The target flow amount ($T$) was set to $80$ Mt${\text{CO}}_2$/yr for all of the California scenarios. For the contiguous United States dataset, the running time periods were $0.5$, $1$, $2$, $4$, $8$ and $16$ hours. The target flow amount was set to $500$ Mt${\text{CO}}_2$/yr for the contiguous United States scenarios. Figure 5 presents each algorithm’s solution cost over the running time periods for the California dataset, and Figure 5 presents the same results for the contiguous United States dataset. The cost of the best solution found by the genetic algorithm in the California dataset was within $0.5$% of the ILP’s solution across all running times. Conversely, the cost of the best solution found by the genetic algorithm in the contiguous United States dataset was $17$% lower than the ILP’s solution after one hour, $7$% lower after four hours, and $2$% lower after $16$ hours. This suggests that the genetic algorithm may have utility for very large problem instances. The utility for small instances is likely limited, due to the speed of CPLEX. Further, in applications that require rapid computation of MC-FCNF solutions, the genetic algorithm may exhibit beneficial performance for even smaller instances.

Problem solvability is not only related to instance size, but also the amount of target flow being found. To identify the impact that target flow amount has on solution quality, scenarios were run on the contiguous United States dataset where the target flow amount was varied from $1$ Mt${\text{CO}}_2$/yr to $532$ Mt${\text{CO}}_2$/yr. The maximum annual capturable amount of ${\text{CO}}_2$ for this dataset is $532.61$ Mt${\text{CO}}_2$/yr. Each algorithm was given two hours to solve each scenario. Figure 6 presents each algorithm’s solution cost for the various target flow amounts. Table 1 presents the specific solution cost values and the percent improvement of the genetic algorithm’s solution over the ILP’s solution. Other than in very low and high target flow amount scenarios, the genetic algorithm was fairly consistent in its improvement over the ILP. Interestingly, in the low target flow amount scenario, the genetic algorithm performed the best relative to the ILP. This suggests that the genetic algorithm could have utility in a very large problem instance, even if the target flow amount is quite small. This is likely a very realistic scenario, where a relatively small target is sought amongst a very large space of options, and provides a compelling argument for the utility of the genetic algorithm.

In this paper, we addressed the MC-FCNF problem by formulating it as an ILP and proposing a novel genetic algorithm to find high-quality solutions efficiently, using a relaxation of the ILP to an LP to ensure the solutions of the GA are valid solutions and do not need repairing. The key novel component of our approach is the use of fixed-cost scaling parameters as a proxy for direct flow values, allowing the genetic algorithm to search the solution space effectively without the need for computationally expensive repair functions.

Our genetic algorithm demonstrated significant efficiency and effectiveness in solving the MC-FCNF problem. By integrating the algorithm into the $SimCCS$ infrastructure optimization software, we were able to evaluate its performance on real-world CCS infrastructure design data. The results showed that the genetic algorithm consistently outperformed CPLEX solving an ILP on very large problem instances, and matched CPLEX’s performance on moderately sized problem instances. The evaluation demonstrated the potential of the genetic algorithm in handling large and complex networks with varied target flow objectives, across a wide range of running time requirements.

The genetic algorithm presented in this paper offers a robust and scalable solution to the MC-FCNF problem, providing an efficient alternative to traditional ILP solvers in realistic scenarios. Future work could involve tailoring the genetic algorithm to more specialized versions of the FCNF problem, including phased network deployments [18]. The genetic algorithm could also be generalized to multi-commodity fixed-charge network design problems. The fixed-cost scaling parameter technique may also prove useful in building evolutionary algorithms for other problems that can be modeled as network flow problems (e.g., facility location problems). Future work could include implementing this genetic algorithm approach for use in facility location applications and testing it against benchmark datasets. Future work could also include pursuing real-time applications where low computational running time is more critical than infrastructure design problems. Finally, further exploring the performance of the genetic algorithm on very large instances with small target flows could reveal useful applications of the genetic algorithm to real-world problems.