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

Donatella Granata and Andrea Raiconi ()
Additional contact information
Donatella Granata: Istituto per le Applicazioni del Calcolo “Mauro Picone”, National Research Council, Via dei Taurini 19, 00155 Rome, Italy
Andrea Raiconi: Istituto per le Applicazioni del Calcolo “Mauro Picone” (Naples Unit), National Research Council, Via Pietro Castellino 111, 80131 Naples, Italy

Mathematics, 2025, vol. 13, issue 22, 1-16

Abstract: 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 (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/13/22/3621/pdf (application/pdf)
https://www.mdpi.com/2227-7390/13/22/3621/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:13:y:2025:i:22:p:3621-:d:1792975

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().