Dynamic Programming in the Precedence Constrained TSP with the Costs Depending on a List of Tasks

Abstract

A scheme of independent calculations of the Bellman function for the Precedence Constrained TSP, in which the cost depends on the list of pending jobs was constructed. The authors use a version of the dynamic programming method to solve a routing problem with the precedence constraints; this method makes use of an extension for the initial problem, which is based on a transformation of the precedence constraints into a special "deletion" rule (for tasks from the "current" list). At the stage of construction of the Bellman function, the whole array of its values is not used. In order to parallelize the computation procedure of the above mentioned function, they propose to distribute the task lists, which are realized at the penultimate stage of the procedure between different cores. In the construction of individual threads of the computational scheme, the authors use discrete dynamical systems, which build the sets, which may look similar to the reachability sets in the optimal control theory; the latter sets are employed in construction of the layers of space of position. The layers of the Bellman function, which are constructed in threads, are defined as restrictions of the latter onto the respective layers of the space of position. The statement of the problem and the solution methods are focused on a real-life problem of dismantling of a decommissioned nuclear power unit.