Example: 'Computes a bidirectional ring for the network using a nearest-neighbor heuristic'

Brief description

Given a set of nodes, this heuristic tries to find a (possibly sub-optimal) minimum cost bidirectional ring (where the cost of a link is given by its length in km) using the nearest-neighbor greedy heuristic.

Algorithm description table

Algorithm inputs

Requires a set of nodes within the netPlan object.

Algorithm parameters:

  • initialNode: The id of the initial node in the algorithm. Default: 0
  • linkCapacities: The capacities to set in the links. Default: 100
Algorithm outputsNew links are added to netPlan object. Any previous links are removed.
Required librariesNone
KeywordsCapacity assignment (CA), Greedy heuristic, Topology assignment (TA)
AuthorsPablo Pavón Mariño, José Luis Izquierdo Zaragoza
DateMarch 2013
CodeTCA_nearestNeighborTSP.java

Detailed description

The algorithm starts in a user-defined initial node, and in each iteration sets the next node to visit as the closest one to current node, that has not been visited yet. Link capacities are fixed to a user-defined constant value.