Applied Sciences (Oct 2024)
A Study of the Multi-Objective Neighboring Only Quadratic Minimum Spanning Tree Problem in the Context of Uncertainty
Abstract
The pursuit of studying the quadratic minimum spanning tree (QMST) problem has captivated numerous academics because of its distinctive characteristic of taking into account the cost of interaction between pairs of edges. A QMST refers to the minimum spanning tree, which is a graph that is both acyclic and minimally connected. It also includes the interaction cost between a pair of edges in the minimum spanning tree. These interaction costs can occur between any pair of edges, whether they are adjacent or non-adjacent. In the QMST problem, our objective is to minimize both the cost of the edges and the cost of interactions. This eventually classifies the task as NP-hard. The interaction costs, sometimes referred to as quadratic costs, inherently exhibit a contradictory relationship with linear edge costs when solving a multi-objective problem that aims to minimize both linear and quadratic costs simultaneously. This study addresses the bi-objective adjacent only quadratic minimum spanning tree problem (AQMSTP) by incorporating the uncertain nature of the linear and quadratic costs associated with the problem. The focus is on the interaction costs between adjacent edges. Consequently, we have introduced a multi-objective problem called the uncertain adjacent only quadratic minimum spanning tree problem (mUAQMSTP) and formulated it using the uncertain chance-constrained programming technique. Afterwards, two MOEAs—non-dominated sorting genetic algorithm II (NSGAII) and duplicate elimination non-dominated sorting evolutionary algorithm (DENSEA)—and the traditional multi-objective solution approach, the global criterion method, are employed to solve the deterministic transformation of the model. Finally, we provide a suitable numerical illustration to substantiate our suggested framework.
Keywords
