I am currently trying to understand the concept of GENIUS. It was a method devoloped to solve the tsp.

The first step seems logical to me: GENI (construction phase): start of with an tour of 3 nodes and randomly add the leftover nodes between the existing nodes until all nodes are in the tour.

Clear so far.. now i get confused how/why the improvement is being performed US(postoptimization phase): Unstring/Stringing

Could anyone outline the idea of this procedure clearly?

  • $\begingroup$ In our book "Fundamentals of Supply Chain Theory" (2nd ed.), we discuss GENI in some detail in §10.4.5, and US in §10.5.3. $\endgroup$ Jan 3, 2022 at 20:07
  • $\begingroup$ I would not say that GENI "randomly adds" the leftover nodes -- there's more to it than that. As for improvement: Many heuristics (not just for TSP) have an improvement phase after the construction phase, since the construction phase will typically not find the optimal solution. Does that clear up your confusion about why? $\endgroup$ Jan 3, 2022 at 20:08
  • $\begingroup$ @LarrySnyder610 Is there an intuitive explaination in words why the approach is better bruteforcing all the routes? $\endgroup$
    – Eddiee
    Jan 5, 2022 at 17:11
  • $\begingroup$ Brute-force elimination of all the routes would be extremely time-consuming even for small instances. The GENI_US method (like many other heuristics for TSP) looks at small pieces of the route at one time and considers only a small number of changes to those pieces at one time. So the search space is much, much smaller than enumeration (of course, at the expense of some accuracy). $\endgroup$ Jan 5, 2022 at 18:59


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.