Optimal routing in problems of sequential traversal of megapolises in the presence of constraints

A. A. Petunin ; A. G. Chentsov ; P. A. Chentsov

Čelâbinskij fiziko-matematičeskij žurnal, Tome 7 (2022) no. 2, pp. 209-233

Résumé

The problem of optimal routing of movements is considered with additional constraints such as precedence conditions and cost functions depending on the job list. Dependencies of this kind refer to the so-called dynamic restrictions, in which the value of the objective function at each step of the movement depends on the trajectory (history) of the path traveled and determines the admissibility of the selected movement. The considered statement is focused, first of all, on engineering applications related to the optimization of the route of the tool of CNC machines; other applications are possible. The objects of visit are non-empty finite sets — megacities. As the main problem in this paper, we consider the problem of optimal tool routing for CNC sheet cutting machines, known as the Cutting Path Problem or Tool Path Problem. This problem arises at the stage of development of control programs for the CNC machine, which set the tool path and a number of technological commands. Among the formal restrictions, the precedence conditions are especially distinguished, which are caused by the technological features of sheet cutting on CNC machines and which can be used to reduce the computational complexity of the problem being solved and construct feasible solutions. The main research method is the widely understood dynamic programming (DP), which takes into account the precedence conditions and the dependence of cost functions on the list of tasks. As applied to the problem of routing the tool of sheet cutting machines, the dependence of the objective function on the list of tasks makes it possible to reduce thermal deformations of the material during thermal cutting. The article provides a rigorous mathematical formalization of the problem of constrained movement routing and a description of the exact solution algorithm. In the process of solving, the order of tasks execution, the specific process trajectory and the starting point are optimized. The algorithm is implemented as a PC program; model examples are solved.

Détail

Keywords: megalopolises, route, trajectory, dynamic programming, precedence constraints, dynamic constraints, tool path optimization problem, CNC sheet cutting machine, feasible optimal solution.