В моем GPS-навигаторе, приобретенном ~ за 10тыс.руб, решается задача, по крайней мере, оптимизации маршрута между пунктом отправки и пунктом назначения. Можно выбирать несколько точек, через которые должен быть проложен маршрут, однако последовательность их объезда GPS-навигатор не оптимизирует - он будет их объезжать в том порядке, в котором они добавлены в маршрут.
Можно выбирать критерии оптимизации:
1) Минимальное расстояние
2) Минимальное время пути (с учетом различной скорости движения по разным трассам)
3) Минимальный расход горючего (нечто среднее между 1 и 2)

При выборе критерия оптимизации №1 навигатор предлагает ехать какими-то "огородами", узкими проулочками между домов, иногда даже дворами.
При выборе критерия оптимизации №2 он старается выбирать наиболее крупные трассы, при этом иногда требуя, чтобы я ехал в противоположном от пункта назначения направлении.

Я не пробовал подключать его к радиоприемнику, где передается информация о пробках (в нем есть такой функционал). Но без учета московских пробок все эти критерии оптимизации выглядят не более чем забава :). Полагаю, что и решение задачи комивояжера без учета пробок будет очень-очень грубым... :)

Кстати, когда-то давно мне пришлось возиться над оптимизационной задачей "множества коммивояжеров", каждый из которых привязан к своему району, но между районами нет четких границ. Это значит, что в зависимости от соотношения числа заказов, поступивших из различных районов, заказы, расположенные ближе к границам районов, могут быть обслужены разными комивояжерами - таким образом выравнивается нагрузка на них. По сути, задача множества комивояжеров разбивается на две задачи:
1) оптимальное распределение заказов между комивояжерами
2) оптимизация маршрута каждого комивояжера
Точнее, не разбивается, но разбить на эти фазы нужно, иначе математическая сложность задачи просто не даст ее решить... :)

Я использовал алгоритмы Дейкстры для решения задачи комивояжера с применением метода ветвей и границ. Для привязки комивояжеров к районам их обслуживания центр каждого района включался в маршрут соответствующего комивояжера как "виртуальный заказ", который он якобы должен обслужить в обязательном порядке. Оптимизировалось расстояние между заказами, расчитанное по прямой без учета ПДД и формы дорог. Попытки алгоритма минимизировать расстояния приводили к тому, что он выбирал заказы примерно вокруг центра района. Сам центр района после завершения первой фазы расчета из маршрута выкидывался, и расчет производился повторно с более глубокой оптимизацией уже в виде задачи одного комивояжера. Там было еще одно интересное требование - заказы на повторное обслуживание должны обрабатываться теми же самыми комивояжерами, которые обслуживали их в прошлый раз. Это требование приводило к весьма причудливым траекториям... :) Но, в общем, это было "самопальное" решение, написанное на Паскале, еще под ОС RT-11 для СМ ЭВМ... :)

Кстати, GPS-навигатор учитывает, на какой стороне улицы находится дом, к которому нужно подъехать. И выбирает маршрут с учетом ПДД и удобства маневрирования. В частности, из дома в Академию он предлагает мне ехать по одному сегменту садового кольца, а возвращаться - по другому.