Перейти к содержанию

прокладка маршрута по нескольким путевым точкам


Рекомендуемые сообщения

Суть вопроса - необходимо объехать порядка 25 объектов по кратчайшему маршруту.

Объекты указал в виде путевых точек.

Выбираю точку, прокладываю маршрут. Далее к маршруту добавляю каждую из оставшихся точек через пункт "заехать". В итоге получается далеко не оптимальный маршрут, поскольку навигатор при прокладке строго следует порядку введеных точек.

Как сделать оптимальный маршрут по всем точкам, не обращая внимание на порядок их ввода?

Ссылка на комментарий
Поделиться на другие сайты

Никак.

Точки надо вводить в определенном порядке. Проще всего для этого пользоваться не кнопкой "Заехать", а кнопкой "Добавить к маршруту".

То есть, прокладываете маршрут до ближайшей точки, и дальше последовательно клацаете "Добавить к маршруту" на каждой точке, в том порядке, в котором собираетесь их объезжать.

 

Порядок объезда Навитель сам не определит: не умеет, нет у него такого функционала...

Ссылка на комментарий
Поделиться на другие сайты

Nailery, это называется задача коммивояжера. Навител и, насколько я представляю себе, ни одна из продаваемых навигационных программ не рещают такую задачу.

Ссылка на комментарий
Поделиться на другие сайты

Furgon:

Nailery, это называется задача коммивояжера. Навител и, насколько я представляю себе, ни одна из продаваемых навигационных программ не рещают такую задачу.

Подозреваю, что софта для решения такой задачи на реальной карте реального города вообще не существует. Никакого.
Ссылка на комментарий
Поделиться на другие сайты

Да нет, всё решаемо. Только вот вопрос за какие деньги и за какое время...

 

Один из самых эффективных можно считать ГЕНЕТИЧЕСКИЙ АЛГОРИТМ. При этом ЗДЕСЬ называются некоторые цифры и факты:

Цитата

Рыночные цены на программные продукты колеблются от 1500$ до десятков тысяч долларов США. Также существуют и продаются специально-адаптированные под ЗК (Задача Коммивояжера) мини-компьютеры, которые позволяют решать задачу «на ходу». Такие программные продукты обладают полезными свойствами и возможностями, но имеют сугубо узкую направленность (связанную с логистической составляющей задачи). Поэтому при производственном применение рекомендуется глубокая проработка условий задачи, для быстрого и грамотного создания оригинального программного продукта или оптимального выбора из имеющихся.
Ссылка на комментарий
Поделиться на другие сайты

Здесь обсуждается ПО Навител Навигатор

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

Ссылка на комментарий
Поделиться на другие сайты

Kuzia:

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


Оказывается, этот интуитивно понятный способ ручной прокладки маршрута отностится к ЖАДНЫМ АЛГОРИТМАМ и называется Алгоритм ближайшего соседа. "Одним из эвристических критериев оценки решения является правило: если путь, пройденный на последних шагах алгоритма, сравним с путём, пройденным на начальных шагах, то можно условно считать найденный маршрут приемлемым, иначе, вероятно, существуют более оптимальные решения."
Ссылка на комментарий
Поделиться на другие сайты

Furgon:

Оказывается, этот интуитивно понятный способ ручной прокладки маршрута отностится к ЖАДНЫМ АЛГОРИТМАМ и называется Алгоритм ближайшего соседа.
"...оказалось, что Остап играет 18 испанских партий..." (С) 12 стульев. И кстати, почему бы этот алгоритм в самом НН не реализовать, не понимаю. Ничего сверхсложного нет. Усложнить можно, если расстояние между точками считать не по полету стрелы, а по маршруту. А для эстетов еще предусмотреть ручное изменение порядка (да-да, то самое редактирование маршрута).
Ссылка на комментарий
Поделиться на другие сайты

Заархивировано

Эта тема находится в архиве и закрыта для дальнейших ответов.

×
×
  • Создать...