Перейти к содержанию
GPS навигатор СитиГИД

Оптимальный проезд через несколько точек.


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

  • Ответов 50
  • Дата создания
  • Последний ответ

Лучшие авторы в теме

Лучшие авторы в теме

Популярные посты

Да, для начала реализовали бы механизм ручного изменения порядка накиданных в карту точек - то, что есть у всех конкурентов.

Может где есть ответ? Я не нашел. Смысл вопроса в заголовке. Халтурю на развозке пассажиров. Нужно забить несколько адресов (точек), и что бы сити гид сам проложил короткий маршрут между всеми точками

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

Изображения в теме

есть такое... ставишь промежуточную точку в середине маршрута и СГ начинает возить тебя кругами, вместо перестроения оптимально короткого маршрута!

 

поддержу, хочется иметь такой вариант маршрута.

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

Ну вообще на встрече с избирателями)) главный программист МИТа сказал, что объединить несколько точек- не проблема. Не помню кол-во правда, но нормальное, штук 5 или 10.


Но до сих пор почему-то не реализовано и даже не слышно по этому поводу ничего. Я вот лично практически всего от СГ дождался, даже не знаю чего желать в новой версии. Только это осталось))

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

Решение задачи коммивояжера достаточно сложное, насколько я понимаю.

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

 

Если решать задачу "в лоб" методом перебора маршрутов, то нужно будет выбирать из n! вариантов (т.е. если три точки, то количество вариантов будет 1х2х3=6, а если пять точек, то - 1х2х3х4х5=120 и т.д.).

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

 

А вот всякие возможные "зигзагобразные" маршруты (например, есть две точки, куда надо ехать, примерно в одном направлении и примерно на одинаковом расстоянии. Едем вначале к точке 1, хлоп, дорожная обстановка изменилась - теперь едем к точке 2, опять изменилась - едем к точке 1 и т.п.) обеспечат головной болью разработчиков от стонов. 

 

М.б.,  производить пересчет "порядка следования точек" гораздо реже, например, через 15 мин, или только, если "новый порядок следования точек" существенно (например, на те же 15 мин) снижает общую длительность маршрута?

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

А как часто обновляются пробки? Разве не раз в 15 минут?

 

И n! как я понимаю не для набора точек, а для набора рёбер по пути к каждой точки.

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


А как часто обновляются пробки?
раз в три минуты.
Ссылка на сообщение
Поделиться на другие сайты

Я думаю, об этом даже никто не мечтает, тем более такой пересчет на перекрестке может потрепать нервы.

Мне кажется, что коммивояжерский расчет должен производиться только один раз (ну, или исключительно по ручному запросу).

То есть задал 5 точек, сказал "оптимизировать", они построились в порядке 3,1,4,2,5. И зафиксировались. Едем. 

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

Либо, если хочу, достигнув точки 3 и разгрузившись, нажимаю снова "Оптимизировать" - и оставшиеся 4 точки снова перестраиваются, с учетом изменившейся обстановки.

Насчет количества обсчитываемых вариантов - наверное не все страшно, поскольку например последовательность 1-2-3 можно рассчитать только один раз, а полученную цифру использовать в 6 разных сочетаниях. При этом она в свою очередь использует маршруты 1-2 и 2-3, которые тоже не надо пересчитывать N раз. Но, конечно, не знаю - насколько это реализуемо на ВинСЕ с 128 МБ.

раз в 3 мин.

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

И n! как я понимаю не для набора точек, а для набора рёбер по пути к каждой точки.

Именно для набора точек.

Сам маршрут вычисляется не методом полного перебора, например алгоритмом Дейкстры, "волны" и т.п.

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


Именно для набора точек.

 

ну да, имеется в виду, что есть стартовая точка  и 3 точки куда нужно заехать (опционально - вернуться на точку старта),  - получается 6 вариантов.  Даже в таком виде получается всего 6 маршрутов, что, как-бы, практически приемлимо (10 секунд? 20 секунд?) может быть построено даже  тупым перебором всех 6 вариантов на имеющемся алгоритме... Лично я согласен подождать 10-20 секунд, чтобы потом сэкономить 10-20 минут...   

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


То есть задал 5 точек, сказал "оптимизировать", они построились в порядке 3,1,4,2,5. И зафиксировались. Едем.

Идеальный вариант!

И ещё что бы гнал к точкам с наименьшим количеством  разворотов, по одной стороне так сказать...

