Biased random-key genetic algorithms for the minimum subgraph diameter problem

This work addresses the Minimum Subgraph Diameter Problem (MSDP), an NP-hard problem with applications to network design. Given an undirected graph with lengths and costs on the edges, the MSDP’s goal is to find a spanning subgraph with total cost limited by a given budget, such that the subgraph’s diameter is minimum. We propose a metaheuristic approach using a Biased Random-Key Genetic Algorithm for the MSDP, with three different decoders, diameter computation caching and warm-start solutions. These are the first heuristic approaches for the MSDP, and we conduct a computational study on a previously established benchmark. The results show our proposed methods contribute significantly to known optimality gaps and are better than the state-of-the-art methods for large instances in solution quality.