Problems of movement routing with precedence constraints and cost functions depending on the list of tasks are considered. Variants of an additive cost aggregation and a minimax setting (bottleneck problem) are studied. It is assumed that the entire set of tasks related to visiting megalopolises (nonempty finite sets) is divided into the sum of two clusters; as a result, two particular problems arise: a preliminary problem and a final one. The execution of tasks of the final problem can be started only after the completion of all tasks of the preliminary one. The aim of the study is to optimize compositional solutions in the cases of the additive and minimax settings. A unified approach is proposed, which is connected with separate solving the preliminary and final problems using a broadly understood dynamic programming approach. An optimal algorithm for the compositional solution of problems of significant dimension with practically acceptable performance is constructed. Possible applications may include the problem of dismantling radiation-hazardous objects, tool control during shaped sheet cutting on machines with computer numerical control (CNC), and some transport problems related to logistical problems in small aviation.
Chentsov et al. (Fri,) studied this question.