Dynamic programming in the generalized bottleneck problem and the start point optimization

A. G. Chentsov, A. A. Chentsov, A. N. Sesekin

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Рассматривается одна «неаддитивная» задача маршрутизации перемещений, являющаяся обобщением известной задачи «на узкие места». Предполагается заданным параметр в виде положительного числа, степень которого определяет вес соответствующего этапа системы перемещений. Варьированием параметра можно сделать доминирующими начальные или, напротив, финальные этапы перемещения. Вариант агрегирования стоимостей с упомянутыми весами соответствует идейно постановке задачи «на узкие места», но открывает возможности исследования новых постановок задач маршрутизации с ограничениями. Предполагается, однако, что постановка осложнена зависимостью стоимостей от списка заданий и включает ограничения в виде условий предшествования. Кроме того, в интересах оптимизации допускается произвольный выбор начального состояния из заданного априори множества. Для построения решения используется аппарат широко понимаемого динамического программирования. Исследуется возможность реализации глобального экстремума с любой степенью точности в условиях, когда множество возможных начальных состояний не является конечным.
Translated title of the contributionDynamic programming in the generalized bottleneck problem and the start point optimization
Original languageRussian
Pages (from-to)348-363
Number of pages16
JournalVestnik Udmurtskogo Universiteta: Matematika, Mekhanika, Komp'yuternye Nauki
Volume28
Issue number3
DOIs
Publication statusPublished - 1 Jan 2018

Fingerprint

Bottleneck Problem
Routing Problem
Dynamic programming
Dynamic Programming
Agglomeration
Optimization
Extremum
Aggregation
Restriction
Formulation
Arbitrary
Form
Generalization

Keywords

  • Dynamic programming
  • Route optimization
  • Start point optimization

ASJC Scopus subject areas

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

WoS ResearchAreas Categories

  • Mathematics

GRNTI

  • 27.00.00 MATHEMATICS

Level of Research Output

  • VAK List

Cite this

@article{9136e4bec7b44525b0bb7fb0b9afdeea,
title = "ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ В ОБОБЩЕННОЙ ЗАДАЧЕ {"}НА УЗКИЕ МЕСТА{"} И ОПТИМИЗАЦИЯ ТОЧКИ СТАРТА",
abstract = "Рассматривается одна «неаддитивная» задача маршрутизации перемещений, являющаяся обобщением известной задачи «на узкие места». Предполагается заданным параметр в виде положительного числа, степень которого определяет вес соответствующего этапа системы перемещений. Варьированием параметра можно сделать доминирующими начальные или, напротив, финальные этапы перемещения. Вариант агрегирования стоимостей с упомянутыми весами соответствует идейно постановке задачи «на узкие места», но открывает возможности исследования новых постановок задач маршрутизации с ограничениями. Предполагается, однако, что постановка осложнена зависимостью стоимостей от списка заданий и включает ограничения в виде условий предшествования. Кроме того, в интересах оптимизации допускается произвольный выбор начального состояния из заданного априори множества. Для построения решения используется аппарат широко понимаемого динамического программирования. Исследуется возможность реализации глобального экстремума с любой степенью точности в условиях, когда множество возможных начальных состояний не является конечным.",
keywords = "Dynamic programming, Route optimization, Start point optimization",
author = "Chentsov, {A. G.} and Chentsov, {A. A.} and Sesekin, {A. N.}",
year = "2018",
month = "1",
day = "1",
doi = "10.20537/vm180306",
language = "Русский",
volume = "28",
pages = "348--363",
journal = "Вестник Удмуртского университета. Математика. Механика. Компьютерные науки",
issn = "1994-9197",
publisher = "Удмуртский государственный университет",
number = "3",

}

TY - JOUR

T1 - ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ В ОБОБЩЕННОЙ ЗАДАЧЕ "НА УЗКИЕ МЕСТА" И ОПТИМИЗАЦИЯ ТОЧКИ СТАРТА

AU - Chentsov, A. G.

AU - Chentsov, A. A.

AU - Sesekin, A. N.

PY - 2018/1/1

Y1 - 2018/1/1

N2 - Рассматривается одна «неаддитивная» задача маршрутизации перемещений, являющаяся обобщением известной задачи «на узкие места». Предполагается заданным параметр в виде положительного числа, степень которого определяет вес соответствующего этапа системы перемещений. Варьированием параметра можно сделать доминирующими начальные или, напротив, финальные этапы перемещения. Вариант агрегирования стоимостей с упомянутыми весами соответствует идейно постановке задачи «на узкие места», но открывает возможности исследования новых постановок задач маршрутизации с ограничениями. Предполагается, однако, что постановка осложнена зависимостью стоимостей от списка заданий и включает ограничения в виде условий предшествования. Кроме того, в интересах оптимизации допускается произвольный выбор начального состояния из заданного априори множества. Для построения решения используется аппарат широко понимаемого динамического программирования. Исследуется возможность реализации глобального экстремума с любой степенью точности в условиях, когда множество возможных начальных состояний не является конечным.

AB - Рассматривается одна «неаддитивная» задача маршрутизации перемещений, являющаяся обобщением известной задачи «на узкие места». Предполагается заданным параметр в виде положительного числа, степень которого определяет вес соответствующего этапа системы перемещений. Варьированием параметра можно сделать доминирующими начальные или, напротив, финальные этапы перемещения. Вариант агрегирования стоимостей с упомянутыми весами соответствует идейно постановке задачи «на узкие места», но открывает возможности исследования новых постановок задач маршрутизации с ограничениями. Предполагается, однако, что постановка осложнена зависимостью стоимостей от списка заданий и включает ограничения в виде условий предшествования. Кроме того, в интересах оптимизации допускается произвольный выбор начального состояния из заданного априори множества. Для построения решения используется аппарат широко понимаемого динамического программирования. Исследуется возможность реализации глобального экстремума с любой степенью точности в условиях, когда множество возможных начальных состояний не является конечным.

KW - Dynamic programming

KW - Route optimization

KW - Start point optimization

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

UR - https://elibrary.ru/item.asp?id=35645986

UR - https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=tsmetrics&SrcApp=tsm_test&DestApp=WOS_CPL&DestLinkType=FullRecord&KeyUT=000467765600006

U2 - 10.20537/vm180306

DO - 10.20537/vm180306

M3 - Статья

VL - 28

SP - 348

EP - 363

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

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

SN - 1994-9197

IS - 3

ER -