Routing of displacements with dynamic constraints: "bottleneck problem"

A. G. Chenstov, A. A. Chenstov

Research output: Contribution to journalArticleResearchpeer-review

2 Citations (Scopus)

Abstract

"Рассматривается усложненный вариант задачи маршрутизации «на узкие места», а именно: исследуется задача последовательного обхода мегаполисов с условиями предшествования. Предполагается, что функции стоимости, а также «текущие» ограничения на выбор перемещений зависят от списка заданий, не выполненных на данный момент времени. Предложен вариант широко понимаемого динамического программирования, в рамках которого не предусматривается (при наличии условий предшествования) построение всего массива значений функции Беллмана; конструируются специальные слои упомянутой функции, реализующие в своей совокупности частичный (это способствует снижению вычислительной сложности) массив ее значений. На этой основе предлагается алгоритм определения значения задачи (глобального экстремума), при компьютерной реализации которого в памяти всякий раз находится только один слой функции Беллмана; найденное значение может использоваться при тестировании эвристик. Построен и реализован на ПЭВМ также оптимальный алгоритм «полного» решения маршрутной задачи, в рамках которого на этапе построения маршрута и трассы используются уже все слои функции Беллмана."
Translated title of the contributionRouting of displacements with dynamic constraints: "bottleneck problem"
Original languageRussian
Pages (from-to)121-140
Number of pages20
JournalVestnik Udmurtskogo Universiteta. Matematika. Mekhanika. Komp'yuternye Nauki
Volume26
Issue number1
DOIs
Publication statusPublished - 2016

Fingerprint

Bottleneck Problem
Routing
Optimal Algorithm
Value Function
Dynamic Programming
Cost Function
Trace
Dynamic programming
Cost functions
Heuristics
Moment
Partial
Imply
Decrease
Testing
Data storage equipment

Keywords

  • Dynamic programming
  • Preceding conditions
  • Route
  • Trace

ASJC Scopus subject areas

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

GRNTI

  • 27.41.00

Level of Research Output

  • VAK List

Cite this

@article{ffc513cb58d840be9d03f6ef9177d52e,
title = "Маршрутизация перемещений при динамических ограничениях: задача «на узкие места»",
abstract = "{"}Рассматривается усложненный вариант задачи маршрутизации «на узкие места», а именно: исследуется задача последовательного обхода мегаполисов с условиями предшествования. Предполагается, что функции стоимости, а также «текущие» ограничения на выбор перемещений зависят от списка заданий, не выполненных на данный момент времени. Предложен вариант широко понимаемого динамического программирования, в рамках которого не предусматривается (при наличии условий предшествования) построение всего массива значений функции Беллмана; конструируются специальные слои упомянутой функции, реализующие в своей совокупности частичный (это способствует снижению вычислительной сложности) массив ее значений. На этой основе предлагается алгоритм определения значения задачи (глобального экстремума), при компьютерной реализации которого в памяти всякий раз находится только один слой функции Беллмана; найденное значение может использоваться при тестировании эвристик. Построен и реализован на ПЭВМ также оптимальный алгоритм «полного» решения маршрутной задачи, в рамках которого на этапе построения маршрута и трассы используются уже все слои функции Беллмана.{"}",
keywords = "Dynamic programming, Preceding conditions, Route, Trace",
author = "Chenstov, {A. G.} and Chenstov, {A. A.}",
year = "2016",
doi = "10.20537/vm160110",
language = "Русский",
volume = "26",
pages = "121--140",
journal = "Вестник Удмуртского университета. Математика. Механика. Компьютерные науки",
issn = "1994-9197",
publisher = "Удмуртский государственный университет",
number = "1",

}

TY - JOUR

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

AU - Chenstov, A. G.

AU - Chenstov, A. A.

PY - 2016

Y1 - 2016

N2 - "Рассматривается усложненный вариант задачи маршрутизации «на узкие места», а именно: исследуется задача последовательного обхода мегаполисов с условиями предшествования. Предполагается, что функции стоимости, а также «текущие» ограничения на выбор перемещений зависят от списка заданий, не выполненных на данный момент времени. Предложен вариант широко понимаемого динамического программирования, в рамках которого не предусматривается (при наличии условий предшествования) построение всего массива значений функции Беллмана; конструируются специальные слои упомянутой функции, реализующие в своей совокупности частичный (это способствует снижению вычислительной сложности) массив ее значений. На этой основе предлагается алгоритм определения значения задачи (глобального экстремума), при компьютерной реализации которого в памяти всякий раз находится только один слой функции Беллмана; найденное значение может использоваться при тестировании эвристик. Построен и реализован на ПЭВМ также оптимальный алгоритм «полного» решения маршрутной задачи, в рамках которого на этапе построения маршрута и трассы используются уже все слои функции Беллмана."

AB - "Рассматривается усложненный вариант задачи маршрутизации «на узкие места», а именно: исследуется задача последовательного обхода мегаполисов с условиями предшествования. Предполагается, что функции стоимости, а также «текущие» ограничения на выбор перемещений зависят от списка заданий, не выполненных на данный момент времени. Предложен вариант широко понимаемого динамического программирования, в рамках которого не предусматривается (при наличии условий предшествования) построение всего массива значений функции Беллмана; конструируются специальные слои упомянутой функции, реализующие в своей совокупности частичный (это способствует снижению вычислительной сложности) массив ее значений. На этой основе предлагается алгоритм определения значения задачи (глобального экстремума), при компьютерной реализации которого в памяти всякий раз находится только один слой функции Беллмана; найденное значение может использоваться при тестировании эвристик. Построен и реализован на ПЭВМ также оптимальный алгоритм «полного» решения маршрутной задачи, в рамках которого на этапе построения маршрута и трассы используются уже все слои функции Беллмана."

KW - Dynamic programming

KW - Preceding conditions

KW - Route

KW - Trace

UR - http://www.scopus.com/inward/record.url?scp=85009808599&partnerID=8YFLogxK

UR - http://elibrary.ru/item.asp?id=25681790

U2 - 10.20537/vm160110

DO - 10.20537/vm160110

M3 - Статья

VL - 26

SP - 121

EP - 140

JO - Вестник Удмуртского университета. Математика. Механика. Компьютерные науки

JF - Вестник Удмуртского университета. Математика. Механика. Компьютерные науки

SN - 1994-9197

IS - 1

ER -