Поскольку ни один из методов не гарантирует оптимального решения, ваш пробег будет отличаться. При небольшом везении любая техника может превзойти другую. Оба метода имеют свои плюсы и минусы.
Ближайший сосед: + быстро, + просто, обычно не оптимально
Генетический алгоритм: - медленнее, - сложнее, + решения стремятся к оптимальному с течением времени
Большая разница в том, что рандомизированные алгоритмы, такие как имитируемый отжиг и генетические алгоритмы, могут продолжать улучшаться со временем - чем дольше вы позволяете им работать, тем больше у вас шансов на оптимальное решение (хотя нет гарантии).
Поскольку NN быстр, ничто не мешает вам комбинировать приемы. Запустите NN, чтобы найти, возможно, лучшее, чем случайное, стартовое решение. Затем включите это решение в свой генетический алгоритм и дайте ему работать так долго, как считаете нужным.
Если вас интересуют оптимальные решения, посмотрите Линейное-Керниганское эвристическое и Линейное программирование . Оба были использованы для поиска оптимальных решений для больших туров, включая это решение для 85 900 экскурсий по городу и 24 978 экскурсий по Швеции по городу .
Сайт Georgia Tech TSP - отличный ресурс.