Two-Stage Dynamic Programming in the Routing Problem with Decomposition
Электронный научный архив УРФУ
Информация об архиве | Просмотр оригинала| Поле | Значение | |
| Заглавие |
Two-Stage Dynamic Programming in the Routing Problem with Decomposition
|
|
| Автор |
Chentsov, A. G.
Chentsov, P. A. |
|
| Тематика |
DYNAMIC PROGRAMMING
MEGALOPOLIS PRECEDENCE CONDITIONS ROUTE COMPUTER CONTROL SYSTEMS COST FUNCTIONS CUTTING TOOLS PERSONAL COMPUTERS STRUCTURAL OPTIMIZATION CONDITION CONTROL PROBLEMS MEGALOPOLIS OPTIMAL MOVEMENTS PRECEDENCE CONDITION ROUTE ROUTING PROBLEMS SUB-PROBLEMS TOOL CONTROLS WORKPIECE DYNAMIC PROGRAMMING |
|
| Описание |
Abstract: This paper considers an optimal movement routing problem with constraints. One such constraint is due to decomposing the original problem into a preliminary subproblem and a final subproblem; the tasks related to the preliminary problem must be executed before the tasks of the final subproblem begin. In particular, this condition may arise in the tool control problem for thermal cutting machines with computer numerical control (CNC): if there are long parts among workpieces, the cutting process near a narrow material boundary should start with these workpieces since such parts are subject to thermal deformations, which may potentially cause rejects. The problem statement under consideration involves two zones for part processing. The aggregate routing process in the original problem includes a starting point, a route (a permutation of indices), and a particular track consistent with the route and the starting point. Each of the subproblems has specific precedence conditions, and the travel cost functions forming the additive criterion may depend on the list of pending tasks. A special two-stage procedure is introduced to apply dynamic programming as a solution method. The structure of the optimal solution is established and an algorithm based on this structure is developed. The algorithm is implemented on a personal computer and a computational experiment is carried out. © 2023, Pleiades Publishing, Ltd.
|
|
| Дата |
2024-04-05T16:32:41Z
2024-04-05T16:32:41Z 2023 |
|
| Тип |
Article
Journal article (info:eu-repo/semantics/article) |info:eu-repo/semantics/publishedVersion |
|
| Идентификатор |
Chentsov, AG & Chentsov, PA 2023, 'Two-Stage Dynamic Programming in the Routing Problem with Decomposition', Automation and Remote Control, Том. 84, № 5, стр. 543-563. https://doi.org/10.1134/S0005117923050053
Chentsov, A. G., & Chentsov, P. A. (2023). Two-Stage Dynamic Programming in the Routing Problem with Decomposition. Automation and Remote Control, 84(5), 543-563. https://doi.org/10.1134/S0005117923050053 0005-1179 Final All Open Access, Gold https://www.scopus.com/inward/record.uri?eid=2-s2.0-85171617413&doi=10.1134%2fS0005117923050053&partnerID=40&md5=782161cff326834bab195e46f7ed9a56 https://doi.org/10.1134/s0005117923050053 http://elar.urfu.ru/handle/10995/130789 10.1134/S0005117923050053 85171617413 001067925500007 |
|
| Язык |
en
|
|
| Права |
Open access (info:eu-repo/semantics/openAccess)
cc-by https://creativecommons.org/licenses/by/4.0/ |
|
| Формат |
application/pdf
|
|
| Издатель |
Pleiades Publishing
|
|
| Источник |
Automation and Remote Control
Automation and Remote Control |
|