OPTIMIZING THE STARTING POINT IN A PRECEDENCE CONSTRAINED ROUTING PROBLEM WITH COMPLICATED TRAVEL COST FUNCTIONS
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 stateme...
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ural Branch of the Russian Academy of Sciences and Ural Federal University named after the first President of Russia B.N.Yeltsin, Krasovskii Institute of Mathematics and Mechanics
2018-12-01
|
| Series: | Ural Mathematical Journal |
| Subjects: | |
| Online Access: | https://umjuran.ru/index.php/umj/article/view/118 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1849416601989808128 |
|---|---|
| author | Alexander G. Chentsov Alexey M. Grigoryev Alexey A. Chentsov |
| author_facet | Alexander G. Chentsov Alexey M. Grigoryev Alexey A. Chentsov |
| author_sort | Alexander G. Chentsov |
| collection | DOAJ |
| description | 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 xemplified 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. |
| format | Article |
| id | doaj-art-5c74a89de4e54d1488f0286f48339fb5 |
| institution | Kabale University |
| issn | 2414-3952 |
| language | English |
| publishDate | 2018-12-01 |
| publisher | Ural Branch of the Russian Academy of Sciences and Ural Federal University named after the first President of Russia B.N.Yeltsin, Krasovskii Institute of Mathematics and Mechanics |
| record_format | Article |
| series | Ural Mathematical Journal |
| spelling | doaj-art-5c74a89de4e54d1488f0286f48339fb52025-08-20T03:33:08ZengUral Branch of the Russian Academy of Sciences and Ural Federal University named after the first President of Russia B.N.Yeltsin, Krasovskii Institute of Mathematics and MechanicsUral Mathematical Journal2414-39522018-12-014210.15826/umj.2018.2.00658OPTIMIZING THE STARTING POINT IN A PRECEDENCE CONSTRAINED ROUTING PROBLEM WITH COMPLICATED TRAVEL COST FUNCTIONSAlexander G. Chentsov0Alexey M. Grigoryev1Alexey A. Chentsov2Krasovskii Institute of Mathematics and Mechanics,Ural Branch of the Russian Academy of Sciences,16 S. Kovalevskaya Str., Ekaterinburg, 620990Krasovskii Institute of Mathematics and Mechanics,Ural Branch of the Russian Academy of Sciences,16 S. Kovalevskaya Str., Ekaterinburg, 620990Krasovskii Institute of Mathematics and Mechanics,Ural Branch of the Russian Academy of Sciences,16 S. Kovalevskaya Str., Ekaterinburg, 620990We 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 xemplified 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.https://umjuran.ru/index.php/umj/article/view/118Dynamic programming, Route, Sequencing, Precedence constraints, Parallel computation |
| spellingShingle | Alexander G. Chentsov Alexey M. Grigoryev Alexey A. Chentsov OPTIMIZING THE STARTING POINT IN A PRECEDENCE CONSTRAINED ROUTING PROBLEM WITH COMPLICATED TRAVEL COST FUNCTIONS Ural Mathematical Journal Dynamic programming, Route, Sequencing, Precedence constraints, Parallel computation |
| title | OPTIMIZING THE STARTING POINT IN A PRECEDENCE CONSTRAINED ROUTING PROBLEM WITH COMPLICATED TRAVEL COST FUNCTIONS |
| title_full | OPTIMIZING THE STARTING POINT IN A PRECEDENCE CONSTRAINED ROUTING PROBLEM WITH COMPLICATED TRAVEL COST FUNCTIONS |
| title_fullStr | OPTIMIZING THE STARTING POINT IN A PRECEDENCE CONSTRAINED ROUTING PROBLEM WITH COMPLICATED TRAVEL COST FUNCTIONS |
| title_full_unstemmed | OPTIMIZING THE STARTING POINT IN A PRECEDENCE CONSTRAINED ROUTING PROBLEM WITH COMPLICATED TRAVEL COST FUNCTIONS |
| title_short | OPTIMIZING THE STARTING POINT IN A PRECEDENCE CONSTRAINED ROUTING PROBLEM WITH COMPLICATED TRAVEL COST FUNCTIONS |
| title_sort | optimizing the starting point in a precedence constrained routing problem with complicated travel cost functions |
| topic | Dynamic programming, Route, Sequencing, Precedence constraints, Parallel computation |
| url | https://umjuran.ru/index.php/umj/article/view/118 |
| work_keys_str_mv | AT alexandergchentsov optimizingthestartingpointinaprecedenceconstrainedroutingproblemwithcomplicatedtravelcostfunctions AT alexeymgrigoryev optimizingthestartingpointinaprecedenceconstrainedroutingproblemwithcomplicatedtravelcostfunctions AT alexeyachentsov optimizingthestartingpointinaprecedenceconstrainedroutingproblemwithcomplicatedtravelcostfunctions |