Маршрутизация перемещений при динамических ограничениях: задача «на узкие места»

A. G. Chenstov, A. A. Chenstov

Результат исследований: Вклад в журналСтатья

5 Цитирования (Scopus)

Аннотация

"Рассматривается усложненный вариант задачи маршрутизации «на узкие места», а именно: исследуется задача последовательного обхода мегаполисов с условиями предшествования. Предполагается, что функции стоимости, а также «текущие» ограничения на выбор перемещений зависят от списка заданий, не выполненных на данный момент времени. Предложен вариант широко понимаемого динамического программирования, в рамках которого не предусматривается (при наличии условий предшествования) построение всего массива значений функции Беллмана; конструируются специальные слои упомянутой функции, реализующие в своей совокупности частичный (это способствует снижению вычислительной сложности) массив ее значений. На этой основе предлагается алгоритм определения значения задачи (глобального экстремума), при компьютерной реализации которого в памяти всякий раз находится только один слой функции Беллмана; найденное значение может использоваться при тестировании эвристик. Построен и реализован на ПЭВМ также оптимальный алгоритм «полного» решения маршрутной задачи, в рамках которого на этапе построения маршрута и трассы используются уже все слои функции Беллмана."
Переведенное названиеRouting of displacements with dynamic constraints: "bottleneck problem"
Язык оригиналаРусский
Страницы (с-по)121-140
Число страниц20
ЖурналVestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki
Том26
Номер выпуска1
DOI
СостояниеОпубликовано - 2016

Предметные области ASJC Scopus

  • Fluid Flow and Transfer Processes
  • Computer Science(all)
  • Mathematics(all)

ГРНТИ

  • 27.41.00 Вычислительная математика

Уровень публикации

  • Перечень ВАК

Fingerprint Подробные сведения о темах исследования «Маршрутизация перемещений при динамических ограничениях: задача «на узкие места»». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать