Examples involving 'Greedy-Randomized Adaptive Search Procedure (GRASP)'

This algorithm computes the bidirectional ring which minimizes the total ring length, using a GRASP heuristic.

Keywords: Capacity assignment (CA), Greedy-Randomized Adaptive Search Procedure (GRASP), Topology assignment (TA)

This algorithm computes the bidirectional ring which minimizes the total ring length, using a GRASP heuristic. The cost of a link equals the euclidean distance between link end nodes. The algorithm executes GRASP iterations until the maxExecTime is reached. In each GRASP iteration, a solution is first created using a greedy-randomized approach. Then, this solution is the starting point of a local search (first-fit) heuristic, where two rings are considered neighbors when they have all but 2 bidirectional links in common. The greedy randomized approach is based on the concept of restricted candidate list (RCL). The ring starts with one single node chosen randomly. In each greedy iteration one node is added to the ring, randomly chosen from a RCL created in this iteration. The RCL contains the non-visited nodes which are closer to current node. In particular, the nodes in the RCL are those which are at a distance from c_min to c_min + alpha * (c_max - c_min). c_min and c_max are the distances from last added node, to closest and furthest non-visited nodes. alpha is an algroithm parameter between 0 and 1, tuning the size of the RCL. When alpha=0, the algorithm is equal to pure greedy nearest neighbor heuristic. If alpha = 1, randomness is maximum: a non-visited node is chosen randomly.