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

[lipskiy]

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

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

3. между какими-то точками требуется избежать посещение

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

отвезти)

Оооо... Вот с этим-то я как раз согласен, что это все

нужно, и когда с годик назад я предлагал на этом форуме маршруты с

промежуточными точками и функцию оптимального порядка объезда - то все

это там описывал.

Вводить все это вовсе не трудно. Для этого нужно развить закладки,

дополня их полями типа "режим работы", "группа по приоритету", "группа

по типу" и прочее подобное. Один раз настроил точку - и потом забивай в

маршруты и не парься. Ну, для точек, которые не обладают такими

постоянными характеристиками, придется вводить перед поездкой. Так это

кому надо - тот попариться.

Согласен,

безусловно так и хотелось бы. Предложите алгоритм? Мне кажется,

вариант, который известно как реализовать однозначно, лучше того,

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

Поддерживаю. Хотя задача тоже не тривиальная, и

результат неочевиден.

[YoGun]

<...>Так что дело за малым - придумать алгоритм. Я' date=' например, пока не в силах описать эту желаемую последовательность четким алгоритмом.
[/quote']

 

А если по кнопке Оптимизировать (кнопку-то надо делать, а не пересчитывать автоматом, а то лишимся ручного ввода) считать все маршруты и выбирать лучший на данный момент. Доехал куда-нибудь или чуствуешь что ситуация кардинально изменилась, нажал ещё раз Оптимизировать... (более подробно писал в 00:26 в P.S., только откидываю идею считать на ходу автоматом - считать только по требованию, а иначе вести на уже выбранную точку).

 

[lipskiy]

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

То есть выбирать самому пользователю?

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

А если нет - как выбирать лучший автоматически? По какому критерию? По минимальному времени, по минимальному расстоянию? В этом случае не факт, что получим именно то, что хотим.

[YoGun]

А если нет - как выбирать лучший автоматически? По какому критерию? По минимальному времени' date=' по минимальному расстоянию? В этом случае не факт, что получим именно то, что хотим.
[/quote']

 

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

 

Итого мы получим:

1) Не нагружаем систему постоянным анализированием всех доступных комбинаций маршрута (только по требованию).

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

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

 

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

 

[alexeyT4]

А меня бы для начала устроила бы оптимизация просто по расстоянию.

Например, когда на выходные едешь на шашлык и собираешь кучу народа по "дороге".

Чтобы не ломать голову кого забрать первого, кого третьего, а кого последнего.

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

[YoGun]

А меня бы для начала устроила бы оптимизация просто по расстоянию. <...>

 

Я тоже сначала так подумал. Но кратчайший не есть быстрейший.

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

 

[Lucky]

Ну от этого лекарство есть - оптимизировать по времени, но без учёта пробок - это и будет почти эквивалентно (на самом деле чуть лучше) оптимизации по расстоянию с использованием преимущественно "хороших" дорог.

[Calamitous]

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

[/quote']

+1000 Полностью поддерживаю! И хотелось бы чтоб разработчики не затягивали до следующей версии, а уже предложили что-то в 3.2 для WinCE.

[Lucky]

А как же быть с такой ситуацией?

...

 

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

      |     /

    C+Ф

 

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

...[/quote']

[lipskiy]

Чтобы учесть по максимуму все возможные варианты, видимо действительно нужно делать так, как предложил YoGun.

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

Наверное, этот вариант учтет максимум желаемого при наличии четкого алгоритма.

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