Izv. IMI UdGU, 2020, Volume 55, Pages 135–154
To the question of optimization of the starting point in the routing problem with restrictions
A. G. Chentsov, P. A. Chentsov
Institute of Mathematics and Mechanics, Ural Branch, Russian Academy of Sciences, ul. S. Kovalevskoi, 16, Yekaterinburg, 620219, Russia
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.
work assumes that the tasks to be performed are related with visiting non-empty finite sets called
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).
significant that procedures based on DP use starting point. Therefore, enumeration of mentioned points is
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.
algorithm was built and implemented on a PC using the aforementioned approach.
dynamic programming, route, precedence conditions.
PDF file (613 kB)
A. G. Chentsov, P. A. Chentsov, “To the question of optimization of the starting point in the routing problem with restrictions”, Izv. IMI UdGU, 55 (2020), 135–154
Citation in format AMSBIB
\by A.~G.~Chentsov, P.~A.~Chentsov
\paper To the question of optimization of the starting point in the routing problem with restrictions
\jour Izv. IMI UdGU
Citing articles on Google Scholar:
Related articles on Google Scholar:
|Number of views:|