Jump to content
GPS навигатор СитиГИД

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


Recommended Posts

  • Replies 50
  • Created
  • Last Reply

Top Posters In This Topic

Top Posters In This Topic

Popular Posts

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

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

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

Posted Images

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

 

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

Link to post
Share on other sites

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


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

Link to post
Share on other sites

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

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

 

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

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

 

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

 

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

Link to post
Share on other sites

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

 

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

Link to post
Share on other sites

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

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

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

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

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

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

раз в 3 мин.

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

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

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

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

Link to post
Share on other sites


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

 

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

Link to post
Share on other sites


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

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

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

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

Link to post
Share on other sites

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


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

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

  • Upvote 2
Link to post
Share on other sites

 

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

 

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

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

Edited by svlad2012
Link to post
Share on other sites


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

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

Link to post
Share on other sites

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

  • Upvote 1
Link to post
Share on other sites

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

Link to post
Share on other sites

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

 

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

 

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

 

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

 

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

Link to post
Share on other sites

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

  • Upvote 2
Link to post
Share on other sites

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

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

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

 

1d1682ef5ba3dfcebf48b5d3ab107e8a.jpg

 

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

Link to post
Share on other sites

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

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

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

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

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

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

Link to post
Share on other sites

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

  • Upvote 1
Link to post
Share on other sites

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

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

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

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

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

Link to post
Share on other sites
Guest
This topic is now closed to further replies.

×
×
  • Create New...