The Minimum Conflict Weighted Spanning Tree Problem is a variant of the Minimum Spanning Tree Problem in which, given a list of conflicting edges modelled as a conflict graph, we want to find a weighted spanning tree with the minimum number of conflicts as main objective function and minimize the total weight of spanning trees as secondary objective function. The problem is proved to be NP-Hard in its general form and finds applications in several real-case scenarios such as the modelling of road networks in which some movements are prohibited. We propose a genetic algorithm designed to minimize the number of conflict edge pairs and the total weight of the spanning tree. We tested our approach on benchmark instances, the results of our GA showed that we outperform the other approaches proposed in the literature.
A Genetic Algorithm for Minimum Conflict Weighted Spanning Tree Problem
Cerrone C.;
2019-01-01
Abstract
The Minimum Conflict Weighted Spanning Tree Problem is a variant of the Minimum Spanning Tree Problem in which, given a list of conflicting edges modelled as a conflict graph, we want to find a weighted spanning tree with the minimum number of conflicts as main objective function and minimize the total weight of spanning trees as secondary objective function. The problem is proved to be NP-Hard in its general form and finds applications in several real-case scenarios such as the modelling of road networks in which some movements are prohibited. We propose a genetic algorithm designed to minimize the number of conflict edge pairs and the total weight of the spanning tree. We tested our approach on benchmark instances, the results of our GA showed that we outperform the other approaches proposed in the literature.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
