Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму
У статті сформульовано нове узагальнення задачі комівояжера — задачі пошуку найкоротшого циклу для відвідування заданої кількості вершин кластерів графа. Розглянуто дві математичні моделі змішаного цілочислового лінійного програмування (МЦЛП): одна на основі узагальнених обмежень Міллера, Такера і З...
Gespeichert in:
| Veröffentlicht in: | Проблеми керування та інформатики |
|---|---|
| Datum: | 2024 |
| Hauptverfasser: | , , , , |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2024
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/211211 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму / П.І. Стецюк, М.М. Корабльов, О.О. Стоян, О.А. Губернатор, О.В. Михайленко // Проблеми керування та інформатики. — 2024. — № 4. — С. 5–27. — Бібліогр.: 14 назв. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862665765404016640 |
|---|---|
| author | Стецюк, П.І. Корабльов, М.М. Стоян, О.О. Губернатор, О.А. Михайленко, О.В. |
| author_facet | Стецюк, П.І. Корабльов, М.М. Стоян, О.О. Губернатор, О.А. Михайленко, О.В. |
| citation_txt | Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму / П.І. Стецюк, М.М. Корабльов, О.О. Стоян, О.А. Губернатор, О.В. Михайленко // Проблеми керування та інформатики. — 2024. — № 4. — С. 5–27. — Бібліогр.: 14 назв. — укр. |
| collection | DSpace DC |
| container_title | Проблеми керування та інформатики |
| description | У статті сформульовано нове узагальнення задачі комівояжера — задачі пошуку найкоротшого циклу для відвідування заданої кількості вершин кластерів графа. Розглянуто дві математичні моделі змішаного цілочислового лінійного програмування (МЦЛП): одна на основі узагальнених обмежень Міллера, Такера і Земліна, інша — Гевіша і Грейвса. Запропоновано комбіновану модель, яка об’єднує ідеї обох підходів. Проведено обчислювальні експерименти, які підтверджують можливість використання цієї моделі для розв’язання задач з додатковими обмеженнями.
The article formulates a new generalization of the traveling salesman problem — the task of finding the shortest cycle visiting a specified number of graph cluster vertices. Two mixed integer linear programming (MILP) models are considered: one based on the generalized Miller-Tucker-Zemlin constraints, and the other on the Gavish-Graves constraints. A combined model integrating the ideas of both approaches is proposed. Computational experiments confirm the feasibility of using this model to solve problems with additional constraints.
|
| first_indexed | 2026-03-16T09:09:51Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-211211 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0572-2691 |
| language | Ukrainian |
| last_indexed | 2026-03-16T09:09:51Z |
| publishDate | 2024 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Стецюк, П.І. Корабльов, М.М. Стоян, О.О. Губернатор, О.А. Михайленко, О.В. 2025-12-25T20:31:12Z 2024 Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму / П.І. Стецюк, М.М. Корабльов, О.О. Стоян, О.А. Губернатор, О.В. Михайленко // Проблеми керування та інформатики. — 2024. — № 4. — С. 5–27. — Бібліогр.: 14 назв. — укр. 0572-2691 https://nasplib.isofts.kiev.ua/handle/123456789/211211 519.85 10.34229/1028-0979-2024-4-1 У статті сформульовано нове узагальнення задачі комівояжера — задачі пошуку найкоротшого циклу для відвідування заданої кількості вершин кластерів графа. Розглянуто дві математичні моделі змішаного цілочислового лінійного програмування (МЦЛП): одна на основі узагальнених обмежень Міллера, Такера і Земліна, інша — Гевіша і Грейвса. Запропоновано комбіновану модель, яка об’єднує ідеї обох підходів. Проведено обчислювальні експерименти, які підтверджують можливість використання цієї моделі для розв’язання задач з додатковими обмеженнями. The article formulates a new generalization of the traveling salesman problem — the task of finding the shortest cycle visiting a specified number of graph cluster vertices. Two mixed integer linear programming (MILP) models are considered: one based on the generalized Miller-Tucker-Zemlin constraints, and the other on the Gavish-Graves constraints. A combined model integrating the ideas of both approaches is proposed. Computational experiments confirm the feasibility of using this model to solve problems with additional constraints. Робота підтримана грантом Volkswagen Foundation grant No 97775. uk Інститут кібернетики ім. В.М. Глушкова НАН України Проблеми керування та інформатики Методи оптимізації та оптимальне керування Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму A combined model for finding the shortest cycle to visit a given number of vertices from the graph clusters: an example ofapplication for walking tourism Article published earlier |
| spellingShingle | Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму Стецюк, П.І. Корабльов, М.М. Стоян, О.О. Губернатор, О.А. Михайленко, О.В. Методи оптимізації та оптимальне керування |
| title | Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму |
| title_alt | A combined model for finding the shortest cycle to visit a given number of vertices from the graph clusters: an example ofapplication for walking tourism |
| title_full | Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму |
| title_fullStr | Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму |
| title_full_unstemmed | Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму |
| title_short | Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму |
| title_sort | комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму |
| topic | Методи оптимізації та оптимальне керування |
| topic_facet | Методи оптимізації та оптимальне керування |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/211211 |
| work_keys_str_mv | AT stecûkpí kombínovanamodelʹznahodžennânaikorotšogocikluprohodžennâzadanoíkílʹkostíveršinklasterívgrafaprikladzastosuvannâdlâpíšohídnogoturizmu AT korablʹovmm kombínovanamodelʹznahodžennânaikorotšogocikluprohodžennâzadanoíkílʹkostíveršinklasterívgrafaprikladzastosuvannâdlâpíšohídnogoturizmu AT stoânoo kombínovanamodelʹznahodžennânaikorotšogocikluprohodžennâzadanoíkílʹkostíveršinklasterívgrafaprikladzastosuvannâdlâpíšohídnogoturizmu AT gubernatoroa kombínovanamodelʹznahodžennânaikorotšogocikluprohodžennâzadanoíkílʹkostíveršinklasterívgrafaprikladzastosuvannâdlâpíšohídnogoturizmu AT mihailenkoov kombínovanamodelʹznahodžennânaikorotšogocikluprohodžennâzadanoíkílʹkostíveršinklasterívgrafaprikladzastosuvannâdlâpíšohídnogoturizmu AT stecûkpí acombinedmodelforfindingtheshortestcycletovisitagivennumberofverticesfromthegraphclustersanexampleofapplicationforwalkingtourism AT korablʹovmm acombinedmodelforfindingtheshortestcycletovisitagivennumberofverticesfromthegraphclustersanexampleofapplicationforwalkingtourism AT stoânoo acombinedmodelforfindingtheshortestcycletovisitagivennumberofverticesfromthegraphclustersanexampleofapplicationforwalkingtourism AT gubernatoroa acombinedmodelforfindingtheshortestcycletovisitagivennumberofverticesfromthegraphclustersanexampleofapplicationforwalkingtourism AT mihailenkoov acombinedmodelforfindingtheshortestcycletovisitagivennumberofverticesfromthegraphclustersanexampleofapplicationforwalkingtourism |