H. I. Calvete, C. Galé, J. A. Iranzo
This research addresses the ring star problem (RSP) which consists of locating a simple cycle through a subset of nodes of a graph and assigning the nodes not in the cycle to their closest vertex on the cycle. In this work, we assume that there is also a cost for placing a facility in the nodes of the ring, so that the total cost of locating the ring, assigning the nodes not in the ring and placing the facilities must be minimized. The RSP is approached as a hierarchical decision process with two decision levels and formulated as a bilevel problem with two decision makers in the lower level. An algorithm which combines different techniques is developed. In the upper level, an evolutionary algorithm is used to select the nodes in the ring. In the lower level, a GRASP algorithm is used to solve the TSP faced by the first decision maker, while the second decision maker optimally solves the problem of assigning nodes not in the ring.
Palabras clave: ring star problem, bilevel programming, evolutionary algorithm
Programado
JB4 Problemas de localización 1
19 de abril de 2012 10:30
Sala París
