On one routing task with the optimization of the start--finish point

A. G. Chentsov ; P. A. Chentsov

Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, Tome 52 (2018), pp. 103-115

Résumé

The optimizing procedure for solving the problem of sequential visiting of megacities under precedence conditions and cost functions depending on the tasks list is considered. The formulation of the problem closed in the sense of coincidence of the starting point (process base) and terminal state is investigated (this is an analog of the closed travelling salesman problem). This condition is natural for applied problems concerning series of procedures with elements of routing. In particular, in problems involved in sheet cutting on CNC, in working with a series of parts corresponding to one cutting plan, the cutting tool must be returned to the starting point for repeated operations. In this setting, optimization of the starting point is interesting not only for theoretical, but also practical reasons. In a mathematical setting, it is not necessary to require the above-mentioned return to the starting point: this condition can be reflected by introducing the corresponding terminal function whose argument is the last point of visiting in the contours of the parts. Such an approach allows one to cover some more general cases where the cost of the terminal state, which includes the starting point in the form of a parameter, is given. As a result, the starting point and the finishing point are related by a functional dependence in the form of the value defining the quality of the final state of the process. This representation is used in the article.

Détail

Mots-clés : route
Keywords: track, precedence conditions.