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

[Koshmar]

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

[sashaan]

нет, такой функции нет...  многие её просят, - но увы и ах.... 

[spacer]

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

 

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

[faceless]

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

[sergges]

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

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

[svlad2012]

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

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

 

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

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

 

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

 

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

[faceless]

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

 

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

[IШIN]

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

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

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

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

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

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

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

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

раз в 3 мин.

[Евгений Ш]

А как часто обновляются пробки?

раз в три минуты.

[svlad2012]

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

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

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

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

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

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

раз в 3 мин.

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

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

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

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

[sashaan]

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

 

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

[ashu]

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

[Koshmar]

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

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

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

Во сказанул!

[/DiOs]

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

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

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

[svlad2012]

 

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

 

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

За 80 дней...

Изменено 9 сентября, 2013 пользователем svlad2012

[eklmn]

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

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

[/DiOs]

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

[Koshmar]

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

[spacer]

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

 

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

 

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

 

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

 

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

[IШIN]

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

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

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

[Koshmar]

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

[sergges]

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

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

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

 

 

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

[max_rl]

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

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

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

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

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

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

[sashaan]

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

[IШIN]

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

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

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

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

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