Falko - a quick update. At version 13.2, PROC OPTNET now solves your TSP to optimality in 594 seconds. I decided to revisit your problem, after writing the: Santa's Gift Assignment Problem blog post.