Example: 'Compute a minimum cost access-to-core network'

Brief description

Given a set of access nodes, this algorithm computes the subset of access nodes which have a core node located next to it (in the same place), and the links access-to-core nodes, so that the network cost is minimized. This cost is given by a cost per core node (always 1) plus a cost per link, given by the product of link distance and the user-defined parameter linkCostPerKm. Access-core link capacities are fixed to the user-defined parameter linkCapacities. This problem is solved using a local-search 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
  • linkCostPerKm: The cost per km of the links between access and core nodes. Default: 1
Algorithm outputsNew links are added to netPlan object. Any previous links are removed.
Required librariesNone
KeywordsCapacity assignment (CA), Local search (LS) heuristic, Topology assignment (TA)
AuthorsPablo Pavón Mariño, José Luis Izquierdo Zaragoza
DateMarch 2013
CodeTCA_LS_nodeLocation.java

Detailed description

Initially, every access node has a core node located next to it. In each iteration, for every core node, I check the cost if we eliminated it and reconnected the access nodes. The best solution among these that also reduces the cost of the current solution becomes the next solution. If no node can be eliminated without worsening the solution, a local optimal has been reached and the algorithm stops.