Open AccessOptimal routing in a problem with constraints and cost functions depending on the task list
Author(s) -
A. A. Chentsov,
А. Г. Ченцов,
A. N. Sesekin
Publication year - 2021
Publication title -
journal of physics. conference series
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.21
H-Index - 85
eISSN - 1742-6596
pISSN - 1742-6588
DOI - 10.1088/1742-6596/1864/1/012050
Subject(s) - permutation (music) , routing (electronic design automation) , computer science , mathematical optimization , sequence (biology) , task (project management) , dependency (uml) , focus (optics) , selection (genetic algorithm) , trajectory , dynamic programming , process (computing) , mathematics , algorithm , artificial intelligence , computer network , physics , management , astronomy , biology , acoustics , optics , economics , genetics , operating system
A routing problem with precedence conditions and complex cost functions is considered. In this problem, we must choose a starting point, a route (permutation of indices) and a specific trajectory for our process. This trajectory must be consistent with the route. In addition, this route or index permutation defines the sequence of tasks. In addition, the selection of the above route must satisfy the precedence conditions defined by the system of ordered index pairs. These ordered pairs are called address pairs. We consider the additive criterion routing problem. This criterion is natural for the problem of dismantling the system of radiation sources. In this article, we will focus on this engineering problem. In this problem very naturally cost functions arise with a dependency on the list of tasks. Namely, each time the performer touches those and only those sources that were not dismantled at that time. The solution uses widely understood dynamic programming. We build the optimal algorithm for the PC; information about the computational experiment is given.