RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Ural Math. J.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Ural Math. J., 2018, том 4, выпуск 2, страницы 43–55 (Mi umj62)  

Optimizing the starting point in a precedence constrained routing problem with complicated travel cost functions

Alexander G. Chentsov, Alexey M. Grigoriev, Alexey A. Chentsov

Krasovskii Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, 16 S. Kovalevskaya str., Ekaterinburg, Russia, 620990

Аннотация: We study the optimization of the initial state, route (a permutation of indices), and track in an extremal problem connected with visiting a finite system of megalopolises subject to precedence constraints where the travel cost functions may depend on the set of (pending) tasks. This problem statement is exemplified by the task to dismantle a system of radiating elements in case of emergency, such as the Chernobyl or Fukushima nuclear disasters. We propose a solution based on a parallel algorithm, which was implemented on the Uran supercomputer. It consists of a two-stage procedure: stage one determines the value (extremum) function over the set of all possible initial states and finds its minimum and also the point where it is achieved. This point is viewed as a base of the optimal process, which is constructed at stage two. Thus, optimization of the starting point for the route through megalopolises, connected with conducting certain internal tasks there, is an important element of the solution. To this end, we employ the apparatus of the broadly understood dynamic programming with elements of parallel structure during the construction of Bellman function layers.

Ключевые слова: Dynamic programming, Route, Sequencing, Precedence constraints, Parallel computation.

Финансовая поддержка Номер гранта
Российский научный фонд 14-11-00109
This work was supported by Russian Science Foundation (project no. 14-11-00109).


DOI: https://doi.org/10.15826/umj.2018.2.006

Полный текст: PDF файл (360 kB)
Полный текст: https:/.../118
Список литературы: PDF файл   HTML файл

Реферативные базы данных:

Тип публикации: Статья
Язык публикации: английский

Образец цитирования: Alexander G. Chentsov, Alexey M. Grigoriev, Alexey A. Chentsov, “Optimizing the starting point in a precedence constrained routing problem with complicated travel cost functions”, Ural Math. J., 4:2 (2018), 43–55

Цитирование в формате AMSBIB
\RBibitem{CheGriChe18}
\by Alexander~G.~Chentsov, Alexey~M.~Grigoriev, Alexey~A.~Chentsov
\paper Optimizing the starting point in a precedence constrained routing problem with complicated travel cost functions
\jour Ural Math. J.
\yr 2018
\vol 4
\issue 2
\pages 43--55
\mathnet{http://mi.mathnet.ru/umj62}
\crossref{https://doi.org/10.15826/umj.2018.2.006}
\mathscinet{http://www.ams.org/mathscinet-getitem?mr=MR3901584}
\elib{http://elibrary.ru/item.asp?id=36702172}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/umj62
  • http://mi.mathnet.ru/rus/umj/v4/i2/p43

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Ural Mathematical Journal
    Просмотров:
    Эта страница:87
    Полный текст:63
    Литература:18
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020