RUS  ENG
Full version
JOURNALS // Trudy Instituta Matematiki i Mekhaniki UrO RAN // Archive

Trudy Inst. Mat. i Mekh. UrO RAN, 2017 Volume 23, Number 1, Pages 275–292 (Mi timm1402)

This article is cited in 5 papers

A discrete-continuous routing problem with precedence conditions

A. G. Chentsovab, A. A. Chentsova

a Institute of Mathematics and Mechanics, Ural Branch of the Russian Academy of Sciences, Ekaterinburg
b Ural Federal University named after the First President of Russia B. N. Yeltsin, Ekaterinburg

Abstract: We consider the problem of visiting closed sets in a compact metric space complicated by constraints in the form of precedence conditions and a possible dependence of the cost function on a list of tasks. We study a variant of the approximate realization of the extremum by applying models that involve problems of sequential visits to megalopolises (nonempty finite sets). This variant is naturally embedded into a more general construction that implements sequential visits to nonempty closed sets (NCSs) from a finite system in a metrizable compactum. The space of NCSs is equipped with the Hausdorff metric, which is used to estimate (under the corresponding condition that the sections of the cost functions are continuous) the proximity of the extrema in the problem of sequential visits for any two systems of NCSs (it is assumed that the numbers or NCSs in the systems are the same). The constraints in the form of precedence conditions are preserved.

Keywords: route, path, precedence conditions.

UDC: 519.6

MSC: 49L20, 90C39

Received: 21.06.2016

DOI: 10.21538/0134-4889-2017-23-1-275-292


 English version:
Proceedings of the Steklov Institute of Mathematics (Supplement Issues), 2018, 300, suppl. 1, S56–S71

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025