на кэгле в новый год было соревнование по tsp на 198000 городов,
вот оно ,только там доп.условие было, по возможности id каждого десятого города в пути должно быть простым числом.
посмотрите в кернелах и дискуссиях, там много инфы по разным решениям и реализации. Если вкратце - то решение сводится к прогонам 2-opt, 3-opt, 4-opt, 5-opt чем дольше, тем лучше, с постепенным улучшением результата. Плюс периодические рандомные изменения в пути, чтобы выбить из локального минимума (метод отжига).
