Формирование оптимальных планов маршрутов передвижения в условиях неопределенности | Статья в журнале «Молодой ученый»

Отправьте статью сегодня! Журнал выйдет 11 июля, печатный экземпляр отправим 15 июля.

Опубликовать статью в журнале

Авторы: ,

Рубрика: Технические науки

Опубликовано в Молодой учёный №24 (314) июнь 2020 г.

Дата публикации: 14.06.2020

Статья просмотрена: 7 раз

Библиографическое описание:

Девятков, В. В. Формирование оптимальных планов маршрутов передвижения в условиях неопределенности / В. В. Девятков, Д. М. Старченко. — Текст : непосредственный // Молодой ученый. — 2020. — № 24 (314). — С. 96-99. — URL: https://moluch.ru/archive/314/71627/ (дата обращения: 03.07.2020).



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

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

В данной статье представлен подход к вычислению оптимальных планов маршрутов в мультимодальном планировании поездки. Проблема моделируется как поиск в пространстве состояний And/Or(далее AO*) [2]. В настоящей работе будут описаны улучшения поиска, используемые поверх алгоритма AO*. Усовершенствования включают в себя следующие основные моменты: дополнительные эвристические критерии для поиска не просто оптимального, но и надежного маршрута, метод, позволяющий снизить затрачиваемые для вычисления маршрута ресурсы компьютера, т. е. повышение производительности алгоритма, сохраняющий при этом полноту и оптимальность, а также гибридный подход поиска с детерминированным и недетерминированным поиском.

Общая схема алгоритма поиска маршрута

В этом разделе мы представляем гибридный подход к решению, который объединяет детерминированный и недетерминированный поиск. Это введено, чтобы ускорить процесс решения в трудных случаях. Идея проиллюстрирована на рисунке 1.

Рис. 1. Схема гибридного алгоритма

Гибридный поиск и обрезка состояний графа

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

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

Представим транспортную сеть, как на рисунке 2.

Рис. 2. Транспортная сеть № 2 с автобусом и пешеходом

В данном примере будут рассмотрены только состояния D и F, так как в них мы гарантированно попадаем на автобус (P(U < B) = 1), состояние E не рассматривается вообще. Таким образом, транспортная сеть может быть преобразована к следующему виду (Рисунок 3).

Рис. 3. преобразованная транспортная сеть № 2

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

В нашем случае пользователь будет двигаться по пути из таблицы 3.

Таблица 3

Траектория

Шаги

Итоговое время прибытия

A → B → C → F → G

11: 00 — сесть на автобус 38 до пункта «B»

11:20 — ходьба до пункта «C»

11:25 — ходьба до пункта «F»

11:37 — ходьба до пункта назначения «G»

~ 12:00

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

Формула (эвристическая формула оценки состояний), по которой происходит расчет на втором этапе, в общем виде выглядит следующим образом: ,

где g(n) — стоимость пройденного пути,

h(n) — оценка расстояния от узла n до целевого узла.

Опишем следующие правила, оценивания функции :

1) В случае, если текущее состояние является целевым, значит полагаем, что ;

2) В случае, если текущее состояние не позволяет ни каким образом достижение целевого состояния, значит полагаем, что

3) В случае, если текущее состояние не относится к предыдущим пунктам, полагаем, что , где =