Во сказанул! :)

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

Народ, вы чего-то путаете. Топикстартер попросил вполне определенно:


и что бы СитиГИДсам проложил короткий маршрут между всеми точками

Такой маршрут в реальной жизни один. Даже обратный в реале не будет той же длинны. Так что задача элементарна и вполне себе решена в айге. Будет ли рад автор решению проблемы -- вопрос постановки ТЗ (вспоминаем негра в пустыне).

  • Upvote 2
Ссылка на сообщение
Поделиться на другие сайты

 

И ещё что бы гнал к точкам с наименьшим количеством  разворотов, по одной стороне так сказать...

 

Вокруг Земли...

За 80 дней... :P

Изменено пользователем svlad2012
Ссылка на сообщение
Поделиться на другие сайты


Топикстартер попросил вполне определенно:

А в заголовке темы он еще и оптимальный маршрут хотел.  :)

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

eklmn, Ну да, в заголовке попросил оптимальный, а в теле письма уточнил критерий оптимизации. А вы тут развели -- коммивояжер, Дейкстра, частота пересчета... Отзывчивее надо быть. И люди начнут становиться до такими же умными, как моя жена после... 

  • Upvote 1
Ссылка на сообщение
Поделиться на другие сайты

И пробки мне не нужны! Ночью я халтурю! Типа добавил ещё один параметр оптимизации. :)

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

ребята, сейчас мы имеем проблему следующего характера... изначально есть три точки - "старт", "финиш" и промежуточная "1". добавляем точку "2" между "1" и "финиш" - маршрут строиться корректно. добавляем точку "3" между "1" и "старт" - получаем "круг" - "старт" - "1" - "2" - возврат в направлении точки"3" (что вовсе не логично!) - путь от "3" до точки "финиш".

 

на мой взгляд нет необходимости отслеживать порядок введения точек, нужно считать их удаление от "старта" до "финиша" (а если это одна и та же точка, то считать маршрут от нее до самой дальней и обратно через промежуточные). не так уж много вариантов маршрута!

 

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

 

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

 

надеюсь изложил алгоритм доступно... 

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

IШIN,Да, нужна будет галочка-учитывать последовательность установки точек-неучитывать последовательность... 

  • Upvote 2
Ссылка на сообщение
Поделиться на другие сайты

Я вот тоже был бы рад подобной опции БЕЗ УЧЕТА ПРОБОК и чтобы маршрут не перестраивался даже ни разу.

Я сейчас сам этим занимаюсь почти каждую пятницу. Сажусь за комп, врубаю СГLite, забиваю старт и финиш- свой ДОМ, а потом выставляю точки и перемещаю их, выбирая оптимальный маршрут, чтобы в субботу с утра отправиться в путь))

В прошлый раз получилось вот что:

 

1d1682ef5ba3dfcebf48b5d3ab107e8a.jpg

 

Правда в процессе работы накидали еще 5 адресов)) но смысл понятен. Пробки и пересчет маршрута не очень важны в этом деле.

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

Не согласен. Далеко не всегда "порядок не важен".

Тут давно кото-то приводил красивейший пример с Васей, который едет к Маше, а по дороге ему надо заехать в банкомат за деньгами и в магазин за цветами.

И заезжать в магазин без денег ему так же бесполезно, как заезжать к Маше без цветов.

Так это тоже в иго решено - изначально он строит оптимальный маршрут, а при перестановке точек вручную уже оптимизирует исходя из заданного руками порядка, который отменяется повторным нажатием оптимизации.

Разговор про оптимизацию идет минимум 3 года, а это очень нужная и востребованная функция.

Отправлено с моего Tapatalkа через GT-P1000

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

да пусть хоть как-то сделают хоть что-то )))) для начала ))))  лишь бы без глюков работало.... 

  • Upvote 1
Ссылка на сообщение
Поделиться на другие сайты

Да для начала пусть и с глюками :))

А там ужо посмотрим.

ПС - мне легко рассуждать, мне эта возможность не нужна. :)

Могла бы пригодиться один раз  - когда надо быдо из Новгорода заехать в Витославлицы, Юрьев монастырь и Перынский скит и вернуться в Новгород.

Но я тогда и так - по карте - сориентировался (в приведенном порядке - намотал бы 3 круга по односторонним дорогам).

Ссылка на сообщение
Поделиться на другие сайты
Гость
Эта тема закрыта для публикации ответов.

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