Текущий выпуск Выпуск 3, 2018 Том 28

Динамическое программирование в обобщенной задаче «на узкие места» и оптимизация точки старта

 pdf (1257K)

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

Ключевые слова: маршрутная оптимизация, динамическое программирование, оптимизация точки старта
Цитата: Вестник Удмуртского университета. Математика. Механика. Компьютерные науки, 2018, т. 28, вып. 3, с. 348-363
DOI: 10.20537/vm180306

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

We consider one non-additive routing problem, which is a generalization of the well-known “bottleneck problem”. The parameter is assumed to be a positive number, the degree of which determines the weight of the corresponding stage of the displacement system. By varying the parameter, it is possible to make the initial or, on the contrary, the final stages of displacement dominant. The variant of aggregation of values with the above-mentioned weights corresponds to the ideological formulation of the “bottleneck problem”, but opens the possibility of investigating new versions of routing problems with constraints. It is assumed, however, that the statement of the problem is complicated by the dependence of values on the list of tasks and includes restrictions in the form of precedence conditions. In addition, in the interest of optimization, an arbitrary choice of the initial state from a given a priori set is allowed. For the construction, the apparatus of widely understood dynamic programming is used. The possibility of realizing a global extremum with any degree of accuracy under conditions when the set of possible initial states is not finite is investigated.

Keywords: route optimization, dynamic programming, start point optimization
Citation in English: Bulletin of Udmurt University. Mathematics, Mechanics, Computer Science, 2018, vol. 28, issue 3, pp. 348-363

Журнал индексируется в Scopus

Журнал входит в базы данных zbMATH, MathSciNet

Журнал включен в базу данных Russian Science Citation Index (RSCI) на платформе Web of Science

Журнал включен в перечень ВАК.

Электронная версия журнала на Общероссийском математическом портале Math-Net.Ru.

Журнал включен в Crossref