Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму
Задача комівояжера є однією з найстаріших та найбільш досліджених задач математичного програмування та дослідження операцій. Навіть у своїй найпростішій постановці вона має безліч застосувань у різноманітних сферах, а потреба враховувати складні додаткові обмеження при побудові маршрутів чи визначен...
Gespeichert in:
| Datum: | 2024 |
|---|---|
| Hauptverfasser: | , , , , |
| Format: | Artikel |
| Sprache: | Ukrainian |
| Veröffentlicht: |
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine
2024
|
| Schlagworte: | |
| Online Zugang: | https://jais.net.ua/index.php/files/article/view/238 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems of Control and Informatics |
Institution
Problems of Control and Informatics| id |
oai:ojs2.jais.net.ua:article-238 |
|---|---|
| record_format |
ojs |
| institution |
Problems of Control and Informatics |
| baseUrl_str |
|
| datestamp_date |
2025-03-11T15:09:03Z |
| collection |
OJS |
| language |
Ukrainian |
| topic |
задача комівояжера гамільтонів цикл змішане цілочислове лінійне програмування AMPL Gurobi CPLEX NEOS server пішохідний туризм |
| spellingShingle |
задача комівояжера гамільтонів цикл змішане цілочислове лінійне програмування AMPL Gurobi CPLEX NEOS server пішохідний туризм Stetsyuk, Petro Korablov, Mykola Stoian, Oleksandr Hubernator, Oleh Mykhailenko, Oleksandra Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму |
| topic_facet |
задача комівояжера гамільтонів цикл змішане цілочислове лінійне програмування AMPL Gurobi CPLEX NEOS server пішохідний туризм Travelling Salesman Problem Hamiltonian cycle Mixed Integer Linear Programming AMPL Gurobi CPLEX NEOS server walking tourism |
| format |
Article |
| author |
Stetsyuk, Petro Korablov, Mykola Stoian, Oleksandr Hubernator, Oleh Mykhailenko, Oleksandra |
| author_facet |
Stetsyuk, Petro Korablov, Mykola Stoian, Oleksandr Hubernator, Oleh Mykhailenko, Oleksandra |
| author_sort |
Stetsyuk, Petro |
| title |
Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму |
| title_short |
Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму |
| title_full |
Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму |
| title_fullStr |
Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму |
| title_full_unstemmed |
Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму |
| title_sort |
комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму |
| title_alt |
A combined model for finding the shortest cycle to visit a given number of vertices from the graph clusters: an example of application for walking tourism |
| description |
Задача комівояжера є однією з найстаріших та найбільш досліджених задач математичного програмування та дослідження операцій. Навіть у своїй найпростішій постановці вона має безліч застосувань у різноманітних сферах, а потреба враховувати складні додаткові обмеження при побудові маршрутів чи визначені послідовності дій спонукає дослідників до створення нових узагальнених моделей. У роботі сформульовано нове узагальнення задачі комівояжера — задача пошуку найкоротшого циклу для відвідування заданої кількості вершин кластерів графа. Для розв’язання даної задачі розглянуто дві математичні моделі змішаного цілочислового лінійного програмування: на основі узагальнених обмежень Міллера, Такера і Земліна (перша); та Гевіша і Грейвса (друга). На тестових прикладах продемонстровано переваги та недоліки обох моделей та запропоновано комбіновану модель, що поєднує їхні ідеї при використанні узагальнених обмежень Міллера, Такера і Земліна разом з узагальненими обмеженнями Гевіша та Грейвса для забезпечення зв’язності отриманого циклу та відсутності підциклів у ньому. Така комбінована модель також дозволяє доповнювати задачу спеціальними додатковими обмеженнями (деякі з них описано в цій роботі), що дає змогу ще більше розширити постановку задачі, яка розв’язується. Наведено обчислювальні експерименти, які підтверджують можливість використання комбінованої моделі для розв’язання задач такого типу з додатковими обмеженнями різного виду та без них. Представлено приклад застосування запропонованої комбінованої моделі для побудови персоналізованих пішохідних туристичних маршрутів центром Києва, описано архітектуру розробленого прототипу веб-застосунку для розв’язання даної задачі. Розглянуто перспективи застосування запропонованої моделі в різних сферах та описано переваги, які можуть отримати кінцеві користувачі від використання застосунків, розроблених на її основі. |
| publisher |
V.M. Glushkov Institute of Cybernetics of NAS of Ukraine |
| publishDate |
2024 |
| url |
https://jais.net.ua/index.php/files/article/view/238 |
| work_keys_str_mv |
AT stetsyukpetro kombínovanamodelʹznahodžennânajkorotšogocikluprohodžennâzadanoíkílʹkostíveršinklasterívgrafaprikladzastosuvannâdlâpíšohídnogoturizmu AT korablovmykola kombínovanamodelʹznahodžennânajkorotšogocikluprohodžennâzadanoíkílʹkostíveršinklasterívgrafaprikladzastosuvannâdlâpíšohídnogoturizmu AT stoianoleksandr kombínovanamodelʹznahodžennânajkorotšogocikluprohodžennâzadanoíkílʹkostíveršinklasterívgrafaprikladzastosuvannâdlâpíšohídnogoturizmu AT hubernatoroleh kombínovanamodelʹznahodžennânajkorotšogocikluprohodžennâzadanoíkílʹkostíveršinklasterívgrafaprikladzastosuvannâdlâpíšohídnogoturizmu AT mykhailenkooleksandra kombínovanamodelʹznahodžennânajkorotšogocikluprohodžennâzadanoíkílʹkostíveršinklasterívgrafaprikladzastosuvannâdlâpíšohídnogoturizmu AT stetsyukpetro acombinedmodelforfindingtheshortestcycletovisitagivennumberofverticesfromthegraphclustersanexampleofapplicationforwalkingtourism AT korablovmykola acombinedmodelforfindingtheshortestcycletovisitagivennumberofverticesfromthegraphclustersanexampleofapplicationforwalkingtourism AT stoianoleksandr acombinedmodelforfindingtheshortestcycletovisitagivennumberofverticesfromthegraphclustersanexampleofapplicationforwalkingtourism AT hubernatoroleh acombinedmodelforfindingtheshortestcycletovisitagivennumberofverticesfromthegraphclustersanexampleofapplicationforwalkingtourism AT mykhailenkooleksandra acombinedmodelforfindingtheshortestcycletovisitagivennumberofverticesfromthegraphclustersanexampleofapplicationforwalkingtourism |
| first_indexed |
2025-10-30T02:48:50Z |
| last_indexed |
2025-10-30T02:48:50Z |
| _version_ |
1847373364950204416 |
| spelling |
oai:ojs2.jais.net.ua:article-2382025-03-11T15:09:03Z Комбінована модель знаходження найкоротшого циклу проходження заданої кількості вершин кластерів графа: приклад застосування для пішохідного туризму A combined model for finding the shortest cycle to visit a given number of vertices from the graph clusters: an example of application for walking tourism Stetsyuk, Petro Korablov, Mykola Stoian, Oleksandr Hubernator, Oleh Mykhailenko, Oleksandra задача комівояжера гамільтонів цикл змішане цілочислове лінійне програмування AMPL Gurobi CPLEX NEOS server пішохідний туризм Travelling Salesman Problem Hamiltonian cycle Mixed Integer Linear Programming AMPL Gurobi CPLEX NEOS server walking tourism Задача комівояжера є однією з найстаріших та найбільш досліджених задач математичного програмування та дослідження операцій. Навіть у своїй найпростішій постановці вона має безліч застосувань у різноманітних сферах, а потреба враховувати складні додаткові обмеження при побудові маршрутів чи визначені послідовності дій спонукає дослідників до створення нових узагальнених моделей. У роботі сформульовано нове узагальнення задачі комівояжера — задача пошуку найкоротшого циклу для відвідування заданої кількості вершин кластерів графа. Для розв’язання даної задачі розглянуто дві математичні моделі змішаного цілочислового лінійного програмування: на основі узагальнених обмежень Міллера, Такера і Земліна (перша); та Гевіша і Грейвса (друга). На тестових прикладах продемонстровано переваги та недоліки обох моделей та запропоновано комбіновану модель, що поєднує їхні ідеї при використанні узагальнених обмежень Міллера, Такера і Земліна разом з узагальненими обмеженнями Гевіша та Грейвса для забезпечення зв’язності отриманого циклу та відсутності підциклів у ньому. Така комбінована модель також дозволяє доповнювати задачу спеціальними додатковими обмеженнями (деякі з них описано в цій роботі), що дає змогу ще більше розширити постановку задачі, яка розв’язується. Наведено обчислювальні експерименти, які підтверджують можливість використання комбінованої моделі для розв’язання задач такого типу з додатковими обмеженнями різного виду та без них. Представлено приклад застосування запропонованої комбінованої моделі для побудови персоналізованих пішохідних туристичних маршрутів центром Києва, описано архітектуру розробленого прототипу веб-застосунку для розв’язання даної задачі. Розглянуто перспективи застосування запропонованої моделі в різних сферах та описано переваги, які можуть отримати кінцеві користувачі від використання застосунків, розроблених на її основі. The travelling salesman problem is one of the oldest and most researched problems in mathematical programming and operations research. Even in its simplest formulation, it has found many applications in various fields, and the need to take into account complex additional restrictions when constructing routes or defining sequences of actions prompts researchers to create new generalized models. In this work, a new generalization of the traveling salesman problem is formulated — the problem of finding the shortest cycle to visit a given number of vertices from the graph clusters. Formulations of two mathematical models of mixed integer linear programming for solving this problem are given. The first one is based on the generalized Miller, Tucker, and Zemlin constraints for the standard traveling salesman problem, the second one is based on the generalized Gavish and Graves constraints for the standard traveling salesman problem. Test examples demonstrate the advantages and disadvantages of both models, and a combined model that combines their ideas is proposed, using the generalized constraints of Miller, Tucker and Zemlin together with the generalized constraints of Gavish and Graves to ensure the connectivity of the resulting cycle and the absence of subcycles in it. This combined model also allows supplementing the problem with special additional constraints (some of which are described in this paper), which makes it possible to further expand the formulation of the problem being solved. Computational experiments are presented that confirm the possibility of using a combined model to solve problems of this type with and without additional constraints of various kinds. An example of the application of the combined model proposed in the work for the construction of personalized walking tourist routes in the center of Kyiv is given, and the architecture of the developed web application prototype for solving this problem is described. An overview of promising applications of the proposed model in various fields is made and the benefits that end users can receive from the use of applications developed on its basis are described. V.M. Glushkov Institute of Cybernetics of NAS of Ukraine 2024-08-30 Article Article application/pdf https://jais.net.ua/index.php/files/article/view/238 10.34229/1028-0979-2024-4-1 Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; Том 69 № 4 (2024): Міжнародний науково-технічний журнал "Проблеми керування та інформатики"; 5=27 International Scientific Technical Journal "Problems of Control and Informatics; Том 69 № 4 (2024): International Scientific Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 5=27 International Scientific Technical Journal "Problems of Control and Informatics"; Vol. 69 No. 4 (2024): International Scientific Technical Journal "PROBLEMS OF CONTROL AND INFORMATICS"; 5=27 2786-6505 2786-6491 uk https://jais.net.ua/index.php/files/article/view/238/323 Copyright (c) 2024 Petro Stetsyuk, Mykola Korablov, Oleksandr Stoian, Oleh Hubernator, Oleksandra Mykhailenko https://creativecommons.org/licenses/by-nc-nd/4.0 |