Это задача близкая к TSP, поэтому решать её особо упорно не имеет смысла. Можно придумывать разные эвристики (что мы и делали), но многие из них бесполезны, потому что они будут неоправданно тормозить обычный случай, где такое не происходит (и поэтому в целом решение получается хуже).