Учитывая состояние , A( — это множество исходящих действий из состояния в недетерминированной области. Для данного действия - количество ветвей этого действия. Для детерминированного действия = 1. Для недетерминированного действия . — соответствующая вероятность, — коэффициент надежности (расхождения во времени маршрутов исходящих из этой точки), а — стоимость пути (время затрачиваемое на передвижение). Поскольку величина всегда больше 1 (т. к. номер следующего маршрута, по которому пойдет пользователь в случае не успеха сесть на автобус, а значит такой маршрут будет иметь заведомо больше времени для достижения цели), следовательно, будет положительным. Здесь в качестве N отмечается N-ый номер маршрута, а - время, затрачиваемое при достижении конечной цели следуя по этому маршруту.

Литература:

  1. Adi Botea, Akihiro Kishimoto, Elizabeth Daly (2016). Combining Deterministic and Nondetermenistic Search for Optimal Journey Planning Under Ucertainty.
  2. Nikolova, E.,Brand, M., & Karger, D.R.(2006). Optimal route planning under uncertainty. In Long, D., Smith, S.F., Borrajo, D., & McCluskey, L.(Eds.), Proceedings of the 16nd International Conference on Automated Planning and Scheduling (ICAPS), 131–141.
  3. Holte, R., Perez, M., Zimmer, R., & MacDonald, A.J. (1995). Hierarchical A*: Searching abstraction hierarchies efficiently. Tech. rep., Department of Computer Science, University of Ottawa.
  4. Hoffmann, J., & Brafman, R. (2005). Contingent planning via heuristic forward search with implicit belief states. In Proceedings of the 15th International Conference on Automated Planning and Scheduling (ICAPS-05), 71–80.
  5. Nikolova, E., Kelner, J.A., Brand, M., & Mitzenmacher, M. (2006). Stochastic shortest paths via quasi-convex maximization, 552–563.
Основные термины (генерируются автоматически): текущее состояние, транспортная сеть, маршрут, недетерминированный поиск, обрезок состояний графа, повышение производительности алгоритма, условие недетерминированности, детерминированный маршрут, время, пункт назначения.


Похожие статьи

Определение рациональных маршрутов доставки транспортных...

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

Интересно отметить, что алгоритм и методы решения транспортной задачи могут быть

 Увеличение производительности автомобильного транспорта за счет минимизации...

Динамическая адаптация эвристического алгоритма для задачи...

Маршрут транспортного средства делится на два этапа. Маршрут Pickup начинается на

Рассмотрим текущую задачу p(s-(t,p)), которая отличается от начальной тестовой тем, что

В среднем, маршрут для каждого транспортного средства, сгенерированный при помощи...

Методы и алгоритмы эффективного решения задачи...

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

Маршрутизация данных. Механизмы, критерии выбора маршрута...

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

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

Выбор оптимального маршрута грузоперевозок автомобильным...

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

Оптимизация загрузки транспортных средств и построение...

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

Решение транспортных задач с применением программирования...

2. Составить алгоритм для реализации методов решения транспортных задач в MathCAD.

- транспортная задача в условиях перепроизводства, в этом случае для сведения ее к

Затем необходимо осуществить поиск оптимального решения задачи с использованием блока Given...

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

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

Анализ существующей маршрутной сети Центрального района...

Количество маршрутов, проходящих через Центральный район по типам маршрутов и по перевозчикам представлено на рис.1 и на рис.2.

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

Математические методы маршрутизации доставки светлых...

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

Похожие статьи

Определение рациональных маршрутов доставки транспортных...

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

Интересно отметить, что алгоритм и методы решения транспортной задачи могут быть

 Увеличение производительности автомобильного транспорта за счет минимизации...

Динамическая адаптация эвристического алгоритма для задачи...

Маршрут транспортного средства делится на два этапа. Маршрут Pickup начинается на

Рассмотрим текущую задачу p(s-(t,p)), которая отличается от начальной тестовой тем, что

В среднем, маршрут для каждого транспортного средства, сгенерированный при помощи...

Методы и алгоритмы эффективного решения задачи...

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

Маршрутизация данных. Механизмы, критерии выбора маршрута...

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

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

Выбор оптимального маршрута грузоперевозок автомобильным...

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

Оптимизация загрузки транспортных средств и построение...

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

Решение транспортных задач с применением программирования...

2. Составить алгоритм для реализации методов решения транспортных задач в MathCAD.

- транспортная задача в условиях перепроизводства, в этом случае для сведения ее к

Затем необходимо осуществить поиск оптимального решения задачи с использованием блока Given...

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

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

Анализ существующей маршрутной сети Центрального района...

Количество маршрутов, проходящих через Центральный район по типам маршрутов и по перевозчикам представлено на рис.1 и на рис.2.

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

Математические методы маршрутизации доставки светлых...

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

Задать вопрос