A constructive heuristic is a type of heuristic method which starts with an empty solution and repeatedly extends the current solution until a complete solution is obtained. (Wikipedia)

Which constructive heuristics exist for the TSP? I know the nearest neighbour algorithm, the savings method and the Match Twice and Stitch (MTS). Which do furthermore exist?

  • 2
    $\begingroup$ you could add the best insertion algorithm, Christofides' algorithm, the sweep algorithm. Check out this link for some more. $\endgroup$
    – Kuifje
    Jun 9 '21 at 14:14

These CH work:

  • Nearest Neighbor
  • First Fit, First Fit Decreasing, Strongest Fit, Strongest Fit Decreasing
  • Cheapest Insertion, Regret Insertion
  • Christofides algorithm (doesn't really deal well with extra constraints)
  • Clarke-Wright algorithm (more for vanilla VRP, doesn't really deal well with extra constraints)

Cook's book "In Pursuit of the Traveling Salesman" explains some of these very well.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.