A Biased Random-Key Genetic Algorithm for Maximum Flow with Minimum Labels

Donatella Granata

doi:10.3390/math13223621

Return

A Biased Random-Key Genetic Algorithm for Maximum Flow with Minimum Labels

2025-11-12

Donatella Granata

Andrea Raiconi *

DOI：10.3390/math13223621

Original

Save

View PDF

Abstract

En 中文

In this work, we propose a novel Biased Random-Key Genetic Algorithm (BRKGA) to solve the Maximum Flow with Minimum Number of Labels (MF-ML) problem, a challenging NP-Complete variant of the classical Maximum Flow problem defined on graphs in which arcs have both capacities and labels assigned. Labels give a qualitative characterization of each connection, in contexts where a solution that is as homogeneous as possible is sought. The MF-ML problem aims to maximize the flow from a source to a sink on a capacitated network while minimizing the number of distinct arc labels used, a modeling framework with applications such as water purification in distribution systems. Our proposed algorithm encodes solutions as random-key vectors, which are decoded into feasible solutions. The BRKGA demonstrates superior performance when compared to a Skewed Variable Neighborhood Search (VNS) approach previously proposed to solve MF-ML. In particular, on the largest considered graphs, BRKGA-MFML outperformed VNS in 55 out of 81 scenarios, with an average improvement per scenario that reaches 7.18%.

Keywords:

Maximum Flow

edge-labeled graphs

metaheuristic

biased random-key genetic algorithm

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.