Поиск кратчайших путей это ерунда (можно даже чуть-чуть быстрее Дейкстровского N Log N если памяти не жалко), вот задача коммивояжёра другое дело.

Шесть лет назад я работал в ООО НИКА КОМ и написал там первую версию программы "Маршрут Мастер":

http://www.ncom.ru/win/soft/marsh_master.php

Она умела решать задачу коммивояжёра точно для 18 точек примерно минуты за три (на пентиуме 4), и для 30-40 точек -- приближённо примерно за час. Первое неплохое приближение выдавала через несколько секунд, а потом улучшала моим методом который я назвал "распутывание узлов" -- это типа теории возмущений: путь представляется узлом с тремя перехлёстами, с четырьмя, с пятью и т.д..  Распутывание узла третьего порядка уменьшало длину пути процентов на 10-20, четвертого - на 1-2, пятого -- на 0.1-0.2%, а меньше и не нужно было -- с такой точностью карту не задашь.