To the question of optimization of the starting point in the routing problem with restrictions

A. G. Chentsov ; P. A. Chentsov

Izvestiya Instituta Matematiki i Informatiki Udmurtskogo Gosudarstvennogo Universiteta, Tome 55 (2020), pp. 135-154

Résumé

We consider the extreme routing problem with an additive criterion, the terminal component of which depends on the starting point. This dependence may be associated, in particular, with the requirement to return to the starting point region after completing the final system of tasks that need to be ordered. The work assumes that the tasks to be performed are related with visiting non-empty finite sets called megacities. In turn, the mentioned visits are associated with the performance of works, the costs of which are involved in the formation of the criterion. Finally, the costs of external movements (between megacities) supplement the formation of an additive criterion to be minimized. It is required to find a global extremum and a solution that includes a starting point, the order of visits to megacities and a specific trajectory of the process. The solution uses widely understood dynamic programming (DP). It is significant that procedures based on DP use starting point. Therefore, enumeration of mentioned points is required. The article proposes an approach to solving the problem of reducing this enumeration through the use of auxiliary DP that are universal with respect to the choice of a starting point. The optimal algorithm was built and implemented on a PC using the aforementioned approach.

Détail

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