Nearest insertion heuristic

from Wikipedia, the free encyclopedia
Nearest insertion heuristic

The nearest insertion heuristic ( NEARIN ) is an insertion heuristic and thus a heuristic opening method from graph theory . It is used to approximate a good solution to the traveling salesman problem ; The aim is to find the shortest possible round trip through all nodes of the graph.

In each step the algorithm selects a node with the shortest distance to a node of the already constructed partial route. This is built into the existing partial route in such a way that the slightest extension of the previous partial route is created.

Strictly speaking, the NEARIN algorithm consists of two parts:

  • near est selection: for the selection of the next node
  • cheapest in sertion: for inserting into the existing circle

The resulting structure always corresponds to a transitive envelope . This procedure is continued up to the nth node and corresponds to the complexity class .

Variants of this are the Farthest-Insertion-Heuristic , the Cheapest-Selection-Heuristic and the Random-Insertion-Heuristic .

The result of the NEARIN algorithm is usually not optimal. If the triangle inequality is present , the length of the round trip found cannot be less than twice the length of an optimal round trip. The shortsightedness of the NEARIN algorithm (when building the round trip, the search is only made for further nodes to be inserted in the next neighborhood) can even lead to round trips with crossings, which for that reason alone cannot be optimal. In practice, such algorithms are therefore to be optimized according to algorithms such as an opt-2 - heuristic combined.

See also