DM841 (E23) -  Heuristics and Constraint Programming for
Discrete Optimization

Sheet 7: Construction Heuristics for TSP

  1. Read the Python tutorial [No]. You find some starting code from that page here.

  2. Implement the exact methods: plain enumeration and Held Karp dynamic programming algorithm.

  3. Following the procedure for Benchmarking described in [No] implement and compare as many TSP heuristics as you can. You find a list below, in bold the heuristics implemented in [No]. For a description of these heuristics see [Be].

    • Heuristics that Grow Fragments
      • Nearest neighborhood heuristic
      • Double-Ended Nearest Neighbor heuristic
      • Multiple Fragment heuristic (aka, greedy heuristic)
    • Heuristics that Grow Tours
      • Nearest Addition
      • Farthest Addition
      • Random Addition
      • Clarke-Wright savings heuristic
      • Nearest Insertion
      • Farthest Insertion
      • Random Insertion
    • Heuristics based on Trees
      • Minimum spanning tree heuristic
      • Christofides’ heuristics
      • Fast recursive partitioning heuristic

  4. In Python kd-trees are already implemented in the module scipy. Try to use them and improve some implementations of the construction heuristics described above (you will probably need to change the representation of points).