|
This article is cited in 4 scientific papers (total in 4 papers)
MATHEMATICS
Dynamic programming and questions of solvability of route bottleneck problem with resource constraints
A. G. Chentsovab, A. A. Chentsovb a Ural Federal University, ul. Mira, 19, Yekaterinburg, 620002, Russia
b N. N. Krasovskii Institute of Mathematics and Mechanics, Ural
Branch of the Russian Academy of Sciences, ul. S. Kovalevskoi, 16, Yekaterinburg, 620219, Russia
Abstract:
The article deals with the problem of admissible routing for a system of cycles each of which contains exterior permutation and works connected with megalopolises (non-empty finite sets) visiting. In the initial setting, a resource constraint is given; this constraint should be fulfilled for every cycle under permutation. The solvability conditions in this problem are connected with the extremum of the auxiliary bottleneck routing problem without above-mentioned constraint, in which the apparatus of widely understood dynamic programming (DP) is used. A particular case of the setting is the known bottleneck courier problem which can be used (in particular) for routing a vehicle (airplane or helicopter) aiming to realize the given shipping system with a limited fuel reserve on each flight. An algorithm implemented on a personal computer is constructed.
Keywords:
dynamic programming, route, precedence conditions.
Received: 07.09.2022 Accepted: 10.10.2022
Citation:
A. G. Chentsov, A. A. Chentsov, “Dynamic programming and questions of solvability of route bottleneck problem with resource constraints”, Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 32:4 (2022), 569–592
Linking options:
https://www.mathnet.ru/eng/vuu827 https://www.mathnet.ru/eng/vuu/v32/i4/p569
|
Statistics & downloads: |
Abstract page: | 170 | Full-text PDF : | 64 | References: | 23 |
|