2
$\begingroup$

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?

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

1 Answer 1

Reset to default
6
$\begingroup$

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.

Improve this answer
$\endgroup$
0

Your Answer

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

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