GENETIC ALGORITHMS FOR FINDING THE SEMI-OBNOXIOUS (K,L)-CORE OF A GRAPH - Motevalli Ashkezari, Samaneh; Fathali, Jafar (International Journal of Industrial Engineering: Theory, Applications and Practice, 2020)
In this paper, we consider the network facility location problem and in particular, we investigate the problem of finding the (k,l)-core of a graph. This problem has been considered in recent years since it plays an important role in some practical applications such as transit routes, pipelines, drainage or irrigation ditches. A -core of a given graph , is a subtree of with at most end nodes and with a diameter of at most which the sum of the distances from all vertices to this subtree is minimized. The vertices of the graph are usually considered as the clients and the demand of client on a vertex is considered as the weight of this vertex. The -core is the location of the facilities. In the semi-obnoxious case, the facilities are desirable for a part of clients and undesirable for the rest. The problem of finding the semi-obnoxious -core on general graphs is NP-hard, therefore, we present three genetic algorithms for solving this problem. The numerical experiments were carried out on some standard test problems. Then we compare three algorithms in terms of speed of algorithms and quality of answers.