Маршрут с промежуточными точками

[Regul78]

СГ 3.2. Маршрут с промежуточными точками.

Ничего не скажешь - вещь полезная, раньше ее не хватало. Отлично когда едешь из Старт в Финиш и вдруг по пути надо куда то заехать, вводишь промежуточную точку и всё!

Источник трудностей с СГ3.2.: необходимо заехать в несколько точек...

Из этого у меня родились вопросы:

1. Как менять местами точки в уже существующем маршруте, не создавая новый взамен удаленного старого, с правильно самим расставленными точками? А точек может быть не 1 или 2, а 5 и более!!!

2. СГ умеет думать как логичнее объехать все точки по оптимальному маршруту, а не в последовательности их ввода в маршрут? Если да, то как это реализуется на практике?

Буду благодарен за отклики, особенно со стороны тех. поддержки.

[lipskiy]

1. Никак, СГ 3.2 это не умеет.

2. Нет, СГ 3.2 это не умеет.

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

Возможно, в новых версиях появится.

[Kentavrus]

2. СГ умеет думать как логичнее объехать все точки по оптимальному маршруту' date=' а не в последовательности их ввода в маршрут?

[/quote']

Сорри, небольшой оффтоп - это, если я не ошибаюсь, "теорема коммивояжера", и если ее решит СГ, то тут не только нобелевская...

[lipskiy]

Мммм...

А что тут сложного?

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

Разве не так?

Да, построение такого маршрута в целом займет много времени у программы, поэтому функцию оптимального объезда точек надо вынести на отдельную кнопку.

[гидро]

не так.

[lipskiy]

А и если бы так - то тоже бы работало и было бы лучше, чем сейчас.

[YoGun]

СГ 3.2. Маршрут с промежуточными точками.
<...>

1. Как менять местами точки в уже существующем маршруте<...>

 

1. Меню/Маршрут/Редактировать - меняете местами точки (в 3.1 работает).

 

(советую почитать для начала http://forum.probki.net/forum_posts.asp?TID=4744) 

 

[sergeyastakhov]

1. Никак' date=' СГ 3.2 это не умеет.[/quote']

 

Умеет.

[lipskiy]

А... да... Невнимательно прочитал. Переставлять местами да, умеет. А вот двигать по карте уже поставленные точки - нет. Если надо отредактировать местоположение точки - то только через удаление.

[Lucky]

До нобелевской далековато - это обычная задача логистики с целевой функцией - минимизация суммарного времени проезда всех промежуточных точек.

Насколько она "по зубам" КПК и при каком предельном количестве промежуточных точек - это другой вопрос.

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

1. Никто не знает заранее, что будет в очередной пробочной инфе.

2. Текущая обстановка отражена не на 100% в СГ, т.е. большинство рёбер учтываются по умолчанию.

[YoGun]

Ну может быть минимизировать по растоянию объезда точек, а потом к первой вести с учётом пробок. От первой ко второй и т.п. Не очень удачно получится, но хоть как-то.

Я например, когда планирую объезжать свои точки, прикидываю, что (допустим) начиная с третей точки время будет обед, пробки будут там-то и там-то, а после моей шестой все поедут домой, поэтому в центр или поперёк я ещё хоть как-то проеду, а вот в область уже всё встанет... Как это объяснить СГ? Если б были Индексы скорости по статистике (от времени суток), то может можно было бы придумать...

[lipskiy]

Согласен.

Можно сразу не решать всю задачу целиком, а решать ее поэтапно.

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

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

[sergeyastakhov]

На старте просчитать маршруты ко всем точкам' date=' выбрать точку наибыстрейшей досягаемости на основе текущей обстановки, и успокоиться, пока пользователь не достигнет этой первой точки. То есть больше не метаться между точками, а строго вести к одной выбранной.
[/quote']

 

Можно ещё проще - добавить в меню редактирования маршрута кнопку "Сортировка", и при её нажатии сортировать список согласно текущей обстановке. И никаких метаний - всё под контролем пользователя.

[balts]

Интересно, а после того, как всё это реализуют, будем просить, чтобы СГ учитывал расписание обеденных перерывов на точках, вес сгружаемого-загружаемого на точках груза или пассажиров (с целью минимизации нагрузки на авто и снижения расхода бензина) и т.п.?

[lipskiy]

В основном, все что просим - не изыски и оригинальности.

Все это уже есть в других программах навигации.

Так что не надо утрировать.

А то многие любят писать в стиле "может еще и щи варить СГ научить".

[Lucky]

...На старте просчитать маршруты ко всем точкам' date=' выбрать точку наибыстрейшей досягаемости на основе текущей обстановки, и успокоиться, пока пользователь не достигнет этой первой точки...

[/quote']

А если в процессе пути к этой точке все возможные пути подъезда к ней будут блокированы пробками? При этом к каким-то другим точкам путь нормальный. При этом СГ может прогнозировать с т. зр. своей логики, что эти пробки "протухнут" не позднее, чем через 30 мин (на самом деле это не факт, но я подчёркиваю - с т. зр. логики СГ) и есть смысл объехать пока другие (доступные) точки - мне кажется СГ должен хотя-бы это предложить.

А для устойчивости алгоритма можно использовать критерий типа не перепрокладывать, если выигрыш меньше...

[YoGun]

<...>На старте просчитать маршруты ко всем точкам' date=' выбрать точку наибыстрейшей досягаемости на основе текущей обстановки,<...> Выбрать следующую, и ехать только к ней. И так далее.<...>выбор точки всегда производится на основе текущей пробочной обстановки.
[/quote']

 

Мне кажется, что не очень хороший способ...

 

Допустим у нас точка N1 - старт, 2,3,4 - точки, 5 - финиш. Точки стоят по кругу (или пятиугольником). В зависимости от пробок может оказаться при выезде из точки 1 наибыстрейшая будет 4, потом 2, потом 3, а оттуда по любому надо на финиш 5. В результате пробег явно больше, чем если объезжать по кругу. И ещё вопрос быстрее ли...

При этом, пробки меняются и не о всех пробках есть информация...

 

Прочитал и сам не очень понял... Может кто-нибудь уловит мою мысль и напишет по человечески... А я пока ещё подумаю...

 

 

P.S. Если точки вдоль маршрута "вытянуты", то в результате последней точкой будет самая дальняя от финиша. 

 

P.P.S. Ещё можно модифицировать идею господина lipskiy и каждый раз искать не быстрейшую по досигаемости точку, а обсчитывать маршрут целиком в поисках Быстрейшего маршрута с учётом точек ({Старт - 2 - 3 - 4 - Финиш} или {Старт - 3 - 4 - 2 - Финиш} и т.п.) . После того, как маршрут найден, его "зафиксировать" т.е. вести на выбранную точку. А по достижении её, опять искать Быстрейший маршрут, но уже вместо "Старт" будет достигнутая "Точка".  То есть, каждый раз маршрут считать целиком (вычёркивая пройденное), с учётом того, что Финиш будет в любом случае последним.

 

[lipskiy]

Я описал алгоритм ясный и просто с точки зрения его реализации.

Я вообще всегда так делаю - если что-то предлагаю, то сразу с описанием того, как именно это можно сделать. Иначе мечты останутся мечтами. Понятно, что это не наилучший вариант. Но как запрограммировать логику действительно оптимального порядка объезда - я не представляю (к примеру, вариант Lucky

). Поэтому предлагаю реально возможный алгоритм.

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

[YoGun]

Мда... Оказывается задачка не такая простая...

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

Мне кажется, что надо сначала придумать как это должно выглядить, а потом придумать алгоритм, при котором это будет работать...

 

 

P.S. Пока вижу один способ: Построить 6 маршрутов (это если три точки)  (С-1-2-3-Ф, С-1-3-2-Ф, С-2-1-3-Ф, С-2-3-1-Ф, С-3-1-2-Ф, С-3-2-1-Ф). Из них выбрать быстрейший и вести до первой точки. Там построить 2 маршрута, выбрать быстрейший.

Но как тогда быть в ситуации, описанной господином Lucky? Если при движении к первой точки всё время будут строиться 6 маршрутов (это опять же если точек всего три), что б проверить не стал ли выгоден какой-то другой, то боюсь мозгов навигатора больше ни на что не останется... Можно правда сделать отдельную кнопку "Оптимизировать" и если чуствуешь, что ситуация кардинально поменялась, то жмёшь её и минуту-две ждёшь результата.

 

[YoGun]

Ещё чем мне не нравится идея искать по одной точке:

 

1----2------3

      |     /

    C+Ф

 

Примерно получится С-2-1-3-Ф, а хотелось бы С-1-2-3-Ф или С-3-2-1-Ф

 

 

 

Вторая ситуация - две точки рядом, но по разные стороны дороги, а до разворотов ехать и ехать:

 

        2

      /   

     |  ][ |

     |  ][ |

     |  ][ |

     |  ][ |

     |-<--|

     |  ][ |

     |  ][ |

   3|  ][ |1

     |  ][ |

     |-->-|

     |  ][ |

     |  ][ |

          /

       С+Ф

 

Хотелось бы получить С-1-2-3-Ф, а не С-1-3-(мимо1)2-(мимо3)Ф

 

[balts]

В основном' date=' все что просим - не изыски и оригинальности.
Все это уже есть в других программах навигации.
Так что не надо утрировать.
А то многие любят писать в стиле "может еще и щи варить СГ научить".
[/quote']

А никто и не утрирует. Если уж просить построение маршрута с промежуточными точками автоматически, то это ведь не для какой-то игры а-ля "объедь все точки"! Реально придётся учитывать, как минимум, что:

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

2. есть свой "коэф-т весомости" (какая-то более важная, а какую-то можно отложить на другой день)

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

... ну и так далее

По-моему, эти и подобные данные устанешь вводить, проще сообразить самому, куда важнее ехать.

[Lucky]

Одним словом, господа, мы пришли к тому, что для оптимизации необходимо прогнозирование пробочной ситуации, т.е. опять пришли к необходимости учёта зависимости скоростей рёбер от времени и дня недели.

[YoGun]

<...>По-моему, все эти и подобные данные устанешь вводить, проще сообразить самому, куда важнее ехать.

 

Ну это-то сейчас есть (Меню/Маршрут/Редактировать и переставляете руками), а хотелось какой-нибудь автоматики...

 

[гидро]

ну так выше намёк, что автоматика может вместо картошки к теще повезти тещу к картошке

[YoGun]

ну так выше намёк' date=' что автоматика может вместо картошки к теще повезти тещу к картошке [/quote']

 

Так я и говорю, что для таких целей пользуемся ручной сортировкой (не будем же мы в самом деле пытаться объяснять программе, что мы хотим "случайно" не успеть к тёще).

 

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