Optimal routing in a problem with constraints and cost functions depending on the task list

Abstract

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. © Published under licence by IOP Publishing Ltd.