Оптимизирующие вставки в задачах маршрутизации и их реализация на основе динамического программирования

 pdf (320K)

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

Ключевые слова: вставка, динамическое программирование, маршрут
Цитата: Вестник Удмуртского университета. Математика. Механика. Компьютерные науки, 2016, т. 26, вып. 4, с. 565-578
DOI: 10.20537/vm160410

The Bellmann insertions in route problems with constraints and complicated cost functions. II

The route problem with precedence conditions and cost functions depending on the jobs list is considered; these singularities correspond to engineering applications. In particular, the above-mentioned singularities exist in statements of some problems arising in nuclear energetics and in machines with numerical control. Problems involved in sequentially circuiting megalopolises and in carrying out some (interior) work during these circuits are investigated. A procedure for local improvement of heuristic solutions for problems of perceptible dimension is proposed; this procedure exploits insertions on the dynamic programming base. Dynamic programming is realized in the form of a variant that does not provide for construction of a “full” array of values of the Bellman function. The search for localization of an insertion involves restricting to the variant of the Bellman procedure that realizes the extremum of the (local) criterion without constructing a corresponding solution in the form of a route-track pair. A more complete and more cost-intensive (in the sense of memory resources) procedure including determination of the above-mentioned (local optimal) solution is planned after the choice of the insertion localization.

Keywords: insertion, dynamic programming, route
Citation in English: Bulletin of Udmurt University. Mathematics, Mechanics, Computer Science, 2016, vol. 26, issue 4, pp. 565-578

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

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

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

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

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

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