Random Insertion Algorithm

This article is not adequately provided with supporting documents (for example individual proofs ). Information without sufficient evidence could be removed soon. Please help Wikipedia by researching the information and including good evidence.

Special knowledge, non-trivial and only to be confirmed with research => supporting documents required .

The Random Insertion Algorithm (from “random insertion”) belongs to the class of insertion heuristics and is used to solve the traveling salesman problem .

In each step, the algorithm inserts a city selected with a uniformly distributing random generator into the existing partial route. Then the selected city is inserted where it causes the smallest (smallest) extension of the previous partial route. Strictly speaking, the RANDIN algorithm consists of two parts:

• "RANDom selection" for selecting the next city
• "Cheapest INsertion" for inserting into the existing partial route

Alternatives

Use alternative algorithms to insert e.g. B. in each case the most distant city ( FARIN ; from "farthest insertion") or the next most distant city ( NEARIN ; from "nearest insertion").